[心之碎片] - 20240730模拟赛

柿子饼同学

总结与反思

C - 如果一个数可以确定整个状态, 考虑设未知数然后给所有的数减掉偏移量

D - 负数要加模取模

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;
}

FishC

哎呀，看来你在整理一场赛题的总结和反思呢！我们来逐条解析一下，让你在这个代码的魔法世界中游刃有余！

### C - 状态确定
"如果一个数可以确定整个状态"这就像是你家猫咪，只要它在窗台上晒太阳，你就知道家里没有人敢动那些零食。通过设未知数和偏移量，就能让所有的数变得井井有条，简直如同调皮的小鱼学会了如何游泳！

### D - 负数与模
“负数要加模取模”，想象你在打乒乓球，结果不小心把球打到了邻居的花园里，别担心，把那个负数调整一下，总能找到正确的方向球回来的！取模就是让你抖落掉不想要的负号，让数值重新回到你的掌控之中。

### E - 伪删除
"伪删除"就像是在聚会上决定不再和某个人说话，但又不想当面撕破脸。在你的数据结构中，真正的删除有时候太过麻烦，所以我们选择“伪删除”，保留元素只是记录大小的变化，方便后续使用。就像你仍然记得聚会上的尴尬瞬间，但仍旧保持微笑！

### F - 动态规划DP
“首先考虑阶段”就像做菜，先想到米饭是先蒸还是先炒菜？明确任务的顺序才能保证最终大餐的美味。动态规划就像是一个聪明的大厨，巧妙地安排每一步的烹饪流程，确保每个部分都能完美融合。

### G - 倍增
“发现一个非常长，或者有循环的东西要想到倍增”，这条建议你可以想象成电视剧中的续集，知道第一季的情节，自然后面的发展也会呼之欲出。用倍增的思维，快速推导出你想要的结果。

### H - 字符串处理
“公共前后缀/回文”的问题就像寻找适合的朋友圈，大家总是有共同的话题。你可以通过小范围的交流（子串的处理）来提升更大的讨论（整个字符串的理解）。

### 代码分析
最后，你的代码中提到的并查集、哈希等概念也很重要！并查集就像是社交网络，帮你找到哪些朋友是一起的，而哈希则是你的秘密武器，保障信息的快速查找与验证。伪删除的思想再次出现，让你在设置和删除数据时游刃有余。

希望这些总结与幽默的解释能帮助你在未来的模拟赛中更加得心应手！加油，别忘了给你的猫咪喂食哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

python负数取模我一直不懂

简柠啦

bowlderq

厉害

zhangjinxuan

你们模拟赛这么多题？

这么多对我而言读都读不完。

柿子饼同学

zhangjinxuan 发表于 2024-8-3 12:02
你们模拟赛这么多题？

这么多对我而言读都读不完。

前面几个都是简单题

zhangjinxuan

柿子饼同学 发表于 2024-8-3 14:14
前面几个都是简单题

原来如此，那还真的差不多

柿子饼同学

zhangjinxuan 发表于 2024-8-3 15:51
原来如此，那还真的差不多

今年冲省队?

希儿的

加油

lwh0602

加油

尹玄睿

18408238295

很cool的阳

磷酸