26年复健

C - Illuminate Buildings 简单DP#include bits/stdc.h using namespace std; int main() { int n; cin n; // dp[i][j] 表示以第 i 栋楼为结尾步长为 j 时的最长长度。 vectorint a(n 1); for(int i 1; i n; i) cin a[i]; vectorvectorint dp(n 1, vectorint(n 1, 1)); int ans 1; for(int i 1; i n; i) { for(int j 1; j i; j) { if(a[i - j] a[i]) { dp[i][j] dp[i - j][j] 1; } else { dp[i][j] 1; } ans max(ans, dp[i][j]); } } cout ans; }D - No-Subsequence Substring 一道很标准的字符串#include bits/stdc.h using namespace std; using ll long long; int main() { string s, t; cin s t; int n s.size(), m t.size(); s s; t t; ll ans 0; vectorvectorint nxt(n 2, vectorint(27, INT_MAX)); // 从i位置开始,字符c最早出现的位置 for(int i n; i 1; i--) { nxt[i] nxt[i 1]; nxt[i][s[i] - a 1] i; } for(int i 1; i n; i) { int ptr i; bool ok 1; for(int j 1; j m; j) { ptr nxt[ptr][t[j] - a 1]; if(ptr INT_MAX) { ok 0; break; } ptr; } if(ok) { ans ptr - 1 - i; } else { ans n - i 1; } } cout ans; }E - You WILL Like Sigma Problem 很神奇的求和题目首先i mod j i - j * floor(i / j) 因此原式拆解为 Σ Σ A[i] * B[j] * i - Σ Σ A[i] * B[j] * j * floor(i / j)分别令前后部分为A、B.A 易计算化简为(sum B[j]) * (sum A[i] * i)B 稍微复杂:n m为1e5 后半部分包含 i j尝试枚举j 所以B[j] * j为定值令为K(j),所以BΣ K(j) * A[i] * floor(i / j) ,即求 每个 j怎么快速算 H(j) Σ A[i] * floor(i / j)固定一个 j 后floor(i / j) 在区间上是常数i ∈ [j, 2j-1] 时floor(i/j)1i ∈ [2j, 3j-1] 时floor(i/j)2i ∈ [3j, 4j-1] 时floor(i/j)3 所以 H(j) 1 * sum(A[j..2j-1]) 2 * sum(A[2j..3j-1]) 3 * sum(A[3j..4j-1]) ... 这部分预先求A_i的前缀和即可求得值得注意的是代码里双重循环是调和级数级别的复杂度不会超时ON logN#include bits/stdc.h using namespace std; using ll long long; const ll MOD 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorll a(n 1), b(m 1); for (int i 1; i n; i) cin a[i]; for (int i 1; i m; i) cin b[i]; vectorll pre(n 1, 0); for (int i 1; i n; i) { a[i] % MOD; pre[i] (pre[i - 1] a[i]) % MOD; } for (int i 1; i m; i) b[i] % MOD; ll sum_b 0; for (int j 1; j m; j) { sum_b (sum_b b[j]) % MOD; } ll ans 0; for (int i 1; i n; i) { ans (ans a[i] * i) % MOD; } ans ans * sum_b % MOD; int lim min(n, m); for (int j 1; j lim; j) { ll cur 0; for (int l j, k 1; l n; l j, k) { int r min(n, l j - 1); ll seg (pre[r] - pre[l - 1] MOD) % MOD; cur (cur 1LL * k * seg) % MOD; } ans (ans - b[j] * j % MOD * cur % MOD MOD) % MOD; } cout ans \n; return 0; }