2017-ICPC-jakarta

 2020.06.27 22:51  2023.09.01 18:14  ACM  multiset  期望dp  状态压缩  容斥原理 󰈭 3719字

B 动态维护两个序列之间的最小差值

尝试将图二分染色。如果不能二分染色，那么两人无论初始处于什么位置一定都有某种策略走到同一个节点；如果能够二分染色，题目则等价转化求$min{|u - v|}, u∈A, v∈B$，并且支持在线修改，这种情况是我们要着重处理的问题。

为此，利用multiset作为一个有序容器来实现这个功能。

初始时将所有的<节点权值，节点类型>存入set，按照节点权值从小到大排序。显然最优的答案只可能出现在这个set中相邻的两个不同类型节点之间，因而再开设另一个multiset记录ans，ans纯粹作为一个多重集合使用。

有了如上的准备工作，每次查询只需要找出ans第一个元素即可；而修改则复杂一些：log地找到将要被修改的元素在set中的迭代器位置，检查其是否已经和左右两个节点配对并在ans中贡献过了答案，如果贡献过则应该在ans中删去一个该答案，再检查是否该位置被移除后左右两个节点互相配对产生答案，如果有可能则应该据此更新ans；处理完之前的影响后就可以在set中删除该值，插入新值；接下来考虑插入新值对set的影响，如果插入的值将之前两个配对的节点隔开了，则应该将ans中对应的答案删去，如果插入的值和左右两个节点有配对，也应该相应地更新答案。

总而言之，对于修改的操作必须要保证ans集合中是一一对应地存set中位置相邻且类型不同的节点的差值 。

因为是log复杂度，所以可以飞快地通过这道题。

然而最开始没有保证ans集合满足上述性质，在插入新值的时候认为旧值不会影响到最优解，就贪图方便没有删除被隔断的值；事实上，这样子就无法使得删去旧值时保证所有与该值配对的答案全部在ans中被删除，会残留一些更小的但本不应该存在的值。

另一个坑点是，multiset的erase支持迭代器删除和按键值删除；使用迭代器删除只会删除指向的这一项，而按键值删除会把所有等于该值的元素全部删除！~~qaq~~

  1const itn maxn = 1e5 + 10;
  2
  3struct {int to, next;}edge[maxn << 2];
  4int n, m;
  5int head[maxn], top = 0, w[maxn];;
  6void add(int u, int v){
  7    edge[top].to = v;
  8    edge[top].next = head[u];
  9    head[u] = top++;
 10}
 11
 12//-1表示未染色。
 13int c[maxn];
 14bool check(int now, int op){
 15    if(c[now] != -1){
 16        if(c[now] != op) return 0;
 17        return 1;
 18    }
 19    c[now] = op;
 20    for(int i = head[now]; ~i; i = edge[i].next){
 21        if(!check(edge[i].to, !op)) return 0;
 22    }
 23    return 1;
 24}
 25
 26struct NODE{
 27    int key, type;
 28    bool operator < (const NODE &b)const{
 29        if(key != b.key) return key < b.key;
 30        else return type < b.type;
 31    };
 32};
 33
 34multiset<NODE> s;
 35multiset<int> ans;
 36/*
 37 如果要修改一个数，在s中找到它的迭代器，将它可能的已经产生的差值(一左一右)从ans中删去
 38 删去这个数，插入新数。
 39 不需要考虑新数对原有结构的影响，直接用新数左右两端的信息更新ans
 40 UPD: 这是错的！必须要考虑！
 41 
 42 如果要查询，看类型、flag等相关信息直接查询就行了...
 43 */
 44
 45int main(){
 46//    Fastin;
 47    clr(c, -1); clr(head, -1);
 48    scanf("%d %d", &n, &m);
 49    for(int i = 1; i <= n; i++) scanf("%d", w + i);
 50    for(int i = 0, u, v; i < m; i++){
 51        scanf("%d %d", &u, &v);
 52        add(u, v); add(v, u);
 53    }
 54    int flag = check(1, 0);
 55    multiset<NODE>::iterator p, q;
 56    if(flag){
 57        for(int i = 1; i <= n; i++) s.insert({w[i], c[i]});
 58        p = s.begin(); q = s.begin(); q++;
 59        for(; q != s.end(); p++, q++){
 60            if(p->type != q->type){
 61                ans.insert(abs(p->key - q->key));
 62            }
 63        }
 64    }
 65    int query; scanf("%d", &query); for(int i = 0; i < query; i++){
 66        int op, x, y; scanf("%d %d %d", &op, &x, &y);
 67        if(!flag){
 68            if(op) puts("0");
 69            continue;
 70        }
 71        
 72        if(op == 0){
 73            //w[x] := y;
 74            p = s.find({w[x], c[x]});
 75            NODE t1, t2; t1.type = t2.type = -1;
 76            q = p; q--; if(p != s.begin()){
 77                t1 = *q;
 78                if(t1.type != c[x]) ans.erase(ans.find(abs(w[x] - t1.key)));
 79            }
 80            q = p; q++; if(q != s.end()){
 81                t2 = *q;
 82                if(t2.type != c[x]) ans.erase(ans.find(abs(w[x] - t2.key)));
 83            }
 84            if(t1.type != -1 && t2.type != -1 && t1.type != t2.type) ans.insert(abs(t1.key - t2.key));
 85            
 86            s.erase(p); w[x] = y; s.insert({y, c[x]});
 87            t1.type = t2.type = -1; p = s.find({w[x], c[x]});
 88            q = p; q--; if(p != s.begin()){
 89                t1 = *q;
 90                if(t1.type != c[x]) ans.insert(abs(w[x] - t1.key));
 91            }
 92            q = p; q++; if(q != s.end()){
 93                t2 = *q;
 94                if(t2.type != c[x]) ans.insert(abs(w[x] - t2.key));
 95            }
 96            if(t1.type != -1 && t2.type != -1 && t1.type != t2.type) ans.erase(ans.find(abs(t1.key - t2.key)));
 97        }
 98        else{
 99            if(c[x] == c[y]) puts("0");
100            else printf("%d\n", *ans.begin());
101        }
102    }
103    return 0;
104}

