A - Two Frogs
思路1:从结果倒推,
1、当一只青蛙被逼到角落时,会因为无路可走而失败。
2、而一旦出现只能后退的情况,就会被不断逼退。
3、因此先遇到这种情况的青蛙必败。
4、不难推出,若两只青蛙之间的距离为奇数时,先手必胜。
思路2:观察数据,大胆猜测
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'void solve(){int n,a,b;cin>>n>>a>>b;int c=abs(a-b);if(c&1)cout<<"NO"<<endl;else cout<<"YES"<<endl;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _;cin>>_;//_=1;while(_--)solve();return 0;
}
B - Crafting
思路:根据题意,如果有不止1个数需要增加时,会出现矛盾(因为a1增加时a2要减少,a2增加时a1要减少)。如果只有1个数需要增加,只要判断其余数字能否支持其达到目标数字即可。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'void solve(){int n;cin>>n;vector<int>a(n+1),b(n+1);for(int i=1;i<=n;i++)cin>>a[i];int f=-1,pos=0;for(int i=1;i<=n;i++){cin>>b[i];if(a[i]<b[i])pos+=b[i]-a[i],f++;}if(f>0)cout<<"NO"<<endl;else {for(int i=1;i<=n;i++){if(a[i]<b[i])continue;else if(a[i]-pos<b[i]){cout<<"NO"<<endl;return ;}}cout<<"YES"<<endl;}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _;cin>>_;//_=1;while(_--)solve();return 0;
}
C - The Trail
目标:设置路径上的数值,实现每行每列的和相等
思路:观察数据范围,可以让目标和为0。从(0,0)开始,
1、若路径为D(向下),则当前位置是该行最后一个需要填数的,直接设置为该行和的负数。
2、若路径为R(向右),则当前位置是该列最后一个需要填数的,直接设置为该列和的负数。
可以预处理出每行每列填数前的和。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long longint e[1005][1005];
void solve(){int m,n;cin>>n>>m;string s;cin>>s;vector<int>h(n+1);vector<int>l(m+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>e[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)h[i]+=e[i][j],l[j]+=e[i][j];int x=1,y=1;for(auto op:s){if(op=='D'){e[x][y]=-h[x];h[x]=0,l[y]+=e[x][y];x+=1;}else{e[x][y]=-l[y];l[y]=0,h[x]+=e[x][y];y+=1;}}e[n][m]=-h[n];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<<e[i][j]<<' ';cout<<endl;}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _;cin>>_;//_=1;while(_--)solve();return 0;
}
D - Scarecrow
目标:得出当稻草人配合乌鸦行动时的时间。
思路:由于乌鸦是从0开始行动,而稻草人的初始位置都为正,因此可以考虑线性处理。
1、在乌鸦第一次移动前,派第一只稻草人向乌鸦前进,当它到达0时,花费ans,乌鸦前进至k。
2、对于后一只稻草人,如果其在ans时间内可以到达k,则让其停在k等待乌鸦,乌鸦到达后前进k,若无法到达,则在其行动ans时间后,
1)若稻草人的位置<k,则乌鸦从距离前一只稻草人k的位置前进到距离当前稻草人k的位置
2)若稻草人的位置>k,则时间增加乌鸦与稻草人距离的一半,乌鸦被前一只稻草人推动一半距离,当前稻草人向乌鸦移动一半距离。两者相遇,乌鸦前进k。
3、如此循环,如果当乌鸦最后一次瞬移后还未到达目标l,则由最后一只稻草人推动乌鸦前进,时间增加两者的距离
注意:最后的结果要*2;float精度不足
if/else内注释的代码为简化版本
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define float doublevoid solve(){int n,k,l;cin>>n>>k>>l;vector<float>a(n+1);for(int i=1;i<=n;i++)cin>>a[i];float ans=a[1];float x=k;for(int i=2;i<=n;i++){if(x>=l)break;if(a[i]>x){// a[i]=max(x,a[i]-ans);// ans+=(a[i]-x)/2.0;// x=(a[i]+x)/2.0+k;if(x>=a[i]-ans){a[i]=x;x+=k;}else{a[i]-=ans;ans+=(a[i]-x)/2.0;x=(a[i]+x)/2.0+k;}}else{// a[i]=min(x,a[i]+ans);// x=a[i]+k;if(x<=a[i]+ans){a[i]=x;x+=k;}else{a[i]+=ans;x=a[i]+k;}}}if(x<l)ans+=l-x;cout<<(int)(ans*2)<<endl;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _;cin>>_;//_=1;while(_--)solve();return 0;
}