牛客多校第一场（除G外）
2019牛客暑期多校训练营（第一场）
A Equivalent Prefixes
题意：
给定长度相等的序列A,B，求最大的x，使得 和
建立的笛卡尔树相同，笛卡尔树是递归构造的，从整个序列出发，查找最小值作为根，然后将序列分成两个部分，分治构造
分析：
对两个序列都跑一遍单调栈，如果在每个位置单调栈的元素的数量都相同，那么建立的笛卡尔树肯定相同，找到最大的x即可
参考代码
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40901481
B Integration
题意：
给定
求
分析：
我们知道
1.
$(a+x)*(b+x)
x = -a 和 x = -b$就可以得到A，B，对于多个相乘同理，求出系数之后就可以计算了
参考代码
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40858470
C Euclidean Distance
题意：
找到一组满足
使得最小
分析：
先对 从大到小排序，所有的
相加等于1，提出来一个
，相当于将m分配到这n个
中去使得他们的平方和最小
我们想一个贪心策略，很明显
if a_i > a_j 我们有x要减去 从a_i 中扣除 有 sum_1 = (a_i-x)^2+a_j^2 = a_i^2+a_j^2-2x*a_i+x^2 从a_j 中扣除 有 sum_2 = a_i^2+(a_j-x)^2 = a_i^2+a_j^2-2x*a_j+x^2 很明显 sum_1 <= sum_2
于是贪心策略就是从大的中扣除，直到和第二大相同，然后再削减
参考
https://blog.nowcoder.net/n/1539da6d6d6e47a6998b5c6f5bba2167
D Parity of Tuples
https://ac.nowcoder.com/discuss/208861?type=101&order=0&pos=1&page=1
E ABBA
题意：
对于一个只有 AB字符组成的长度为 2*(n+m) 的字符串，要求其中存在AB子序列n个，BA子序列m个，给定n，m问存在多少中方法？
分析：
我们知道序列到某一个位置的时候有一个限制，是A的个数不能超过B个，B的个数不能超过Am个，其他情况都是合法的。
参考代码：
const int maxn = 2e3 + 10;
LL dp[maxn][maxn];
int main(void)
{
LL n, m;
while (cin >> n >> m) {
for (int i = 0; i <= n + m; ++i) {
for (int j = 0; j <= n + m; ++j) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for (int i = 0; i <= n + m; ++i) {
for (int j = 0; j <= n + m; ++j) {
if (i - j < n)
(dp[i + 1][j] += dp[i][j]) %= mod;
if (j - i < m)
(dp[i][j + 1] += dp[i][j]) %= mod;
}
}
printf("%lld\n", dp[n + m][n + m]);
}
return 0;
} F Random Point in Triangle
11/36
我们可以直接出来随出来一个三角形，然后跑随机看是36分之几
G Substrings 2
题意：
计算 所有的满足异或和为0的所有集合的元素个数的和
分析：
计算集合的元素个数之和可以改成求所有的元素的贡献来做。
考虑线性基，我们先对所有n个元素的元素求线性基
- 线性基外的元素的贡献是
, r 是线性基中元素的个数，也就是基底的个数，为什么是
- 对于线性基中的元素a，我们考虑将剩下的
的元素建立一个线性基B，每次添加除a以外原线性基中的元素r-1个，如果a可以由这个新线性基表示出来，那么同样它的贡献也是
const int MN = 62;
LL A[MN], B[MN], C[MN];
bool Ins(LL x, LL *a) {
for (int i = MN - 1; i >= 0; --i) {
if (x & (1LL << i)) {
if (!a[i])
{
a[i] = x;
return true;
}
else
x ^= a[i];
}
}
return false;
}
const int maxn = 1e5 + 10;
LL pow2[maxn];
LL a[maxn];
int main() {
pow2[0] = 1;
for (int i = 1; i < maxn; ++i)
pow2[i] = pow2[i - 1] * 2 % mod;
// cout << pow2[10] << endl;
int n;
while (~scanf("%d", &n)) {
me(A), me(B);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
vector<LL> v;
for (int i = 1; i <= n; ++i) {
if (!Ins(a[i], A))
Ins(a[i], B);
else
v.Pb(a[i]);
}
int cnt = 0;
for (int i = 0; i < MN; ++i)
if (A[i] != 0)
cnt++;
if (cnt == n) {
puts("0");
continue;
}
LL ans = 0;
// cout << " r = " << cnt << endl;
ans = n - cnt;
for (auto c : v) {
memcpy(C, B, sizeof(C));
for (auto c2 : v) {
if (c == c2) continue;
Ins(c2, C);
}
// cout << c << " " << Ins(c, C) << endl;
if (!Ins(c, C))
ans++;
}
// cout << " ans = " << ans << endl;
printf("%lld\n", ans * pow2[n - cnt - 1] % mod);
}
return 0;
}
/*
2
1000000000000000000 1000000000000000000
*/ I
https://blog.nowcoder.net/n/7205418146f3446eb0b1ecec8d2ab1da
查看6道真题和解析
