牛客周赛round59

比赛链接https://ac.nowcoder.com/acm/contest/89860

A - TD

题意

有m个人，其中n个人发送了TD，那么从m个人中随机挑选一个人，他发送过TD的概率是多少。

思路

直接输出undefinedfrac{n}{m}$ 即可（要注意这里不是整数除法）

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,m;cin>>n>>m;
    cout<<double(n)/m<<endl;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B - 你好，这里是牛客竞赛

题意

给你一个链接，如果这个链接以https://ac.nowcoder.com或者ac.nowcoder.com 开头，就输出Ac

如果链接以https://www.nowcoder.com 或者www.nowcoder.com 开头，就输出Nowcoder ，

如果都不是，那么就输出No

思路

可以先判断前几个字符如果是https;//就删掉这部分。

然后我们读取字符串，直到遇到.com就停止。

最后对读取的字符串判断即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    string str;
    cin>>str;
    if(str.substr(0,8) == "https://"){
        str = str.substr(8);
    }
    string ans = "";
    for(int i = 0;i<str.size();i++){
        if(i >= 3 && str.substr(i-3,3) == "com") break;
        ans += str[i];
    }
    if(ans == "ac.nowcoder.com") cout<<"Ac\n";
    else if(ans == "www.nowcoder.com") cout<<"Nowcoder\n";
    else cout<<"No\n";
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C - 逆序数

题意

已知一个**排列**undefined{ x_1 ,x_2,…,x_n \}$的逆序对的数量是$k$, 请你输出$\{x_n,…,x_2,x_1\}$ 的逆序对数量。

现在给你$n,k$ ，请你输出结果。

思路

一个长度为n的排列，一共有undefinedfrac{n*(n-1)}{2}$个对， 并且只有正序对和逆序对，我们设数量分别为$t,k$, 那么在翻转整个排列后，显然原先的正序对会变为逆序的，逆序对会变为正序的。 那么反转后的逆序对的数量，就是原先正序对的数量。 即$ans = t = \frac{n*(n-1)}{2} - k$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,k;
    cin>>n>>k;
    cout<<n*(n-1)/2 - k;
    
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D - 构造mex

题意

给你整数$s,k$，请你将$s$分为**恰好**n个非负整数$a_1,a_2,..,a_n$， 使得$a_1+a_2+...+a_n = s$ 并且 $mex(a) = k$ 。

注：$mex(a)$的含义是**在a数组中，未出现过的最小的非负整数**。

思路

大讨论题，对于一般情况，我们很容易得知，需要构造$0,1,2,...,k-1, s-(\frac{k*(k-1)}{2}),0,0,0$ 这样的数列。但是本题的关键在于考虑特殊情况。下面列举需要特判的条件：

1. 如果$k = 0$ 并且$s < n$ ，条件无法成立那（这n个数中一定存在0，就不能使得k = 0.）
2. 如果$k = 1,s = 1$ ,那么无论如何都不能成立。（a数组一定为一个1和一些0（可能为0个0），最后的mex一定为0或2，不是1）
3. 如果$n < k$ 那么无法成立（显然无法分出k份也就无法使得$[0,k-1]$都在$a$中出现，也就无法使得最终的mex是k）
4. 如果$n=k$ 且$s \not= \frac{k*(k-1)}{2}$ ，无法成立（如果n和k相等，就代表应该恰好将s分为$0,1,2,...,k-1$ 这k个数，如果总和不是s就违背了构造规则）
5. 如果$n = k+1$ 并且$s = \frac{k*(k-1)}{2} + k$ 那么无法成立（即我们需要设置a数组为$0,1,2,...,k-1,k$ , 那么它的mex就变为了$k+1$ 而不是$k$)

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int s,n,k;
    cin>>s>>n>>k;
    int sum = k*(k-1)/2;
    if(k == 0){
        if(s < n) {cout<<"NO\n";return ;}
        cout<<"YES\n";
        rep(i,1,n-1){
            cout<<1<<' ';
        }cout<<s-n+1;
        puts("");return ;
    }
    if(k == 1 && s == 1){cout<<"NO\n";return ;}
    if(n < k) {cout<<"NO\n"; return ;}
    if(sum > s) {cout<<"NO\n"; return ;}
    if(n == k) {
        if(sum != s) {cout<<"NO\n"; return ;}
        else {
            cout<<"YES\n";
            rep(i,0,n-1){
                cout<<i<<' ';
            }puts("");return ;
        }
    }
    if(n == (k+1) && sum+k == s) {cout<<"NO\n";return ;}
    cout<<"YES\n";
    for(int i = 0;i<k;i++){
        cout<<i<<' ';
    }
    int left = s-sum;
    if(left == k){
        cout<<1<<" "<<k-1<<' ';
        for(int i = k+3;i<=n;i++) cout<<"0 ";
    }else{
        cout<<left<<' ';
        for(int i =k+2;i<=n;i++) cout<<"0 ";
    }
    puts("");return ;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E - 小红的X型矩阵

题意

给你一个$n*n$ 的01矩阵， 你进行若干次如下操作，使得最终的矩阵为X型矩阵 ，操作方法如下：

• 操作一：将矩阵中的一个元素反转（0变为1，1变为0）
• 操作二：将矩阵循环右移或者循环下移一位。

问最少需要几次操作一，能够使得矩阵变为X型矩阵

注：当且仅当一个矩阵的两个对角线全为1，其余地方全为0时，该矩阵为X型矩阵 （$a_{ii}= 1,a_{i,n-i+1}= 1$ 其余全为0）

