CF979
CF979(div2)
A. A Gift From Orangutan(贪心)
题意:有一个长度为n的数组a,构造数组b和c,存在bi=数组a的最小值,ci=数组a的最大值,求∑i=1nci-bi的最大值
分析:让数组b全部都赋值为a的最小值,数组c全部赋值为a的最大值
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; void sol(){int n;cin>>n;int a[n+10];for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int sum=0;for(int i=1;i<n;i++){sum+=a[n]-a[1];}cout<<sum<<endl; } int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0; }
B.Minimise Oneness(构造)
题意:对于任意二进制字符串t,设ft是t的子序列中只包含0的个数,gt是t的子序列中至少包含一个1的个数,给定|ft-gt|,求t。子序列可以不连续
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; void sol(){int n;cin>>n;for(int i=1;i<n;i++){cout<<"0";}cout<<"1"<<endl; } int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0; }
C. A TRUE Battle(博弈)
题意:给定一个二进制字符串,Alice和Bob先后可以放&或|放入两个字符中间,如果最后放完的答案是true,输出YES,否则NO
分析:对于最左边的1来说,如果插入|无法改变它,同理右边。如果存在11,可以插入|,形成1|1,无法改变它。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; void sol(){int n;cin>>n;string s;cin>>s;int len=s.size();if(s[0]=='1'||s[len-1]=='1'){cout<<"YES"<<endl;return ;}for(int i=0;i<len-1;i++){if(s[i]=='1'&&s[i+1]=='1'){cout<<"YES"<<endl;return;}}cout<<"NO"<<endl;return; } int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0; }
D. QED's Favorite Permutation(排序)
题意:给定长度为n的排序p,字符串s,QED喜欢非递减排序的排列,可以进行以下任意次操作:1.选择索引i,使得si=L,交换pi和pi-1 2.选择索引i,使得si=R,交换pi和pi+1,给定q个查询,每次查询,选择一个索引i,并将si从L更改为R或R更改为L,这些更改都是持久的
分析:
LR串只有四种情况
...LLL.....循环向左
....RRR...循环向右
....RL....互相交换
....LR...以LR中间为分界线
只要不存在LR的情况一定可以排好序
用数组ok记录每个数字和前面的数是否有大于当前牵引的数,用数组qe判断LR的存在,如果最后问题cnt=0就可以排好序
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; bool ok[N]; int qe[N],a[N]; void sol(){int n,q;cin>>n>>q;for(int i=1;i<=n;i++){ok[i]=false;qe[i]=0;cin>>a[i];} string s;int maxn=0;cin>>s;s='#'+s;for(int i=1;i<=n;i++){maxn=max(maxn,a[i]);if(maxn>i){ok[i]=true;}}int cnt=0;for(int i=1;i<=n-1;i++){if(ok[i]&&s[i]=='L'&&s[i+1]=='R'){cnt++;qe[i]=1;}}while(q--){int id;cin>>id;if(s[id]=='L'){s[id]='R';if(s[id+1]=='R'&&qe[id]==1){qe[id]=0;cnt--;}if(s[id-1]=='L'&&ok[id-1]){qe[id-1]=1;cnt++;}}else if(s[id]=='R'){s[id]='L';if(s[id-1]=='L'&&qe[id-1]==1){qe[id-1]=0;cnt--;}if(s[id+1]=='R'&&ok[id]){qe[id]=1;cnt++;}}if(cnt==0)cout<<"YES"<<endl;else cout<<"NO"<<endl;} } int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0; }