CF-Global-R-24解题报告

发表于 分类于

B. Doremy’s Perfect Math Class

题意：有一个集合 ss，初始有一些元素，每次操作可以选择两个元素并将它们的差加入集合。问若干次操作后集合内元素最多有多少个。

直觉告诉我们，集合中元素的 gcd⁡\gcd 的倍数都能出现（前提是小于等于最大值）。证明：考虑相邻元素通过若干次减法操作可以得到它们的 gcd⁡\gcd，再与下一个元素进行同样操作，最终得到所有元素的 gcd⁡\gcd。有了 gcd⁡\gcd 后，可以将最大值反复减 gcd⁡\gcd 得到所有元素。

By QAQAutoMaton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
namespace run{
    bool main(){
        int n;
        read(n);
        int g=0;
        int m=0;
        for(int i=1;i<=n;++i){
            int x;
            read(x);
            g=__gcd(g,x);
            chkmax(m,x);
        }
        write(m/g,'\n');
        return 0;
    }
}
signed main(){
#ifdef QAQAutoMaton
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
#endif
    int t;
    read(t);
    for(;t;--t)run::main();
    return 0;
}

C. Doremy’s City Construction

题意：给你一个数组 aa，你需要在元素之间连边，使得没有重边自环且边数尽可能多。要求不存在一组 x−y−zx-y-z 使得 ax≤ay≤aza_x\le a_y\le a_z。输出最多边数。

考虑贪心。首先数组的顺序没有关系，所以可以进行排序，问题转化为不存在左-中-右的一条链。于是可以转化为，每个点要么往左连要么往右连。所以答案一定为分界线左边全部往右连，分界线右边全部往左连。答案即为两边点数的乘积。需要注意的是，左右两边不能有相同元素（否则不满足条件）。枚举分界线取最大值即可。所有元素相同需要特判。

By maroonrk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void slv(){
    int n;cin>>n;
    vi a=readvi(n);
    sort(all(a));
    int ans=n/2;
    rng(i,1,n)if(a[i-1]<a[i])chmax(ans,i*(n-i));
    print(ans);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int t;cin>>t;rep(_,t)
    slv();
}

D. Doremy’s Pegging Game

题意：有 nn 个钉子，标号 1∼n1\sim n，以正 nn 边形的顶点形状排列，正中间有一个较小的钉子。初始时一个橡皮筋绕着这 nn 个顶点，每次可以任意拿走一个钉子（除了中间的特殊钉子），直到橡皮筋碰到中间的钉子时停止。特殊地，在 nn 为偶数时正对面的两个钉子缠绕不会碰到中间的钉子（因为较小）。求拿走钉子的方案数（考虑顺序）。

可以考虑最终状态。容易发现，最终状态一定是一些钉子聚集在某一半，而另一边的钉子全部删空了。此时聚集的这一半只与两端的钉子位置有关，中间的钉子任何状态都有可能。于是可以枚举这两段的钉子的距离 ii，考虑剩下的如何填。首先有一个想法，剩下的任意顺序取都可以，但这是不对的。由于这是最终状态，而一旦碰到中间钉子就会停止，所以要求最终状态的上一步还没有碰到中间钉子。所以最后一步其实是有限制的，而限制的区间则与两段钉子的距离相等。

实现上，枚举距离 ii，再枚举最终状态下除了端点还剩的钉子个数 jj，则答案为 i×(i−1j)×(n−3−j)!i\times\binom{i-1}{j}\times (n-3-j)!。由于聚集的那一半位置可以仁义移动，还要再乘 nn。

By QAQAutoMaton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
namespace run{
    Z fac[5005],inv[5005],invf[5005];
    Z C(int a,int b){return fac[a]*invf[b]*invf[a-b];}
    bool main(){
        int n;
        read(n,p);
        fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
        for(int i=2;i<=n;++i){
            fac[i]=fac[i-1]*i;
            inv[i]=(p-p/i)*inv[p%i];
            invf[i]=inv[i]*invf[i-1];
        }
        Z ans(0);
        for(int i=1;i<=n-(n>>1);++i){
            Z c=0;
            for(int l=i+1;l<=n;++l)if(l-i-1<(n>>1) && (n-l)<(n>>1)){
                ++c;
            }
            c*=n;
            Z v=0;
            if(i==1)v=fac[n-2];
            else{
                for(int j=0;j<=i-2;++j)v+=C(i-2,j)*fac[n-3-j];
            }
            ans+=v*c;
        }
        write(ans.x,'\n');
        return 0;
    }
}

E. Doremy’s Number Line

题意：有一个整数数轴，初始每个点都没有颜色。你有 nn 种操作，第 ii 种操作有两个属性 ai,bia_i,b_i。进行操作时，你可以选择一个没涂色的位置 xx 涂上颜色 ii，要求：要么 x≤aix\le a_i，要么存在一个涂过色的 y≤aiy\le a_i 且 x≤y+bix\le y+b_i。你可以以任意顺序执行这些操作，但每种最多一次，问是否能将 kk 染成颜色 11。

首先有一个显然的推论：操作顺序固定时，设最后一次染的位置的最大值为 xx，则一定可以通过微调来染到 ≤x\le x 的任意位置。

可以倒序考虑。要想将 kk 染成颜色 11，则最后一次操作一定为 11 操作。若 k≤a1k\le a_1 则可以直接染，否则必须有“跳板 xx”。容易发现，xx 必须 ≥k−b1\ge k-b_1。由于如果能取到更大，则一定也能取到最小值，所以可以要求 x=k−b1x=k-b_1。问题转化为是否通过 2∼n2\sim n 操作来涂上 xx。

考虑哪些操作可能覆盖到 xx：要么 ai≥ya_i\ge y，要么 ai+bi≥ya_i+b_i\ge y（后者包含前者）。如果有满足前者要求的操作，则显然有解；如果有大于等于两个满足后者要求的操作也有解。证明：设该两个操作分别为 i,ji,j 且 ai≤aja_i\le a_j，则可以先通过 jj 操作涂上 aia_i 位置，再通过 ii 操作涂上 ai+bia_i+b_i 位置。如果没有满足后者要求的操作则无解。

现在只剩一种可能的情况：有且仅有一种满足后者要求的操作。此时可以直接使用该操作，即让 x←x−bix\leftarrow x-b_i。每一步均如此递归处理即可。