codeforces水题

水博客

反省为什么练了这么久还这么拉
可能真是sb
zhihu偷图

round#826
D:
题意：一颗二叉树的所有最小儿子上分布着1-n的不同数，问时候可以交换任意个结点的左右儿子，使得最后最小儿子从左到右递增排序，输出ans值

dfs跑一下

int a[N],ans=0;
void dfs(int l,int r){
    if(l>=r)return ;
    if(l+1==r){
        if(a[l]>a[r]){
            swap(a[l],a[r]);
            ans++;
        }else return ;
    }
    dfs(l,(l+r)/2);
    dfs((l+r)/2+1,r);
    if(a[l]>a[(l+r)/2+1]){
        ans++;
        int k=(r-l)/2+1;
        rep(i,l,(l+r)/2){
            swap(a[i],a[i+k]);
        }
    }
}
void solve()
{
    int n;cin>>n;
    ans=0;
    rep(i,1,n)cin>>a[i];
    dfs(1,n);
    // rep(i,1,n)cout<<a[i]<<' ';
    // cout<<endl;
    rep(i,1,n)
    if(a[i]<a[i-1]){
        cout<<-1<<endl;
        return ;
    }
    cout<<ans<<endl;
}

F ：
题意：给定一个数组，问是否可以将其分为若干连续段，使得每一段的最左或最右值表示该段中其他元素的个数

左右dp一下

const int N=3e5+10;
int dp[N],a[N];
void solve()
{
    int n;cin>>n;
 
    rep(i,1,n)cin>>a[i];
 
    memset(dp,0,sizeof dp);
 
    dp[0]=1;
 
    rep(i,1,n){
        if(i>=a[i]+1)dp[i]|=dp[i-a[i]-1];
 
        if(a[i]+i<=n)dp[a[i]+i]|=dp[i-1];
    }
    if(dp[n])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

round#827
这道题卡了好久。。。
D:一个数组是否使得其中gcd(a[i],a[j])==1，求i+j的最大值

因为a[i]<=1000，所以map存一下暴力，我他妈脑子有坑,还用暴力tle了两发

map<int,int>p;
void solve()
{
    int n,ans=-1;cin>>n;
    p.clear();
    rep(i,1,n){
        int x;cin>>x;
        p[x]=i;
    }
    for(auto [x,y]:p){
        for(auto [xx,yy]:p){
            if(__gcd(xx,x)==1){
                ans=max(ans,y+yy);
            }
        }
    }
        cout<<ans<<endl;
}

E：前缀和，前最大值存一下二分

ll a[N],p[N],h[N];
void solve()
{
    ll n,m;cin>>n>>m;
    rep(i,1,n){
        cin>>a[i];
        p[i]=max(a[i],p[i-1]);
        h[i]=h[i-1]+a[i];
    }
    while(m--){
        ll x;cin>>x;
        ll l=1,r=n;
        while(l<=r){
            int k=(l+r)>>1;
            if(x>=p[k])l=k+1;
            else r=k-1;
        }
        cout<<h[r]<<' ';
    }
    cout<<endl;
}

F:问每次操作给初始字符串都为’a’的s和t加k次字符串x，是否可以排序使得a<b

记录操作后a和b的最大字符和长度

void solve() {
    int n,lens=1,lent=1;cin>>n;
    char maxs='a',maxt='a';
    rep(i,1,n){
        int o,k;string s;cin>>o>>k>>s;
        for(auto c:s){
            if(o==1) {
                maxs=max(maxs,c);
                lens+=k;
            } else {
                maxt=max(maxt,c);
                lent+=k;
            }
        }
        //如果maxt>'a'  ,那么必然可以使得成立
        //否则若a和b中都是'a'，那就比较长度
        if('a'<maxt||('a'==maxt&&'a'==maxs&&lens<lent))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        
    }
}

G:重新排列数组a，使得a的前缀异或和按最大排列

int二进制位只有三十多，所以排列前31次找出按位补1位的最大值，剩下的随便

int a[N],num;
bool cmp(int a,int b){
    return (a|num) > (b|num);
}
void solve()
{
    int n;cin>>n;
    num=0;
    rep(i,1,n)cin>>a[i];
    rep(i,1,min(31,n)){
    ///最多就30*nlog2n
        sort(a+i,a+n+1,cmp);
        num|=a[i];
    }
    rep(i,1,n)cout<<a[i]<<' ';
    cout<<endl;
}

起床想到的第一件事就是我怎么这么废，这都没ak，二十几号还有两门结课考试，忙去了。。。