整理的算法模板合集: ACM模板
点我看算法全家桶系列!!!
实际上是一个全新的精炼模板整合计划
VP了一下,体验不是太好
比赛地址:
https://ac.nowcoder.com/acm/contest/15600
%VP地址(密码 swpuacm):
%[https://ac.nowcoder.com/acm/contest/16646#description]https://ac.nowcoder.com/acm/contest/16646#description)
Problem
给定一个 n n n 个点的无向完全图, i i i 和 j j j 之前的边权是 gcd ( a i , a j ) \gcd(a_i,a_j) gcd(ai,aj) ,保证数组 a 随机,求 MST。
Solution
边权为 gcd ( a i , a j ) \gcd(a_i, a_j) gcd(ai,aj),显然如果存在一个点 a x a_x ax 是素数,则从该点向所有的点连边,这样连接的 n − 1 n-1 n−1条边的权值都是1,答案就是 n − 1 n-1 n−1 。
若 L = R L=R L=R,则 R + L + 1 = 1 R+L+1=1 R+L+1=1,模1之后得到的显然都是0,也就是说 n 2 n^2 n2 条边的权值都是 L L L,答案显然就是 L × ( n − 1 ) L\times (n-1) L×(n−1)。
然后因为 n n n 比较大, n ≤ 1 0 5 n\le 10^5 n≤105,所以我们考虑分情况讨论。
若 n n n 比较小,可以直接暴力 O ( n 2 ) O(n^2) O(n2) 连边然后求最小生成树即可。
若 n n n 较大,若 R − L + 1 R-L+1 R−L+1 较大,则根据素数分布,int范围内的素数间距大概就是几百左右,这样 L ∼ L + ( R − L + 1 ) L\sim L+(R-L+1) L∼L+(R−L+1) 中一定会有素数,也就是说一定会出现一个 a i is prime a_i\ \text{is\ prime} ai is prime,答案显然就是上面讨论的 n − 1 n-1 n−1。
若 n n n 较大, R − L + 1 R-L+1 R−L+1 较小,出题人可以找一个没有素数的区间 [ L , R ] [L,R] [L,R],那么答案还是 n − 1 n-1 n−1 吗?显然仍然是,因为 n n n 较大, R − L + 1 R-L+1 R−L+1 较小说明 a 1 ∼ a n a_1\sim a_n a1∼an 一定会把 [ L , R ] [L,R] [L,R] 给取满了,也就是 a i a_i ai 是一堆连续的数,而相邻两个数互质,所以答案一定还是 n − 1 n-1 n−1。
Code
#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; const int maxn = 2e5+5; bool prime[maxn]; int n,L,R,a[maxn]; ull seed; void getprime() { memset(prime,1,sizeof(prime)); prime[1] = 1; for(int i = 2;i <= 200000;++i){ if(prime[i]){ for(int j = i+i;j <= 200000;j += i)prime[j] = 0; } } } ull xorshift64() { ull x = seed; x ^= x<<13; x ^= x>>7; x ^= x<<17; return seed=x; } int gen() { return xorshift64()%(R-L+1)+L; } struct Edge { int x,y,cost; }; void solve1() { vector<Edge>edge; for(int i = 1;i <= n;++i){ for(int j = i+1;j <= n;++j){ edge.push_back({i,j,__gcd(a[i],a[j])}); } } vector<int> pre(n+1); for(int i = 1;i <= n;++i)pre[i] = i; sort(edge.begin(),edge.end(),[](const Edge&a,const Edge&b)->bool{ return a.cost<b.cost; }); function<int(int)> Find = [&](int x)->int{ return pre[x]==x?x:pre[x] = Find(pre[x]); }; int ans = 0; for(auto &x:edge){ int fx = Find(x.x); int fy = Find(x.y); if(fx!=fy){ pre[fx] = fy; ans += x.cost; } } printf("%d\n",ans); } int main() { getprime(); scanf("%d%d%d%llu",&n,&L,&R,&seed); for(int i = 1;i <= n;++i){ a[i] = gen(); } for(int i = 1;i <= n;++i){ if(prime[a[i]]){ printf("%d\n",n-1); return 0; } } if(n <= 3000){ solve1(); } else if(L!=R){ printf("%d\n",n-1); } else printf("%lld\n",1ll*R*(n-1)); }
Problem
给定一棵树,黑白染色方案,满足一个黑点的子树都是黑点,白点任意。
你现在构造一棵树,使得它的染色方案数为
K
K
K。
Solution
给定方案数让我们构造出一颗满足条件的树,我们先考虑对于一颗树,我们如何计算它的方案数。
我们设 f ( u ) f(u) f(u) 表示染色 u u u 以及 u u u 的所有子树的方案数,显然对于 u u u 的所有子节点 v v v,其中若将 u 染成黑色结点,则方案数为1(儿子全都是黑色结点),若将 u 染成 白色,则方案数为 ∏ f ( v ) \prod f(v) ∏f(v),即: f ( u ) = ∏ ( f ( v ) + 1 ) + 1 f(u)=\prod (f(v)+1)+1 f(u)=∏(f(v)+1)+1。
这里要求构造一棵染色方案数等于 k k k 的树。
对于 k k k:
若 k k k 是奇数,显然我们可以为 k k k 分配一个左右儿子 l , r l,r l,r ,我们继续往右儿子的方向往下走,这样 f ( r ) = k − 1 2 f(r)=\cfrac{k-1}{2} f(r)=2k−1, f ( l ) = 2 , f ( u ) = f ( r ) × f ( l ) + 1 f(l)=2,f(u)=f(r)\times f(l)+1 f(l)=2,f(u)=f(r)×f(l)+1。
若 k k k 是偶数,我们可以直接给 u 连接一个子节点,然后到下一层,方案数就变成了 k − 1 k-1 k−1。
直接dfs即可。
Code
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 7; int n, m; int k; int cnt; int tot; int u[N], v[N]; void dfs(int p, int k) { if(k == 3) { u[ ++ tot] = p; v[tot] = p + 1; return ; } if(k < 3) return ; if(k & 1) { u[ ++ tot] = p; v[tot] = p + 1; u[ ++ tot] = p; v[tot] = p + 2; dfs(p + 2, k >> 1); } else { u[ ++ tot] = p; v[tot] = p + 1; dfs(p + 1, k - 1); } } signed main() { scanf("%lld", &k); if(k == 2) { printf("1"); return 0; } dfs(1, k); cout << tot + 1 << endl; for(int i = 1; i <= tot; ++ i) { printf("%lld %lld\n", u[i], v[i]); } return 0; }
Problem
二维空间里放了 n n n 个盒子,有水平往左和竖直往下两种重力,求重力作用之后形成的轮廓周长。
Solution
读完题直接模拟一下即可,一共8种情况,elif
即可。
Code
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int U[N],L[N]; int main() { int n; scanf("%d",&n); int a = 0, b = 0; for(int i = 0;i < n;++i){ int x,y; scanf("%d%d",&x,&y); x++; y++; int now = 4; int cnt = 0; if(U[x]) cnt++; U[x]++; if(U[x-1] >= U[x]) cnt++; if(U[x+1] >= U[x]) cnt++; a += now - cnt * 2; now = 4; cnt = 0; if(L[y]) cnt++; L[y]++; if(L[y-1] >= L[y]) cnt++; if(L[y+1] >= L[y]) cnt++; b += now - cnt * 2; printf("%d %d\n", a,b); } return 0; }
Problem
给定 n n n 个串,求有多少对串能拼出平方串(能够表示成两个相同的字符串连接在一起的,即 A A AA AA)。
Solution
Code
#include <bits/stdc++.h> using namespace std; const int mod[2] = {998244353,1000000007}; const int maxn = 4e5+5; const int sz = 233; using ll = long long; string a[maxn]; ll Hase[maxn][2]; ll fac[maxn][2]; map<pair<ll,ll>,int> mp; int main() { fac[0][0] = fac[0][1] = 1; for(int i = 1;i <= 400000;++i){ fac[i][0] = fac[i-1][0]*sz%mod[0]; fac[i][1] = fac[i-1][1]*sz%mod[1]; } ios::sync_with_stdio(false); int n; cin>>n; for(int i = 1;i <= n;++i){ cin>>a[i]; } sort(a+1,a+1+n,[](const string&a,const string &b)->bool{ return a.size()<b.size(); }); ll ans = 0; for(int i = 1;i <= n;++i){ ll val[2] = {0,0}; for(int j = 0;j < a[i].size();++j){ val[0] = val[0]*sz+a[i][j]; val[0] %= mod[0]; Hase[j+1][0] = val[0]; val[1] = val[1]*sz+a[i][j]; val[1] %= mod[1]; Hase[j+1][1] = val[1]; } ans += mp[make_pair(val[0],val[1])]; int len = a[i].size(); for(int j = 1;j <= len/2;++j){ ll hs1 = Hase[j][0]; ll hs2 = (Hase[len][0]-Hase[len-j][0]*fac[j][0]%mod[0]+mod[0])%mod[0]; ll hs3 = Hase[j][1]; ll hs4 = (Hase[len][1]-Hase[len-j][1]*fac[j][1]%mod[1]+mod[1])%mod[1]; if(hs1==hs2&&hs3==hs4){ ll hs5 = (Hase[len-j][0]-Hase[j][0]*fac[len-j-j][0]%mod[0]+mod[0])%mod[0]; ll hs6 = (Hase[len-j][1]-Hase[j][1]*fac[len-j-j][1]%mod[1]+mod[1])%mod[1]; ans += mp[make_pair(hs5,hs6)]; } } mp[make_pair(val[0],val[1])]++; } cout<<ans<<endl; return 0; }
输出 ∑ i = 1 n a i n \cfrac{\sum_{i=1}^{n}a_i}{n} n∑i=1nai,保留小数点后 位(直接截断后面的)。
Solution
模拟除法即可。
Code
#include <bits/stdc++.h> using namespace std; int main() { int n,m; scanf("%d%d",&n,&m); int p = n; int q = 0; for(int i = 0;i < n;++i){ int tmp; scanf("%d",&tmp); q += tmp; } string res; int gcd = __gcd(p,q); p/=gcd; q/=gcd; res+=to_string(q/p); q %= p; res.push_back('.'); for(int i = 0;i < m;++i){ q *= 10; res.push_back(q / p + '0'); q %= p; } cout << res << endl; return 0; }
Problem
Yuna 的生命值是 H H H ,体力值是 S S S,有 n n n 个任务,每个任务有生命值和体力值的花费。生命值不能降到 0 0 0 或 0 0 0 以下,体力值的多余消耗会算到生命值里。求最大任务收益。
Solution
二维费用背包即可。
Code
#include <bits/stdc++.h> using namespace std; using ll = long long; ll dp[305][305]; struct node { int h,s,w; }a[1005]; int main() { int n,h,s; scanf("%d%d%d",&n,&h,&s); for(int i = 1;i <= n;++i)scanf("%d%d%d",&a[i].h,&a[i].s,&a[i].w); for(int i = 1;i <= n;++i){ for(int j = h;j >= 0;--j){ for(int k = s;k >= 0;--k){ if(k >= a[i].s&&j > a[i].h){ dp[j][k] = max(dp[j][k],dp[j-a[i].h][k-a[i].s]+a[i].w); } else if(j > a[i].h&&j+k>a[i].s+a[i].h){ int res = a[i].s-k; dp[j][k] = max(dp[j][k],dp[j-a[i].h-res][0]+a[i].w); } } } } cout<<dp[h][s]<<endl; return 0; }
Problem
Piggy 是一个辅导班的老板,对于第 i i i 个客户,Piggy有两个选择:
每给一个学生安排一对一的家教,他就能赚钱。只有等级高的人才可以教等级低的人。其中, 1 1 1 是最高的等级。第 i i i 个客户有一个编号 R i R_i Ri,每个客户的等级都是不同的。
求得到的最大利润。
Solution
Code
Problem
数轴上 1 ∼ n 1\sim n 1∼n,每个点都有一个人站在整点上。有 m m m 个基站,每个基站 { x , p [ x ] } \{x,p[x]\} {x,p[x]},代表位置为 x x x ,每一个人连接该基站成功的概率为 p x p_x px。
每个人,都会按照由近及远,先左后右的顺序依次尝试连接基站,成功连接基站
i
i
i 的概率是
p
i
p_i
pi ,如果都
失败了,那么重新再来一遍。
每个基站的开销是连接人数的平方。求所有基站期望运行总代价。
Solution
显然考虑几何概型。
Time
O ( n ) O(n) O(n)
Code
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 7, mod = 998244353; int n, m; int a[N]; int pre[N], pre2[N], suf[N], suf2[N]; int F, ans; int p[N], now; int qpow(int a, int b) { int res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int inv(int x) { return qpow(x, mod - 2); } signed main() { F = 1; scanf("%lld%lld", &n, &m); for(int i = 1; i <= m; ++ i) { int x, pi; scanf("%lld%lld", &x, &pi); p[x] = pi; F = F * (1 - pi + mod) % mod; } if(n == 1) { puts("1"); return 0; } F = inv(1 - F + mod); pre[2] = (1 - p[1] + mod) % mod; pre2[2] = (1 - p[1] + mod) % mod * (1 - p[1] + mod) % mod; now = (1 - p[1] + mod) % mod; for(int i = 3; i <= n; ++ i) { int ansb = (1 - p[i - 1] + mod) % mod * (1 - p[i - 2] + mod) % mod;//先左再右,x在右边 now = now * (1 - p[i - 1] + mod) % mod; int ansa = pre[i - 2]; pre[i] = (ansb * ansa % mod + ansb + now) % mod; ansa = pre2[i - 2]; pre2[i] = (ansb * ansb % mod * ansa % mod + ansb * ansb % mod + now * now % mod) % mod; } suf[n - 1] = (1 - p[n] + mod) % mod; suf2[n - 1] = (1 - p[n] + mod) % mod * (1 - p[n] + mod) % mod; now = (1 - p[n] + mod) % mod; for(int i = n - 2; i >= 1; -- i) { int ansb = (1 - p[i + 1] + mod) % mod * (1 - p[i + 2] + mod) % mod; int tmp = (1 - p[i + 1] + mod) % mod;//先左再右,x在左边 now = now * (1 - p[i + 1] + mod) % mod; int ansa = suf[i + 2]; suf[i] = (ansb * ansa % mod + tmp + now) % mod; ansa = suf2[i + 2]; suf2[i] = (ansb * ansb % mod * ansa % mod + tmp * tmp % mod + now * now % mod) % mod; } for(int i = 1; i <= n; ++ i) { int A = (pre[i] + 1 + suf[i]) % mod * p[i] % mod * F % mod; int B = (pre2[i] + 1 + suf2[i]) % mod * p[i] % mod * p[i] % mod * F % mod * F % mod; ans = (ans + A * A % mod - B + A + mod) % mod; } printf("%lld\n", ans); return 0; }
Problem
给定
0
/
1
0/1
0/1 矩阵
C
C
C,构造两个矩阵
A
,
B
A,B
A,B,其中
A
,
B
A,B
A,B 矩阵中的
1
1
1 形成了完整的不分散的一块四连通块,并且对于
C
C
C 中所有位置,若是
1
1
1 ,则
A
,
B
A,B
A,B 对应位置必须都是
1
1
1,否则
A
,
B
A,B
A,B 之中必须有一个这个位置为
0
0
0。
保证
C
C
C 矩阵的边框都是
0
0
0。
Solution
因为保证 C C C 矩阵的一圈全部都是 0 0 0 ,所以我们只需要将 A A A 矩阵最左边一列置 1 1 1, B B B 矩阵最右边的一列置 1 1 1,然后 A , B A,B A,B矩阵奇偶分别负责一半,即A矩阵所有的奇数行(除最后一列)为 1 1 1, B B B 矩阵所有的偶数行(除第一列)全部为 1 1 1,这样 C C C 矩阵需要的话就直接让 A A A 或者 B B B 为 0 0 0 的那个变成 1 1 1 即可。
这样构造的关键在于可以完全覆盖1的前提下,使得所有的1连通。前段时间做过一道CF的题,大致意思就是矩阵连通所有的1,那道题就是先横着造一个连续的1(第一行全是1),然后往下垂直连通所有的其他的1,构造思路基本相同。
Code
#include <bits/stdc++.h> using namespace std; const int N = 500 + 10; int n,m; int A[N][N], B[N][N], C[N][N]; int main() { scanf("%d%d",&n, &m); for(int i = 0;i < n;++i){ getchar(); for(int j = 0;j < m;++j){ char ch = getchar(); C[i][j] = ch - '0'; } } for(int j = 0;j < n;++j){ A[j][0] = 1; B[j][m-1] = 1; } for(int i = 0;i < n;++i){ if(i & 1){ for(int j = 1;j < m - 1;++j){ A[i][j] = 1; } } else{ for(int j = 1;j < m - 1;++j){ B[i][j] = 1; } } } for(int i = 0;i < n;++i){ for(int j = 0;j < m;++j){ if(C[i][j] == 1){ A[i][j] = B[i][j] = 1; } } } for(int i = 0;i < n;++i){ for(int j = 0;j < m;++j){ printf("%d",A[i][j]); } puts(""); } for(int i = 0;i < n;++i){ for(int j = 0;j < m;++j){ printf("%d",B[i][j]); } puts(""); } return 0; }