9.4美团笔试（AK代码）
T1：DP
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL dp[N][2][2];//dp[i][j][k] 表示前i个字符 倒数第二个是j，倒数第一个是k的方案数。0表示a，1表示b
int main() {
int n; cin >> n;
if(n <= 3) {
cout <<n * 2;
return 0;
}
dp[3][0][0] = dp[3][1][1] = 2;
dp[3][0][1] = dp[3][1][0] = 1;
for(int i = 4; i <= n; i++) {
dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0]) % MOD;
dp[i][0][1] = dp[i-1][0][0];
dp[i][1][0] = dp[i-1][1][1];
dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][1][1]) % MOD;
}
LL ans = 0;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++) {
ans += dp[n][i][j];
ans %=MOD;
}
}
cout << ans;
return 0;
}
/*
3
6
*/ T2：跑floyd
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e2+ 50;
const LL MOD = 998244353;
LL dp[N][2][2];
int f[N][N];
vector<int> e[N];
int main() {
int n, m; cin >> n >> m;
memset(f, 63, sizeof f);
int limit = f[0][0];
for(int i = 1; i <= n; i++) {
f[i][i] = 0;
int k; cin >> k;
while(k--) {
int x; cin >> x;
e[x].push_back(i);
}
}
for(int i = 1; i < N; i++){
for(int j = 0; j < e[i].size(); j++) {
for(int k = 0; k < e[i].size(); k++) {
int S = e[i][j];
int T = e[i][k];
f[S][T] = f[T][S] = min(f[S][T], 1);
}
}
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(f[i][j] == limit) {
f[i][j] = -1;
}
cout << f[i][j];
if(j != n) {
cout << ' ';
}
}
cout << "\n";
}
return 0;
}
/*
3 2
1 1
2 1 2
1 2
0 1 2
1 0 1
2 1 0
*/ T3：变成ccccc...aaaaa..就行，倒着计数每个a后面有多少个c
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL dp[N][2][2];
int main() {
int n; cin >> n;
string s; cin >> s;
LL ans = 0;
int cnt_c = 0;
for(int i = n-1; ~i; i--){
cnt_c += s[i] == 'c';
if(s[i] == 'a') {
ans += cnt_c;
}
}
cout << ans;
return 0;
}
/*
4
acca
2
*/ T4：四元环计数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e2 + 50;
const LL MOD = 998244353;
int mp[N][N];
vector<int>e[N], q[N];
int ID[N], du[N],RANK[N], num[N];
int main() {
int n; cin >> n;
for(int i = 1; i <= n; i++) {
ID[i] = i;
for(int j = 1; j <= n; j++) {
int x; cin >> x;
if(x){
e[i].push_back(j);
}
}
}
for(int i = 1; i <= n; i++) {
du[i] = e[i].size();
}
sort(ID + 1, ID + n + 1,[](int a,int b) {
if(du[a] == du[b]) {
return a < b;
}
return du[a] < du[b] ;
});
LL ans = 0;
for(int i = 1; i <= n; i++) {
RANK[ID[i]] = i;
}
for(int i = 1; i <= n; i++) {
for(int x : e[i]) {
if(RANK[x] > RANK[i]) {
q[i].push_back(x);
}
}
}
for(int i = 1; i <= n; i++) {
for(int x : e[i]) {
for(int y : q[x]) {
if(RANK[y] > RANK[i]) {
ans += num[y];
num[y]++;
}
}
}
for(int x : e[i]) {
for(int y : q[x]) {
if(RANK[y] > RANK[i]) {
num[y] = 0;
}
}
}
}
cout << ans;
return 0;
}
/*
6
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 1
1 0 0 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0
3
*/ T5：滑动窗口求区间最大/最小值 + 枚举
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL a[N];
int MAX[N], MIN[N];
deque<int> que, quee;
int main() {
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
while(!que.empty() && i - que.front() + 1 > m) que.pop_front();
while(!que.empty() && a[i] >= a[que.back()] ) que.pop_back();
que.push_back(i);
if(i>=m) {
MAX[i] = a[que.front()];
}
}
for(int i = 1; i <= n; i++) {
while(!quee.empty() && i - quee.front() + 1 > m) quee.pop_front();
while(!quee.empty() && a[i] <= a[quee.back()] ) quee.pop_back();
quee.push_back(i);
if(i>=m) {
MIN[i] = a[quee.front()];
}
}
for(int i = 1; i <= n; i++) {
a[i] += a[i-1];
}
int ans = -1;
LL ave = 0;
for(int i = m; i <= n; i++) {
LL now = (a[i] - a[i-m] - MAX[i] - MIN[i]) ;
if(now > ave) {
ans = i - m + 1;
ave = now;
}
}
cout << ans;
return 0;
}
/*
5 3
3 2 3 1 1
1
10 3
14 24 14 22 44 29 33 45 36 48
8
*/ #美团笔试##美团##笔经#
