Atcoder ABC 391

· · 题解

C - Pigeonhole Query

思路：模拟题目操作的同时，记录每个巢里有多少鸽子，同时维护有多少个巢穴鸽子的数量大于1；

#include<bits/stdc++.h>
using namespace std; 
const int N = 1e6+5;
int cnt[N];
int pos[N];
signed main(){
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        pos[i] = i; // 记录i的位置 
        cnt[i] = 1; // i处的数量 
    }
    int ans = 0; // 维护大于1的数量 
    while(q--){
        int op, p, h;
        cin >> op;
        if(op == 1){
            cin >> p >> h;
            cnt[pos[p]]--;
            if(cnt[pos[p]] == 1) ans--;
            pos[p] = h;
            cnt[pos[p]]++;
            if(cnt[pos[p]] == 2) ans++;
        }else{
            cout << ans << endl;
        }
    }
    return 0;
}

D - Gravity

有一个 10^{9}行 W 列的网格。左起第 x列和下起第 y 行的单元格用 (x,y) 表示。

共有 N 个图块。每个区块是 1×1 的正方形，第 i 个区块（1≤i≤N）在 0 时刻位于单元格(X_{i},Y_{i})。

在 t=1,2,...,10^{100}时，区块按照以下规则移动：

[预处理](https://so.csdn.net/so/search?q=预处理&spm=1001.2101.3001.7020)答案。 ​ 哪些块一定会消失？会构成底行都为图块的块。那么先就求会消掉的层数，即每列的最少块数。 ​ 那么最后会处于同一行的什么时候消失呢？这个由最终同行的最高点决定。 ​ 不消失的块则一直存在。 ```cpp #include<bits/stdc++.h> using namespace std; void solve(){ int n, w; cin >> n >> w; vector<int>dt(n + 1, -1); //记录第i块消失的时间 vector< vector< pair<int, int> > > db(w + 1); // 记录第i列信息(高度，第几块) for(int x, y, i = 1; i <= n; i++){ cin >> x >> y; db[x].push_back({y, i}); } int tot = INT_MAX;// 统计最多能删除的行的数量 for(int i = 1; i <= w; i++){ sort(db[i].begin(), db[i].end());// 对每列按行高排列 tot = min(tot, (int)db[i].size());//能删除的数量为每列当中最少的行数 } for(int i = 1; i <= tot; i++){//处理每一次删除操作 int cur = 0; // 当前这次删除的时间 for(int j = 1; j <= w; j++) cur = max(cur, db[j][i - 1].first); // 时间为当前这次最高的行 // 即第j列第i-1最大的数 for(int j = 1; j <= w; j++) dt[db[j][i - 1].second] = cur; // 将消除时间记录下来 } int q; cin >> q; while(q--){ int t , a; cin >> t >> a; if(dt[a] == -1 || dt[a] > t) puts("Yes"); else puts("No"); } } int main(){ solve(); return 0; } ``` [E - Hierarchical Majority Vote](https://atcoder.jp/contests/abc391/tasks/abc391_e) 手动画一下样例1，则能发现：原来字符串每个字符是叶子节点，每三个往上合并一个成为新节点。最后形成一棵树。 题目就是求这个树根节点原数值发生改变所需的最少修改次数。 可以递归求解。 记录每棵子树的根节点修改成`0`或者`1`时所需的最少次数，自底向上求解，显然，这过程其实是动态规划， 这里用$dp[i][0/1]$来保存结果。 具体过程详见代码： ```cpp #include<bits/stdc++.h> using namespace std; const int N = 5e6 + 5; vector<int>g[N]; int tot, n; int dp[N][2], cur[N]; // dp[i][0/1]表示节点i，变成0/1需要的修改次数 // cur[i]不修改i的情况下，i节点的数字 string s; void dfs(int u){ if(u <= n){ // 叶子节点 if(s[u] == '1') dp[u][0] = 1; else dp[u][1] = 1; cur[u] = s[u] - '0'; return; } int cnt = 0; // 计算不修改情况下，u的3个儿子有多少个1 for(auto v : g[u]){ dfs(v); cnt += cur[v]; } if(cnt == 2 || cnt == 3) cur[u] = 1; // 得出当前u节点在未修改的情况下的数值 else cur[u] = 0; // 接下来考虑修改为0或者1，需要的最少操作次数 for(int t = 0; t <= 1; t++){// 假设u点改成t的话，需要的最少次数 int sum = 0, mx = 0; // sum表示改成t时，所有子节点的所需的次数之和，mx表示最多的那条分支 for(auto v : g[u]){ sum += dp[v][t]; mx = max(mx, dp[v][t]); } dp[u][t] = sum - mx; // 总共修改次数 - 最多的修改分支，即为剩余最少修改的次数之和 } } int main(){ cin >> n >> s; n = tot = s.size();// tot表示总的节点个数 s = ' ' + s; for(int i = 1; i + 2 <= tot; i += 3){ // 建树过程 ++tot; g[tot].push_back(i); g[tot].push_back(i + 1); g[tot].push_back(i + 2); } dfs(tot); // tot就是建完数据后的根节点 cout << dp[tot][cur[tot] ^ 1] << endl; return 0; } ```