「CF1242X」Codeforces Round #599 (Div. 1)
A. Tile Painting
对 n 做因式分解，如果 n 有超过一个质因数 t，则答案是 1，否则答案是 t。
因为两个质因数求 gcd 以后是 1，则 ax + by 可以把所有格子染上。
|
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 |
#include<map> #include<set> #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; } ll n, t = -1; int main() { n = read(); if(n == 1) { cout << 1 << endl; return 0; } ll ans = n; for(int i = 2; i <= 1000000; i++) if(n % i == 0) { while(n % i == 0) n /= i; t = i; break; } if(n != 1) { if(t == -1) cout << n << endl; else cout << 1 << endl; } else cout << t << endl; return 0; } |
B. 0-1 MST
求补图的联通块个数，BZOJ 1098 原题。
维护一个 1 – n 的链表，表示有哪些点还没确定所在连通块。
从 1 – n 枚举点 x，用 bfs 把与 x 同一连通块的点找出来，每次 bfs 只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点的连通块确定，则复杂度不超过 n + m。
|
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<set> #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,m,ans,cnt; struct edge{int to,nxt;}e[200005]; int q[100005]; int pre[100005],nxt[100005],last[100005]; int belong[100005]; bool vis[100005],t[100005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].nxt=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].nxt=last[v];last[v]=cnt; } void del(int x) { int t=pre[x]; nxt[t]=nxt[x]; pre[nxt[x]]=t; } void bfs(int x) { int head=0,tail=1; q[0]=x; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].nxt)t[e[i].to]=1; for(int i=nxt[0];i<=n;i=nxt[i]) if(!t[i]) del(i),q[tail++]=i; for(int i=last[now];i;i=e[i].nxt)t[e[i].to]=0; } } int main() { n=read();m=read(); for(int i=0;i<=n;i++)nxt[i]=i+1; for(int i=1;i<=n+1;i++)pre[i]=i-1; for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=nxt[0];i<=n;i=nxt[0]) del(i),ans++,bfs(i); printf("%d\n",ans - 1); return 0; } |
C. Sum Balance
所有数字互不相同这一性质，保证每个数字都确定了一个所在的箱子。
如果我们从第一个箱子里拿出一个数，为了达到目标总和，需要补一个差值，把它从某个箱子里拿过来，接着就要考虑被拿出数的箱子，这样会形成一个置换的环。
即拿出某个数字，会推导出一个一些箱子的环。现在的问题是，能不能选若干个环，使得某个箱子恰好在一个环上。
考虑 n <= 15，第二步就用状压 dp 来解决，预处理是 O(n * k^2) 的，枚举子集 O(3^k)
|
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#include<map> #include<set> #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 k; int n[5005], a[20][5005]; ll sum[20], S, tmp[20]; bool f[100005], g[100005]; int ansc[100005][20], ansp[100005][20]; int c[20], p[20]; int first; bool mark[20], flag; map<int, int> mp; int pre[100005]; void dfs(int x) { int m = S - tmp[x]; int t = mp[m]; c[t] = m; p[t] = x; if(m == first) { flag = 1; mark[t] = 1; return; } if(!t || mark[t])return; mark[t] = 1; tmp[t] -= m; dfs(t); } int main() { k = read(); for(int i = 1; i <= k; i++) { n[i] = read(); for(int j = 1; j <= n[i]; j++) { a[i][j] = read(); sum[i] += a[i][j]; mp[a[i][j]] = i; } S += sum[i]; } S /= k; g[0] = 1; for(int i = 1; i <= k; i++) for(int j = 1; j <= n[i]; j++) { for(int p = 1; p <= k; p++) tmp[p] = sum[p]; memset(mark, 0, sizeof(mark)); memset(p, 0, sizeof(p)); memset(c, 0, sizeof(c)); flag = 0; first = a[i][j]; tmp[i] -= a[i][j]; dfs(i); if(!flag)continue; int st = 0; for(int l = 1; l <= k; l++) if(mark[l])st += (1 << (l - 1)); for(int l = 1; l <= k; l++) ansc[st][l] = c[l], ansp[st][l] = p[l]; f[st] = 1; } for(int i = 1; i < (1 << k); i++) for(int x = i; x; x = (x - 1) & i) { if(f[x] && g[i - x]) { g[i] = 1; pre[i] = i - x; break; } } if(!g[(1 << k) - 1]) { puts("No"); return 0; } else { memset(c, 0, sizeof(c)); memset(p ,0, sizeof(p)); puts("Yes"); int now = (1 << k) - 1; while(now) { int t = now - pre[now]; for(int i = 1; i <= k; i++) if(ansp[t][i]) p[i] = ansp[t][i], c[i] = ansc[t][i]; now = pre[now]; } for(int i = 1; i <= k; i++) cout << c[i] <<' '<<p[i] << endl; } return 0; } |
Subscribe
计数器 9321087
OI 课件=>
OI 课件=>