2024CCPC网络赛

B 军训 II

对于这类问题一个很经典的思路就是求每个位置的贡献

首先能感性的判断出来从小到大/从大到小排不整齐度是最小的(因为最大/最小值都是依次递增的)

然后可以理性的证明一下：

对于已经排好序的数组a 有a1<=a2<=a3<=…<=an,此时交换a2,ak(假设a2<ak);

交换完的结果就是l在[1,k-1],r在[l,k-1]的区间内最大值变大，最小值不变,l在[k,n]，r在[l,n]的区间内最大值不变，最小值变小

身高相同的人可以交换位置,$A_{k}^k$,表示k个身高相同的人的排列方案,

注意特判全相等序列(从小到大和从大到小排列一样)

void solve(){
    int n;cin>>n;
    vector<int>a(n);
    map<int,int>mp;
    for(int i=0;i<n;i++){
        cin>>a[i];mp[a[i]]++;
    }
    sort(a.begin(),a.end());
    int ans1=0,ans2=1;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            ans1+=a[j]-a[i];
        }
    }
    auto A=[&](int x){
        int tem=1;
        for(int i=1;i<=x;i++){
            tem=(tem*i)%mod;
        }
        return tem;
    };
    a.erase(unique(a.begin(),a.end()),a.end());
    for(auto i:a){
        ans2=(ans2*A(mp[i]))%mod;
    }
    if(a.size()!=1) ans2=(ans2*2)%mod;
    cout<<ans1<<' '<<ans2<<endl;
}

K 取沙子游戏

考虑n的奇偶性

当n为奇数时，第一手取1必然获胜

当n为偶数时，考虑变成必胜态，即将n减去某两个数得到奇数，可知这两个数必然为一奇一偶，且先手必选偶数，当先手选择奇数后，后手必胜。

由于选择的是偶数，初步猜想寄了，因为后手必然不会选择奇数，所以后手选择偶数阻止先手到达必胜态，此时第二轮到达先手手上的数还是偶数，这样归纳一下可以发现当n为偶数的时候，先后手都只会选择偶数

考虑二进制，当先手第一次选择lowbit(n)时，后手无论选择什么我们都和其选择一样即可获胜，因为二进制下需要偶数次选择偶数才能将这个数归零