Codeforces Round #827 (Div. 4) A - G

A. Sum

题意:

是否能凑出a+b=c

分析:

可以升序排序,看前两个之和是否等于第三个数,我是直接枚举哪个是最大值。

代码:

#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin >> t;
while(t --){
int a,b,c;
cin >> a >> b >> c;
int mmax = max({a,b,c});
if(a==mmax){
if(b + c == a)cout << "YES" <<endl;
else cout << "NO" <<endl;
}else if(b == mmax){
if(a + c == b)cout << "YES" <<endl;
else cout <<"NO"<<endl;
}else if(c == mmax){
if(a + b == c)cout << "YES"<<endl;
else cout << "NO"<<endl;
}
}
return 0;
}

B. Increasing

题意:

排序之后 a1 < a2 <⋯< an是否成立

分析:

直接排序,看有无相邻值相等即可

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
const int N = 110;
int a[N];

signed main(){
cin >> t;
while(t --){
int n;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> a[i];
}
sort(a, a + n);
int flag = 0;
for(int i = 1; i < n; i ++){
if(a[i] == a[i - 1]){
flag = 1;
break;
}
}
if(flag==1){
cout << "NO" << endl;
}else cout << "YES" <<endl;
}
return 0;
}

C. Stripes

题意:

蓝色涂列,红色涂行,看哪个是最后涂的

分析:

如果存在一行都是R,那么一定R是最后涂的,反证:假如R不是最后涂的,那么B必然有一格覆盖R成B

代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t --){
int flag = 0;
string s;
for(int i = 1; i <= 8; i ++){
cin >> s;
//count查看s中R的出现次数,新学到的一种统计方式(
if(count(s.begin(), s.end(),'R')== 8){
flag = 1;
}
}
if(flag){
cout<<"R"<<endl;
}else cout << "B" << endl;
}
return 0;
}

D. Coprime

题意:

是否能找两个数a[i],a[j] i可以等于j,使得a[i]和a[j]的最大公约数为1且i+j最大

分析:

注意n的极限范围2e5,双重循环n^2一定超时,a[i]的数据范围<1000,那么可以初始读a数组时,将每个数的最后下标记录下来,这样避免了重复值造成影响,然后枚举1-1000出现过的数更新下标和

代码:

#include<bits/stdc++.h>
using namespace std;
int T;
const int N = 2e5 + 10;
int a[N];
bool prime[1001];

int main(){
cin >> T;
while(T --){
int n;
map<int, int> mp;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
mp[a[i]] = i;
//存取下标
}
int mmax = -1;
for(int i = 1; i <= 1000; i ++){
for(int j = i; j <= 1000; j ++){
if(mp.count(i)&&mp.count(j) && __gcd(i,j)==1)
//更新下标和
mmax = max(mp[i] + mp[j], mmax);
}
}
cout << mmax << endl;
}
}

E. Scuza

Timur一次最多爬a[j]高的台阶,问一次一次爬能爬多高(极限)

分析:

找到不能爬的位置,也就是x < a[i]的时候,考虑一次一次枚举会超,可以二分,

二分前提要让a[i]有序,所以让a[i] = max(a[i], a[i - 1])使得具有单调性,查找第一个>x的位置 l,最后 l -1 即为最高处,用前缀和预处理直接输出s[l-1]即可

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
const int N = 2e5 + 10;
int a[N];
int s[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t --){
memset(a,0,sizeof a);
memset(s,0,sizeof s);
int n, q;
cin >> n >>q;
for(int i = 1; i <= n; i ++){
cin >> a[i];
s[i] = s[i - 1] + a[i];
//构造能够二分查找的a序列
a[i] = max(a[i -1],a[i]);
}
while(q --){
int x;
cin >> x;
int ans = 0;
int l = 0,r = n+1;
while(l < r){
//二分查找第一个不能爬到的位置
int mid = l + r >>1;
if(a[mid] > x)r = mid;
else l = mid + 1;
}
cout << s[r-1] <<" ";
}
cout << endl;
}
return 0;
}

F. Smaller

题意:

给s,t两个”a”加字符串,每轮加完看看能否让重排s,使其小于t

分析:

分类讨论:

如果t存在一个非a字符,不管s有没有非a的,由于t有a,我们可以重排s的a放在第一位,那么必然满足小于,输出”YES”。

如果t是纯a字符,s有非a,输出”NO”; s是纯a的串,比较两者的长度,s长则no

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,op,x;
string a;
signed main(){
cin >> t;
while(t --){
int slen = 0, tlen = 0,flag1=0,flag2=0;
cin >> n;
while(n --){
cin >> op >> x;
cin >> a;
if(op==1){
for(int i = 0; i <a.size(); i ++){
if(a[i]!='a'){
flag2 = 1;
}
}
slen += x*a.size();
}else{
for(int i = 0; i < a.size(); i ++){
if(a[i]!='a'){
flag1 = 1;
}
}
tlen += x*a.size();
}
if(!flag1&&flag2){
cout << "NO" <<endl;
}else if(flag1){
cout << "YES"<<endl;
}else if(slen<tlen)cout <<"YES"<<endl;
else cout <<"NO"<<endl;
}
}
return 0;
}

G. Orray

题意:

给定数组,求排序后的前缀OR最大的一个序列

分析:

第一个放最大的,使得后面都尽可能的大,之后放和前一个进行OR后贡献最大的数

代码:

#include<bits/stdc++.h>
using namespace std;
int T;
const int N = 2e5 + 10;
int a[N];
int st[N];
int main(){
cin >> T;
while(T --){
vector<int> ans;
int n;
cin >> n;
memset(st,0,sizeof st);
memset(a, 0, sizeof a);
for(int i = 1 ;i <= n; i ++)
cin >> a[i];
sort(a+1,a+n+1);
//cur为当前放进去的最新的数
int cur = a[n];
st[n] = 1;
ans.push_back(n);
while(true){
int pos=0;
int mmax = 0;
for(int i = n -1; i >= 1; i --){
if(st[i])continue;
//枚举给cur最大贡献的数
if((a[i] | cur) - cur > mmax){
mmax = (a[i] | cur) - cur;
pos = i;
}
}
if(mmax == 0)break;
cur = cur | a[pos];
ans.push_back(pos);
st[pos] = 1;
}
for(int i = 0; i < ans.size(); i ++){
cout << a[ans[i]] << " ";
}
for(int i = 1; i <= n; i ++){
if(!st[i])cout << a[i] <<" ";
}
cout << endl;
}
return 0;
}