4.25 Codeforces Global Round 20 A

Codeforces Global Round 20 A"/>

4.25 Codeforces Global Round 20 A

Codeforces Global Round 20
A. Log Chopping
题意：俩人轮流掰n个东西，一个东西掰完之后分成两个，等到这些东西的数值到1了就不能掰了，到谁的回合没东西掰这人就输了，问你谁赢了

思路：递推预处理之后直接判断就行

#include <bits/stdc++.h>using namespace std;
const int N =3e5+100;
int dp[55];
int main()
{dp[1]=0;dp[2]=1;for(int i=3;i<=50;i++){dp[i]=dp[i/2]+dp[(i-1)/2+1]+1;}int t;for(cin>>t;t;t--){int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){int temp;cin>>temp;ans+=dp[temp];}if(ans%2){cout<<"errorgorn"<<endl;}else{cout<<"maomao90"<<endl;}}return 0;
}

B. I love AAAB
思路：首先最后一个字母必须为B否则白扯，其次对于每个位置的前缀和，A的数量必须大于等于B的数量

#include <bits/stdc++.h>using namespace std;
const int N =3e5+100;
int main()
{string s;int t;for(cin>>t;t;t--){cin>>s;if(s.length()<2||s[s.length()-1]!='B'){cout<<"NO"<<endl;continue;}bool falg=true;int ca=0,cb=0;for(int i=0;i<s.length();i++){if(s[i]=='A')ca++;elsecb++;if(ca<cb){falg=false;break;}}if(falg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}

C. Unequal Array

思路：贪心，证明略，找到最左最优的两个a[i]=a[i+1]和b[j]=b[j-1]，记录i+1和j-1，两者做差和1取最大值输出

注意特判a[i]=a[i+1]对数小于等于1的情况

#include <bits/stdc++.h>using namespace std;
const int N =3e5+100;
int a[N];
int main()
{int t;for(cin>>t;t;t--){int n;cin>>n;int pos1=0;int pos2=0;int con=0;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){if(a[i]==a[i+1]){con++;}}if(con<=1){cout<<0<<endl;continue;}for(int i=1;i<=n-1;i++){if(a[i]==a[i+1]){pos1=i+1;break;}}for(int j=n;j>=2;j--){if(a[j]==a[j-1]){pos2=j-1;break;}}int ans=pos2-pos1;cout<<max(ans,1)<<endl;}return 0;
}

D. Cyclic Rotation
题意：给定数组a，b，每次可以让数组a中满足a[l]==a[r]的区间[l，r]循环左移，问能否通过有限步骤令a和b相等

思路：对于a的反操作就是寻找到b[j]=b[j-1]后可以让b[j]放到b[j-1]前方位置，所以可以通过让a和b逐个比对当a[i]=b[j]便让i和j后移一位否则

1.检查之前是否有未配对的a中元素和目前的b[j]相等并且b[j]==b[j-1]，可以让b[j]抵消一个未配对的a中元素
2.如果1不符合，那么让i在不越界的情况下再向后移动一位，并且记录这个未配对成功的a中元素
3.1和2都不符合就可以跳出了，必然是不符合的

复杂度nlogn级别吧，，，，
这题先码一下，理解的不是很透彻，看的是严格鸽的思路，主要不能理解为什么b[j]可以变成b[j-1]前方任意一个位置。

#include <bits/stdc++.h>using namespace std;
const int N = 3e5+100;
int a[N];
int b[N];
int n;
int main()
{int t;for(cin>>t;t;t--){cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)cin >> b[i];map<int, int>cnt;int i = 1, j = 1;bool flag = 1;while (j <= n) {if (i <= n && a[i] == b[j])i++, j++;else {if (cnt[b[j]] && b[j] == b[j - 1])cnt[b[j]]--, j++;//动jelse if (i <= n)cnt[a[i]]++, i++;//动ielse { flag = 0; break; }}}if (flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

背包变型
B. Checkout Assistant
变型：每个物品价值为给定数值，题意为“在扫描这个物品的过程中，包括自身和偷盗的所有物品数量”，所以预处理原本的扫描时间加一就是每个物品的体积，贪心的来看，每个物品扫描时间为0那么背包容量就是n，否则应该是"体积最大值"+n（注意，这里的操作，实际上你可以想想，如果有个物品的扫描时间大于n，但是你的背包容量不能装下这个物品，你不就落下了一种最优解的可能吗，所以最低值n不重要，重要的是最大值）。

#include <bits/stdc++.h>using namespace std;
#define int long long
struct node
{int t,v;
};
node obj[2000+100];
int dp[5000];
signed main()
{int n;//freopen("in.txt","r",stdin);cin>>n;int maxxt=-1;for(int i=1;i<=n;i++){cin>>obj[i].t>>obj[i].v;obj[i].t++;maxxt=max(maxxt,obj[i].t);}maxxt+=n;for(int i=0;i<5000;i++)dp[i]=1e16;dp[0]=0;for(int i=1;i<=n;i++){for(int j=maxxt;j>=obj[i].t;j--){dp[j]=min(dp[j],dp[j-obj[i].t]+obj[i].v);}}int ans=1e9;for(int i=n;i<=maxxt;i++){ans=min(ans,dp[i]);}cout<<ans<<endl;return 0;
}