题解 | 北华大学计算机程序设计算法提高训练营个人赛题解

洛姐打题日记

https://ac.nowcoder.com/acm/contest/37219/A

北华大学计算机程序设计算法提高训练营个人赛 · 题解

前言：由于实力有限，在命题方面可能尚有不足，望各位海涵。

A-签到题

B-签到题

设二元一次方程组求解即可

C-签到题

化简式子 $\sum_{i=1}^{n-1}(a_{i+1}-a_i)=a_n-a_1$ 只需找出数组中的最大值和最小值，相减即可得到两个最值

D-贪心

考虑溢出最少，就先考虑先将其尽可能填满（无溢出）之后优先考虑再加小书；如果小书不够，考虑加中书，并在保证达到目标的前提下去掉几本小书；如果中书不够，考虑加大书，并在保证达到目标的前提下去掉几本小书、中书；如果大书也不够，则不能达到目标QAQ。注意特判x=1，或者A,B,C中有等于0的情况。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp[1010][1010],zz[5];
struct qq{ll x,y,t;}q[N],aq[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x<v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

int main(){
	scanf("%lld%lld",&n,&m);
	k=1000;ans=0;
	L(i,2,n){
		ans+=k;
		k+=m;
	}
	sum=ans;//printf("%lld\n",sum);
	scanf("%lld%lld%lld",&x,&y,&z);
	if(x>=ans/20000)nx=ans/20000,ans%=20000;
	else ans-=20000*x,nx=x;
	if(y>=ans/5000)ny=ans/5000,ans%=5000;
	else ans-=5000*y,ny=y;
	if(z>=ans/1000)nz=ans/1000,ans%=1000;
	else ans-=1000*z,nz=z;
	
	if(ans>0){
		if(nz<z)nz++;
		else if(ny<y){
			ny++;nz=0;
		}
		else if(nx<x){
			nx++;ny=nz=0;
		}
		else{
			printf("QAQ\n");
			return 0;
		}
	}
	ans=nx*20000+ny*5000+nz*1000-sum;
	printf("%lld\n",ans);
}

E-DFS/BFS

经典迷宫题，求有几个入口可以到达唯一出口，即求从出口出发，能到达几个入口。从出口开始dfs/bfs，并标记能到达的入口即可。

另一种做法，从入口出发，记忆化搜索。

F-博弈

经典的取石子问题，因为同时取三堆，所以多考虑一个轮数，之后只考虑轮数小的那一堆的输赢即可。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],c[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp[1010][1010],zz[5];
struct qq{ll x,y,t;}q[N],aq[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x<v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
	ll x0=x/4*2+(x%4>0),x1=y/5*2+(y%5>0),x2=z/6*2+(z%6>0);
	ll k=min(x0,min(x1,x2));
	ans=k%2;
	if(ans)printf("(^-^)\n");
	else printf("(T-T)\n");
}

int main(){
	lim=1e6;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&x,&y,&z);
		solve();
	}
}

G-二分

将数组排序，从i=1开始遍历，对每一个i去寻找大于i的j的个数，满足a[j]=m-a[i]。简单的做法就是用upper_bound-lowerbound（大于m-a[i]的下标-大于等于m-a[i]的下标）

另一种做法，开map<int,int>，记录每个数字有多少个，之后直接返回结果即可。注意，不能加上自己！

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],zz[5];
struct qq{ll x,y,t;}q[N],aq[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x<v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
	sort(a+1,a+n+1);
	ans=0;
	L(i,1,n){
		k=m-a[i];
		y=upper_bound(a+1,a+n+1,k)-a;
		x=lower_bound(a+1,a+n+1,k)-a;
		if(k==a[i])y--;
		ans+=y-x;
	}
	ans/=2;
	printf("%lld\n",ans);
}

int main(){
	scanf("%lld%lld",&n,&m);
	L(i,1,n)scanf("%lld",&a[i]);
	solve();
}

H-构造

将s1字符串全部转化成小写，再按顺序重组s0字符串即可。切忌贪心，贪心可能会出错

#include<bits/stdc++.h>

#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],s0[N],s1[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;


int main(){
	scanf("%s",s+1);
	scanf("%s",s0+1);
	n=strlen(s+1);
	m=strlen(s0+1);
	k=0;
	L(i,1,m){
		if(s0[i]>='A'&&s0[i]<='Z')s1[++k]=s0[i]+32,s1[++k]=s0[i]+32;
		else s1[++k]=s0[i];
	}
	k=1;
	L(i,1,n){
		if(s[i]=='!')s[i]=s1[k]-32;
		else if(s[i]=='?')s[i]=s1[k];
		if(s[i]=='!'||(s[i]>='A'&&s[i]<='Z'))k+=2;
		else k++;
	}
	printf("%s\n",s+1);
}

I-暴力，bfs

对于每个询问，从询问的点开始跑bfs（因为所有边长均为1，所以不用跑最短路），遇到异性节点跳出即可。

J-bfs

常见的题目中，bfs大多以一个出发点开始对周围开始遍历。但本题中，一个点0作为出发点，那么所有的点1都是该点的终点；一个点1作为出发点，同样所有的点0都是该点的终点。那么我们可以反向考虑，所有点1作为出发点，即可算出到其余点0的最短路程，反之亦然。考虑多源bfs。初始将所有点1压入队列跑bfs，即可得到所有点0的最短路程；同样，初始将所有点0压入队列跑bfs，即可得到所有点1的最短路程。

