本文主要是介绍Codeforces Round 827 (Div. 4)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
A. Sum
B. Increasing
C. Stripes
D. Coprime
E. Scuza
F. Smaller
G. Orray
A. Sum
给定3个数求存不存在两个数之和等于另一个数
我们直接排序求和简单判断即可
void solve()
{vector<int> a(3);for(auto&v:a) cin>>v;sort(a.begin(),a.end());cout<<(a[0]+a[1]==a[2] ? "YES" : "NO")<<endl;return ;
}B. Increasing
能否排序之后严格单调增,判断是否重复即可
void solve()
{cin>>n;vector<int> a(n);for(auto&v:a) cin>>v;sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());cout<<( (int)a.size()==n ? "YES" : "NO")<<endl;return ;
}C. Stripes
注意行只能是R,竖只能是B,所以判断有没有一行全是R即可
void solve()
{n=8;bool ok=false;for(int i=1;i<=n;i++){string a; cin>>a;ok |= count(a.begin(),a.end(),'R')==8;} cout<<(ok ? "R" : "B")<<endl;return ;
}D. Coprime
厚此薄彼,注意每一个维度的大小
我们可以明显发现,的数值是很小的,n是2e5的,
<=1000,所以我们考虑对它处理,可以直接做一个
的预处理然后暴力数值来处理即可
#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=1e6+10;
vector<int> a[N];
int n,t;
int p[M],st[N];
void intn()
{for(int i=1;i<=1000;i++)for(int j=1;j<=1000;j++)if(gcd(i,j)==1){a[i].push_back(j);a[j].push_back(i);}
}
int main ()
{intn();cin>>t;while(t--){cin>>n;memset(st,0,sizeof st);for(int i=1;i<=n;i++){cin>>p[i];st[p[i]]=i;}int ans=-1;for(int i=1;i<=1000;i++)if(st[i]){for(auto t:a[i])if(st[t]){ans=max(ans,st[i]+st[t]);}}cout<<ans<<endl;}return 0;
}E. Scuza
前缀和优化 + (双指针 or 二分)
我们是否能抵达就取决于我们的一步是不是比到这个点中出现的所有的长度有关系,所以我们可以
按腿长度来排序接着双指针来判断是不是可以到达当前点,或者对跨度做前缀最大值优化
PII c[N];
int n,m;
int t;
int main()
{cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++) {cin>>a[i];s[i]=a[i]+s[i-1];}for(int i=1;i<=m;i++){cin>>b[i];c[i]={b[i],i};}sort(c+1,c+1+m);int l=1;for(int i=1;i<=n;i++)while(l<=m&&c[l].first<a[i])ans[c[l++].second]=s[i-1];while(l<=m) ans[c[l++].second]=s[n];for(int i=1;i<=m;i++) cout<<ans[i]<<" ";cout<<endl;}return 0;前缀最大值优化二分
int a[N];
LL s[N];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];a[i]=max(a[i],a[i-1]);}while(m--){int x; cin>>x;int l=0,r=n;while(l<r){int mid=l+r+1>>1;if(a[mid]>x) r=mid-1;else l=mid;}cout<<s[l]<<' ';}cout<<endl;return ;
}F. Smaller
字典序是按照前面的字母来的和长度没有关系
注意我们要的是让a<b那么只有b有其他的就直接放最
LL a[26],b[26];
void solve()
{cin>>n;a[0]=b[0]=1;memset(a,0,sizeof a);memset(b,0,sizeof b);for(int i=1;i<=n;i++){int op,k; string s; cin>>op>>k>>s;if(op==1){for(int i=0;s[i];i++)a[s[i]-'a']+=k;}else{for(int i=0;s[i];i++)b[s[i]-'a']+=k;}bool ok=0;for(int i=1;i<26;i++){if(b[i]) ok=true;}if(ok){cout<<"YES"<<endl;continue;}for(int i=1;i<26;i++) if(a[i]) ok=true;if(ok){cout<<"NO"<<endl;continue;}if(a[0]>=b[0]) cout<<"NO"<<endl;else cout<<"YES"<<endl;}return ;
}G. Orray
给定一个排列要求我们重新排列使得前缀或最大
我们可以考虑这样一个问题对于或或者与 | & 我们更加需要使用拆位因为他们不具有区间的属性前缀的属性
我们发现最多logn次选择后面的就可以随便选择了 所以直接排序之后把最大的数放在前面然后每次来选择最优
如果不再变化后面的随便输出即可
气那么就好,接着如果a有其他的肯定是
不行的,如果否是只有’a’那就是比较a的数量
LL a[N];
bool st[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i],st[i]=false;sort(a+1,a+1+n,greater<int>());cout<<a[1]<<" ";LL now=a[1];st[1]=true;while(1){LL pos=0,maxn=-1;for(int i=1;i<=n;i++){if(st[i]) continue;if((a[i]|now)>=maxn){maxn=a[i]|now;pos=i;}}if(maxn==-1||maxn==now) break;st[pos]=true;cout<<a[pos]<<" ";now=maxn;}for(int i=1;i<=n;i++)if(!st[i]) cout<<a[i]<<" ";cout<<endl;return ;
}这篇关于Codeforces Round 827 (Div. 4)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
