练习记录-cf-Codeforces Round 909 (Div. 3)(A-G)-526互联

好久没打div了然后思维太差现在被抓回来继续打了QWQ

终于被我逮到一场G数据结构的 ak了既然ak了就开心地写下题解别被hack别被hack别被hack

这场挺简单的之前打的div3都好难qaq

A. Game with Integers

题意：给一个数字，两人轮流操作，可以+1或者-1 先手能把这个数变成3的倍数就获胜，否则失败

解法：先手第一步不能变成3的倍数那么永远都不行，所以就判这个数+1/-1是不是3的倍数

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
void solve(){
    int n;cin>>n;
    if((n-1)%3==0||(n+1)%3==0){
        cout<<"First\n";
    }
    else{
        cout<<"Second\n";
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--)
    solve();
}

View Code

B. 250 Thousand Tons of TNT

题意:你需要选一个k k能整除n，然后从前往后每k个装一车，问两车最大的差值的最大值

解法:枚举n的所有因子，用前缀和快速处理出1-k k+1-2*k ...的重量，然后记录最大最小值，一直取max就好了

复杂度证明:可能写的不太准，一个1e5的数的因子应该不超过17个（全是2的情况最多），那么不同因子的排列组合方法一共有2^17种，所以枚举的复杂度不超过1e5，中间还有重复，我算不太来，反正挺符合的（）。然后用前缀和加速就是里面O1 总体1e5

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define int ll
int a[MAXN];
int pre[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    } 
    int ans=0;
    for(int i=1;i<n;i++){
        if(n%i) continue;
        int mx=0,mn=inf; 
        for(int j=1;j<=n;j+=i){
            int st=j,ed=j+i-1;
            mx=max(mx,pre[ed]-pre[st-1]);
            mn=min(mn,pre[ed]-pre[st-1]);
        }
        if(mn!=inf)
        ans=max(ans,mx-mn);
    }
    cout<<ans<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

C. Yarik and Array

这题不多说最大区间和dp改下就行了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int dp[MAXN],a[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) dp[i]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(i==1||(abs(a[i]%2)!=abs(a[i-1]%2))){
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        else dp[i]=a[i];
    }
    int ans=inf*-1;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

D. Yarik and Musical Notes

题意：问对于任意两个aiaj，满足匹配的2^ai,2^aj有多少对，匹配方法就是互相pow相等