C 贪心构造

如果没有等于号，最坏的构造一下，最后判断一下是否确实不存在等于的情况。

如果有等于号，考虑从最坏的为基准开始构造：

因为每次从两端开始询问会使得可能的答案个数-1，因而如果全部最坏询问，可能的答案个数就是n - [询问次数] 。

考虑每一次二分都尽可能多排除一些可能答案，使得剩余的可能答案尽快为1。那么显而易见，每次根据不等号方向确定区间收缩方向，进而确定最远收缩的位置。如果收缩到最远位置仍然有不止一个可能答案那么就最优的选择这里，不然的话就可以选择恰好为1个答案的位置进行收缩。当剩余答案仅为1时，每次就不需要多排除答案了，最坏的进行排除答案即可。

因为读题有误没有注意到奇数长度的中点保证返回’<’~~以及vj上这道题的评测机炸了~~所以吃了1000发WA

 1const int maxn = 5e4 + 10;
 2char s[maxn];
 3
 4ll n, k;
 5vector<ll> vec;
 6
 7int main(){
 8//    Fastin;
 9    while(~scanf("%lld %lld", &n, &k)){
10        vec.clear();
11        scanf("%s", s); int top = (int)strlen(s);
12        if(top == k && s[top - 1] != '='){
13            ll left = 1, right = n;
14            itn fail = 0;
15            for(int i = 0; i < top; i++){
16                if(s[i] == '<'){
17                    vec.push_back(right); right--;
18                }
19                else{
20                    vec.push_back(left); left++;
21                }
22                if(left > right){
23                    fail = 1;
24                    break;
25                }
26            }
27            if(fail) puts("-1");
28            else{
29                for(auto x: vec) printf("%lld ", x); printf("\n");
30            }
31        }
32        else{
33            //猜到了
34            ll r = n - top;
35            if(r < 0) puts("-1");
36            else{
37                ll left = 1, right = n;
38                for(int i = 0; i < top - 1; i++){
39                    if(s[i] == '>'){
40                        ll M = (right + left - 1) >> 1;
41                        if(M - left >= r){
42                            vec.push_back(left + r);
43                            left = left + r + 1;
44                            r = 0;
45                        }
46                        else{
47                            vec.push_back(M);
48                            r -= M - left;
49                            left = M + 1;
50                        }
51                    }
52                    else{
53                        ll m = (left + right + 1) >> 1;
54                        if(right - m >= r){
55                            vec.push_back(right - r);
56                            right = right - r - 1;
57                            r = 0;
58                        }
59                        else{
60                            vec.push_back(m);
61                            r -= right - m;
62                            right = m - 1;
63                        }
64                    }
65                }
66                if(left != right) puts("-1");
67                else{
68                    vec.push_back(left);
69                    for(auto x: vec) printf("%lld ", x); printf("\n");
70                }
71            }
72        }
73        
74    }
75    return 0;
76}

