2023 (ICPC) Jiangxi Provincial Contest -- Official Contest

2023 (ICPC) Jiangxi Provincial Contest -- Official Contest

 A - Drill Wood to Make Fire

思路：n>=s*v

B - Wonderful Array

思路：对a进行a%m，不会对结果造成影响，则0<=b_i+1-b_i<m。可以求b_i+1%m<b_i%m的个数，等价于b_i+1/m>b_i/m，整体来看，就是求bn/m

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
#define int long long


int k,n,m,x,ans=0;
int a[N],b[N],all=0;
void solve(){
    cin>>k;
    for(int i=1;i<=k;++i){
        cin>>a[i];
    }
    cin>>n>>m>>x;x%=m;
    for(int i=1;i<=k;++i){
        a[i]%=m;
        all+=a[i];
    }
    int c=ceil(1.0*n/k)-1,s=n-c*k;
    b[1]=x+c*all+a[1];
    for(int i=2;i<=s;++i){
        b[i]=a[i]+b[i-1];
    }
    ans=n-(b[s]/m);
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

I - Tree

思路：用f[i]维护所有到i点的边的边权异或和，对于修改操作x→y，可以看出x→y中除了x和y以外的点的f不变，修改x和y点的f即可

#include<bits/stdc++.h>
using namespace std;
int f[500005];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for (int i = 0; i < n-1; ++i) {
        int x,y,z;
        cin>>x>>y>>z;
        f[x]^=z;
        f[y]^=z;
    }
    while(k--){
        int op;
        cin>>op;
        if(op==2){
            int x;
            cin>>x;
            cout<<f[x]<<'\n';
        }
        else{
            int x,y,z;
            cin>>x>>y>>z;
            f[x]^=z,f[y]^=z;
        }
    }
}

J - Function

思路：由于a，b小于等于n，当询问x=c时，经过x=c的函数f在x=c±√n范围内，枚举每一个范围内的f即可（当y=n，b=1（极限）时，n=（x-a）²+1，可知x在±√n内的函数可达到x=a；对于增加操作，由于询问只求最小的函数值，维护每个a（x）的最小b即可

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
//#define int long long


int n,c[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>c[i];
    int m;
    cin>>m;
    int s= ::sqrt(1.0*n);
    while(m--){
        int op,a,b;
        cin>>op;
        if(op){
            cin>>a;
            int ans=INF;
            for(int i=0;i<=s;++i){
                int l=a-i,r=a+i;
                if(l>0&&c[l])ans=min(ans,(a-l)*(a-l)+c[l]);
                if(r<=n&&c[r])ans=min(ans,(a-r)*(a-r)+c[r]);
            }
            cout<<ans<<'\n';
        }
        else{
            cin>>a>>b;
            c[a]=min(c[a],b);
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

K - Split

思路：序列是不递增的，分成k段，每个分段点i对答案的贡献为a[i+1]-a[i]，那么求出差分，找出前k-1个即可

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
//#define int long long


int n,a[N],b[N];
void solve(){

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
        if(i)b[i]=a[i]-a[i-1];
    }
    sort(b+1,b+n);
    for(int i=1;i<n;++i){
        b[i]+=b[i-1];//cout<<b[i]<<' ';
    }//cout<<'\n';
    int m;
    cin>>m;
    while(m--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            cout<<a[0]-a[n-1]+b[x-1]<<'\n';
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

L - Zhang Fei Threading Needles - Thick with Fine

思路：n-1