牛客周赛 Round 59(思维、构造、数论)

---

E题，对于对角线的处理，常用。

F题，范德蒙恒等式推论的应用。

---

A. TD

简单数学题。

#include<bits/stdc++.h>using namespace std;int main(){double n, m;cin >> n >> m;double res = n / m;printf("%.10lf", res); // 注意精度return 0;
}

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

判断四个模式串是否为输入字符串的前缀即可。

#include<bits/stdc++.h>using namespace std;bool is_prefix(const string& A, const string& B){	// 判断B是否为A的前缀return A.find(B) == 0;		// str.find() 返回首次匹配的下标，没找到返回str.npos
}int main(){map<string, string> mp;mp["https://www.nowcoder.com"] = "Nowcoder";mp["www.nowcoder.com"] = "Nowcoder";mp["https://ac.nowcoder.com"] = "Ac";mp["ac.nowcoder.com"] = "Ac";int ncase;cin >> ncase;while(ncase--){string s;cin >> s;int is_find = 0;for(auto x : mp){if(is_prefix(s, x.first)){is_find = 1;cout << x.second << endl;break; }}if(!is_find) cout << "No" << endl;}return 0;
}

C. 逆序数（思维）

通过简单思考，一个序列A，任选两个元素，共有 |A| * （|A|-1）/ 2 种选择。（|A| 表示A序列中元素的个数）

对于任选的A_i 和 A_j，要么其在 A 中为逆序对，要么在 A’ 中为逆序对。（设A序列的逆序序列为A’）

综上，A 和 A’ 中逆序对的和为 |A| * （|A|-1）/ 2。

在已知A的逆序对个数和元素个数时，可以计算出A’ 中逆序对的个数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;int main(){ll n, k;cin >> n >> k;ll res = n * (n-1) / 2 - k; // 注意数据范围cout << res << endl;return 0;
}

D. 构造mex（构造）

一点点细节的构造题。

根据 k 与 n 的大小关系进行了分类，具体看代码吧。