D

也是读题有误，从签到题到ak题

没有注意到给出的每一条边都是有向边，所以最开始不知道用哪一端去粘，就gg了

知道了的话随便记录一下剩余可用的度数即可。

 1const itn maxn = 1e5 + 10;
 2unordered_map<ll, int> tong;
 3
 4struct NODE{
 5    ll u, v, w;
 6    bool operator < (const NODE &b)const{
 7        return w < b.w;
 8    }
 9}node[maxn];
10
11int main(){
12//    Fastin;
13    int n, m; scanf("%d %d", &n, &m);
14    for(int i = 0; i < n; i++) scanf("%lld %lld %lld", &node[i].u, &node[i].v, &node[i].w);
15    sort(node, node + n);
16    int ans = 0;
17    fro(int i = 0; i < n; i++){
18        if(tong.count(node[i].u) == 0 || tong[node[i].u] == 0){
19            ans++;
20            tong[node[i].u] = m - 1;
21            tong[node[i].v] += m;
22        }
23        else{
24            tong[node[i].u]--;
25            tong[node[i].v] += m;
26        }
27    }
28    printf("%d\n", ans);
29    return 0;
30}

F 期望dp

~~确实是个没有写过的方法qaq~~

具体有哪几个数出现过我们不用关心，我们只需要记录状态(x, y, z)分别表示出现0次、1次、不少于2次的数的总个数即可。

设dp[x][y][z]表示从当前状态开始到停机所需要的次数的期望。

容易有递推关系

$dp[x][y][z] = 1 + \frac xn dp[x-1][y+1][z] + \frac yndp[x][y-1][z+1] + \frac zndp[x][y][z]$

最开始看到这个式子感到非常神奇

仔细想了一下感觉确实很符合期望的表达

当前状态操作1次分别有$\frac xn \frac yn \frac zn$的几率转移到上述三种状态，因而加权(即转移的概率)求和再加1后就得到当前的操作期望。

~~虽然具体所以然说不真切，但是感觉上还是很精妙的~~

~~留个期望dp的坑待补~~

之后做两个优化：

由$x + y + z = n$ 从3维优化到2位
化简后发现期望之间的转移关系与$n$成正比，启示我们求解$\frac {dp}n$ 的状态，将复杂度从$O(nT)$降低到$O(n)$

化简后得到L10-12行所示的公式，因为hexo-next好像不太支持\frac和其他一些公式的组合嵌套，所以就不放乱码上来了。

 1const itn maxn = 3e3 + 10;
 2
 3double dp[maxn][maxn];
 4int tong[maxn];
 5
 6int main(){
 7//    Fastin;
 8    for(int j = 1; j < maxn; j++) dp[0][j] = dp[0][j - 1] + 1.0 / j;
 9    fro(int i = 1; i < maxn; i++) for(int j = 0; i + j < maxn; j++){
10        dp[i][j] = 1 + i * dp[i - 1][j + 1];
11        if(j >= 1) dp[i][j] += j * dp[i][j - 1];
12        dp[i][j] = dp[i][j] * 1.0 / (i + j);
13    }
14    
15    int t; scanf("%d", &t); while(t--){
16        clr(tong, 0);
17        int n, k; scanf("%d %d", &n, &k);
18        int cnt0 = 0, cnt1 = 0;
19        for(int i = 0, x; i < k; i++){
20            scanf("%d", &x); tong[x]++;
21        }
22        for(int i = 1; i <= n; i++){
23            if(tong[i] == 0) cnt0++;
24            else if(tong[i] == 1) cnt1++;
25        }
26        printf("%.15f\n", n * dp[cnt0][cnt1]);
27    }
28    return 0;
29}