解法：打了个表发现对于两个不同的数只有（1,2）是符合情况的，相同的肯定符合，map记录出现次数然后组合一下就行了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
map<int,int> mp;
void solve(){
     int n;cin>>n;
     mp.clear();
     for(int i=1;i<=n;i++){
         int a;cin>>a;
         mp[a]++;
     }
     int t1=mp[1];
     int t2=mp[2];
     int ans=0;
     ans+=t1*t2;
     for(auto &it:mp){
         int cnt=it.second;
         if(cnt>=2){
             ans+=(cnt*(cnt-1))/2;
         }
     }
     cout<<ans<<"\n";
    
}
signed main(){
    close;
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

E. Queue Sort

题意：题目给出排序方法：先把第一个元素塞到最后，然后一直往前挪直到前面的数小于等于这个数。问能否通过有限次排序让数组递增，并输出最少次数

解法：分析一下-1的情况，我们发现如果此时头是最小值（相同取最左边），那么不管怎么挪后面都动不了了，所以我们判一下最小值在哪，后面是否升序就行了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int a[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int mx=1;
    for(int i=1;i<=n;i++){
        if(a[i]<a[mx]){
            mx=i;
        }
    }
    int flag=1;
    for(int i=mx+1;i<=n;i++){
        if(a[i]<a[i-1]) flag=0;
    }
    if(!flag){
        cout<<"-1\n";
        return;
    }
    cout<<mx-1<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

F. Alex's whims

题意：构造一棵树，每给出一次询问x，表示需要移动至多一个节点让树上存在两个距离为x的叶子节点，输出移动方案

解法：我发现，对于一个链（1-2-3-..-n），叶子节点距离为n-1，如果我们把最后一个节点放到2节点上那长度就变成2,3上就变成3....这是一个很有意思的规律，所以它要求长度是哪个我们就把节点n移动到哪个节点上就行了

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
void solve(){
    int n,q;cin>>n>>q;
    for(int i=1;i<n;i++){
        cout<<i<<" "<<i+1<<"\n";
    }
    int now=n-1;
    while(q--){
        int k;cin>>k;
        if(k==now){
            cout<<"-1 -1 -1\n";
            continue;
        }
        else{
            cout<<n<<" "<<now<<" "<<k<<"\n";
            now=k;
        }
    }
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

G. Unusual Entertainment

题意：q次询问，问一个打乱的排列l-r中，是否有点在x的子树内

解法：很容易想到，我们可以通过dfs维护dfs序，然后dfn在一个连续区间内的点都在x的子树内，此处我拉的树剖板子。

问题现在转化成了对于一个区间l-r 是否有数字的dfn在一个连续区间ab内。

对这个问题我们考虑离线然后扫描线对于一个单独的问题，我们需要知道在l-1以前 dfn在（a，b）内的数有x个，以及在r以前（ a,b）区间的数有y个，这样的话如果y比x大，就说明在l-r里面增加了新的属于（a，b）的数那么对于这个询问答案就是yes 否则no

在树状数组上统计（a，b）的答案

就for一遍排列数组，然后对在每个点上的询问，分别记录两个ans 最后看是否变大就是答案了

记得清空算dfn的东西和询问和把加的树状数组减回去

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
vector<int> adj[MAXN];
vector<array<int,4> > Q[MAXN];
int a[MAXN];
int siz[MAXN],f[MAXN],hson[MAXN],deep[MAXN],top[MAXN],dfn[MAXN],rdfn[MAXN],rak[MAXN],cnt;
int t[MAXN];
int ans[2][MAXN];
int lowbit(int x) {
    return x&-x;
}
ll getsum(int x) {
    ll sum=0;
    while(x) {

        sum+=t[x];
        x-=lowbit(x);
    }
    return sum;
}
void addv(int x,int val) {
    while(x<=MAXN) {
        t[x]+=val;
        x+=lowbit(x);
    }
}
void tree_build(int u,int fa) {//重链优先搜索
    siz[u]=1;
    f[u]=fa;
    hson[u]=0;
    for(auto &v:adj[u]) {
        if(v==fa) continue;
        deep[v]=deep[u]+1;
        tree_build(v,u);
        siz[u]+=siz[v];
        if(hson[u]==0||siz[v]>siz[hson[u]]) hson[u]=v;
    }
}
void tree_decom(int u,int t) {//dfn序
    top[u]=t;
    cnt++;
    dfn[u]=cnt;
    rak[cnt]=u;
    if(hson[u]!=0) {
        tree_decom(hson[u],t);
        for(auto &v:adj[u]) {
            if(hson[u]!=v&&v!=f[u]) tree_decom(v,v);
        }
    }
    rdfn[u]=cnt;
}
void solve() {
    cnt=0;
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=q;i++) ans[0][i]=0,ans[1][i]=0;
    for(int i=1; i<=n; i++) {
        adj[i].clear();
        Q[i].clear();
    }
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    tree_build(1,0);
    tree_decom(1,1);
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=q; i++) {
        int l,r,x;
        cin>>l>>r>>x;
        int a=dfn[x];
        int b=rdfn[x];
        Q[l].push_back({0,a,b,i});
        Q[r].push_back({1,a,b,i});
    }
    for(int i=1;i<=n;i++){
        for(auto &it:Q[i]){
            int ty=it[0];
            int a=it[1];
            int b=it[2];
            int id=it[3];
            if(ty==0)
            ans[ty][id]=getsum(b)-getsum(a-1);
        }
        int k=dfn[a[i]];
        addv(k,1);
        for(auto &it:Q[i]){
            int ty=it[0];
            int a=it[1];
            int b=it[2];
            int id=it[3];
            if(ty==1)
            ans[ty][id]=getsum(b)-getsum(a-1);
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[0][i]<ans[1][i]) cout<<"YES\n";
        else cout<<"NO\n";
    }
    for(int i=1;i<=n;i++) addv(i,-1);
    cout<<"\n";
}
signed main() {
    close;
    int t;
    cin>>t;
    while(t--)
        solve();
}

View Code

cf-codeforces codeforces round 909

codeforces round 909 div

cf-codeforces codeforces round 881

codeforces round 888 a-g

codeforces round 891 a-g

codeforces round div3 909

codeforces round 909 a-e

codeforces round 883 a-g

codeforces round 874 a-g

cf-codeforces