#include<bits/stdc++.h>
#define ll long long
using namespace std;void print_yes(int k, int is_end){cout << "YES" << endl;for(int i = 0; i < k; i++){cout << (i == 0 ? "" : " ") << i;}if(is_end) cout << "\n";
}int main(){int ncase;cin >> ncase;while(ncase--){ll s, n, k;cin >> s >> n >> k;if(k == 0){if(s >= n){cout << "YES" << endl; int sum = s - n;for(int i = 1; i < n; i++) cout << "1 ";cout << sum + 1 << endl;}else cout << "NO" << endl;}else if(k == 1 && s == 1) cout << "NO" << endl;else if(k > n) cout << "NO" << endl;else if(k == n){ll sum = k * (k-1) / 2;if(sum == s) print_yes(k, 1);else cout << "NO" << endl;}else if(k+1 == n){ll sum = k * (k-1) / 2;if(sum + k != s && s >= sum){print_yes(k, 0);cout << " " << s - sum << endl;}else cout << "NO" << endl;}else {	// 这是一种普遍的构造方法，上边的分类，均为当前分支不适配的特殊情况。ll sum = k * (k-1) / 2;if(sum > s) cout << "NO" << endl;else if(sum + k != s){print_yes(k, 0);cout << " " << s - sum;for(int i = k+2; i <= n; i++) cout << " " << 0;cout << endl;}else{print_yes(k, 0);cout << " " << s - sum - 1 << " 1";for(int i = k+3; i <= n; i++) cout << " " << 0;cout << endl;}}}return 0;
}

E. 小红的X型矩阵

操作二等价于：可以在保证元素相对位置的基础上，把任意点放在矩阵中间。

X形矩阵的形状与 n 的奇偶有关。

• 主对角线：左上到右下；副对角线：右上到左下。

• 任意点(x, y) 所在的主对角线上的点都满足：(x-y+n) % n

• 任意点(x, y) 所在的福对角线上的点都满足：(x+y) % n

当 n为奇数时，任意点(x,y)需要的操作一的数量为：对角线上 0 的个数 + (全部 1 的个数为 X - 对角线上 1 的个数)

当 n为偶数时，任意点(x,y)需要的操作一的数量为：对角线上 0 的个数 + (全部 1 的个数为 X - 对角线上 1 的个数)

#include<bits/stdc++.h>using namespace std;const int maxn = 1005;
int a[maxn][maxn];
int z[maxn], f[maxn];int main(){int n;cin >> n;int sum_1 = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> a[i][j];z[(i-j+n)%n] += a[i][j];	 // 主对角线 1的个数 f[(i+j)%n] += a[i][j];  	 // 副对角线 1的个数 sum_1 += a[i][j];}}int res = n * n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){int pos_z = (i-j+n) % n, pos_f = (i+j) % n, tmp, d_0, d_1;if(n % 2 == 0){pos_f = (pos_f + 1) % n; 			// 偶数时，副对角线下移一格 d_1 = z[pos_z] + f[pos_f];			// 对角线上 1 的个数 d_0 = 2*n - d_1;	// 对角线上 0 的个数 }else{// 如果是奇数，(i,j) 会被重复统计d_1 = z[pos_z] + f[pos_f] - a[i][j];d_0 = 2*n-1 - d_1;}tmp = d_0 + (sum_1 - d_1);res = min(res, tmp); 
//			cout << i << " " << j << " " << res << " " << tmp << endl;}}cout << res << endl;return 0;
}/*0 1 2 3 4
0	0 4 3 2 1 
1	1 0 4 3 2
2	2 1 0 4 3
3	3 2 1 0 4
4	4 3 2 1 0*/

F. 小红的数组回文值（数论、范德蒙恒等式）

思路不是很复杂，任选两个元素 a_i 与 a_j ，考虑这两个元素对答案的贡献。

• 当 a_i == a_j 时，不需要操作，贡献为零。

• 当 a_i != a_j 时，需要操作，贡献为 a_i 与 a_j 在对称位置的子序列的个数。

如上图，要保证 a_i 与 a_j 在对称位置，集合A和集合C贡献的元素个数必须相等。集合B对对称性没有影响 ，可自行枚举。

• 集合B对子序列个数的贡献为 2^|B|，其中 |B| 表示集合B中元素的个数。

• 集合A和集合C对子序列个数的贡献为${\sum }_{i=0}^{min(|A|,|C|)}C(i,|A|)\ast C(i,|C|)$

综上，a_i 与 a_j 在对称位置的子序列的个数 = 2^|B| * ${\sum }_{i=0}^{min(|A|,|C|)}C(i,|A|)\ast C(i,|C|)$ 。枚举所有的 a_i 与 a_j 的组合，求和即可得出答案。

但是，在枚举时，会发现时间复杂度是O(n^3), 需要优化${\sum }_{i=0}^{min(|A|,|C|)}C(i,|A|)\ast C(i,|C|)$，这里就需要用到范德蒙恒等式。

范德蒙恒等式推论：${\sum }_{i=0}^{min(|A|,|C|)}C(i,|A|)\ast C(i,|C|)=C(min(|A|,|C|),|A|+|C|)$

给一个学习的博客：范德蒙德卷积 - Gensokyo Algorithm Research Institute (enonya.github.io)

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2000 + 10;
const ll mod = 1e9 + 7;ll C[maxn][maxn], P[maxn][maxn];
ll p[maxn];
int a[maxn];void init(){// 预处理组合数C[0][0] = 1;for(int i = 1; i < maxn; i++){for(int j = 0; j <= i; j++){C[i][j] = C[i-1][j];if(j-1 >= 0) C[i][j] += C[i-1][j-1];C[i][j] %= mod;}}// 预处理2的整次幂p[0] = 1;for(int i = 1; i <= 2000; i++) p[i] = p[i-1] * 2 % mod;
}ll f(int a, int b){ // 当时一个愚蠢的写法，忽略掉这个函数名if(a > b) swap(a, b);return C[a+b][a];
}int main(){init();int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];ll res = 0;for(int i = 1; i <= n; i++){for(int j = i+1; j <= n; j++){if(a[i] != a[j]){res += f(i-1, n-j) * p[j-i-1] % mod;res %= mod;				}}}cout << res << endl;return 0;
}