Codeforces Round 827 (Div. 4) 7

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

厚此薄彼,注意每一个维度的大小

我们可以明显发现${a_i}$的数值是很小的,n是2e5的,${a_i}$<=1000,所以我们考虑对它处理,可以直接做一个${n^2}$的预处理然后暴力数值来处理即可

#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有其他的就直接放最气那么就好,接着如果a有其他的肯定是
不行的,如果否是只有’a’那就是比较a的数量

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次选择后面的就可以随便选择了 所以直接排序之后把最大的数放在前面然后每次来选择最优

如果不再变化后面的随便输出即可

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 ;
}