AtCoder ExaWizards2019题解
AtCoder
(因为代码直接用模板写的，可能有点冗长)
A.Regular Triangle
给你三根棍子的长度，问你能否用他们组成等边三角形。
什么逗逼玩意？
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int main()
{
int A=read(),B=read(),C=read();
if(A==B&&B==C&&C==A)puts("Yes");
else puts("No");
return 0;
}
B.Red or Blue
给你一个由
RB组成的字符串，回答R的个数是否严格大于B的个数。
什么逗逼玩意？
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,r,b;char ch[10000];
int main()
{
n=read();scanf("%s",ch+1);
int l=strlen(ch+1);
for(int i=1;i<=n;++i)
if(ch[i]=='R')++r;
else ++b;
if(r>b)puts("Yes");
else puts("No");
}
C.Snuke the Wizard
终于是正常题了。。。
给定一行\(n\)个格子，每个格子都有一个类型(不同格子类型可能会相同)，一开始每个格子上都有一个人。现在每次指定一个类型的格子，以及左右中的一个方向，如果某个格子属于这个类型，且这个格子上有人，则让人朝着给定方向走一步。如果一个人掉出了格子的边界他就消失了。
问最后格子内剩下的人数。
发现掉出去的人一定是一段前缀和一段后缀，直接二分就可以了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,Q,ans;char s[MAX];
char ch[2],A[MAX],B[MAX];
bool vis[MAX];
int chk(int x)
{
for(int i=1;i<=Q;++i)
if(s[x]==A[i])
{
x+=(B[i]=='L')?-1:1;
if(x<1)return 0;
if(x>n)return 1;
}
return 2;
}
int main()
{
n=read();Q=read();scanf("%s",s+1);
for(int i=1;i<=Q;++i)scanf("%s",ch),A[i]=ch[0],scanf("%s",ch),B[i]=ch[0];
{
int l=1,r=n,ret=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(chk(mid)==0)l=mid+1,ret=mid;
else r=mid-1;
}
for(int i=1;i<=ret;++i)vis[i]=true;
}
{
int l=1,r=n,ret=n+1;
while(l<=r)
{
int mid=(l+r)>>1;
if(chk(mid)==1)r=mid-1,ret=mid;
else l=mid+1;
}
for(int i=ret;i<=n;++i)vis[i]=true;
}
for(int i=1;i<=n;++i)ans+=!vis[i];
printf("%d\n",ans);
return 0;
}
D.Modulo Operations
一开始你有一个数\(X\)。你还有\(n\)个数\(a_i\)，现在问你在所有的\(n!\)种\(a_i\)的排列下，让\(X\)顺次模\(a_i\)的结果的和。
发现如果先模了一个较小的数再模一个较大的数就没有意义了。
因此把所有\(a\)从大往小排序，依次考虑每个\(a_i\)模了是否有意义，如果没有意义就等价于要放在后面的一个\(a_i\)之后进行模操作，乘一下方案数就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
#define MOD 1000000007
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,X,a[MAX],ans,f[2][MAX];
int main()
{
n=read();X=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(&a[1],&a[n+1]);reverse(&a[1],&a[n+1]);
f[0][X]=1;
for(int i=1,nw=1,pw=0;i<=n;++i,pw^=1,nw^=1)
{
memset(f[nw],0,sizeof(f[nw]));
if(i!=n)for(int j=0;j<=X;++j)add(f[nw][j],1ll*(n-i)*f[pw][j]%MOD);
for(int j=0;j<=X;++j)add(f[nw][j%a[i]],f[pw][j]);
}
for(int i=0;i<=X;++i)add(ans,1ll*i*f[n&1][i]%MOD);
printf("%d\n",ans);
return 0;
}
E.Black or White
有\(W\)个白球，\(B\)个黑球，如果当前两种球都有，就会等概率的拿出一个某种颜色的球，否则就只能拿出还有的那种颜色的球。对于\(i\in [1,B+W]\)，回答第\(i\)次拿出黑球的概率。
先计算一下前\(i\)次恰好拿完所有白(黑)球的概率，这个可以用组合数很方便的计算。
那么最终的结果就是在前\(i-1\)次操作没有拿完任意一种球的概率乘上\(\frac{1}{2}\)，再加上前\(i-1\)次已经把白球拿完的概率。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MOD 1000000007
#define inv2 500000004
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
int n,B,W,jc[MAX],jv[MAX],inv[MAX];
int C(int n,int m){if(n<m||m<0||n<0)return 0;return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int pw[MAX],pb[MAX],sum[MAX];
int bin[MAX];
int main()
{
B=read();W=read();n=B+W;
jc[0]=jv[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;
for(int i=1;i<=n;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
bin[0]=1;for(int i=1;i<=n;++i)bin[i]=1ll*bin[i-1]*inv2%MOD;
for(int i=1;i<=n;++i)pw[i]=(pw[i-1]+1ll*C(i-1,W-1)*bin[i])%MOD;
for(int i=1;i<=n;++i)pb[i]=(pb[i-1]+1ll*C(i-1,B-1)*bin[i])%MOD;
for(int i=1;i<=n;++i)
{
int ans=(1ll*(1ll+MOD-pw[i-1]+MOD-pb[i-1])%MOD*inv2%MOD+pw[i-1])%MOD;
printf("%d\n",ans);
}
return 0;
}
F.More Realistic Manhattan Distance
给定一张网格图，每一行每一列的边都都强制定为相同的方向。
每次给定起点终点，求出最短路。
对于起点终点，把周围的每个方向的边都找一条最近的出来，这样子最多是一个\(6*6\)的网格图，然后建边跑最短路就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
vector<int> N,W,E,S;
int Findpre(vector<int> &A,int x)
{
if(!A.size())return 1;
int l=0,r=A.size()-1,ret=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(A[mid]<=x)ret=mid,l=mid+1;
else r=mid-1;
}
return A[ret];
}
int Findsuf(vector<int> &A,int x)
{
if(!A.size())return 1;
int l=0,r=A.size()-1,ret=r;
while(l<=r)
{
int mid=(l+r)>>1;
if(A[mid]>=x)ret=mid,r=mid-1;
else l=mid+1;
}
return A[ret];
}
int n,m,Q;char dS[100100],dT[100100];
struct Line{int v,next,w;}e[1000];
int bh[20][20],tot;
int h[100],cnt;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int dis[200];bool vis[200];
int SPFA(int S,int T)
{
for(int i=1;i<=tot;++i)dis[i]=1e9,vis[i]=false;
queue<int> Q;Q.push(S);dis[S]=0;vis[S]=true;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=e[i].next)
if(dis[e[i].v]>dis[u]+e[i].w)
{
dis[e[i].v]=dis[u]+e[i].w;
if(!vis[e[i].v])vis[e[i].v]=true,Q.push(e[i].v);
}
vis[u]=false;
}
return dis[T]<1e9?dis[T]:-1;
}
int main()
{
n=read();m=read();Q=read();
scanf("%s",dS+1);scanf("%s",dT+1);
for(int i=1;i<=n;++i)
if(dS[i]=='E')E.push_back(i);
else W.push_back(i);
for(int i=1;i<=m;++i)
if(dT[i]=='N')N.push_back(i);
else S.push_back(i);
while(Q--)
{
int a=read(),b=read(),c=read(),d=read();
vector<int> X,Y;
X.push_back(Findpre(E,a));X.push_back(Findpre(W,a));
X.push_back(Findsuf(E,a));X.push_back(Findsuf(W,a));
X.push_back(Findpre(E,c));X.push_back(Findpre(W,c));
X.push_back(Findsuf(E,c));X.push_back(Findsuf(W,c));
Y.push_back(Findpre(N,b));Y.push_back(Findpre(S,b));
Y.push_back(Findsuf(N,b));Y.push_back(Findsuf(S,b));
Y.push_back(Findpre(N,d));Y.push_back(Findpre(S,d));
Y.push_back(Findsuf(N,d));Y.push_back(Findsuf(S,d));
sort(X.begin(),X.end());X.resize(unique(X.begin(),X.end())-X.begin());
sort(Y.begin(),Y.end());Y.resize(unique(Y.begin(),Y.end())-Y.begin());
int lx=X.size(),ly=Y.size(),S,T;tot=0;
for(int i=0;i<lx;++i)
for(int j=0;j<ly;++j)
{
bh[i][j]=++tot;
if(X[i]==a&&Y[j]==b)S=tot;
if(X[i]==c&&Y[j]==d)T=tot;
}
for(int i=1;i<=tot;++i)h[i]=0;cnt=2;
for(int i=0;i<lx;++i)
if(dS[X[i]]=='E')for(int j=0;j<ly-1;++j)Add(bh[i][j],bh[i][j+1],Y[j+1]-Y[j]);
else for(int j=1;j<ly;++j)Add(bh[i][j],bh[i][j-1],Y[j]-Y[j-1]);
for(int i=0;i<ly;++i)
if(dT[Y[i]]=='N')for(int j=1;j<lx;++j)Add(bh[j][i],bh[j-1][i],X[j]-X[j-1]);
else for(int j=0;j<lx-1;++j)Add(bh[j][i],bh[j+1][i],X[j+1]-X[j]);
printf("%d\n",SPFA(S,T));
}
}