L 状态压缩 & 容斥

题目要求每行都有至少一个稻草人，相邻两列至少有一个稻草人。

思想与校赛类似，先优先考虑一个，之后利用朴素的容斥满足另一个。

枚举行的子集，求解这些行只考虑列方向上的约束关系的排列个数。可以用dp进行$O(m)$的求解:

$dp[i][0] = dp[i - 1][1]$

$dp[i][1] = (dp[i - 1][0] + dp[i -1][1]) * (2^{cnt_i} - 1),$

其中$cnt_i$表示第$i$列拥有空地的个数。

这里注意总列数为1的时候有dp[0][0] = 0，其余情况下都有dp[0][0] = 1，需要特判一下。

因为仅满足了列上的约束，所以求得的dp值满足行上要求的行个数至多为r，r是当前枚举的行的子集的大小。

为了要求恰有n行，可以从<=n行减去所有<=n-1行的情况，这样仅保证所有恰为n-1的情况都被不重不漏得减去，但是<=n-2的情况会被重复剪去，因而要加上所有的<=n-2的情况…之后一加一减以此类推

不过这样说明是不严谨的，应该用容斥原理说明。

~~之前就没有补完知识点，现在还是，所以就先继续🐦着了。~~

时间复杂度必须压缩在$O(2^r*C)$，再多个$r$就爆了，必须要妥善的预处理才行。

另外空间也有点紧(？)评测机说可以512MB，本地跑下来300MB还是内存溢出。不过后来意识到没有必要存储每次的dp值最后再遍历，直接在处理完当前状态后实时将结果添加到答案中就行了。这样就可以AC了。

 1const int maxn = 15;
 2const int maxm = 1e3 + 5;
 3const int M = 1e9 + 7;
 4
 5
 6int pow2[maxn];
 7int n, m;
 8char mp[maxn][maxm];
 9int cnt[1 << maxn][maxm], vis[1 << maxn];
10pair<int, int> nxt[1 << maxn];
11vector<int> order[maxn];
12
13int count_1(int sts){
14    int cnt = 0;
15    for(int i = 0; i < n; i++) if(sts & 1 << i) cnt++;
16    return cnt;
17}
18
19void ini(int sts){
20    if(vis[sts]) return; vis[sts] = 1;
21    order[count_1(sts)].push_back(sts);
22    for(int i = 0; i < n; i++) if((sts & 1 << i) == 0){
23        if(nxt[sts].first == -1){
24            nxt[sts].first = sts | 1 << i;
25            nxt[sts].second = i;
26        }
27        ini(sts | 1 << i);
28    }
29}
30
31ll a[maxm][2];
32void sove(int sts){
33    int *b = cnt[sts];
34    a[0][0] = m == 1? 0: 1;
35    a[0][1] = pow2[b[0]] - 1;
36    for(int i = 1; i < m; i++){
37        a[i][0] = a[i - 1][1];
38        a[i][1] = (a[i - 1][0] + a[i - 1][1]) % M * 1ll * (pow2[b[i]] - 1) % M;
39    }
40}
41
42
43ll sgn(int x){ return x & 1? -1: 1;}
44
45int main(){
46//    Fastin;
47    pow2[0] = 1;
48    fro(int i = 1; i < maxn; i++) pow2[i] = 2 * pow2[i - 1];
49    
50    scanf("%d %d", &n, &m);
51    clr(nxt, -1);
52    for(int i = 0; i < n; i++) scanf("%s", mp[i]);
53    
54    ini(0);
55    int sts = (1 << n) - 1;
56    for(int c = 0; c < m; c++) for(int i = 0; i < n; i++) cnt[sts][c] += mp[i][c] == '.';
57    ll ans = 0;
58    for(int i = n; i >= 1; i--) for(auto x: order[i]){
59        if(i != n) for(int i = 0; i < m; i++) cnt[x][i] = cnt[nxt[x].first][i] - (mp[nxt[x].second][i] == '.');
60        sove(x);
61        int cnt = count_1(x);
62        ans += sgn(n - cnt) * (a[m - 1][0] + a[m - 1][1]);
63        ans = (ans % M + M) % M;
64    }
65    
66    printf("%lld\n", ans);
67    return 0;
68}