「CF1229X」Codeforces Round #588
A. Marcin and Training Camp
若A觉得自己没有B强，B向A连边
度数为 0 的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<%map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, cnt, top; int q[7005], d[7005]; ll a[7005], b[7005], ans; vector<int> v[7005]; bool check(ll x, ll y) { ll t = (x & y); return y == t; } int main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= n; i++) b[i] = read(), ans += b[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j && check(a[j], a[i])) { v[j].push_back(i); d[i]++; } for(int i = 1; i <= n; i++) if(!d[i]) { q[++top] = i; cnt++; ans -= b[i]; } while(top) { int x = q[top]; top--; for(int i = 0; i < v[x].size(); i++) { int y = v[x][i]; d[y]--; if(d[y] == 0) { q[++top] = y; cnt++; ans -= b[y]; } } } if(cnt == n - 1) puts("0"); else cout << ans << endl; return 0; } |
B. Kamil and Making a Stream
从一个点向上走，区间 gcd 单调下降，且最多变化 log 次
可以用树上倍增维护区间 gcd，枚举每个点往上二分跳，暴力统计答案
更简单的做法是用 vector 维护一个点往上的不同 gcd，以及它们贡献答案的次数，这个 vector 大小是 log
dfs 暴力往儿子转移
倍增：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int fa[100005][17], dep[100005]; ll g[100005][17]; vector<int> v[100005]; ll gcd(ll a, ll b) { return b == 0? a: gcd(b, a % b); } void dfs(int x) { for(int i = 0; i < v[x].size(); i++) { int y = v[x][i]; if(y == fa[x][0])continue; fa[y][0] = x; dep[y] = dep[x] + 1; dfs(y); } } int main() { n = read(); for(int i = 1; i <= n; i++) g[i][0] = read(); for(int i = 1; i < n; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dep[1] = 1; dfs(1); for(int i = 1; i <= 16; i++) for(int j = 1; j <= n; j++) { int tmp = fa[j][i - 1]; fa[j][i] = fa[tmp][i - 1]; g[j][i] = gcd(g[j][i - 1], g[tmp][i - 1]); } ll ans = 0; for(int x = 1; x <= n; x++) { ll tmp = g[x][0], D = dep[x]; int tx = x; while(tmp != 1 && D != 1) { for(int i = 16; i >= 0; i--) if(fa[tx][i] != 0 && gcd(tmp, g[tx][i]) == tmp) { tx = fa[tx][i]; D -= (1 << i); ans = (ans + (1 << i) * tmp) % mod; } tmp = gcd(g[tx][0], tmp); } ans = (ans + (tmp * D) % mod) % mod; } cout << ans << endl; return 0; } |
dfs：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<ll, ll> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll v[100005], ans; vector<int> e[100005]; vector<pa> st[100005]; ll gcd(ll a, ll b) { return b == 0? a: gcd(b, a % b); } void dfs(int x, int fa) { for(int i = 0; i < st[fa].size(); i++) { ll t = gcd(st[fa][i].first, v[x]), tmp = st[fa][i].second; if(st[x].size() && st[x].back().first == t) st[x].back().second += tmp; else st[x].push_back(make_pair(t, tmp)); } if(st[x].size() && st[x].back().first == v[x]) st[x].back().second++; else st[x].push_back(make_pair(v[x], 1)); for(int i = 0; i < st[x].size(); i++) ans += st[x][i].first % mod * st[x][i].second % mod; ans %= mod; for(int i = 0; i < e[x].size(); i++) { int y = e[x][i]; if(y == fa)continue; dfs(y, x); } } int main() { n = read(); for(int i = 1; i <= n; i++) v[i] = read(); for(int i = 1; i < n; i++) { int x = read(), y = read(); e[x].push_back(y); e[y].push_back(x); } dfs(1, 0); cout << ans << endl; return 0; } |
C. Konrad and Company Evaluation
给无向图定向，权值小的连向权值大的，答案是每个点的入度乘以出度求和 每次修改其实是把一个点的所有出边改成入边，暴力修改感觉卡不掉 实际上用势能分析可以证明复杂度 n√n
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<ll, ll> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, q; int d[100005], v[100005]; ll big[100005], small[100005]; vector<int> e[100005], ne[100005]; int mark[100005]; int main() { n = read(); m = read(); for(int i = 1; i <= n; i++) v[i] = i; for(int i = 1; i <= m; i++) { int u = read(), v = read(); e[u].push_back(v); e[v].push_back(u); d[u]++; d[v]++; if(u > v) big[v]++, small[u]++; else big[u]++, small[v]++; } ll ans = 0; for(int i = 1; i <= n; i++) ans += big[i] * small[i]; for(int i = 1; i <= n; i++) { for(int j = 0; j < e[i].size(); j++) { int y = e[i][j]; if(v[y] > v[i]) ne[i].push_back(y); } e[i] = vector<int>(); } cout << ans << endl; q = read(); for(int i = 1; i <= q; i++) { int x = read(); ans = ans - big[x] * small[x]; small[x] = d[x]; big[x] = 0; for(int j = 0; j < ne[x].size(); j++) { int y = ne[x][j]; if(v[y] > v[x]) { ans = ans - big[y] * small[y]; big[y]++; small[y]--; ans = ans + big[y] * small[y]; } ne[y].push_back(x); } v[x] = n + i; ne[x] = vector<int>(); cout << ans << endl; } return 0; } |
Subscribe
计数器 9320699
OI 课件=>
OI 课件=>