AtCoder ExaWizards 2019 简要题解
Tags：题解
link：https://atcoder.jp/contests/exawizards2019
很水的一场ARC啊，随随便便就ABCDE了，F最后想到了还没有写出来。
D题花了太久时间所以只有Rank31，我是真的菜。
嘿嘿嘿，上述装逼方式是我最为反感的机房里的言语，既然快退役了，也就学一学，感受一下机房里dalao们怎么样装逼一时爽、一直装逼一直爽，听者一时丧，一直听一直丧的快感咯
有意思的题应该是DE了。
A Regular Triangle
如果三个数相等输出Yes，否则No。
#include<iostream>
using namespace std;
int main()
{
int A,B,C;
cin>>A>>B>>C;
if(A==B&&B==C) puts("Yes");
else puts("No");
}
B Red or Blue
字符串中R个数超过一半输出Yes，否则No。
#include<iostream>
using namespace std;
int n,a;
char s[1000000];
int main()
{
cin>>n;
scanf("%s",s+1);
for(int i=1;i<=n;i++)
if(s[i]=='R') a++;
if(a*2>n) puts("Yes");
else puts("No");
}
C Snuke the Wizard
一排格子，每个格子有一个属性，用小写字母表示。
初始每个格子上都有一枚硬币，Q次操作形如某种属性的格子上的硬币全部左移或右移一位。
移出边界就消失，问最后剩余硬币数。
发现移出去的一定是一段前缀和一段后缀，具有可二分性。
#include<iostream>
using namespace std;
const int N=2e5+10;
int n,Q;
char s[N],t[N],d[N];
int Drop(int x)
{
for(int i=1;i<=Q;i++)
{
if(s[x]==t[i]) x+=(d[i]=='R')?1:-1;
if(x>n) return -1;
if(x<1) return 1;
}
return 0;
}
int main()
{
cin>>n>>Q;
scanf("%s",s+1);
for(int i=1;i<=Q;i++) cin>>t[i]>>d[i];
int l=1,r=n,la=0,ra=n+1;
while(l<=r)
{
int mid=(l+r)>>1;
if(Drop(mid)==1) la=mid,l=mid+1;
else r=mid-1;
}
l=1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(Drop(mid)==-1) ra=mid,r=mid-1;
else l=mid+1;
}
cout<<ra-la-1<<endl;
}
D Modulo Operations
给一个长度为\(n\)的数列和\(X\)，对于一种排列，其权值为X依次对排列中的数取模、最后剩下的值。
问\(n!\)种情况的权值和。\(n\le 200,X\le 10^5\)
详见UOJ22。有一个性质就是大的数排在小的数的后面，则那个大数没有影响。
所以从大往小排序后依次做。设\(f[i][j]\)表示做了\(i\)次操作，剩余数为\(j\)的方案数。
转移有两种：
- 选\(f[i+1][j\%p[i]]+=f[i][j]\)
- 不选\(f[i+1][j]+=f[i][j]*(n-i)\)
即如果选了这个数则必须放在这一位，否则可以放在后面\(n-i\)个数的任意一位。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,X,f[N],Ans,g[N],s[N];
int cmp(int a,int b) {return a>b;}
int main()
{
cin>>n>>X;
f[X]=1;
for(int i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+n+1,cmp);
for(int i=1,x;i<=n;i++)
{
x=s[i];
for(int j=0;j<=X;j++) g[j]=0;
for(int j=0;j<=X;j++)
{
(g[j%x]+=f[j])%=mod;
(g[j]+=1ll*f[j]*(n-i)%mod)%=mod;
}
for(int j=0;j<=X;j++) f[j]=g[j];
}
for(int j=0;j<=X;j++) (Ans+=1ll*f[j]*j%mod)%=mod;
cout<<Ans<<endl;
}
E Black or White
有一些黑球和白球，如果两种球都有则各有一半的几率取出，否则一定取出剩下的那种颜色的求。
对于\(i\le 2e5\)，求第\(i\)次拿到黑球的概率。
令前\(i\)次把白球拿完的概率是\(T_w\)，把黑球拿完的概率是\(T_b\)，则第\(i+1\)次取出黑球的概率是\(T_w+(1-T_W-T_b)*\frac{1}{2}\)。
转成在恰好第\(i\)次拿完白球的概率\(g_i=2^{i}{i-1 \choose W-1}\)，\(W\)为白球总数。
#include<iostream>
using namespace std;
const int N=2e5+10,mod=1e9+7;
int jc[N],inv[N],bit[N],B,W,sw[N],sb[N];
int ksm(int x,int k)
{
int s=1;for(;k;k>>=1,x=1ll*x*x%mod)
if(k&1) s=1ll*s*x%mod;return s;
}
int C(int n,int k) {return 1ll*jc[n]*inv[k]%mod*inv[n-k]%mod;}
int main()
{
cin>>B>>W;
jc[0]=bit[0]=inv[0]=1;
for(int i=1;i<=B+W;i++) jc[i]=1ll*i*jc[i-1]%mod;
for(int i=1;i<=B+W;i++) inv[i]=ksm(jc[i],mod-2);
for(int i=1;i<=B+W;i++) bit[i]=1ll*bit[i-1]*inv[2]%mod;
for(int i=W;i<B+W;i++)
sw[i]=1ll*bit[i]*C(i-1,i-W)%mod;
for(int i=B;i<B+W;i++)
sb[i]=1ll*bit[i]*C(i-1,i-B)%mod;
for(int i=1;i<=B+W;i++)
{
(sw[i]+=sw[i-1])%=mod;
(sb[i]+=sb[i-1])%=mod;
}
for(int i=1;i<=B+W;i++)
{
int w=(sw[i-1]+1ll*((mod+1-sw[i-1]-sb[i-1])%mod+mod)%mod*
(i==B+W?1:inv[2])%mod)%mod;
cout<<w<<endl;
}
}
F More Realistic Manhattan Distance
给你一张网格图，同一行或同一列的边的方向都一样，求多组询问，问两点之间的最短路。
发现有用的边就只有距离起点终点四个方向最近的两条边，一共16条边，把交点抠出来跑最短路就好了。
我的实现方式要3700ms，租酥雨只要跑970ms真的墙。
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,m,q,Ans,HH[N],ZZ[N],dis[N],vis[N];
char s[N],t[N];
set<int> H[2],Z[2];
queue<int> Q;
struct Node{int x,y;}P[N];
void GetAns(int x1,int y1,int x2,int y2)
{
int ch=0,cz=0,c=0;
set<int>::iterator it;
for(int i=0;i<2;i++)
{
it=H[i].lower_bound(x1);
if(it!=H[i].end()) HH[++ch]=*it;
if(it!=H[i].begin()) HH[++ch]=*(--it);
it=H[i].lower_bound(x2);
if(it!=H[i].end()) HH[++ch]=*it;
if(it!=H[i].begin()) HH[++ch]=*(--it);
it=Z[i].lower_bound(y1);
if(it!=Z[i].end()) ZZ[++cz]=*it;
if(it!=Z[i].begin()) ZZ[++cz]=*(--it);
it=Z[i].lower_bound(y2);
if(it!=Z[i].end()) ZZ[++cz]=*it;
if(it!=Z[i].begin()) ZZ[++cz]=*(--it);
}
sort(HH+1,HH+ch+1);
ch=unique(HH+1,HH+ch+1)-HH-1;
sort(ZZ+1,ZZ+cz+1);
cz=unique(ZZ+1,ZZ+cz+1)-ZZ-1;
for(int i=1;i<=ch;i++)
for(int j=1;j<=cz;j++)
P[++c]=(Node){HH[i],ZZ[j]};
for(int i=1;i<=c;i++)
if(P[i].x==x1&&P[i].y==y1)
dis[i]=0,Q.push(i),vis[i]=1;
else dis[i]=1e9;
while(!Q.empty())
{
int x=Q.front();
for(int i=1;i<=c;i++)
{
if(P[i].x!=P[x].x&&P[i].y!=P[x].y) continue;
if(P[i].x==P[x].x)
{
if(P[i].y>P[x].y&&s[P[i].x]=='W') continue;
if(P[i].y<P[x].y&&s[P[i].x]=='E') continue;
}
if(P[i].y==P[x].y)
{
if(P[i].x>P[x].x&&t[P[i].y]=='N') continue;
if(P[i].x<P[x].x&&t[P[i].y]=='S') continue;
}
int val=dis[x]+abs(P[i].x-P[x].x)+abs(P[i].y-P[x].y);
if(dis[i]<=val) continue;
dis[i]=val;
if(!vis[i]) Q.push(i),vis[i]=1;
}
Q.pop(),vis[x]=0;
}
for(int i=1;i<=c;i++)
if(P[i].x==x2&&P[i].y==y2)
Ans=dis[i];
}
int main()
{
scanf("%d%d%d%s%s",&n,&m,&q,s+1,t+1);
for(int i=1;i<=n;i++)
if(s[i]=='E') H[1].insert(i);
else H[0].insert(i);
for(int i=1;i<=m;i++)
if(t[i]=='N') Z[1].insert(i);
else Z[0].insert(i);
for(int i=1,x1,y1,x2,y2;i<=q;i++)
{
cin>>x1>>y1>>x2>>y2;
GetAns(x1,y1,x2,y2);
if(Ans==1e9) puts("-1");
else printf("%d\n",Ans);
}
return 0;
}