比赛信息
Solved ：4/8
Rank ：52/7277
[A] 数字游戏
题意&&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,n,x,y,z;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read(); x=read(); y=read(); z=read();
if (x<y || x<z || y>z || (x>y && y==z) || (x>y && x==z)){
puts("no");
continue;
}
if (x==y && y==z){
puts("yes"); continue;
}
if (n==1){
if (x==y && y==z) puts("yes");
else puts("no");
continue;
}
if (n==2){
if (x==y && y==z) puts("yes");
else if (x>y && x+y==2*z) puts("yes");
else puts("no");
continue;
}
if (x==y){
if (y==z) puts("yes");
else puts("no");
continue;
}
x-=y; z-=y;
if (z*n < x){
puts("no");
continue;
}
z=z*n-x*(n-1);
if (z<=0) puts("yes");
else puts("no");
}
return 0;
}
[B] 网格路径
题意
给出一个网格图，要从(1,1)走到(n,n)。每次只能向右或者向下走，且路上有一些位置走不了。问能选出最多几条互不相交的从起点到终点的路径(起点和终点不算相交)。
题解
典型的网络流题目。
拆上下分点，普通的点的上分点往下分点连一条流量为 1 的边。起点终点连流量为 INF 的边。然后每个格子的下分点再向右，下方的上分点连边，流量为 1。跑一遍网络流即为答案。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 210
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i,j,Ans,cnt,lsum=1,Found,al,flow;
int head[N],gap[N],gaps[N];
int a[N][N];
char c[N];
struct Flow{
int t,next,fl,re;
}e[N*32];
inline void Add(int s,int t,int fl){
e[lsum].t=t; e[lsum].fl=fl; e[lsum].next=head[s]; e[lsum].re=lsum+1; head[s]=lsum++;
e[lsum].t=s; e[lsum].fl=0; e[lsum].next=head[t]; e[lsum].re=lsum-1; head[t]=lsum++;
}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Sap(int x){
int i=0,mingap=cnt-1,F=al;
if (x==cnt) {Found=1; flow+=al; return;}
for (i=head[x];i;i=e[i].next)
if (e[i].fl){
if (gap[e[i].t]+1==gap[x]){
al=Min(al,e[i].fl); Sap(e[i].t);
if (gap[1]>=cnt) return;
if (Found) break;
al=F;
}
mingap=Min(mingap,gap[e[i].t]);
}
if (!Found){
gaps[gap[x]]--; if (!gaps[gap[x]]) gap[1]=cnt;
gaps[gap[x]=mingap+1]++;
} else e[i].fl-=al,e[e[i].re].fl+=al;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++){
scanf("%s",c+1);
for (j=1;j<=n;j++){
if (c[j]=='.') a[i][j]=0;
else a[i][j]=1;
}
}
if (a[1][1]==1 || a[n][n]==1){
puts("0");
continue;
}
memset(head,0,sizeof(head));
memset(gap,0,sizeof(gap));
memset(gaps,0,sizeof(gaps));
memset(e,0,sizeof(e));
lsum=1; flow=0;
Add(1,n+1,INF);
Add(n*n,2*n*n,INF);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
if (a[i][j]==1) continue;
Add((i-1)*n+j,(i-1)*n+j+n*n,1);
if (j<n && !a[i][j+1]) Add((i-1)*n+j+n*n,(i-1)*n+j+1,1);
if (i<n && !a[i+1][j]) Add((i-1)*n+j+n*n,i*n+j,1);
}
cnt=2*n*n;
gaps[0]=cnt;
while (gap[1]<cnt){
Found=0; al=INF; Sap(1);
}
cout<<flow<<endl;
}
return 0;
}
[C] 虫族基地
题意
给出一个n*m的网格图。一开始在(1,x),(n,y)处有两个障碍。在到达第i^{2}秒后，距离两个初始障碍曼哈顿距离不超过i的位置也会变成障碍。
问在哪一秒开始，不存在从左上角到右下角的不经过障碍路径。
题解
分三种情况讨论
- 障碍一开始就在起点或终点 ：显然答案为0
- 障碍在某个时刻内遮住了起点或终点
- 上下两边延伸出的障碍在某个时刻相遇，将方格分隔为了左右两部分
第二，三种情况的用时取最小值即为答案。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,T,x,y,z,t;
LL Ans;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read(); m=read(); x=read(); y=read();
if (x==1 || y==m){
puts("0");
continue;
}
t=Min(x-1,m-y);
t=Min(t,n-1);
if (x==y){
Ans=(n-1)>>1;
Ans=Min(Ans,t);
printf("%lld\n",Ans*Ans);
continue;
}
z=Abs(x-y);
n=n-2+z;
Ans=n>>1;
Ans=Min(Ans,t);
printf("%lld\n",Ans*Ans);
}
return 0;
}
[D] 环上游走
题意
给出一个大小为n的环，一开始有个人在1号位置。第i个时刻可以选择向左或者向右走i步。
问有多少种方案，使得经过了n-1个时刻后，每个位置恰好被走了一遍。
题解
n不超过80，打表秒出结果。。。
赛后对着 OEIS 查了一下，这个数列叫做 Glaisher's sequence 或是 Dress's sequence。
可以通过如下方法构造：对于k \geq 0，如果有了a_{0},a_{1},a_{2},...,a_{2^{k}-1}，则接下来2^{k}个数为2a_{0},2a_{1},2a_{2},...,2a_{2^{k}-1}
不难从上面得知，数列的每一项都是2的次幂。且2^{n}会第一次出现在2^{n}-1的位置。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
int T,i,n;
LL Ans;
int v[N],a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Dfs(int pos,int x){
reg int y=0;
if (x==n){
Ans++; return;
}
v[pos]=1;
y=pos+x;
if (y>n) y%=n;
if (!v[y]) Dfs(y,x+1);
// Right
y=pos-x;
if (y<=0) y=n+y;
if (!v[y]) Dfs(y,x+1);
// Left
v[pos]=0;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
a[1]=1;
a[2]=2;
a[3]=2;
a[4]=4;
a[5]=2;
a[6]=4;
a[7]=4;
a[8]=8;
a[9]=2;
a[10]=4;
a[11]=6;
a[12]=8;
a[13]=2;
a[14]=8;
a[15]=6;
a[16]=16;
a[17]=2;
a[18]=4;
a[19]=6;
a[20]=8;
a[21]=4;
a[22]=12;
a[23]=6;
a[24]=16;
a[25]=4;
a[26]=4;
a[27]=4;
a[28]=16;
a[29]=2;
a[30]=12;
a[31]=10;
a[32]=32;
a[33]=4;
a[34]=4;
a[35]=8;
a[36]=8;
a[37]=2;
a[38]=12;
a[39]=6;
a[40]=16;
a[41]=2;
a[42]=8;
a[43]=6;
a[44]=24;
a[45]=6;
a[46]=12;
a[47]=8;
a[48]=32;
a[49]=6;
a[50]=8;
a[51]=6;
a[52]=8;
a[53]=2;
a[54]=8;
a[55]=10;
a[56]=32;
a[57]=4;
a[58]=4;
a[59]=6;
a[60]=24;
a[61]=2;
a[62]=20;
a[63]=6;
a[64]=64;
a[65]=6;
a[66]=8;
a[67]=8;
a[68]=8;
a[69]=4;
a[70]=16;
a[71]=6;
a[72]=16;
a[73]=2;
a[74]=4;
a[75]=8;
a[76]=24;
a[77]=14;
a[78]=12;
a[79]=6;
a[80]=32;
T=read();
while (T--){
n=read();
printf("%d\n",a[n]);
}
return 0;
}
总结
百度之星初赛赛事的最后一场了，暑假事情比较少就全都参加了。先说一下这一场的感受吧，感觉签到题的难度稍微有所提升，第一题就有不少坑点，包括我在内很多人都 WA 了数发；第二题就直接上网络流拆点了；以及一道玄学打表唬住了不少人，后期大家才发现榜被带歪了。今天晋级的条件是在五十分钟内无罚时过掉第一题，时间更短但吃一点点罚时也行。果然难度上来了晋级门槛就高了。有一道博弈论和数据结构的题没有做出来有些可惜，之后一定补上（等题解出来真的会补）。
三场比赛下来最大的感受是：OJ是真TM的垃圾。提交一次代码都能崩好几次，崩了刷新也不知道有没有交上，也没法看个人的提交记录，只能去总提交记录里面查。排名也是，只有总的没有个人的。哪怕不单列一个页面，学牛客那样个人信息置顶首行也好呢。点题目链接跟抽奖一样看运气，随机获得题目页面或者 502 页面。虽然没有报名费，但是以百度的财力，换个好点的服务器或者网站框架应该不难吧，希望明年有所改进，目前这个OJ太破坏比赛体验了实在是。
比赛的整体难度两极分化感觉比较严重，基本上每次都是前 1h 做题，后 2h 发呆的节奏，没有合适的中档题填补中期的空洞。做到中期的时候，剩下的题都只过了十几个或者几个人，让人瞬间就没有了做的欲望了。希望这一情况在复赛中会有所改善。
复赛一共晋级 3000 人，刨去三场中只会签到的，真正有实力的选手应该还是轻松破 K 的，想拿到 80 个决赛名额压力着实不小，希望之后发挥顺利吧。三场比赛的排名加起来370名，复赛前 400 有T恤，所以今年拿T恤稳了。
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2021 百度之星大赛初赛第三场题解
本文地址: 2021 百度之星大赛初赛第三场题解
