T1 一眼看成博弈论…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std ;int T;long long n, a, b;inline void solve () cin >> n >> a >> b; if (a > b) swap(a, b); if (a + b > n && b - a == a) { cout << "wfl\n" ; return ; } n /= __gcd(a, b); if (n & 1 ) cout << "lidian\n" ; else cout << "wfl\n" ; } int main () cin >> T; for (int i = 0 ; i < T; i++) solve(); return 0 ; }
T2 40分 双Hash暴力匹配…
100分 打标记，对于当前枚举串 $now$，从前往后扫。若扫到 $i$，$s_i$ 是 $s_j$ 的子串 $(i < j < now)$，我们就可以跳过不匹配 $i$。因为若 $s_i$ 不是 $s_{now}$ 的子串，则 $s_j$ 一定也不是 $s_{now}$ 的子串；若 $s_i$ 是 $s_{now}$ 的子串，$s_j$ 也有可能不是 $s_{now}$ 的子串。若不存在这样的 $j$，匹配即可，若 $s_i$ 是 $s_{now}$ 的子串，$i$ 之后就可以跳过了 (打个 $vis$ 标记)；否则 $now$ 就可以更新答案，然后 $break$。
复杂度 $O(TNL)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include <bits/stdc++.h> using namespace std ;inline void getNext (char *p, int m, int *next) for (register int i = 1 , k = 0 ; i < m; i++) { while (k && p[i] != p[k]) k = next[k - 1 ]; if (p[i] == p[k]) k++; next[i] = k; } } inline bool kmp (char *t, char *p, int n, int m, int *next) getNext(p, m, next); for (register int i = 0 , k = 0 ; i < n; i++) { while (k && t[i] != p[k]) k = next[k - 1 ]; if (t[i] == p[k]) k++; if (m == k) return true ; } return false ; } int t, n;char s[510 ][2100 ];int len[510 ], next[510 ][2100 ];bool vis[510 ];inline void solve () cin >> n; register int ans = 0 ; memset (vis, 0 , sizeof (vis)); for (int i = 1 ; i <= n; i++) { cin >> s[i]; len[i] = strlen (s[i]); for (int j = i - 1 ; j > 0 ; j--) { if (vis[j]) continue ; if (kmp(s[i], s[j], len[i], len[j], next[i])) { vis[j] = true ; } else { ans = i; break ; } } } if (ans) cout << ans << "\n" ; else cout << "-1\n" ; } int main () ios::sync_with_stdio(0 ); cin .tie(0 ); cin >> t; for (int i = 1 ; i <= t; i++) solve(); return 0 ; }
T3 首先可以很简单地想出 $O(n^6)$ 的 $dp$，然后我们可以简单优化成 $O(n^4)$，然后就能过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> using namespace std ;const long long mod = 1e17 ;long long dp[127 ][127 ][127 ];int n, a, b, c;long long line[201 ], pre[201 ];inline long long dfs (int x, int a1, int b1) if (~dp[x][a1][b1]) return dp[x][a1][b1]; register int c1 = pre[x - 1 ] - a1 - b1; long long ret = 0 ; if (x == n) return 1 ; for (int i = 0 ; i <= line[x] && i <= a - a1; i++) for (int j = 0 ; j <= b - b1 && j + i <= line[x]; j++) if (line[x] - i - j <= c - c1) ret = (ret + dfs(x + 1 , a1 + i, b1 + j)) % mod; dp[x][a1][b1] = ret; return ret; } int main () memset (dp, -1 , sizeof (dp)); ios::sync_with_stdio(0 ); cin .tie(0 ); cin >> n >> a >> b >> c; long long ans = 0 , sum = a + b + c; for (int i = 1 ; i <= n; i++) cin >> line[i], pre[i] += pre[i - 1 ] + line[i], ans += line[i]; if (ans != sum) cout << 0 , exit (0 ); cout << dfs(1 , 0 , 0 ); return 0 ; }
