程序设计实习实验班2017推荐习题
区间众数问题
这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x7fffffff #define ll long long #define pa pair<int,int> 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,blo=200; int nl,nr; int v[50005],bl[50005],st[50005],ans[50005],cnt[50005]; struct query{ int l,r,id; }q[50005]; struct data{ int cnt,v; }ANS; bool operator<(data a, data b) { if(a.cnt != b.cnt)return a.cnt < b.cnt; else return a.v > b.v; } priority_queue<data,vector<data> >heap[50005]; bool operator<(query a,query b) { if(bl[a.l]!=bl[b.l])return bl[a.l]<bl[b.l]; if(bl[a.l]&1)return a.r<b.r; else return a.r>b.r; } void add(int x) { cnt[v[x]]++; ANS.cnt=cnt[ANS.v]; int tmp=cnt[v[x]]; auto d=(data){tmp,v[x]}; heap[tmp].push(d); if(ANS<d)ANS=d; } void del(int x) { cnt[v[x]]--; ANS.cnt=cnt[ANS.v]; heap[cnt[v[x]]].push((data){cnt[v[x]],v[x]}); for(int k=0;k<2;k++) { int tmp=cnt[v[x]]+k; while(heap[tmp].size()) { auto top=heap[tmp].top(); if(top.cnt!=cnt[top.v])heap[tmp].pop(); else { if(ANS<top)ANS=top; break; } } } } void query(int l,int r) { while(nr<r) { nr++; add(nr); } while(nl>l) { nl--; add(nl); } while(nr>r) { del(nr); nr--; } while(nl<l) { del(nl); nl++; } } int main() { n=read(); nl=1;nr=0; for(int i=1;i<=n;i++) v[i]=st[i]=read(); sort(st+1,st+n+1); for(int i=1;i<=n;i++) v[i]=lower_bound(st+1,st+n+1,v[i])-st; for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1; for(int i=1;i<=n;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+n+1); for(int i=1;i<=n;i++) { query(q[i].l,q[i].r); ans[q[i].id]=st[ANS.v]; } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } |
「BZOJ3659」Which Dreamed It 神奇钥匙
求以1为起点的欧拉回路的个数乘1的度数
BEST theorem
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 1000003 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 a[105][105]; int deg[105]; ll fac[mod + 1]; int gauss(int n) { if(n < 0)return 0; ll det = 1; int flag = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = (a[i][j] % mod + mod) % mod; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) while(a[j][i]) { ll tmp = a[i][i] / a[j][i]; for(int k = i; k <= n; k++) a[i][k] = ((a[i][k] - a[j][k] * tmp) % mod + mod) % mod; swap(a[i], a[j]); flag = -flag; } if(!a[i][i])return 0; det = det * a[i][i] % mod; } if(flag == -1)return mod - det; return det; } int main() { fac[0] = 1; for(int i = 1; i <= mod; i++) fac[i] = fac[i - 1] * i % mod; while(1) { memset(a, 0, sizeof(a)); memset(deg, 0, sizeof(deg)); n = read(); if(!n)break; for(int i = 1; i <= n; i++) { deg[i] = read(); for(int j = 1; j <= deg[i]; j++) { int x = read(); a[i][x]++; } } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i == j)a[i][j] = deg[i] - a[i][j]; else a[i][j] = -a[i][j]; if(n == 1 && !deg[1])puts("1"); else { ll ans = 1; for(int i = 1; i <= n; i++) ans = ans * fac[deg[i] - 1] % mod; ans = ans * gauss(n - 1) % mod; ans = ans * deg[1] % mod; cout << ans << endl; } } return 0; } |
「bzoj4031」[HEOI2015]小Z的房间
矩阵树定理
推荐阅读 算
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 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; } ll a[105][105]; int n, m, id[15][15]; char ch[15][15]; int xx[4] = {1, -1, 0, 0}, yy[4] = {0, 0, 1, -1}; int gauss(int n) { if(n < 0)return 0; ll det = 1; int flag = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = (a[i][j] % mod + mod) % mod; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) while(a[j][i]) { ll tmp = a[i][i] / a[j][i]; for(int k = i; k <= n; k++) a[i][k] = ((a[i][k] - a[j][k] * tmp) % mod + mod) % mod; swap(a[i], a[j]); flag = -flag; } if(!a[i][i])return 0; det = det * a[i][i] % mod; } if(flag == -1)return mod - det; return det; } int main() { while(1) { memset(a, 0, sizeof(a)); n = read(); m = read(); if(n == 0)break; for(int i = 1; i <= n; i++) scanf("%s", ch[i] + 1); int tmp = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(ch[i][j] != '*') id[i][j] = ++tmp; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(ch[i][j] != '*') for(int k = 0; k < 4; k++) { int x = i + xx[k], y = j + yy[k]; int u = id[i][j], v = id[x][y]; if(x > 0 && y > 0 && x <= n && y <= m && ch[x][y] != '*') a[u][v]--, a[u][u]++; } cout << gauss(tmp - 1) << endl; } return 0; } |
POJ2373 Dividing the Path
用 dp(i) 表示覆盖到 i 的最小喷水装置数，单调队列优化 dp
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 1000003 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, l; int A, B; int dp[1000005]; bool mark[1000005]; struct data{ int x, y; friend bool operator<(data a, data b){ if(a.x == b.x)return a.y < b.y; return a.x < b.x; } }a[1005]; deque<int>q; int main() { n = read(); l = read(); A = read(); B = read(); for(int i = 1; i <= n; i++) a[i].x = read() + 1, a[i].y = read() - 1; sort(a + 1, a + n + 1); int now = 0; for(int i = 1; i <= n; i++) { now = max(now, a[i].x); while(now <= a[i].y) { mark[now] = 1; now++; } } dp[0] = 0; for(int i = 1; i <= l; i++) { if(i >= 2 * A) { while(q.size() && dp[q.back()] > dp[i - 2 * A]) q.pop_back(); q.push_back(i - 2 * A); } while(q.size() && i - q.front() > 2 * B)q.pop_front(); if(mark[i] || (i & 1))dp[i] = inf; else { if(q.size()) { int x = q.front(); dp[i] = dp[x] + 1; } else dp[i] = inf; } } if(dp[l] >= inf)puts("-1"); else cout << dp[l] << endl; return 0; } |
Squares
预处理每个点向右和向下延伸的线段长度，枚举每个正方形左上角的点和边长
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 1000003 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; int D[1505][1505], R[1505][1505]; int main() { while(scanf("%d%d", &n, &m) != EOF) { memset(D, 0, sizeof(D)); memset(R, 0, sizeof(R)); char opt[2]; while(m--) { scanf("%s", opt); int x = read(), y = read(), k = read(); if(opt[0] == 'H') { R[x][y] = k; } else D[x][y] = k; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { D[i][j] = max(D[i][j], D[i - 1][j] - 1); R[i][j] = max(R[i][j], R[i][j - 1] - 1); } int ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= min(D[i][j], R[i][j]); k++) if(R[i + k][j] >= k && D[i][j + k] >= k) ans++; cout << ans << endl; } return 0; } |
CF449D Jzzhu and Numbers
膜zmx（洵老师233）：
直接做不好做，考虑容斥，求出f[s]表示选出若干个数字and起来之后对应于s二进制表示中为1的那些位置必须是1的方案。
考虑and的FWT的过程。
当前只考虑选出1个数字的话，令g[s]表示给定的数中s出现次数。
tf (g ) = (tf (g 0 + g 1), tf (g 1))
事实上就是处理了最高位的情况!这样继续分治下去做就可以弄出只选出1个数字时的f[s]。
考虑取若干个的情况，那么f[s]对应的可选集合{x1, x2, · · · , xf [s]}中的数任选，最后and出来都能保证对应于s的那些位置仍然为1。
令ans[s] = 2^f[s]，这里的ans[s]即为选若干个数使得它们and起来对应s的位置必须是1的方案数。
考虑FWT的“意义”。
g[s]表示了and起来恰好是s的方案数，那么做了一次FWT之后求得
了and起来至少是s的方案数tf (g)。 那么IFWT的意义就和FWT相反。
ans[s]表示and起来至少是s的方案数，那么做了一次IFWT之后求得 了and起来恰好是s的方案数utf (ans)。
所求答案就是utf (ans)[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 73 74 75 76 77 78 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long #define pa pair<int,int> 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 T; int n, m, L; ll A[1048576]; ll qpow(ll a, ll b) { ll ans = 1; for(ll i = b; i; i >>= 1, a = a * a % mod) if(i & 1)ans = ans * a % mod; return ans; } void fwtand(ll *A, int n) { if(n == 1)return; int h = n >> 1; fwtand(A, h); fwtand(A + h, h); for(int i = 0; i < h; i++) { ll u = A[i], v = A[i + h]; A[i] = (u + v) % mod; A[i + h] = v % mod; } } void ifwtand(ll *A, int n) { if(n == 1)return; int h = n >> 1; for(int i = 0; i < h; i++) { ll u = A[i], v = A[i + h]; A[i] = (u - v) % mod; A[i + h] = v % mod % mod; } ifwtand(A, h); ifwtand(A + h, h); } int main() { T = read(); while(T--) { memset(A, 0, sizeof(A)); n = read(); for(int i = 1; i <= n; i++) { int x = read(); A[x]++; } for(L = 1; L <= 1000000; L <<= 1); fwtand(A, L); for(int i = 0; i < L; i++)A[i] = qpow(2, A[i]); ifwtand(A, L); cout << A[0] << endl; } return 0; } |
SRM518 NIM
FWT xor 卷积
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long #define pa pair<int,int> 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 T; int n, m, L; ll ine; bool mark[50005]; ll A[65536]; ll qpow(ll a, ll b) { ll ans = 1; for(ll i = b; i; i >>= 1, a = a * a % mod) if(i & 1)ans = ans * a % mod; return ans; } void fwt(ll *A, int n) { if(n == 1)return; int h = n >> 1; fwt(A, h); fwt(A + h, h); for(int i = 0; i < h; i++) { ll u = A[i], v = A[i + h]; A[i] = (u + v) % mod; A[i + h] = (u - v + mod) % mod; } } void ifwt(ll *A, int n) { if(n == 1)return; int h = n >> 1; for(int i = 0; i < h; i++) { ll u = A[i], v = A[i + h]; A[i] = (u + v) * ine % mod; A[i + h] = ((u - v + mod) % mod) * ine % mod; } ifwt(A, h); ifwt(A + h, h); } int main() { mark[1] = 1; for(int i = 2; i <= 50000; i++) if(!mark[i]) for(int j = i + i; j <= 50000; j += i) mark[j] = 1; T = read(); ine = qpow(2, mod - 2); while(T--) { memset(A, 0, sizeof(A)); n = read(); m = read(); for(L = 1; L <= m; L <<= 1); for(int i = 1; i <= m; i++) if(!mark[i])A[i] = 1; fwt(A, L); for(int i = 0; i < L; i++)A[i] = qpow(A[i], n); ifwt(A, L); cout << A[0] << endl; } return 0; } |
黄学长怎么区间众数强行多个log啊 不太行吧