2023江西省赛

Dashboard - 2023 (ICPC) Jiangxi Provincial Contest -- Official Contest - Codeforces

A - Drill Wood to Make Fire

void solve()
{
    int s,v;
    cin>>n>>s>>v;
    if(s*v>=n) cout<<1<<endl;
    else cout<<0<<endl;
}

L - Zhang Fei Threading Needles - Thick with Fine

void solve()
{
    cin>>n;
    cout<<n-1<<endl;
}

I - Tree

#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 1e6 + 10 , INF = 2e9;

int n,q;
int e[N],h[N],ne[N],w[N],idx;
int v[N];

void add(int a,int b,int c)
{
    w[idx]=c;
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void solve()
{
    cin>>n>>q;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y,z;
            cin>>x>>y>>z;
            v[x]^=z,v[y]^=z;
        }
        else
        {
            int x;cin>>x;
            int res=0;
            for(int i=h[x];~i;i=ne[i])
            {
                int t=w[i];
                // look(t);
                res^=w[i];
            }
            res^=v[x];
            cout<<res<<endl;
        }
    }
}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","r",stdin);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}

J - Function

思路：

注意到bi<=n 所以x=a的答案最多为n

对于x=a的最小值 首先考虑对称轴为x=a的函数 ans=min(bi);
对于其他对称轴来说 想要比ans还小 则(a-ai)^2+bi的值一定要小于等于n
也就是(a-ai)^2+bi<=n 则a-sqrt(n-bi)<=ai<=a+sqrt(n-bi)
当bi=0时 x的范围最大 为2sqrt(n);
所以直接枚举即可

/*
J - Function

 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 1e6 + 10 , INF = 2e9;

int n;
vector<int> b[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        b[i].push_back(x);
    }

    int q;cin>>q;
    while(q--)
    {
        int op;
        cin>>op;
        if(op==0)
        {
            int x,y;
            cin>>x>>y;
            b[x].push_back(y);
        }
        else
        {
            int a;
            cin>>a;

            int l=max(1ll,a-(int)sqrt(n)-1ll),r=min(n,a+(int)sqrt(n)+1ll);
            int ans=1e18;

            for(int i=l;i<=r;i++)
            {
                for(int j=0;j<b[i].size();j++)
                {
                    ans=min(ans,b[i][j]+(a-i)*(a-i));
                }
            }
            cout<<ans<<endl;
        }
    }

}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","r",stdin);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}

K - Split

思路：

首先考虑查询操作
由于序列是非递增的所以每一段的差值就是左端-右端 进一步的 把相邻数差分 答案也就是这些差分的和
哪些差分需要去掉能使答案最小
假设有一组数 49 39 28 8 3 1
差分为 10 11 29 5 2
如果k=3 假设分成[49][39,..,8][3,1] 那么答案为11+29+2
可以发现49-39之间的10 和 8-3之间的5 不被计算
也就是说分成k个区间后有k-1个差分的数不会被计算
要使答案最小则去掉k-1个最大的差分数即可

对于修改操作
a[x-1],a[x],a[x+1]----a[x-1],a[x-1]+a[x+1]-a[x],a[x+1]
对于差分的数来说 可以发现没有变化 所以 修改操作不会改变整体差分的数的值

/*
K - Split
 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 1e6 + 10 , INF = 2e9;

int n;
int a[N],b[N],s[N];

void solve()
{
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i!=1)
            b[++cnt]=a[i-1]-a[i];
    }

    sort(b+1,b+cnt+1);

    // for(int i=1;i<=cnt;i++)
    //     cout<<b[i]<<" \n"[i==n];
    // look(cnt);

    for(int i=1;i<=cnt;i++)
        s[i]=s[i-1]+b[i];

    int q;
    cin>>q;
    while(q--)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            cout<<s[cnt-x+1]<<endl;
        }
    }

}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","r",stdin);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}