|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
总结与反思
C - 如果一个数可以确定整个状态, 考虑设未知数然后给所有的数减掉偏移量 E - 要删除一个东西, 我们更常见的做法是伪删除 F - DP 首先考虑阶段, 即以什么样的顺序完成这个任务, 状态要符合转移 G - 发现一个非常长, 或者有循环的东西要想到倍增, 知 1 就知道所有 H - 字符串的公共前后缀/回文 之类的都有相等的关系, 这类结构相似的问题可以由小的给大的问题提供上下界或者答案
E - POI2008 Trains
关键在于如何更新每个种类的值, 可以用动态开点或者平衡树
这里用并查集的写法, 因为时间的先后, 为了强制让后来的字符串没法用以前的答案更新, 可以把后来的点当作根
伪删除很重要的思想
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ll;
- const int N = 1005;
- const int M = 1e5 + 5;
- const int P = 131;
- struct Node {
- int pa, val;
- Node(int a = 0, int b = 0) {
- pa = a;
- val = b;
- }
- };
- // 最多有 N + M 个 hash 值, dsu 给每个 hash 值存点
- vector<Node> dsu[N + M];
- // pos 给哈希值的编号, 对应 dsu 的位置, siz 是对应 vec 的实际大小
- // 值只和当前的大小有关, 可以只改变 siz 实现伪删除
- unordered_map<ll, int> pos;
- int cnt, l[N], siz[N + M];
- int ans[N], n, m, q;
- // hash 用
- ll H[N], p[N];
- char s[N][105];
- // h 是哈希的哈希
- int Findpa(int u, int h) {
- if (dsu[h][u].pa == u)
- return dsu[h][u].val;
- dsu[h][u].val = max(dsu[h][u].val, Findpa(dsu[h][u].pa, h));
- dsu[h][u].pa = dsu[h][dsu[h][u].pa].pa;
- return dsu[h][u].val;
- }
- // u 字符串编号, h 新的哈希值
- // l[u] 相当于 u 在 vec 中的位置
- void Insert(int u) {
- int& id = pos[H[u]];
- if (!id)
- id = ++cnt;
- siz[id]++;
- l[u] = dsu[id].size();
- // 如果有就把原来的树并到 u 上
- if (l[u])
- dsu[id][l[u] - 1].pa = l[u];
- dsu[id].emplace_back(l[u], siz[id]);
- }
- void Del(int u) {
- siz[pos[H[u]]]--;
- ans[u] = max(ans[u], Findpa(l[u], pos[H[u]]));
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n >> m >> q;
- p[0] = 1;
- for (int i = 1; i <= m; i++) {
- p[i] = p[i - 1] * P;
- }
- for (int i = 1; i <= n; i++) {
- cin >> (s[i] + 1);
- for (int j = 1; j <= m; j++) {
- H[i] = H[i] * P + s[i][j];
- }
- Insert(i);
- ans[i] = 1;
- }
- while (q--) {
- int x, xp, y, yp;
- cin >> x >> xp >> y >> yp;
- Del(x);
- if (x != y)
- Del(y);
- H[x] += (s[y][yp] - s[x][xp]) * p[m - xp];
- H[y] += (s[x][xp] - s[y][yp]) * p[m - yp];
- swap(s[x][xp], s[y][yp]);
- Insert(x);
- if (x != y)
- Insert(y);
- }
- for (int i = 1; i <= n; i++) {
- cout << max(ans[i], Findpa(l[i], pos[H[i]])) << '\n';
- }
- return 0;
- }
复制代码
F - P2593 [ZJOI2006] 超级麻将
想 DP 不要盲目看整个问题, 想想以什么样子的顺序完成, 把四周的状态放进状态里可以参考 P2157 [SDOI2009] 学校食堂
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 102;
- const int M = 100;
- bool f[N][N][N][2];
- int n, cnt[N];
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
-
- cin >> n;
- while(n--){
- memset(f, 0, sizeof(f));
- f[0][0][0][0] = 1;
- for(int i = 1; i <= M; i++){
- cin >> cnt[i];
- for(int j = 0; j <= cnt[i - 1]; j++){
- for(int k = 0; k <= cnt[i]; k++){
- // 阶段: 前 i 个已经拿完了, 现在考虑 i
- // 对于现有的状态我们可以选择不同拿法
- // 出对子
- if(k > 1){
- f[i][j][k][1] |= f[i][j][k - 2][0];
- }
- // 出刻子
- if(k > 2){
- f[i][j][k][0] |= f[i][j][k - 3][0];
- f[i][j][k][1] |= f[i][j][k - 3][1];
- }
- if(k > 3){
- f[i][j][k][0] |= f[i][j][k - 4][0];
- f[i][j][k][1] |= f[i][j][k - 4][1];
- }
- // 出 k 个顺子
- if(i == 1 && k == 0){
- f[i][j][k][0] = 1;
- f[i][j][k][1] = 1;
- continue;
- }
-
- if(k <= j && k <= cnt[i - 2]){
- f[i][j][k][0] |= f[i - 1][cnt[i - 2] - k][j - k][0];
- f[i][j][k][1] |= f[i - 1][cnt[i - 2] - k][j - k][1];
- }
- }
- }
- }
- if(f[M][cnt[M - 1]][cnt[M]][1]) cout << "Yes\n";
- else cout << "No\n";
- }
-
- return 0;
- }
复制代码
G - BZOJ2062 素颜2
基环树森林上一个点一定跳到最后是在环上, 如何比较生成的字符串? 字符串很长, 倍增就行
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ll;
- const int N = 1e5 + 5;
- const int P = 131;
- int n;
- ll h[N][18], p[18];
- int t[N][18];
- int ans[N];
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- p[0] = P;
- for (int i = 1; i <= 17; i++) {
- p[i] = p[i - 1] * p[i - 1];
- }
- for (int i = 1; i <= n; i++) {
- char ch;
- cin >> ch;
- h[i][0] = ch;
- }
- for (int i = 1; i <= n; i++) {
- cin >> t[i][0];
- }
- // 研究非常长的东西的时候可以想想倍增口牙
- // 知道 1 也就知道所有
- // 比如从一个点一直往后跳 / 超级长的序列之类的
- for (int j = 1; j < 18; j++) {
- for (int i = 1; i <= n; i++) {
- t[i][j] = t[t[i][j - 1]][j - 1];
- h[i][j] = h[i][j - 1] * p[j - 1] + h[t[i][j - 1]][j - 1];
- }
- }
- for (int i = 1; i <= n; i++) ans[i] = i;
- sort(ans + 1, ans + n + 1, [](int x, int y) {
- // 如果 两个相同, 就返回编号小的
- if (h[x][17] == h[y][17])
- return x < y;
- for (int i = 16; i >= 0; i--) {
- // 如果前缀相等就跳
- if (h[x][i] == h[y][i]) {
- x = t[x][i], y = t[y][i];
- }
- }
- // 跳到最远的地方, 下一个就是不相等位置
- return h[x][0] < h[y][0];
- });
- for (int i = 1; i <= n; i++) {
- cout << ans[i] << '\n';
- }
- return 0;
- }
复制代码
H - P3546 [POI2012] PRE-Prefixuffix
利用前后缀相等性质, 可以找出 i 的上界, 这种一递推关系, 答案规模慢慢扩大一定要想到, 字符串的 next 数组也是同样理念
找出 i 和 i + 1 的关系
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 1e6 + 5;
- const ll P = 131;
- const ll M = 1e9 + 7;
- int n, b[N / 2];
- ll p[N], h[N];
- string s;
- void Init() {
- s = '-' + s;
- p[0] = 1;
- for (int i = 1; i <= n; i++) {
- p[i] = p[i - 1] * P % M;
- h[i] = (h[i - 1] * P % M + s[i]) % M;
- }
- }
- ll Get(int l, int r) { return (h[r] + M - (h[l - 1] * p[r - l + 1] % M)) % M; }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n >> s;
- Init();
- int ans = 0;
- for (int i = n / 2; i >= 1; i--) {
- // 求出 [i + 1, n - i] 的 最长公共前后缀
- // 考虑知道 b[i] 求 b[i + 1], 推出 b[i + 1] >= b[i] - 2 (还有可以拓展的空间)
- // 那么 b[i] <= b[i + 1] + 2, 这就是上界
- for (int j = b[i + 1] + 2; j >= 1; j--) {
- if (i + j <= n / 2 && Get(i + 1, i + j) == Get(n - i - j + 1, n - i)) {
- b[i] = j;
- break;
- }
- }
- if (Get(1, i) == Get(n - i + 1, n)) {
- ans = max(ans, i + b[i]);
- }
- }
- cout << ans;
- return 0;
- }
复制代码 |
|