ACM
线段树
3200字
ACM
102字
ACM
DP
711字
ACM
3938字
G 线段树 区间修改、取模，区间哈希和查询 需要维护一个支持区间加1并对固定模数取模、区间哈希查询的线段树
开局就想写的一道题，写到最后艰难调出来后wa7，最终放弃上机辅助队友看别的题
晚上回去又调了很久，发现了几个错误
线段树哈希写错了，在求哈希和的时候不像普通的线段树区间和一样，查询哈希和时查询的区间[L, R]是需要动态变化的，必须保证L被不断地截断，才能保证算法的正确性 眼睛比较瞎，前缀和pre[]对M(65536)取模了 最开始的purify(将那些超过65536的位置取模)写挫了，在终止条件(l == r)之前就调用了down函数。调了一年才发现原来是这里有问题：如果在终止条件之前就调用down函数，这会导致地址的越界访问。因为st只开了4倍空间，所以如果在那种边角叶子结点（在满二叉树上多一个节外生枝的结构）仍然尝试down下去，就会访问到8倍的位置！在CF居然没有发生RE报警，以至于我一度怀疑是自己算法写错了，其实是空间的计算错误导致了UKE。 cpp 1#define ls (p << 1) 2#define rs ((p << 1) | 1) 3#define mid ((l + r) >> 1) 4 5using namespace std; 6const int maxn = 5e5 + 10; 7const int M = 65536; 8 9const int pp = 999983; 10const int mod = 1000237529; 11 12int a[maxn]; 13ll tag1[maxn << 2], st2[maxn << 2], st[maxn << 2]; 14ll po[maxn], pre[maxn]; 15 16void up(int p, int l, int r){ 17 st[p] = st[ls] + st[rs] * po[mid - l + 1] % mod; st[p] %= mod; 18 st2[p] = max(st2[ls], st2[rs]); 19} 20 21void build(int p, int l, int r, int k, int x){ 22 if(l == r && l == k){ 23 st[p] = st2[p] = x; 24 return ; 25 } 26 if(k <= mid) build(ls, l, mid, k, x); 27 else build(rs, mid + 1, r, k, x); 28 up(p, l, r); 29} 30 31void down(int p, int l, int r){ 32 if(tag1[p]){ 33 tag1[ls] += tag1[p]; 34 tag1[rs] += tag1[p]; 35 36 st[ls] += pre[mid - l] * tag1[p] % mod; st[ls] %= mod; 37 st[rs] += pre[r - mid - 1] * tag1[p] % mod; st[rs] %= mod; 38 39 st2[ls] += tag1[p]; 40 st2[rs] += tag1[p]; 41 42 tag1[p] = 0; 43 } 44} 45 46void update(int p, int l, int r, int L, int R){ 47 if(L <= l && r <= R){ 48 st[p] += pre[r - l]; st[p] %= mod; 49 st2[p]++; tag1[p]++; 50 return ; 51 } 52 down(p, l, r); 53 if(L <= mid) udpate(ls, l, mid, L, R); 54 if(R > mid) update(rs, mid + 1, r, L ,R); 55 up(p, l, r); 56} 57 58void purify(int p, int l, int r){ 59 if(st2[p] < M) return; 60 down(p, l, r); 61 if(l == r){ 62 st[p] %= M; st2[p] %= M; 63 return ; 64 } 65 66 if(st2[ls] >= M) purify(ls, l, mid); 67 if(st2[rs] >= M) purify(rs, mid + 1, r); 68 up(p, l, r); 69} 70 71ll hsh(int p, int l, int r, int L, int R){ 72 if(L <= l && r <= R) return st[p]; 73 down(p, l, r); 74 75 if(R <= mid) return hsh(ls, l, mid, L, R); 76 else if(L > mid) return hsh(rs, mid + 1, r, L, R); 77 else{ 78 ll ans = hsh(ls, l, mid, L, mid); 79 ans += hsh(rs, mid + 1, r, mid + 1, R) * po[mid - L + 1] % mod; 80 ans %= mod; 81 return ans; 82 } 83} 84 85int main(){ 86// Fastin; 87 po[0] = 1; 88 for(int i = 1; i < maxn; i++) po[i] = po[i - 1] * 1ll * pp % mod; 89 pre[0] = 1; 90 for(int i = 1; i < maxn; i++) pre[i] = pre[i - 1] + po[i], pre[i] %= mod; 91 92 int n, m; scanf("%d %d", &n, &m); 93 for(int i = 1; i <= n; i++){ 94 scanf("%d", a + i); 95 build(1, 1, n, i, a[i]); 96 } 97 98 while(m--){ 99 int op; scanf("%d", &op); 100 if(op == 1){ 101 int l, r; scanf("%d %d", &l, &r); 102 update(1, 1, n, l, r); 103 } 104 else{ 105 int l, r, k; scanf("%d %d %d", &l, &r, &k); 106 purify(1, 1, n); 107 108 ll res1 = hsh(1, 1, n, l, l + k - 1); 109 ll res2 = hsh(1, 1, n, r, r + k - 1); 110 puts(res1 == res2? "yes": "no"); 111 } 112 } 113 114 return 0; 115} L 分组背包 & LCM 给出n，构造某种拆分$p_1+p_2+…+p_k = n$，使得$lcm(p_1, p_2, …, p_k)$最大。
...
J RQD-IGVA树 树上DSU 最开始以为险段长度跟n无关，所以加了根[1, n]的线段进去就WA到死，后来改成[1, 1000000]即可。
大概是叫dsu on tree，可以处理一些与子树有关的询问，复杂度Onlogn
可惜IGVA不知道场上什么地方写挫了 场后10分钟A了
cpp 1const int maxn = 3e5 + 10; 2 3int n, w[maxn]; 4struct star{int to, next;}; 5int head[maxn], top = 0; 6star edge[maxn]; 7void add(int u, int v){ 8 edge[top].to = v; 9 edge[top].next = head[u]; 10 head[u] = top++; 11} 12 13struct NODE{ 14 int l, r, w; 15 bool operator < (const NODE &b) const{ 16 if(l != b.l) return l < b.l; 17 else return r > b.r; 18 } 19}; 20vector<NODE> vec; 21priority_queue<ll> pq[maxn]; 22int conv[maxn]; 23vector<ll> temp; 24 25//合并边i和边j的优先队列，放到i里面 26void merge(int i , int j){ 27 temp.clear(); 28 if(pq[conv[i]].size() < pq[conv[j]].size()) swap(conv[i], conv[j]); 29 30 while(!pq[conv[j]].empty()){ 31 temp.push_back(pq[conv[i]].top() + pq[conv[j]].top()); 32 pq[conv[i]].pop(); pq[conv[j]].pop(); 33 } 34 for(auto x: temp) pq[conv[i]].push(x); 35} 36 37void sove(int now){ 38 for(int i = head[now]; ~i; i = edge[i].next){ 39 sove(edge[i].to); 40 merge(now, edge[i].to); 41 } 42 pq[conv[now]].push(vec[now].w); 43} 44 45stack<int> sta; 46 47int main(){ 48 // Fastin; 49 clr(head, -1); 50 scanf("%d", &n); 51 for(int i = 1; i <= n; i++){ 52 int u, v, w; scanf("%d %d %d", &u, &v, &w); 53 vec.push_back({u, v, w}); 54 } 55 vec.push_back({1, 1000000, 0}); 56 sort(vec.begin(), vec.end()); 57 58 sta.push(0); 59 for(int i = 1; i <= n; i++){ 60 int top = sta.top(); 61 while(!(vec[top].l <= vec[i].l && vec[i].r <= vec[top].r)){ 62 sta.pop(); 63 if(sta.empty()){while(1);}; 64 top = sta.top(); 65 } 66 add(top, i); sta.push(i); 67 } 68 69 for(itn i = 0; i <= n; i++) conv[i] = i; 70 sove(0); 71 72 ll ans = 0; 73 for(int i = 1; i <= n; i++){ 74 if(!pq[conv[0]].empty()){ 75 ans += pq[conv[0]].top(); pq[conv[0]].pop(); 76 } 77 printf("%lld ", ans); 78 } 79 80 return 0; 81} I 最小直径生成树 MDST 为了求解MDST，就需要求解绝对中心所在的位置。绝对中心不一定在节点上，可以在边上。
...
ACM
237字
K 树dp 场上想了一个不太对的排序办法，真正的排序方法应该是将子树按照最深深度从低到高进行排序。然后随便维护一个dp数组表示从根节点派遣若干士兵遍历完i子树所需要的最小时间，每次尝试用子树的结果更新他们共同父节点的信息：
如果某节点是叶子，那么用其深度作为结果； 如果某节点不是叶子，将子树按照上述顺序排序后，考虑子树v1可能对v2造成的贡献：当height[v1] + 2 <= dep[v2]，那么从v1的士兵原路返回会比重新派遣一个人过来更优，将结果减去差值，不断重复更新。每次只需要考虑子树$i$对子树${i + 1}$的贡献，这是因为子树序列是单调的，一旦到某个位置后重新派遣更优，之后的所有位置也一定是重新派遣更优。 cpp 1const int manx = 1e6 + 10; 2 3struct star{int to, next;}; 4int head[maxn], top = 0; 5star edge[maxn << 1]; 6 7void add(int u, int v){ 8 edge[top].to = v; 9 edge[top].next = head[u]; 10 head[u] = top++; 11} 12 13int dep[maxn], height[maxn]; 14void dfs(int x, int par){ 15 height[x] = 0; 16 for(int i = head[x]; ~i; i = edge[i].next){ 17 int to = edge[i].to; if(to == par) continue; 18 dep[to] = dep[x] + 1; 19 dfs(to, x); 20 height[x] = max(height[x], height[to] + 1); 21 } 22} 23 24//从根结点派遣若干人，遍历完i子树所需要的最小代价即为dp[i] 25bool cmp(int x, int y){return height[x] < height[y];} 26ll dp[maxn]; 27void sove(int now, int par){ 28 vector<int> vec; 29 for(int i = head[now]; ~i; i = edge[i].next){ 30 itn to = edge[i].to; if(to == par) continue; 31 vec.push_back(to); 32 sove(to, now); 33 } 34 sort(vec.begin(), vec.end(), cmp); 35 if(vec.empty()) dp[now] = dep[now]; 36 else{ 37 int top = (int)vec.size(); 38 for(auto x: vec) dp[now] += dp[x]; 39 fro(int i = 1; i < top; i++){ 40 if(height[vec[i - 1]] + 2 <= dep[vec[i]]){ 41 dp[now] -= dep[vec[i]] - height[vec[i - 1]] - 2; 42 } 43 } 44 } 45} 46 47int main(){ 48 // Fastin; 49 int _; scanf("%d", &_); fro(int __ = 1; __ <= _; __++){ 50 top = 0; 51 int n; scanf("%d", &n); 52 for(int i = 1; i <= n; i++){ 53 dp[i] = height[i] = dep[i] = 0; 54 head[i] = -1; 55 } 56 for(int i = 2; i <= n; i++){ 57 int x; scanf("%d", &x); 58 add(x, i); add(i, x); 59 } 60 dfs(1, 0); 61 sove(1, 0); 62 printf("Case #%d: %d\n", __, dp[1]); 63 } 64 return 0; 65} J 哈希与组合数学 感谢冯佬的指点qaq 不然我可能一年都调不出来这题…sro flukehn….
...
ACM
构造
1016字
24点小游戏~
cpp 1#include <iostream> 2 3#include <algorithm> 4#include <string> 5#include <vector> 6#include <stack> 7#include <queue> 8#include <set> 9#include <map> 10#include <unordered_map> 11#include <unordered_set> 12#include <random> 13#include <chrono> 14 15#include <cstdio> 16#include <cstring> 17#include <cmath> 18#include <ctime> 19#include <cstdlib> 20#include <cassert> 21 22#define itn int 23#define fro for 24#define scnaf scanf 25#define sacnf scanf 26#define manx maxn 27#define pritnf printf 28 29#define Fastin freopen("in.txt", "r", stdin) 30#define Fastout freopen("out.txt", "w", stdout) 31#define min(a, b) ((a) < (b)? (a): (b)) 32#define max(a, b) ((a) > (b)? (a): (b)) 33#define lowbit(x) ((x) & (-x)) 34#define ceil(n, p) (((n) +(p) - 1) / (p)) 35#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n') 36#define clr(a, x) memset((a), x, sizeof (a)) 37#define TTT int __; scanf("%d", &__); while(__--) 38using namespace std; 39typedef long long ll; 40 41int a[5], b[5], p[5]; 42 43struct NODE{ 44 string s; double w; 45 bool operator < (const NODE& b)const{return s < b.s;} 46}; 47set<NODE> s[5][5]; 48//处理[left, right]的值 49void sove(int left, int right){ 50 if(left > right) return ; 51 if(left == right){ 52 NODE temp; 53 temp.s = to_string(a[left]); temp.w = a[left]; 54 s[left][right].insert(temp); 55 return; 56 } 57 for(int i = left; i <= right - 1; i++){ 58 sove(left, i); sove(i + 1, right); 59 NODE temp; 60 for(auto x: s[left][i]) for(auto y: s[i + 1][right]){ 61 temp.s = x.s; if(left != i) temp.s = "(" + temp.s + ")"; 62 temp.s += "+"; temp.w = x.w + y.w; 63 if(i + 1 != right) temp.s += "(" + y.s + ")"; 64 else temp.s += y.s; 65 s[left][right].insert(temp); 66 67 temp.s = x.s; if(left != i) temp.s = "(" + temp.s + ")"; 68 temp.s += "-"; temp.w = x.w - y.w; 69 if(i + 1 != right) temp.s += "(" + y.s + ")"; 70 else temp.s += y.s; 71 s[left][right].insert(temp); 72 73 temp.s = x.s; if(left != i) temp.s = "(" + temp.s + ")"; 74 temp.s += "*"; temp.w = x.w * y.w; 75 if(i + 1 != right) temp.s += "(" + y.s + ")"; 76 else temp.s += y.s; 77 s[left][right].insert(temp); 78 79 if(y.w == 0) continue; 80 temp.s = x.s; if(left != i) temp.s = "(" + temp.s + ")"; 81 temp.s += "/"; temp.w = x.w / y.w; 82 if(i + 1 != right) temp.s += "(" + y.s + ")"; 83 else temp.s += y.s; 84 s[left][right].insert(temp); 85 } 86 87 } 88} 89 90const double eps = 1e-6; 91set<string> ans; 92 93int main(){ 94// Fastin; 95 for(int i = 1; i <= 4; i++) scnaf("%d", b + i); 96 p[1] = 1; p[2] = 2; p[3] = 3; p[4] = 4; 97 98 do{ 99 for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) s[i][j].clear(); 100 for(int i = 1; i <= 4; i++) a[i] = b[p[i]]; 101 sove(1, 4); 102 for(auto x: s[1][4]) if(abs(x.w - 24) <= eps){ 103 ans.insert(x.s); 104 } 105 }while(next_permutation(p + 1, p + 5)); 106 107 if(ans.empty()) puts("-1"); 108 else for(auto s: ans) cout << s << '\n'; 109 return 0; 110}
ACM
set
588字
ACM
树
构造
1094字
C 思维 & 树 C* Namomo 2C 区间减1，代价为长度的平方，问将区间操作为全0的最小代价和最大代价。
cpp 1#include <iostream> 2 3#include <algorithm> 4#include <string> 5#include <vector> 6#include <stack> 7#include <queue> 8#include <set> 9#include <map> 10#include <unordered_map> 11#include <unordered_set> 12#include <random> 13#include <chrono> 14 15#include <cstdio> 16#include <cstring> 17#include <cmath> 18#include <ctime> 19#include <cstdlib> 20#include <cassert> 21 22#define itn int 23#define fro for 24#define scnaf scanf 25#define sacnf scanf 26#define Fastin freopen("in.txt", "r", stdin) 27#define Fastout freopen("out.txt", "w", stdout) 28#define manx maxn 29#define lowbit(x) ((x) & (-x)) 30#define ceil(n, p) (((n) +(p) - 1) / (p)) 31#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n') 32#define clr(a, x) memset((a), x, sizeof (a)) 33#define min(a, b) ((a) < (b)? (a): (b)) 34#define max(a, b) ((a) > (b)? (a): (b)) 35 36using namespace std; 37typedef long long ll; 38 39int read(){ 40 int ng=0,x=0; 41 char ch=getchar(); 42 for(;ch<'0' || ch>'9';ch=getchar()) ng|=ch=='-'; 43 for(;ch>='0' && ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; 44 return ng?-x:x; 45} 46/*------------------------------------------------------------------------------------*/ 47ll gcd(ll x, ll y){return !x? y: gcd(y % x, x);} 48void exgcd(ll a, ll b, ll &x, ll &y){ 49 if(!b){x = 1; y = 0;return;} 50 exgcd(b, a % b, y, x); y -= a / b * x; 51} 52ll qp(ll a, ll p){ 53 if(p < 0) return 0; 54 ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;} 55 return ans; 56} 57ll qp(ll a, ll p, ll M){ 58 ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;} 59 return ans; 60} 61/*------------------------------------------------------------------------------------*/ 62 63const int maxn = 5e5 + 10; 64const int M = 1e9 + 7; 65int a[maxn], b[maxn]; 66 67ll cal(int l, int r){return (r - l) * 1ll * (r - l) % M;} 68 69stack<pair<int, int>> sta; 70 71int main(){ 72// Fastin; 73 int n; scnaf("%d", &n); 74 for(int i = 1; i <= n; i++) scanf("%d", a + i); a[n + 1] = 0; 75 76 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 77 while(b[n + 1] == 0) n--; 78 ll ans = 0; 79 int p = 1, q = 1; while(b[q] >= 0) q++; 80 while(p <= n + 1){ 81 if(b[p] + b[q] > 0){ 82 ans += -b[q] * cal(p, q); ans %= M; 83 b[p] += b[q]; 84 q++; while(q <= n + 1 && b[q] >= 0) q++; 85 } 86 else if(b[p] + b[q] == 0){ 87 ans += b[p] * cal(p, q); ans %= M; 88 p++; q++; while(p <= n + 1 && b[p] < 0) p++; while(q <= n + 1 && b[q] >= 0) q++; 89 } 90 else{ 91 ans += b[p] * cal(p, q); ans %= M; 92 b[q] += b[p]; 93 p++; while(p <= n + 1 && b[p] < 0) p++; 94 95 } 96 } 97 printf("%lld ", ans % M); 98 99 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 100 ans = 0; 101 for(int i = 1; i <= n + 1; i++){ 102 if(b[i] > 0) sta.push({i, b[i]}); 103 else if(b[i] < 0){ 104 while(1){ 105 pair<int, int> now = sta.top(); sta.pop(); 106 if(now.second + b[i] < 0){ 107 ans += now.second * cal(now.first, i); ans %= M; 108 b[i] += now.second; 109 } 110 else{ 111 ans += -b[i] * cal(now.first, i); ans %= M; 112 now.second += b[i]; 113 sta.push(now); 114 break; 115 } 116 117 } 118 } 119 } 120 121 printf("%lld\n", ans); 122 123 return 0; 124} I 构造 虽然感觉还是说不太清楚qaq
...
ACM
1550字
1006 cpp 1const itn maxn = 1e5 + 10; 2 3int n, m, w[maxn]; 4struct star{int to, next;}; 5 6int head[maxn], top = 0; 7int du[maxn], K; 8star edge[maxn << 1]; 9void add(int u, int v){ 10 edge[top].to = v; 11 edge[top].next = head[u]; 12 head[u] = top++; 13} 14 15unordered_map<int, int> mp[maxn]; 16unordered_map<int, int> conv; 17 18int c[700][maxn], bitcnt = 0, zero[maxn]; 19void add(int id, int i, int x, int n){ 20 while(i <= n){ c[id][i] += x; i += lowbit(i);} 21} 22int query(int id, int i){ 23 int ans = 0; 24 while(i){ans += c[id][i]; i -= lowbit(i);} return ans; 25} 26 27void bitupdate(int u, int key, int op){ 28 assert(conv.count(u) == 1); 29 int id = conv[u]; add(id, key, op, du[u]); 30} 31 32//将u节点的邻接权值key的数量 += op 33void update(int u, int key, int op){ 34 if(key > du[u]) return; 35 36 //特判断0 37 if(key == 0){ 38 zero[u] += op; return; 39 } 40 41 mp[u][key] += op; 42 // 1 - >0 43 if(mp[u][key] == 0){ 44 bitupdate(u, key, -1); 45 mp[u].erase(key); 46 } 47 //0 -> 1 48 if(mp[u][key] == 1 && op == 1) bitupdate(u, key, 1); 49 50} 51 52//检查u节点的邻点中 权值x及其之前是否填满 53bool check(int u, int x){ 54 if(x == 0){ 55 if(zero[u] == 0) return 0; 56 return 1; 57 } 58 int cnt = query(conv[u], x); 59 return x == cnt; 60} 61 62int temp[maxn]; 63int mex(int u){ 64 if(du[u] < K){ 65 for(int i = 0; i <= du[u]; i++) temp[i] = 0; 66 for(int i = head[u]; ~i; i = edge[i].next){ 67 if(w[edge[i].to] > du[u]) continue; 68 temp[w[edge[i].to]] = 1; 69 } 70 for(int i = 0; i <= du[u]; i++) if(!temp[i]) return i; 71 return -1; 72 } 73 else{ 74 if(zero[u] == 0) return 0; 75 76 int left = 0, right = du[u], middle; 77 while(left < right){ 78 middle = (left + right) >> 1; 79 if(check(u, middle)) left = middle + 1; 80 else right = middle; 81 } 82 return left; 83 } 84} 85 86unordered_set<int> vec[maxn]; 87 88struct NODE{ 89 int x, y; 90 NODE(int _x, int _y){ 91 x = min(_x, _y); 92 y = max(_x, _y); 93 } 94 bool operator <(const NODE &b)const{ 95 if(x != b.x) return x < b.x; 96 else return y < b.y; 97 } 98}; 99set<NODE> EDGE; 100 101int main(){ 102// Fastin; 103 int t; scanf("%d", &t); while(t--){ 104 clr(head, -1); top = 0; clr(du, 0); clr(zero, 0); bitcnt = 0; 105 106 n = read(); m = read(); 107 108 for(int i = 1; i <= n; i++) mp[i].clear(); conv.clear(); 109 110 K = sqrt(m); 111 for(int i = 1; i <= n; i++){ 112 w[i] = read(); vec[i].clear(); 113 } 114 115 EDGE.clear(); 116 for(int i = 0; i < m; i++){ 117 int u, v; u = read(); v = read(); 118 EDGE.insert(NODE(u, v)); 119 } 120 for(auto edge: EDGE){ 121 if(edge.x != edge.y){ 122 add(edge.x, edge.y); add(edge.y, edge.x); 123 du[edge.x]++; du[edge.y]++; 124 } 125 else{ 126 add(edge.x, edge.y); 127 du[edge.x]++; 128 } 129 } 130 //只有O(sqrt(m))个点的度>= K = sqrt(m) 131 for(int i = 1; i <= n; i++) if(du[i] >= K){ 132 memset(c[bitcnt], 0, sizeof (c[bitcnt])); 133 conv[i] = bitcnt++; 134 for(int j = head[i]; ~j; j = edge[j].next){ 135 int to = edge[j].to; vec[to].insert(i); 136 update(i, w[to], 1); 137 } 138 } 139 140 int q; scanf("%d", &q); while(q--){ 141 itn op, x, y; scanf("%d", &op); 142 if(op == 1){ 143 x = read(); y = read(); 144 //w[x] := y; 145 //v是所有的相邻大度点 146 for(auto v: vec[x]){ 147 update(v, w[x], -1); 148 update(v, y, 1); 149 } 150 w[x] = y; 151 } 152 else{ 153 x = read(); 154 printf("%d\n", mex(x)); 155 } 156 } 157 } 158 return 0; 159} 160
ACM
网络流
666字
两个定理的证明
https://www.cnblogs.com/cniwoq/p/9245813.html
spfa的一些说明
https://blog.csdn.net/xiazdong/article/details/8193680
dinic
cpp 1const itn maxn = 1200 + 10; 2const int maxe = 120000 + 10; 3const ll inf = 1ll << 60; 4 5struct star{int to, next, w;}; 6int head[maxn], top = 0; 7star edge[maxe << 1]; 8 9void add(int u, int v, int w){ 10 edge[top].to = v; 11 edge[top].next = head[u]; 12 edge[top].w = w; 13 head[u] = top++; 14} 15 16int d[maxn], cur[maxn]; 17 18ll dfs(int s, int t, ll flow){ 19 if(flow == 0 || s == t) return flow; 20 21 ll res = 0, f; 22 for(int i = cur[s]; ~i; i = edge[i].next){ 23 cur[s] = i; 24 if(d[edge[i].to] == d[s] + 1){ 25 f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w)); 26 edge[i].w -= f; edge[i ^ 1].w += f; res += f; flow -= f; 27 if(flow == 0) break; 28 } 29 } 30 return res; 31} 32 33queue<int> q, q0; 34bool bfs(int s, int t){ 35 clr(d, 0); 36 q = q0; q.push(s); 37 cur[s] = head[s]; d[s] = 1; 38 while(!q.empty()){ 39 int now = q.front(); q.pop(); 40 for(int i = head[now]; ~i; i = edge[i].next) if(!d[edge[i].to] && edge[i].w > 0){ 41 cur[edge[i].to] = head[edge[i].to]; d[edge[i].to] = d[now] + 1; 42 if(edge[i].to == t) return true; 43 q.push(edge[i].to); 44 } 45 } 46 return false; 47} 48 49ll dinic(int s, int t){ 50 ll ans = 0; 51 while(bfs(s, t)) ans += dfs(s, t, inf); 52 return ans; 53} 54 55 56 57int main(){ 58// Fastin; 59 clr(head, -1); 60 int n, m, s, t; scanf("%d %d %d %d", &n, &m, &s, &t); 61 for(int i = 0, u, v, w; i < m; i++){ 62 scanf("%d %d %d", &u, &v, &w); 63 add(u, v, w); add(v, u, 0); 64 } 65 printf("%lld\n", dinic(s, t)); 66 return 0; 67} isap
...
ACM
157字
ACM
计算几何
2111字
H
二分答案然后跑圆的k次交即可。
因为学习完k次交后精疲力竭就不写完整这道题了。
贴一下用自己的码风写的板子。已更新入模版中。
给出n个圆的平面坐标和半径，能够获得所有圆k次交的面积。
cpp 1const int manx = 1e2 + 10; 2const double eps = 1e-8; 3const double pi = acos(-1); 4 5inline int sgn(double x){return x < -eps? -1: x > eps? 1: 0;} 6inline double sqr(double x){return x * x;} 7 8struct CIRCLE{ 9 double x, y, r, angle; 10 int d; 11 CIRCLE(){d = 1; angle = 0;} 12 CIRCLE(double _x, double _y, double _angle = 0, int _d = 0){ 13 x = _x; y = _y; angle = _angle; d = _d; r = 0; 14 } 15 bool operator < (const CIRCLE &b)const{ 16 return sgn(r - b.r) == -1; 17 } 18}; 19 20inline double dis(CIRCLE a, CIRCLE b){return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} 21inline double cross(CIRCLE a, CIRCLE b, CIRCLE c){ 22 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); 23} 24 25//有两个交点返回true，以及两个交点的坐标和方位角，p1按照顺时针，p2按照逆时针 26bool cir_inter_cir(CIRCLE a, CIRCLE b, CIRCLE &p1, CIRCLE &p2){ 27 double d = dis(a, b); 28 if(sgn(d - a.r - b.r) >= 0 || sgn(abs(b.r - a.r) - d) >= 0) return false; 29 double cosa = (sqr(a.r) + sqr(d) - sqr(b.r)) / (2 * a.r * d); 30 double sina = sqrt(max(0., 1. - sqr(cosa))); 31 //旋转矩阵 [cosa, -sina; sina, cosa] 32 p1 = p2 = a; 33 p1.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * -sina); 34 p1.y += a.r / d * ((b.x - a.x) * sina + (b.y - a.y) * cosa); 35 p2.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * sina); 36 p2.y += a.r / d * ((b.x - a.x) * -sina + (b.y - a.y) * cosa); 37 return true; 38} 39 40bool cmp(const CIRCLE &a, const CIRCLE &b){ 41 if(sgn(a.angle - b.angle)) return sgn(a.angle - b.angle) == -1; 42 else return a.d > b.d; 43} 44 45double cal(CIRCLE a, CIRCLE p1, CIRCLE p2){ 46 double ans = sqr(a.r) * (p2.angle - p1.angle) - cross(a, p1, p2) + cross(CIRCLE(0, 0), p1, p2); 47 return ans / 2; 48} 49 50CIRCLE dot[maxn << 1]; 51double area[maxn]; 52void cirunion(CIRCLE cir[], int n){ 53 sort(cir, cir + n); 54 //记录每个圆被完全覆盖的次数，初始值显然为1 55 for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) 56 if(sgn(dis(cir[i], cir[j]) + cir[i].r - cir[j].r) <= 0) cir[i].d++; 57 CIRCLE p1, p2; 58 for(int i = 0; i < n; i++){ 59 //针对每一个圆考虑它与所有其他圆的交 60 int cnt = 0, top = 0; 61 for(int j = 0; j < n; j++){ 62 if(i == j) continue; 63 if(!cir_inter_cir(cir[i], cir[j], p1, p2)) continue; 64 p1.angle = atan2(p1.y - cir[i].y, p1.x - cir[i].x); 65 p2.angle = atan2(p2.y - cir[i].y, p2.x - cir[i].x); 66 p1.d = -1; p2.d = 1; 67 dot[top++] = p1; dot[top++] = p2; 68 if(sgn(p2.angle - p1.angle) == 1) cnt++; 69 } 70 71 //加入起点终点位置 72 dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, -pi, -2); 73 dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, pi, 2); 74 sort(dot, dot + top, cmp); 75 int now = cir[i].d + cnt; 76 for(int j = 1; j < top; j++){ 77 area[now] += cal(cir[i], dot[j - 1], dot[j]); 78 now += dot[j].d; 79 } 80 } 81} 82 83CIRCLE cir[maxn]; 84int main(){ 85// Fastin; 86 int t; scanf("%d", &t); while(t--){ 87 clr(area, 0); 88 int n; scanf("%d", &n); 89 for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &cir[i].x, &cir[i].y, &cir[i].r); 90 cirunion(cir, n); 91 for(int i = 1; i <= n; i++) printf("%.5f\n", area[i]); 92 } 93 return 0; 94} 因为网上基本没有讲解只有代码..oi-wiki甚至好像都没有收录这个算法，所以我学了好久才…
...
参考说明：
added saltyfish/2016 ACM/ICPC Asia Regional Qingdao Onsite.page
Fibnacci
D 概率 cpp 1double qp(double a, int p){ 2 double ans = 1; 3 while(p){ 4 if(p & 1) ans *= a; 5 a *= a; p >>= 1; 6 } 7 return ans; 8} 9 10int n; 11int num[20]; 12double p[20], ans[20]; 13 14//除了x硬币其余硬币活不到第k轮的概率 15double sove(int x, int k){ 16 double ans = 1; 17 for(int i = 0; i < n; i++){ 18 if(i == x) continue; 19 ans *= qp((1 - qp(p[i], k)), num[i]); 20 } 21 return ans; 22} 23 24int main(){ 25// Fastin; 26 int t; scanf("%d", &t); while(t--){ 27 scanf("%d", &n); 28 fro(int i = 0; i < n; i++){ 29 scanf("%d %lf", num + i, p + i); 30 ans[i] = 0; 31 } 32 if(n == 1) printf("1.000000\n"); 33 else{ 34 //实验100轮 35 for(int i = 1; i <= 100; i++) for(int x = 0; x < n; x++){ 36 ans[x] += (sove(x, i) - sove(x, i - 1)) * (1 - qp((1 - qp(p[x], i)), num[x])); 37 } 38 for(int i = 0; i < n; i++){ 39 printf("%.6f", ans[i]); 40 if(i != n - 1) printf(" "); 41 else printf("\n"); 42 } 43 } 44 } 45 return 0; 46} 考虑所有三元组，图是若干个团之并的充要条件是不存在某个三元组中有两条边（实际上就是要满足传递性），于是任取一个有两条边的三元组，枚举加上剩下的边或者删除现有两条边之一，修改一条边之后会有$O(n)$个三元组受影响，暴力修改这些三元组，同时用一个队列+时间戳维护当前有两条边的三元组，搜$10$步即可，复杂度是$O(n^3+n3^{10})$
...
ACM
树上二分
1860字
ACM
模拟
528字