2023牛客暑期多校训练营2（D/E/F/H/I/K）

目录

D.The Game of Eating

E.Square

F.Link with Chess Game

H.0 and 1 in BIT

I.Link with Gomoku

K.Box

---

D.The Game of Eating

思路：倒着贪心。因为正着贪会导致一种局面：我选了当前喜爱值最大的菜，但是就算我不选这个菜，后面的人也可能选这一道菜，我依然能吃上这道菜，那么我为什么不选其它的菜而两者兼得呢？所以我们考虑倒着贪心。贪心到第i个人时，根据喜爱值从大到小遍历一遍菜，如果这个菜被后面的人选过了，那就不选了，直到有一个菜是没被选过的。

bool cmp(PII a,PII b) {return a.first>b.first;
}
void solve() {map<int,int>mp;int n,m,k;cin>>n>>m>>k;for(int i=1; i<=n; i++)v[i].clear();for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {int x;cin>>x;v[i].push_back({x,j});}sort(v[i].begin(),v[i].end(),cmp);}for(int i=k; i>=1; i--) {int now=i%n,j=0;if(!now)now=n;while(mp[v[now][j].second])j++;mp[v[now][j].second]=true;}for(auto x:mp) {cout<<x.first<<" ";}cout<<endl;
}

 

E.Square

思路：题目的公式可以表示为，求Y使得：

Y^2-(Y^2)%(10^K) = X*(10^K)

 可见只需枚举K的大小然后判断即可。 

代码：

string cmp;
bool pd(int y) {string now=to_string(y*y);while(now.size()<cmp.size())now+='0';//防止runtime errorfor(int i=0; i<cmp.size(); i++) {if(cmp[i]!=now[i])return false;//有一位不相同就不合法答案}return true;
}
void solve() {int x;cin>>x;cmp=to_string(x);for(int k=0; k<=9; k++) {//枚举k的大小int now=pow(10,k)*x;int y=sqrt(now);if(pd(y)) {//判断这个y是否合法cout<<y<<endl;return;}if(pd(y+1)) {//因为y*y会减掉一部分余数，所以要判一下y+1cout<<y+1<<endl;return;}}cout<<-1<<endl;
}

F.Link with Chess Game

思路：若只有一个棋子，当棋子有距离边界为奇数长度的局面为先手必胜态，因为两个人必须在这个奇数区间里一直走，而先手可以一直选到所有位置选完。该情况可推广至三个棋子，三个棋子的距离端点距离可以抽象为所有棋子距离端点的距离之和，棋子可以在端点之和为奇数的区间内反复横跳，来保持自己的最终的奇偶性，从而导致先手必胜，反之先手必败。

代码：

void solve() {int n,a,b,c;cin>>n>>a>>b>>c;int sum1=(a-1)+(b-1)+(c-1);int sum2=(n-a)+(n-b)+(n-c);if(sum1%2||sum2%2)cout<<"Alice"<<endl;else cout<<"Bob\n";
}

H.0 and 1 in BIT

思路：操作A相当于将x变成反码，也就是在取模意义下，操作A会令x=-x-1，而操作B会x=x+1，所以我们先开两个前缀和数组，一个记录前缀A的个数，一个记录前缀的贡献，然后在每次操作中，若l~r的区间内的A的个数为奇数，则原本的贡献要乘上-1，如此模拟即可。

代码：

int sum1[maxn],sum2[maxn];
//sum1记录前缀A的个数，sum2记录前缀的贡献
void solve() {int n,q,l,r,L,R,ans=0;string s,x;cin>>n>>q>>s;for(int i=1; i<=n; i++) {sum1[i]=sum1[i-1]+(s[i-1]=='A');if(s[i-1]=='A')sum2[i]=-sum2[i-1]-1;else sum2[i]=sum2[i-1]+1;}while(q--) {int sum=0;cin>>l>>r>>x;L=min((ans^l)%n+1,(ans^r)%n+1),R=max((ans^l)%n+1,(ans^r)%n+1);int now1=(sum1[R]-sum1[L-1])%2,now2;for(int i=0; i<x.size(); i++) {sum=sum*2+(x[i]-'0');}//将x转换为10进制，方便与贡献进行运算if(now1) {//若区间A的个数为奇数，则贡献*-1now2=sum2[R]+sum2[L-1];sum=-sum;} else now2=sum2[R]-sum2[L-1];int mod=(1<<(int)x.size());ans=(now2+sum+mod)%mod;for(int i=(int)x.size()-1; i>=0; i--) {cout<<((ans>>i)&1);}cout<<endl;}
}

I.Link with Gomoku

思路：在前面的n-n%2行中，摆放方式和题目样例一样：

xxxxoxxxxoxxxxo......

ooooxooooxoooox......

最后一行若为奇数行，则这样摆放即可：

xoxoxoxoxo......

代码： 

void solve() {int n,m;cin>>n>>m;for(int i=1; i<=n-n%2; i++) {int cnt=0;for(int j=1; j<=m; j++) {if(cnt%5==4) {//前4个放相同的 if(i%2)cout<<"o";//行与行之间连续4个xo交替放 else cout<<"x";} else {//最后一个放不同的 if(i%2)cout<<"x";else cout<<"o";}cnt++;}cout<<endl;}if(n%2) {//若最后一行为奇数行则xoxox......交替放 for(int i=1; i<=m; i++) {if(i%2)cout<<"x";else cout<<"o";}cout<<endl;}
}

K.Box

思路：我们设：

dp[i][0]表示第i位移动到i-1位的情况

dp[i][1]表示第i位不移动的情况

dp[i][2]表示第i位移动到i+1位的情况

具体实现见代码注释。

代码：

void solve() {int n;cin>>n;for(int i=1; i<=n; i++)cin>>a[i];for(int i=1; i<=n; i++)cin>>b[i];for(int i=1; i<=n; i++) {if(b[i]) {//只有1有主动权，0是被迫的QAQdp[i][0]=dp[i-1][0]+a[i-1];//当前1左移只能由上一个1左移转移过来dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[i];//当前位置不动，上一个位置1不动或者左移都可以dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[i+1];//当前位置右移，上一个位置1不动、左移、右移都可以} else {dp[i][0]=max({dp[i-1][0],dp[i-1][1]});// 当前位左移，可以由上一个位置左移，或者上一个位置1还没动的过转移过来dp[i][1]=dp[i-1][2];//这个0可以被上个右移的1挤到左边}}cout<<max(dp[n][0],dp[n][1])<<endl;//最终答案在左移和不动的情况下取max(因为最后一个位置无法右移)
}