【A】Protect Sheep
题意：
一个\(R*C\)的牧场中有一些羊和一些狼，如果狼在羊旁边就会把羊吃掉。
可以在空地上放狗，狼不能通过有狗的地方，狼的行走是四联通的。
问是否能够保护所有的羊不被狼吃掉，如果能输出方案。
题解：
判断是否有羊的旁边有狼，有的话就-1。没有的话把所有空地换成狗就好。
#include#define F(i,a,b) for(int i=a;i<=(b);++i)#define F2(i,a,b) for(int i=a;i<(b);++i)using namespace std;int n,m,ok=1;char str[501][505];int main(){ scanf("%d%d",&n,&m); F(i,1,n){ scanf("%s",str[i]); } F(i,1,n){ F2(j,0,m){ if(str[i][j]=='S'&&(str[i-1][j]=='W'||str[i][j-1]=='W'||str[i+1][j]=='W'||str[i][j+1]=='W')) ok=0; } } if(ok){ puts("Yes"); F(i,1,n){ F2(j,0,m){ printf("%c",str[i][j]=='.'?'D':str[i][j]); } puts(""); } } else puts("No"); return 0;}
【B】Primal Sport
题意：
初始有一个数\(X_0\)，每一次可以对\(X_i\)这个数进行一个操作变成\(X_{i+1}\)：
选择一个小于\(X_i\)的质数\(p\)，则\(X_{i+1}\)等于\(\left\lceil\frac{X_i}{p}\right\rceil\cdot p\)。
给定了\(X_2\)，问最小的可能\(X_0\)。
题解：
令\(p_1\)等于\(X_2\)的最大质因数，那么显然\(X_1\)可能为\([X_2-p_1+1,X_2]\)中的合数。
再对这个范围内的\(X_1\)执行相同的过程即可。
#include#define F(i,a,b) for(int i=a;i<=(b);++i)using namespace std;const int INF=0x3f3f3f3f;int n,ans=INF;int np[1000001]={1,1},pr[1000001],cnt;int maxp[1000001];void init(int num){ F(i,2,num){ if(!np[i]) pr[++cnt]=i, maxp[i]=i; F(j,1,cnt){ if(i*pr[j]>num) break; np[i*pr[j]]=1; maxp[i*pr[j]]=maxp[i]; if(i%pr[j]==0) break; } }}int main(){ init(1000000); scanf("%d",&n); F(i,n-maxp[n]+1,n) if(maxp[i]!=i) ans=min(ans,i-maxp[i]+1); else ans=min(ans,i); printf("%d",ans); return 0;}
【C】Producing Snow
题意：
每天Bob都能用造雪机造出体积\(V_i\)的一堆雪，但是现在是夏天，每天每堆雪都会融化\(T_i\)体积（如果不足\(T_i\)则全部融化掉）。
问每天会融化多少体积的雪？
题解：
简单set+lower_bound，就很显然。注意点：multiset。
#include#define F(i,a,b) for(int i=a;i<=(b);++i)#define F2(i,a,b) for(int i=a;i<(b);++i)#define dF(i,a,b) for(int i=a;i>=(b);--i)#define dF2(i,a,b) for(int i=a;i>(b);--i)#define eF(i,u) for(int i=h[u];i;i=nxt[i])#define ll long long#define ld doubleusing namespace std;int n;ll v[100001],t[100001];ll ans,sum;multiset st;int main(){ scanf("%d",&n); F(i,1,n) scanf("%lld",v+i); F(i,1,n) scanf("%lld",t+i); F(i,1,n){ st.insert(v[i]+sum); multiset ::iterator it,it2,it3; sum+=t[i]; ans=t[i]*st.size(); it=st.lower_bound(sum+1); for(it2=st.begin();it2!=st.end()&&it2!=it;){ ans+=*it2-sum; it3=it2; ++it2; st.erase(it3); } printf("%lld\n",ans); } return 0;}
【D】Perfect Security
题意：
有一个长度为\(n\)的数组\(A\)，和一个等长的数组\(B\)，要求你重排数组\(B\)，使得序列\(A_1\oplus B_1,A_2\oplus B_2,\cdots,A_n\oplus B_n\)在字典序上最小。
题解：
从1到n遍历每一个\(A_i\)，选出当前\(B\)中的让\(A_i\oplus B_i\)最小的\(B_i\)即可，重复\(n\)遍。
那么每次必须要在较快时间内完成，考虑set内按二进制位二分。每次可以\(log^2n\)完成。
#include#define F(i,a,b) for(int i=a;i<=(b);++i)#define dF(i,a,b) for(int i=a;i>=(b);--i)using namespace std;int n,a[300001];multiset b;int main(){ int x; scanf("%d",&n); F(i,1,n) scanf("%d",a+i); F(i,1,n) scanf("%d",&x), b.insert(x); F(i,1,n){ int now=0; dF(j,29,0){ if((a[i]>>j)&1){ now+=1<