前面的碎碎念：
本次小白月赛做的心急了一点，因为大部分题目都会，但是需要码量，所以写完没怎么仔细检查就交了。导致出现了各种神奇的错误：忘记取模/数组开小/数据范围看错/多组样例忘记初始化。不过整体做题速度还是挺快的，可惜最后一小时战略错误选择开A题，做了一小时各种解方程人都做没了，开E题的话应该能再多A一道。
题解部分：
A-最短路
太菜了，做了一小时人给做没了，以后还是自动放弃计算几何算了...
B-组队
我们对数组排序一下，使用尺取法：若右端点的值-左端点的值小于等于k，那么在这两段点间的所有元素都可以被选，因此更新ans=max(ans,R-L+1)，之后再移动右端点。若右端点的值-左端点的值大于k，我们就移动左端点，直到其差值小于等于k。
时间复杂度：O(nlog(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int i,L,R,ans,n,k,T,a[200005];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k),ans=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(L=R=1;R<=n;R++)
{
while(a[R]-a[L]>k)L++;
ans=max(ans,R-L+1);
}
printf("%d\n",ans);
}
return 0;
}C-十面埋伏
这里提供一个比较蠢的做法。我们先把"#"边缘所有的"."都变成"*"，但是这样会导致"#"内部的"."也变成"*"，因此我们考虑如何把"#"内部的"*"再重新变回"."。这里我们可以看出，若把"#"当做墙壁，从"#"外部任意一点出发进行上下左右的移动，肯定是可以走到地图边缘的，而"#"内部的任意一点出发是无法走到地图边缘的，因此我们把那些无法走到地图边缘的"*"再重新变回"."就行了。
时间复杂度：O(nm)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int n,m;
char R[505][505];
bool flag,V[505][505]={0},V2[505][505]={0};
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
//检查是否能走到地图边缘
void DFS(int x,int y)
{
int i,X,Y;
for(i=0;i<4;i++)
{
X=x+dx[i],Y=y+dy[i];
if(X<0||X>=n||Y<0||Y>=m)
{
flag=1;
continue;
}
if(!V[X][Y]&&R[X][Y]!='#')V[X][Y]=1,DFS(X,Y);
}
}
//把"#"内部全部填充为"."
void DFS2(int x,int y)
{
int i,X,Y;
for(i=0;i<4;i++)
{
X=x+dx[i],Y=y+dy[i];
if(X<0||X>=n||Y<0||Y>=m||V2[X][Y]||R[X][Y]=='#')continue;
V2[X][Y]=1,R[X][Y]='.',DFS2(X,Y);
}
}
int main()
{
int i,j,k,x,y;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%s",R[i]);
//先把"#"边缘所有的"."变为"*"
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(R[i][j]!='#')continue;
for(k=0;k<4;k++)
{
x=i+dx[k],y=j+dy[k];
if(R[x][y]!='#')R[x][y]='*';
}
}
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(R[i][j]=='#'||V[i][j])continue;
//检查从这点出发是否能到地图边缘
flag=0,V[i][j]=1,DFS(i,j);
//若不能到地图边缘，说明此处是"#"内部，进行填充操作
if(!flag)V2[i][j]=1,R[i][j]='.',DFS2(i,j);
}
for(i=0;i<n;i++)printf("%s\n",R[i]);
return 0;
}D-牛妹吃豆子
差分思想的二维前缀和板子题，不会的话建议百度学习一下，不过题目给出的x与y与我们数组下标的x与y不同，因此记得进行一下坐标变换。
时间复杂度：O(nm+k+q)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long S[2005][2005]={0};
int main()
{
int i,j,n,m,k,q,x1,y1,x2,y2;
scanf("%d%d%d%d",&m,&n,&k,&q);
while(k--)
{
scanf("%d%d%d%d",&y1,&x2,&y2,&x1),x1=n-x1+1,x2=n-x2+1;
S[x1][y1]++,S[x1][y2+1]--,S[x2+1][y1]--,S[x2+1][y2+1]++;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)S[i][j]+=S[i][j-1]+S[i-1][j]-S[i-1][j-1];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)S[i][j]+=S[i][j-1]+S[i-1][j]-S[i-1][j-1];
while(q--)
{
scanf("%d%d%d%d",&y1,&x2,&y2,&x1),x1=n-x1+1,x2=n-x2+1;
printf("%lld\n",S[x2][y2]+S[x1-1][y1-1]-S[x1-1][y2]-S[x2][y1-1]);
}
return 0;
}E-旅旅旅游
本题的套路和练习赛61的D题几乎一样，我们从1号节点跑一遍最短路，再从n号节点跑一遍最短路。那么对于任意一条边(u,v,w)，若1到u的最短距离+w+n到v的最短距离等于1到n的最短距离，或者1到v的最短距离+w+n到u的最短距离等于1到n的最短距离，则说明这条边在最短路上，从而这条边不能被选择。
那么我们参照克鲁斯卡尔算法的思想，使用并查集，对于任意一条可以选择的边，若两个节点的根节点不同，我们就把其中一个节点的根节点指向另一个结点的根节点。若相同，表明两个结点都已经属于同一个连通分量了，无需操作。最后检查一下2到n号节点的根节点是否与1号节点的根节点相同即可。
时间复杂度：O(nlog(n)+m)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long x,h;
bool operator<(const node &a)const
{
return a.h<h;
}
}r,f;
struct node2
{
int x,y,w;
}E[500005];
priority_queue<node>Q;
int n,m,V[100005];
long long ans,D[2][100005];
vector<int>R[100005],W[100005];
int find(int a)
{
if(a==V[a])return a;
return V[a]=find(V[a]);
}
void dij(bool a,int sx)
{
int i,j;
for(i=1;i<=n;i++)D[a][i]=2e18;
r.h=D[a][sx]=0,r.x=sx,Q.push(r);
while(!Q.empty())
{
f=Q.top(),Q.pop();
if(D[a][f.x]<f.h)continue;
for(i=0;i<R[f.x].size();i++)
{
j=R[f.x][i];
if(D[a][j]<=f.h+W[f.x][i])continue;
r.h=D[a][j]=f.h+W[f.x][i],r.x=j,Q.push(r);
}
}
}
int main()
{
int i,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)V[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
R[E[i].x].push_back(E[i].y),R[E[i].y].push_back(E[i].x);
W[E[i].x].push_back(E[i].w),W[E[i].y].push_back(E[i].w);
}
dij(0,1),dij(1,n),ans=D[0][n];
for(i=1;i<=m;i++)
{
if(D[0][E[i].x]+E[i].w+D[1][E[i].y]==ans||D[0][E[i].y]+E[i].w+D[1][E[i].x]==ans)continue;
a=find(E[i].x),b=find(E[i].y);
if(a!=b)V[a]=b;
}
for(i=2;i<=n;i++)if(find(i)!=find(1))break;
if(i<=n)printf("NO\n");
else printf("YES\n");
return 0;
}F-斗兽棋
简单的字符串处理题，按照题意我们手工列举出所有牛牛胜利和牛妹胜利的情况，剩下的情况自然全是平局，按题目要求输出答案即可。
时间复杂度：O(1)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
char A[]={"elephant"},B[]={"tiger"},C[]={"cat"},D[]={"mouse"};
int main()
{
char R1[9],R2[9];
scanf("%s%s",R1,R2);
if(!strcmp(R1,A)&&!strcmp(R2,B))printf("tiangou yiwusuoyou\n");
else if(!strcmp(R1,A)&&!strcmp(R2,D))printf("tiangou txdy\n");
else if(!strcmp(R1,B)&&!strcmp(R2,C))printf("tiangou yiwusuoyou\n");
else if(!strcmp(R1,B)&&!strcmp(R2,A))printf("tiangou txdy\n");
else if(!strcmp(R1,C)&&!strcmp(R2,D))printf("tiangou yiwusuoyou\n");
else if(!strcmp(R1,C)&&!strcmp(R2,B))printf("tiangou txdy\n");
else if(!strcmp(R1,D)&&!strcmp(R2,A))printf("tiangou yiwusuoyou\n");
else if(!strcmp(R1,D)&&!strcmp(R2,C))printf("tiangou txdy\n");
else printf("tiangou yiwusuoyou\n");
return 0;
}G-做题
简单的贪心题，想要做题的数量最多，自然是做题时间从小往大选。所以我们对所有元素从小到大排序，之后再用变量i从前到后进行遍历，用一个变量j记录[1,i]的前缀和。若此处的前缀和已经大于m了，那么就break退出循环，输出i-1即是答案。
时间复杂度：O(nlog(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long i,j=0,n,m,a[500005];
int main()
{
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for(i=1;i<=n;i++)
{
j+=a[i];
if(j>m)break;
}
printf("%lld\n",i-1);
return 0;
}H-人人都是好朋友
假如两个人是朋友，我们就对两个人连一条边，那么根据题目给出的朋友的传递性，同属于一个连通分量的人互相都是朋友，所以我们可以使用并查集实现这个功能。那么判断部分就很简单了，我们先把所有的朋友关系处理一遍，之后再处理敌人关系。对于所有的敌人关系，我们检查他们是否是朋友，即两个人的根节点是否相同，如果相同代表他们是朋友，与数据给出的敌人关系矛盾。
注意此题要使用离散化处理，数据量很大的情况下使用哈希表或者map可能会导致超时。
时间复杂度：O(Tn
log(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a,b,c;
}R[1000005];
int T,L1,L2,A[2000005],V[2000005];
int find(int a)
{
if(a==V[a])return a;
return V[a]=find(V[a]);
}
int main()
{
int i,j,k,n,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),L1=1;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&R[i].a,&R[i].b,&R[i].c);
A[L1++]=R[i].a,A[L1++]=R[i].b;
}
sort(A+1,A+L1);
for(i=L2=2;i<L1;i++)if(A[i]!=A[i-1])A[L2++]=A[i];
for(i=1;i<L2;i++)V[i]=i;
for(i=1;i<=n;i++)
{
if(!R[i].c)continue;
j=lower_bound(A+1,A+L2,R[i].a)-A,k=lower_bound(A+1,A+L2,R[i].b)-A;
a=find(j),b=find(k);
if(a!=b)V[a]=b;
}
for(i=1;i<=n;i++)
{
if(R[i].c)continue;
j=lower_bound(A+1,A+L2,R[i].a)-A,k=lower_bound(A+1,A+L2,R[i].b)-A;
a=find(j),b=find(k);
if(a==b)break;
}
if(i<=n)printf("NO\n");
else printf("YES\n");
}
return 0;
}I-求和
一道DFS序+树状数组or线段树的板子题，我们从根节点对其进行DFS遍历，那么DFS遍历的顺序可以形成一个序列，而一个子树的所有节点，其DFS的遍历顺序恰好是一段连续的序列，因此我们可以通过DFS遍历把一个树型结构变成线性结构。那么问题就变成了修改单点值，查询区间和，很显然这个通过线段树或者树状数组就能做到。如果想详细学习DFS序和树状数组或者线段树，建议直接百度。
时间复杂度：O(nlog(n)+m
log(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int n,m,k,tot=0,in[1000005],out[1000005],a[1000005];
long long S[1000005]={0};
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int x)
{
while(i<=n)S[i]+=x,i+=lowbit(i);
}
long long getsum(int i)
{
long long s=0;
while(i)s+=S[i],i-=lowbit(i);
return s;
}
vector<int>R[1000005];
void DFS(int x,int fa)
{
int i,j;
in[x]=++tot,update(tot,a[x]);
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j!=fa)DFS(j,x);
}
out[x]=tot;
}
int main()
{
int i,x,y,op;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
scanf("%d%d",&x,&y);
R[x].push_back(y),R[y].push_back(x);
}
DFS(k,0);
while(m--)
{
scanf("%d%d",&op,&x);
if(op==1)scanf("%d",&y),update(in[x],y);
else printf("%lld\n",getsum(out[x])-getsum(in[x]-1));
}
return 0;
}J-建设道路
数学题，拿纸笔推一推，字丑见谅QAQ，过程见下图：
那么很显然答案分为两个部分，前面一部分是a1,a2,...,an每个数字平方之和再乘以(n-1)。而后面一部分则可以遍历一边数组，利用前缀和求解。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long i,n,ans=0,a[500005],S[500005]={0};
int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]),ans=(ans+a[i]*a[i])%mod,S[i]=(S[i-1]+a[i])%mod;
ans=ans*(n-1)%mod;
for(i=1;i<n;i++)ans=(ans+mod-2*a[i]%mod*(S[n]-S[i]+mod)%mod)%mod;
printf("%lld\n",ans);
return 0;
}完结撒花，题解若有疏漏之处，还望大佬们轻喷。
京公网安备 11010502036488号