北华大学计算机程序设计算法提高训练营个人赛 · 题解
前言：由于实力有限，在命题方面可能尚有不足，望各位海涵。
A-签到题
B-签到题
设二元一次方程组求解即可
C-签到题
化简式子 只需找出数组中的最大值和最小值，相减即可得到两个最值
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
*/
京公网安备 11010502036488号