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 */#美团笔试##美团##笔经#