比赛地址:https://codeforc.es/contest/1726
A题:大意是给出一个数组a,然后可以选择一个l和r,可以使得l和r做任意次转换 al = al+1对于l - r之间的所有元素,其中ar = al。求出an - a1的最大值。
上来第一题感觉就不简单,wa了好几次。这个题需要分情况来讨论。
当选择l和r是整个范围,那么最大值就是ai - ai+1,因为我们总能够将ai置为an ,将ai+1置为a1.
同样的,如果a1存在一个小数,那么我们可以通过l和r来找 一个最大数,这样值就是max - a1. 右侧同理。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n,x; cin>>n; vector<int>ve; int maxt = 0,mint=9999; for(int i=1;i<=n;i++) cin>>x,ve.push_back(x),maxt=max(maxt,x),mint=min(mint,x); maxt = maxt - ve[0]; maxt = max(maxt,ve[n-1] - mint); for(int i=0;i<ve.size()-1;i++) maxt = max(maxt,ve[i]-ve[i+1]); maxt = max(maxt,ve[n-1]-ve[0]); cout<<maxt<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
B题:大意是给出一个n和m,有n个数总和为m,这n个数的互相异或的结果为0。求是否能构造,并输出构造。ai>0
如果n>m肯定无法构造
如果n是2的倍数,m不是2的倍数也无法构造。因为这样一定存在一个偶数异或一个奇数。
其他可以构造。
我们可以使得前缀2k个数全部为1,这样的异或一定是0。如果n不是2的倍数我们使得最后的数 为1 和一个m剩余的偶数;如果n是2的倍数,我们需要使得最后构造两个偶数,那么我们输出m剩余的m/2。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n,m; cin>>n>>m; if(n>m||(n%2==0&&m%2!=0)) cout<<"NO"<<endl; else{ cout<<"YES"<<endl; if(n%2==0){ for(int i=1;i<=n-2;i++) m--,cout<<1<<' '; m>>=1,cout<<m<<' '<<m<<endl; }else for(int i=1;i<=n;i++) m--,printf("%d%c",i==n?m+1:1,i==n?'\n':' '); } } int main() { //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:
也就是说如果存在一个内嵌的(),那么一定可以形成一个连通分量,再加上本身的连通的分量这样,连通分量的数量就是 ((或))数量+1
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n; cin>>n; string a; cin>>a; int ans = 0; for(int i=1;i<n*2;i++) if(a[i]=='('&&a[i-1]=='(') ans++; cout<<ans+1<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }