整理的算法模板合集： 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)
第十一届山东省大学生程序设计竞赛（9 / 13）
B. Build Roads
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));
}
C. Cat Virus
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;
}
D. Dyson Box
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;
}
F. Birthday Cake
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;
}
G. Grade Point Average
输出 ∑ 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;
}
H. Adventurer’s Guild
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;
}
J. Tuition Agent
Problem
Piggy 是一个辅导班的老板，对于第 i i i 个客户，Piggy有两个选择:
- 花费 X i X_i Xi 让他变成老师
- 花费 Y i Y_i Yi 让他变成需要老师来辅导的学生
每给一个学生安排一对一的家教，他就能赚钱。只有等级高的人才可以教等级低的人。其中， 1 1 1 是最高的等级。第 i i i 个客户有一个编号 R i R_i Ri，每个客户的等级都是不同的。
求得到的最大利润。
Solution
Code
L. Construction of 5G Base Stations
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;
}
M. Matrix Problem
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;
}
转载：https://blog.csdn.net/weixin_45697774/article/details/116902043