#include<bits/stdc++.h>
#define ll int
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],head[N],ask[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char zz[5];
struct qq{ll x,y,t;}q[N],aq[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg[N*2];

bool cmp(qq u,qq v){
    return u.x<v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void add(ll u,ll v){
	eg[++cnt].to=v;
	eg[cnt].nxt=head[u];
	head[u]=cnt;
}

void solve(){
	L(i,1,n){
		if(a[i]==0)sq.push(i);
	}
	ll p=0;MS(b,inf);
	while(!sq.empty()){
		ll siz=sq.size();
		L(i,1,siz){
			ll x=sq.front();sq.pop();
			if(b[x]>p){
				b[x]=p;
				ll k=head[x];
			    while(k){
			        ll y=eg[k].to;
			        sq.push(y);
			        k=eg[k].nxt;
			    }
			}
		}
		p++;
	}
	L(i,1,n){
		if(a[i]==1)ask[i]=((b[i]==inf)?-1:b[i]);
	}
	
	L(i,1,n){
		if(a[i]==1)sq.push(i);
	}
	p=0;MS(b,inf);
	while(!sq.empty()){
		ll siz=sq.size();
		L(i,1,siz){
			ll x=sq.front();sq.pop();
			if(b[x]>p){
				b[x]=p;
				ll k=head[x];
			    while(k){
			        ll y=eg[k].to;
			        sq.push(y);
			        k=eg[k].nxt;
			    }
			}
		}
		p++;
	}
	L(i,1,n){
		if(a[i]==0)ask[i]=((b[i]==inf)?-1:b[i]);
	}
}

int main(){
	//lim=1e6;
	scanf("%d%d%d",&n,&m,&t);
	L(i,1,n)scanf("%lld",&a[i]);
	L(i,1,m){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	solve();
	while(t--){
		scanf("%d",&x);
		printf("%d\n",ask[x]);
	}
}

K-模拟

按题目多个if模拟计算过程即可

L-Kruskal重构树

数据结构题，根据图的最小生成树建立kruskal重构树，树上倍增判断该毒力能到达的最高节点，倍增求两病毒的lca。如果一旦有一种病毒能达到两病毒的lca，那么两病毒将会发生合并，合并后再倍增求最高节点即可，最后算子树的节点个数。本题改编自2021ICPC上海站的H题，kruskal算法不做过多讲述。 https://ac.nowcoder.com/acm/contest/24872/H

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,pos,tot,root,block,key,cnt,mn,mx,ans;
ll pre[N],dep[N],num[N],sum[N],ban[25][N],fa[25][N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s,mapp,zz[5];
struct qq{ll x,y,z;}q[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.z<v.z;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

ll find(ll x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void meg(ll x,ll y,ll z){
	ll fx=find(x),fy=find(y);
	if(fx!=fy){
		cnt++;
		pre[fx]=cnt;pre[fy]=cnt;
		sum[cnt]=sum[fx]+sum[fy];
		num[cnt]=num[fx]+num[fy];
		fa[0][fx]=cnt;fa[0][fy]=cnt;
		ban[0][fx]=max(0ll,z-sum[fx]);
		ban[0][fy]=max(0ll,z-sum[fy]);
	}
}

ll lca(ll x,ll y){
	if(dep[x]<dep[y])swap(x,y);
	R(i,20,0){
		if(dep[fa[i][x]]>=dep[y])x=fa[i][x];
	}
	if(x==y)return x;
	R(i,20,0){
		if(fa[i][x]!=fa[i][y]){
			x=fa[i][x];y=fa[i][y];
		}
	}
	return fa[0][x];
}

int main(){
	scanf("%lld%lld%lld",&n,&m,&t);
	L(i,1,n){
		scanf("%lld",&sum[i]);
		pre[i]=i;pre[i+n]=i+n;
		num[i]=1;
	}
	cnt=n;
	L(i,1,m){
		scanf("%lld%lld%lld",&x,&y,&z);
		q[i]={x,y,z};
	}
	sort(q+1,q+m+1,cmp);
	L(i,1,m)meg(q[i].x,q[i].y,q[i].z);
	fa[0][cnt]=0;
	R(i,cnt,1)dep[i]=dep[fa[0][i]]+1;
	L(i,1,20)L(j,1,cnt){
		fa[i][j]=fa[i-1][fa[i-1][j]];
		ban[i][j]=max(ban[i-1][j],ban[i-1][fa[i-1][j]]);
	}
		
	while(t--){
		scanf("%lld%lld%lld%lld",&x,&nx,&y,&ny);
		ll pos=lca(x,y);ll mx=x,my=y;
		
		R(i,20,0){
			if(fa[i][x]&&ban[i][x]<=nx)x=fa[i][x];
		}
		R(i,20,0){
			if(fa[i][y]&&ban[i][y]<=ny)y=fa[i][y];
		}
		if(dep[x]<=dep[pos]||dep[y]<=dep[pos]){
			R(i,20,0){
				if(fa[i][pos]&&ban[i][pos]<=nx+ny)pos=fa[i][pos];
			}
			ans=num[pos];
		}
		else ans=num[x]+num[y];
		printf("%lld\n",ans);
	}
}
/*
8 10 10
3 1 4 1 5 9 2 6
1 2 7
1 3 15
2 3 15
3 4 1
3 6 31415
4 5 27182
5 6 1
5 7 2333
5 8 5555
7 8 37
1 13 5 17
1 4 2 6
1 5 2 6
1 3 1 1
1 2 1 1
1 28000 5 22
5 2333 7 1
5 28000 8 1
6 8 8 1
1 1 2 1
*/