L - Recover Statistics

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    cout<<100<<'\n';
    for(int i=1;i<=49;i++) cout<<1<<' ';
    cout<<a<<' ';
    for(int i=51;i<=95;i++) cout<<b<<' ';
    for(int i=96;i<=99;i++) cout<<c<<' ';
    cout<<c+1<<'\n';
    return 0;
}

A. Arrow a Row

statements

G - Expanding Array

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    set<int> s;
    for(int i=2;i<=n;i++){
        int x=a[i-1],y=a[i];
        s.insert(x);
        s.insert(y);
        s.insert(x|y);
        s.insert(x&y);
        s.insert(x^y);
        s.insert(x&(x^y));
        s.insert(y&(x^y));
        s.insert(0);
    }
    cout<<s.size()<<'\n';
    return 0;
}

J - Grand Prix of Ballance

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct people{
    int id,score,giveup;
}p[N];
bool cmp(people a,people b){
    if(a.score!=b.score) return a.score>b.score;
    return a.id<b.id;
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    int now=0;
    int cnt=m;
    vector<int> tmp;
    for(int i=1;i<=m;i++) p[i].id=i,p[i].score=0,p[i].giveup=0;
    while(q--){
        int op,id,x;
        cin>>op;
        if(op==1){
            cin>>x;
            now=x;
            cnt=m;
            for(int id:tmp) p[id].giveup=0;
            tmp.clear();
        }
        else if(op==2){
            cin>>id>>x;
            if(x==now&&!p[id].giveup){
                p[id].score+=cnt;
                p[id].giveup=1;
                tmp.push_back(id);
                cnt--;
            }
        }
        else{
            cin>>id>>x;
            if(x==now){
                p[id].giveup=1;
                tmp.push_back(id);
            }
        }
    }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++) cout<<p[i].id<<' '<<p[i].score<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

I - Good Partitions

statements

称满足的下标为断点，显然好的划分大小需使得 与 在不同的划分序列中，即划分大小是断点的因数。答案即是所有断点的gcd的因数个数。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs (p<<1)|1
using namespace std;
const int N=2e5+10;
struct node{
    int l,r,g;
}tr[4*N];
int arr[N];
void pushup(int p){
    tr[p].g=__gcd(tr[ls].g,tr[rs].g);
}
void build(int p,int l,int r){
    //只有当时叶子结点时对sum的直接赋值有意义
    tr[p]={l,r,(arr[l]>arr[l+1])?l:0};
    if(l==r) return ;
    int m=(l+r)>>1;
    build(ls,l,m);
    build(rs,m+1,r);
    pushup(p);
}
void update(int p,int x,int k){
    if(tr[p].l==tr[p].r){
        tr[p].g=k;
        return ;
    }
    int m=(tr[p].l+tr[p].r)>>1;
    if(x<=m) update(ls,x,k);
    else update(rs,x,k);
    pushup(p);
}
int query(int p,int x,int y){
    if(x<=tr[p].l&&tr[p].r<=y) return tr[p].g;
    int m=(tr[p].l+tr[p].r)>>1;
    int g=0;
    if(x<=m) g=__gcd(g,query(ls,x,y));
    if(y>m) g=__gcd(g,query(rs,x,y));
    return g;
}
int primes[N],cnt=0;
bool vis[N];
int a[N],d[N];
//a[i]存放a[i]的最小质因子的次数
void euler(int n){
    d[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            primes[++cnt]=i;
            a[i]=1,d[i]=2;
        }
        for(int j=1;i<=n/primes[j];j++){
            int m=primes[j]*i;
            vis[m]=1;
            if(i%primes[j]==0){
                a[m]=a[i]+1;
                d[m]=d[i]/a[m]*(a[m]+1);
                break;
            }
            else{
                a[m]=1;
                d[m]=d[i]*2;
            }
        }
    }
}
void solve(){
    int n,q;
    cin>>n>>q;
    d[0]=n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    if(n==1){
        cout<<1<<'\n';
        while(q--){
            int p,v;
            cin>>p>>v;
            cout<<1<<'\n';
        }
    }
    else{
        build(1,1,n-1);
        cout<<d[query(1,1,n-1)]<<'\n';
        while(q--){
            int p,v;
            cin>>p>>v;
            if(p>1&&arr[p-1]<=arr[p]&&arr[p-1]>v) update(1,p-1,p-1);
            if(p>1&&arr[p-1]>arr[p]&&arr[p-1]<=v) update(1,p-1,0);
            if(p<n&&arr[p]<=arr[p+1]&&v>arr[p+1]) update(1,p,p);
            if(p<n&&arr[p]>arr[p+1]&&v<=arr[p+1]) update(1,p,0);
            arr[p]=v;
            cout<<d[query(1,1,n-1)]<<'\n';
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    euler(N-10);
    while(t--) solve();
    return 0;
}

参考题解

(20 封私信 / 80 条消息) The 2024 ICPC Asia Chengdu Regional Contest部分题解 - 知乎
2024.11.2 2024ICPC成都站 - EssnSlaryt - 博客园