写一个牛牛的题解：这场前三题很简单，d分类分了半天，分不清楚，感觉写的时候脑子很乱。

然后E骗了一点分，剩下的题再补补吧。

把D,E补一补，剩下的F以后再说了 --------- 2024.9.9

1.TD

没啥写的，保留小数，基础操作

void solve()
{
   double n,m;
   cin>>n>>m;
   printf("%.8lf",n/m);
}

2.你好，这里是牛客竞赛

就是对于开头的网站进行匹配即可，后面的不需要管 用substr取下来即可

void solve()
{
    string s;
    cin>>s;
    string t = s.substr(0,24);
    string t1 = s.substr(0,23);
    string t2 = s.substr(0,16);
    string t3 = s.substr(0,15);
  //  cout<<t2<<" "<<t3<<" ";
    if(t=="https://www.nowcoder.com" || t2=="www.nowcoder.com"){
        cout<<"Nowcoder"<<endl;
    }
    else if(t1=="https://ac.nowcoder.com" || t3=="ac.nowcoder.com"){
        cout<<"Ac"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
  //  cout<<t<<endl;
}

3.逆序数

手搓一下样例就会发现，正反序列相加的个数正好等于这个序列长度的C(n,2)个 所以减一下就可以了

void solve()
{
    LL n,k;
    cin>>n>>k;
    LL ans = (n-1)*n/2;
    cout<<LL(ans-k);
}

4.构造mex

要分类讨论的情况挺多的，而且一多就乱

超绝构造

1.判断k=0的时候

2.特判s==1&k==1 || s-k*(k-1)/2<0的情况

3.判断n与k的关系，然后再分三小块

个人感觉最难写的就是最后一块，n>k的情况

n>k里面再分res==k和res!=k讨论

细节挺多的，本人没考虑到2和res<0的情况

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
    LL s,n,k;
    cin>>s>>n>>k;
    LL sum = k*(k-1)/2;
    if(k==0){
        if(n>s){
            cout<<"NO"<<endl;
            return;
            }
        else{
            cout<<"YES"<<endl;
            for(int i=1;i<n;i++){
                cout<<1<<" ";
            }
            cout<<s-(n-1)<<endl;
             return;
            }
    }
    LL res = s - sum;
    if(s==1 && k==1){
        cout<<"NO"<<endl;
        return;
    }
    if(res<0){
        cout<<"NO"<<endl;
        return;
    }
    
    if(n<k){
        cout<<"NO"<<endl;
        return;
    }
    else if(n==k){
        if(sum==s){
            cout<<"YES"<<endl;
            for(int i=0;i<k;i++){
                cout<<i<<" ";
            }
            cout<<endl;
            return;
        }
        else{
            cout<<"NO"<<endl;
            return;
        }
    }
    else{
        if(res==k){
            if(n-k>1){
                cout<<"YES"<<endl;
                for(int i=0;i<k;i++){
                    cout<<i<<" ";
                }
                cout<<k-1<<" "<<1<<" ";
                for(int i=k+3;i<=n;i++){
                    cout<<0<<" ";
                }
                cout<<endl;
                return;

            }else{
                cout<<"NO"<<endl;
                return;
            }
        }
        else{
            cout<<"YES"<<endl;
            for(int i=0;i<k;i++){
                cout<<i<<" ";
            }
            cout<<res<<" ";
            for(int i=k+2;i<=n;i++){
                cout<<0<<" ";
            }
            cout<<endl;
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

5.小红的X型矩阵

启始，想的解法是n2暴力过去，发现无法做到o(1)计算对角线上的值（菜！）

随后，去b站看题解，来来回回1小时才弄明白(lll￢ω￢)

具体思路就是把矩阵抽象的拓展，但对于每次移动，对角线上的1的个数是不会变的（重点！），

然后用b,c,两个数组抽象为两个斜着的数的1的个数（很不好理解），感觉像是在求1的贡献。。。

最后判断一下奇数和偶数的情况就行了

void solve()
{
    int n;
    cin>>n;
    vector<int> b(n+1,0),c(n+1,0);
    vector<vector<int> > a(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    auto cal1 = [&](int x,int y){//左上到右下
        return (x-y+n)%n;
    };
    auto cal2 = [&](int x,int y){//右上到左下
        return (x+y)%n;
    };
    LL sum = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==1){
                sum++;
                b[cal1(i,j)]++;
                c[cal2(i,j)]++;
            }
        }
    }
    LL ans = 1e7;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t1 = cal1(i,j);
            int t2 = cal2(i,j+n-1);
            int tt = b[t1]+c[t2]-n%2*(a[(i+n/2)%n][(j+n/2)%n]==1);
            ans = min(ans , sum-tt+2*n-n%2-tt);
        }
    }
    cout<<ans;

}