SDOI2019 快速查询
考虑维护双标记，题目的难点在于如何维护单点赋值操作。
推式子发现，直接修改原本的值变为$\frac{x-add}{mul}$，用hash维护下标即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define MOD 10000019 4 namespace hash{ 5 #define sz 299999 6 int h[300010], num[300010], clo[300010]; 7 int All, CLO; 8 inline int get_Num(int x) { 9 int wt = x % sz; 10 while(num[wt] != x && num[wt]) { 11 ++ wt; 12 if(wt == sz) wt = 0; 13 } 14 num[wt] = x; 15 return wt; 16 } 17 inline int upd(int x, int y, int CL) { 18 int wt = get_Num(x); 19 if(clo[wt] < CLO) h[wt] = All; 20 int ret = y - h[wt]; 21 h[wt] = y; clo[wt] = CL; 22 return ret; 23 } 24 inline int query(int x) { 25 int wt = get_Num(x); 26 if(clo[wt] < CLO) h[wt] = All, clo[wt] = CLO; 27 return h[wt]; 28 } 29 } 30 int inv[MOD+10]; 31 inline void init() { 32 inv[0] = inv[1] = 1; 33 for(int i = 2; i < MOD; ++ i) { 34 inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD; 35 } 36 } 37 struct Node { 38 int op, x, y; 39 } que[100010]; 40 int main() { 41 //freopen("a.in", "r", stdin); 42 init(); 43 int n, q; 44 scanf("%d%d", &n, &q); 45 for(int i = 1; i <= q; ++ i) { 46 int op, x = 0, y = 0; 47 scanf("%d", &op); 48 if(op == 1) { 49 scanf("%d%d", &x, &y); 50 y %= MOD; 51 y = (y + MOD) % MOD; 52 } 53 else if(2 <= op && op <= 5) { 54 scanf("%d", &x); 55 if(op != 5) { 56 x %= MOD; 57 x = (x + MOD) % MOD; 58 } 59 } 60 //cerr << op << " " << x << " " << y << endl; 61 que[i] = (Node){op, x, y}; 62 } 63 int mul = 1, add = 0, sum = 0; 64 int t; 65 scanf("%d", &t); 66 int Ans = 0, cnt = 0; 67 while(t --) { 68 int A, B; 69 scanf("%d%d", &A, &B); 70 //cerr << A << B << endl; 71 for(int i = 1; i <= q; ++ i) { 72 ++ cnt; 73 int id = (A + 1ll * i * B) % q + 1; 74 int op = que[id].op, x = que[id].x, y = que[id].y; 75 if(op == 1) { 76 int ry = 1ll * (y - add + MOD) * inv[mul] % MOD; 77 int d = hash::upd(x, ry, cnt); 78 sum += d; 79 if(sum >= MOD) sum -= MOD; 80 if(sum < 0) sum += MOD; 81 } 82 else if(op == 2) { 83 add += x; 84 if(add >= MOD) add -= MOD; 85 } 86 else if(op == 4 || (op == 3 && x == 0)) { 87 sum = 1ll * n * x % MOD; 88 add = 0, mul = 1; 89 hash::All = (x + MOD) % MOD; 90 hash::CLO = cnt; 91 } 92 else if(op == 3) { 93 mul = 1ll * mul * x % MOD; 94 add = 1ll * add * x % MOD; 95 } 96 else if(op == 5) { 97 int res = hash::query(x); 98 res = (1ll * res * mul + add) % MOD; 99 Ans += res; 100 if(Ans >= MOD) Ans -= MOD; 101 } 102 else { 103 int res = (1ll * sum * mul + 1ll * n * add) % MOD; 104 Ans += res; 105 if(Ans >= MOD) Ans -= MOD; 106 } 107 if(mul < 0) mul += MOD; 108 if(add < 0) add += MOD; 109 if(sum < 0) sum += MOD; 110 //cerr << sum << endl; 111 } 112 } 113 printf("%d\n", Ans); 114 }
SDOI2019 热闹的聚会与尴尬的聚会
一道构造好题。
$\lfloor\frac{n}{p+1}\rfloor \leq q$可以推出$(p+1)(q+1)>n$。
每次枚举当前图中度数最小的点$x$，删除$x$以及与$x$相邻的点。
设总共会删除$q$次，显然有$\sum_{i=1}^q (d_i+1) = n$。
对于每次枚举的$x$度数中的最大值$mxd$，一定可以找到一个$p=mxd$的构造方案。
所以有$\sum_{i=1}^q (d_i+1)\leq mxd*q$。
稍加推倒可以证明如果找到$p=mxd$的构造方案，那么可以满足$(p+1)(q+1)>n$。
构造的方案即为当$d_x=mxd$时，当前图中剩余的全部点。
显然可以发现除了$x$以外，其他的点$y$满足$mxd \leq d_y$。
用$set$维护即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Edge{ 4 int u, v, Next; 5 } G[200010]; 6 int head[100010], tot; 7 int d[100010]; 8 struct Node{ 9 int D, x; 10 inline bool operator < (const Node& rhs) const{ 11 return D < rhs.D || (D == rhs.D && x < rhs.x); 12 } 13 }; 14 set<Node> S; 15 inline void add(int u, int v) { 16 G[++ tot] = (Edge){u, v, head[u]}; 17 head[u] = tot; 18 } 19 int ans1[100010], t1; 20 int ans2[100010], t2; 21 inline void solve() { 22 int n, m; 23 scanf("%d%d", &n, &m); 24 tot = 0; 25 for(int i = 1; i <= n; ++ i) { 26 head[i] = -1; 27 d[i] = 0; 28 } 29 for(int i = 1; i <= m; ++ i) { 30 int u, v; 31 scanf("%d%d", &u, &v); 32 add(u, v), add(v, u); 33 ++ d[u], ++ d[v]; 34 } 35 for(int i = 1; i <= n; ++ i) { 36 S.insert((Node){d[i], i}); 37 } 38 int mxd = 0, pos; 39 t1 = t2 = 0; 40 while(!S.empty()) { 41 set<Node> :: iterator t = S.begin(); 42 //cerr << "element " << t -> x << endl; 43 S.erase(t); 44 if(t -> D > mxd) { 45 mxd = t -> D; 46 pos = t1; 47 } 48 int x = t -> x; 49 ans2[++ t2] = x; 50 ans1[++ t1] = x; 51 for(int i = head[x]; i != -1; i = G[i].Next) { 52 t = S.find((Node){d[G[i].v], G[i].v}); 53 54 if(t == S.end()) continue; 55 //cerr << x << " " << G[i].v << endl; 56 int X = t -> x; 57 ans1[++ t1] = X; 58 S.erase(t); 59 for(int j = head[X]; j != -1; j = G[j].Next) { 60 set<Node> :: iterator it = S.find((Node){d[G[j].v], G[j].v}); 61 if(it == S.end()) continue; 62 S.erase(it); 63 S.insert((Node){-- d[G[j].v], G[j].v}); 64 } 65 } 66 } 67 printf("%d ", t1 - pos); 68 for(int i = pos + 1; i <= t1; ++ i) { 69 printf("%d ", ans1[i]); 70 } 71 puts(""); 72 printf("%d ", t2); 73 for(int i = 1; i <= t2; ++ i) { 74 printf("%d ", ans2[i]); 75 } 76 puts(""); 77 } 78 int main() { 79 int T; 80 scanf("%d", &T); 81 while(T --) { 82 solve(); 83 } 84 }
原文：https://www.cnblogs.com/iamqzh233/p/11431853.html