思路

我们将最终目标的X矩阵进行一些次数的循环移动后，可以发现，X的中心移动到了矩阵中的某个位置，而其他的1同样在它的四个角落方向（若越界则循环至矩阵另一边）,因此这些1同样在两条对角线上。

10001           11000
01010           11000
00100    --->   00101
01010           00010
10001           00101

因此我们对输入矩阵维护每条对角线上的1的数量，然后我们枚举中心点的每个位置，找到和原矩阵匹配程度最大的那个即可（即在这两条对角线上，原矩阵的1出现的数量最多）。

需要注意如果n为偶数，因为两条对角线不存在交点，那么处理方式和奇数略有不同。

可以发现对于左上-右下对角线，我们可以这样表示它：$i-j \equiv d (mod\ n)$ (对于每个$d\in[0,n-1]$，表示一条对角线)

对于左下-右上对角线，可以这样表示它：$i+j \equiv d(mod\ n)$(对于每个$d\in[0,n-1]$，表示一条对角线)

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int mp[1005][1005];
int n;
int sum1[2005];
int sum2[2005];
void solve(){
    cin>>n;
    int sum = 0;
    for(int i =1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin>>mp[i][j];
            if(mp[i][j]) sum ++ ;
        }
    }
    for(int d = 0;d<=n-1;d++){
        for(int i = 1;i<=n;i++){
            int j = i + d;
            if(j > n) j -=n;
            sum1[d] += mp[i][j];
        }
    }
    for(int d = 0;d<=n-1;d++){
        for(int i = 1;i<=n;i++){
            int j = d - i;
            if(j < 1) j += n;
            sum2[d] += mp[i][j];
        }
    }
    
    int res = INF;
    if(n%2 == 1){
      for(int i = 1;i<=n;i++){
        for(int j =1;j<=n;j++){
            int cnt = sum1[(j-i+n)%n] + sum2[(i+j)%n] - mp[i][j];
            int ans =(2 * n - 1 - cnt) + (sum - cnt);
            res = min(res,ans);  
        }
      }  
    }else{
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                int cnt = 0;
                cnt += sum1[(j-i+n)%n];
                int ii = i%n+1;
                cnt += sum2[(ii+j)%n];
                int ans =(2 * n - cnt) + (sum - cnt);
                res = min(res,ans);
            }
        }
    }
    cout<<res;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F - 小红的数组回文值

题意

定义一个数组的回文值为：至少需要修改多少个数，能使得这个数组变为回文数组。

现在给你一个长度为$n(1\le n \le 2000)$的数组$a_1,a_2,...,a_n$ ，问它的所有**子序列**的回文值的和是多少。答案对$10^9+7$ 取模

思路

我们应该先想到，一个数组的回文值，即为每对**对称的数** 不相等的数量。例：$1,2,4,5,7$ ，那么undefined1,7)$对称，$(2,5)$ 对称，并且这两个对都不相同，回文值为2。

即**只有不相同的数对会产生贡献**。 那么我们枚举数组a中的每个数对undefineda_i, a_j )$， 如果他们不相等， 我们就计算在多少个子序列中，这两个数是对称的。

很容易求出对于给定的undefinedi,j)$他们之间有$mid = j-i-1$个数， 左边有$le = i-1$个数，右边有$ri = n-j$ 个数。

分布如下：...i.....j....

我们得知，选择$i,j$中间的任意数不会破坏$i$和$j$对称。那么他们有$2^{mid}$ 种方案。

对于两侧，我们必须选择同样多的数，才能保证$i$和$j$是对称的。假设我们选择了$k$个数。$0 \le k \le min(le,ri)$

于是两侧的方案数为undefinedsum_{k=0}^{min(le,ri)} C_{le}^{k} C{ri}^k$, 我们根据组合数的公式$C_n^m = C_n^{n-m}$，就可以将式子变为$\sum_{k=0}^{min(le,ri)} C_{le}^{le-k} C_{ri}^k$,那么根据**范德蒙恒等式** ， 方案数即为$C_{le+ri}^{le}$, 因此对于这个数对$(i,j)$，它的贡献为$2^{mid} * C_{le+ri}^{le}$

注：范德蒙恒等式如下：$C_{n+m}^k = \sum_{t=0}^{k} C_n^t C_m^{k-t}$ , 解释为：有两个盒子，分别装有$n$个球和$m$个球 , 从中一共选择k个球（$C_{n+m}^k$） 等价于， 从第一个盒子中选择t个球$C_n^t$，从另一个盒子中选择$k-t$个球 $C_m^{k-t}$ 。枚举每个$t \in [0,k]$ 将方案数相加。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int a[2005];
int fac[2005];
int ifac[2005];
const int mod = 1e9+7;
int qpow(int x,int n){
    int ans = 1;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
int inv(int x){
    return qpow(x,mod-2);
}
int C(int n,int m){
    if(m == 0 || n == m) return 1;
    return fac[n] * ifac[n-m] % mod * ifac[m] % mod;
}
void solve(){
    fac[0] = 1;
    for(int i = 1;i<=2000;i++) fac[i] = fac[i-1] * i % mod;
    for(int i = 1;i<=2000;i++) ifac[i] = inv(fac[i]);
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        for(int j = i+1;j<=n;j++){
            int l = i-1,m = (j-i-1),r=(n-j);
            int sum = 0;
            int mn = min(l,r);
            ans = (ans + (a[i]!=a[j])*qpow(2,m)*(C(l+r,l))%mod)%mod;
        }
    }
    cout<<ans;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}