比赛题目训练系列05 (2020-2021 ACM-ICPC, Asia Seoul Regional Contest)

训练网址

A. Autonomous Vehicle

大模拟。挖坑

B. Commemorative Dice

题意：给两个色子六个面的数字，第一个人掷色子的数字比第二个人大算作胜利。问第一个人胜利的概率是多少?
签到，很简单，不讲了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}
int a[10], b[10];
int main() {for (int i = 1; i <= 6; i++) scanf("%d", &a[i]);for (int i = 1; i <= 6; i++) scanf("%d", &b[i]);int res = 0;for (int i = 1; i <= 6; i++) {for (int j = 1; j <= 6; j++) {res += a[i] > b[j];}}int d = gcd(res, 36);res /= d;printf("%d/%d\n", res, 36 / d);return 0;
}

C. Dessert Café

题意：给你n个点的树，边权为距离，然后给出k个特殊的点。现在要找的是点p，对于点p，有一个特殊点z，除了p和z之外的任何点x，d(p,z)<d(x,z)；而且又存在一个特殊的点z1，d(p,z1)<d(z,z1)。问这样的点p有多少个？
这道题想一想不难，对于一个结点。如果他有小于等于一个子树，那么该点满足条件当且仅当它是complex。对于度数大于等于2的结点，如果存在两棵子树，每个子树都至少有一个complex（这里子树是从u和v相连的中间那条边划分的），那么该结点满足条件。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100010, maxm = 200010;
int h[maxn], e[maxm], ne[maxm], w[maxm], idx;
int sz[maxn];
bool is_candidate[maxn], ok[maxn];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}int N, K, ans;int dfs(int u, int fa) {sz[u] = is_candidate[u] ? 1 : 0;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (v == fa) continue;sz[u] += dfs(v, u);}return sz[u];
}
void dfs2(int u, int fa) {if (is_candidate[u]) ok[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (v == fa) continue;if (sz[v] && K - sz[v]) ok[u] = true;dfs2(v, u);}
}
int main() {memset(h, -1, sizeof h);scanf("%d%d", &N, &K);for (int i = 1; i < N; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}for (int i = 1; i <= K; i++) {int x;scanf("%d", &x);is_candidate[x] = true;}dfs(1, -1);dfs2(1, -1);for (int i = 1; i <= N; i++) {ans += ok[i] ? 1 : 0;}printf("%d\n", ans);return 0;
}

D. Electric Vehicle

没搜到题解，挖坑。

E. Imprecise Computer

题意：IC出了问题，对于两个差值小于二的数a,b进行大小比较时，有可能输出a >b也有可能输出a <b。现对于长度为n的数列 Pn={1,2,3,…,n} 中每个数依次与别的数进行比较，若大于得一分，比赛进行两轮，让你判断输入的数组Dn是否为两场比赛中每个数可能出现的分差。
思路：不难的，就是分类讨论一下。当计算到 i 的时候，我们只需要关注 $i - 1$ , $i + 1$ 即可。其实只需要关注 i 和 i + 1 即可。因为 i 和 i - 1 已经在 i - 1 的时候比较过了。直接看代码。
这道题其实手动把样例1模拟一遍，思路就出来了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000010;
int a[maxn], b[maxn], r[maxn];
int N;
bool check() {for (int i = 1; i < N; i++) {if (abs(a[i] - b[i]) < r[i]) {if (a[i] > b[i]) a[i]++, b[i + 1]++;else a[i + 1]++, b[i]++;}else if (abs(a[i] - b[i]) == r[i]) a[i]++, b[i]++;else {if (a[i] > b[i]) a[i + 1]++, b[i]++;else a[i]++, b[i + 1]++;}if (abs(a[i] - b[i]) != r[i]) return false;}return abs(a[N] - b[N]) == r[N];
}
int main() {scanf("%d", &N);for (int i = 1; i <= N; i++) scanf("%d", &r[i]);if (check()) printf("YES\n");else printf("NO\n");return 0;
}

F. Ink Mix

没搜到题解。挖坑。

G. Mobile Robot

韩国人出题，题意怎么这么绕！好几道题都是题目巨长，信息冗杂
题意：给一个序列和公差d，让你把这个序列调节为等差序列，最小化移动距离的最大值。
可以看出来是一个凹函数，并且第一个位置确定后，答案就确定了。因此我们可以三分第一个位置。
然后，浮点数误差出了问题，我改用 long long，因为只保留一位小数，因此我把数字都乘了10.
然后，三分的板子出了问题，while(ub - lb > 1) 不对，因为和二分不一样。我改了改板子。改了n多次。
然后，才明白不一定是个递增序列，还可能是递减序列。
然后，三分超时了。看来得换个方法了。
我们这样思考，假设第一个位置 a[1] 就是等差序列的起点，那么我们可以计算每一个点的移动，记录最多向左移动的距离 lmost，和最多向右移动的距离 rmost。如果我们要把等差序列起点左移的话，rmost一定会增加。如果右移的话，lmost 必然会增加。因为我们只关心最大值。那么，我们可知最小化的最大值就是 $\frac{lmost + rmost}{2}$ . 但是我们也要注意的是，可能是个递减序列，因此要把 $D * = - 1$ ，然后再跑一遍上述过程。
然后，神奇的题目，用 GNU C++17 (64) 会莫名其妙超时，我查看了一下，答案已经输出了，但是似乎检测出了问题？评测姬快来背锅

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int maxn = 1000010;
typedef long long ll;
ll a[maxn], D;
int N;ll f() {ll lmost = 0, rmost = 0;for (int i = 1; i <= N; i++) {ll x = a[1] + (i - 1LL) * D;if (x > a[i]) rmost = max(rmost, x - a[i]);if (x < a[i]) lmost = max(lmost, a[i] - x);}return (lmost + rmost) / 2;
}int main() {scanf("%d%lld", &N, &D);D *= 10;for (int i = 1; i <= N; i++) {scanf("%lld", &a[i]);a[i] *= 10;}ll ans = f();D = -D;ans = min(ans, f());printf("%lld.%lld\n", ans / 10, ans % 10);return 0;
}

H. Needle

给三条等间距的平行线，平行线上有一些点（坐标范围是 $[- 30000, 30000]$ ）。分别从三条直线上任取一点，问有多少种取法，使得他们在同一直线上。
我们想想充要条件是什么。从第一条直线和第三条直线上分别任取一点 $x_1, x_3$ . 那么，如果第二条直线上有一点可以和 $x_1, x_3$ 共线，等价于 $x_2 = \frac{x1 + x3}{2}$ . 因此，我们看看第一条直线和第三条直线可以有多少种组合形式。那么，是不是可以看成两个多项式的卷积啊。设 $f = a * c$ ，然后答案就是 $\sum\limits b[i]* f[2*i]$ .
不过傅里叶变换一定要小心细节。（1）数组中存的是多项式的系数。（2）最后a.x一定要除以 tot 才是卷积的系数。（3）数组开多大取决于数的取值范围，而且一定要大于2的整数幂。
由此可见，计数类问题，有时候可以用FFT解决。因为计数类问题有时候可以转化为多项式得卷积。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double PI = acos(-1);
const int maxn = 300010;
typedef long long ll;
struct Complex {double x, y;Complex operator + (const Complex& t)const {return { x + t.x, y + t.y };}Complex operator - (const Complex& t)const {return { x - t.x, y - t.y };}Complex operator * (const Complex& t)const {return { x * t.x - y * t.y, x * t.y + y * t.x };}
}a[maxn], c[maxn];
int rev[maxn], bit, tot;
int b[maxn];
void fft(Complex a[], int inv) {for (int i = 0; i < tot; i++) {if (i < rev[i]) swap(a[i], a[rev[i]]);}for (int mid = 1; mid < tot; mid <<= 1) {auto w1 = Complex({ cos(PI / mid), inv * sin(PI / mid) });for (int i = 0; i < tot; i += mid * 2) {auto wk = Complex({ 1, 0 });for (int j = 0; j < mid; j++, wk = wk * w1) {auto x = a[i + j], y = wk * a[i + j + mid];a[i + j] = x + y, a[i + j + mid] = x - y;}}}
}
int dif = 30000;
int main() {int N1, N2, N3;scanf("%d", &N1);for (int i = 1; i <= N1; i++) {int x;scanf("%d", &x);a[x + dif].x += 1;}scanf("%d", &N2);for (int i = 1; i <= N2; i++) {int x;scanf("%d", &x);b[x + dif] += 1;}scanf("%d", &N3);for (int i = 1; i <= N3; i++) {int x;scanf("%d", &x);c[x + dif].x += 1;}bit = 17;tot = (1 << bit);for (int i = 0; i < tot; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));}fft(a, 1), fft(c, 1);for (int i = 0; i < tot; i++) a[i] = a[i] * c[i];fft(a, -1);ll ans = 0;//一定要小心，这里是数据范围最大，即60000//而且，卷积的结果在 a 中，要除以 tot 才对。而且，四舍五入的话（比如round），不要加上 0.5，+0.5意味着舍弃小数部分。for (int i = 0; i <= 60000; i++) {ll x = a[2 * i].x / tot + 0.5;ans += x * b[i];}printf("%lld\n", ans);return 0;
}

I. Stock Analysis

给一个序列 $(n\le 2000)$ ，给 $Q(Q\le20000)$ 组询问 $(l, r, u)$ ，问在 $(l, r)$ 内，不大于 $u$ 的最大连续子段和是多少？
一开始用线段树套平衡树，后来发现不对。因为树套树只能维护一段一段的区间。如果某个区间横跨线段树的维护的两个区间，答案也是横跨了结点的两个区间，这样的答案是查询不到的。
有一个思路是，所有区间和总共也只有 2e6 个。因此预处理出所有区间和，再读入所有询问。然后按照值排序。这样子的话，大于 U 的区间和只会在 U 之后出现，这样子的话，就可以转化为求小矩形最大值的问题。
但是，不会求小矩形最大值。
看不懂的二维树状数组写法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 2010, maxm = 200010;
struct node {int l, r, id;ll val;
};
vector<node> q;
ll w[maxn], tr[maxn][maxn], ans[maxm];
int lowbit(int x) {return x & -x;
}
bool cmp(const node& u, const node& v) {return u.val < v.val || u.val == v.val && u.id < v.id;
}
int N, M;
void update(int x, int y, ll v) {while (x) {int z = y;while (z <= N) {tr[x][z] = max(tr[x][z], v);z += z & -z;}x -= x & -x;}
}ll query(int x, int y) {ll res = -INF;while (x <= N) {int z = y;while (z) {res = max(res, tr[x][z]);z -= z & -z;}x += x & -x;}return res;
}
int main() {scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) {fill(tr[i], tr[i] + N + 1, -INF);}for (int i = 1; i <= N; i++) {scanf("%lld", &w[i]);w[i] += w[i - 1];}for (int i = 1; i <= N; i++) {for (int j = i; j <= N; j++) {q.push_back({ i, j, 0, w[j] - w[i - 1] });}}for (int i = 1; i <= M; i++) {int l, r;ll x;scanf("%d%d%lld", &l, &r, &x);q.push_back({ l, r, i, x });}sort(q.begin(), q.end(), cmp);for (auto p : q) {int l = p.l, r = p.r, id = p.id;ll val = p.val;if (!id) update(l, r, val);else ans[id] = query(l, r);}for (int i = 1; i <= M; i++) {if (ans[i] != -INF) printf("%lld\n", ans[i]);else printf("NONE\n");}return 0;
}

J. Switches

题意：已知有 $n$ 个开关和 $n$ 盏灯，现在每一个开关可以控制若干盏灯，该信息用矩阵表示。一盏灯要亮，当且仅当这盏灯对应的开关数量为奇数。问对于每一盏灯，能否打开若干个开关，使得只有该盏灯是亮的，而其他灯都是灭的。若可以，输出每一盏灯对应的开关，否则输出 $- 1$ 。
这个是别人写的题解，我觉得讲的非常清楚，就不多言了。

如果对于每个灯列一个n*n的01矩阵进行高斯消元求解,
总复杂度是O(n^4)的,显然不行.设矩阵A为系数矩阵,
X为开关操作矩阵(未知数矩阵),
B为结果矩阵(常数矩阵),
那么有A*X=B,
左右同时乘上A^(-1)得:X=A^(-1)*B.求出A矩阵的逆矩阵A^(-1),
因为B矩阵是n*1的,
所以A^(-1)*B是O(n^2)的,
枚举i,构造Bi,计算第i个灯的答案,
总复杂度是O(n^3)的.但是n<=500,O(n^3)还是会T,
矩阵求逆 和 矩阵乘法 都需要用bitset优化.版权声明：本文为CSDN博主「live4m」的原创文章，遵循CC 4.0 BY - SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https ://blog.csdn.net/weixin_44178736/article/details/113361135

注意题目输入，说的是第 i 行表示第 i 个开关控制那些灯。而我们在列异或方程组的时候，每一行应该是都有哪些开关控制着第 i 个灯。因此要把输入矩阵转置一下。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int maxn = 510;
bitset<maxn * 2> a[maxn];
bitset<maxn> b, inv_a[maxn], ans;
int N;
bool Gauss_inv() {for (int c = 1; c <= N; c++) {int t = c;for (int i = c; i <= N; i++) {if (a[i][c]) {t = i;break;}}if (a[t][c] == 0) return false;swap(a[t], a[c]);//小心这个地方要从第一行开始看。大雪菜那个是从 r + 1 行开始，那是因为他没有化成单位矩阵//但是求逆矩阵必须要化为单位阵。for (int i = 1; i <= N; i++) {if (a[i][c] && i != c) {a[i] ^= a[c];}}}return 1;
}
// A = B * C
void mul(bitset<maxn>& a, bitset<maxn> b[], bitset<maxn>& c) {for (int i = 1; i <= N; i++) {//小心这个地方是与，不是异或。矩阵乘法怎么可以写异或呢！a[i] = (b[i] & c).count() % 2;}
}int main() {scanf("%d", &N);for (int i = 1; i <= N; i++) {a[i][i + N] = 1;for (int j = 1; j <= N; j++) {int x;scanf("%d", &x);if (x) a[j][i] = 1;}}if (!Gauss_inv()) {printf("-1\n");}else {for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) inv_a[i][j] = a[i][j + N];}/*for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) cout << a[i][j + N] << " ";cout << endl;}*/for (int i = 1; i <= N; i++) {b.reset();b[i] = 1;ans.reset();mul(ans, inv_a, b);for (int i = 1; i <= N; i++) {if (ans[i]) printf("%d ", i);}printf("\n");}}return 0;
}

K. Tiling Polyomino

挖坑。找到题解或者看懂代码再补

L. Two Buildings

题意：给定长度为 $n$ 的数组 $h$ ，要求计算 $max\{(h[i]+h[j])*(j-i)\}$ ，其中 $i < j$ 。数据范围： $n < = 1 e 6, 1 < = h (i) < = 1 e 6$ .
极为优秀的题解. 由于原题解图片以及讲解有点小问题（也可能是我没理解对）。下面做了一些改动

(h[i]+h[j])*(j-i)
=(h[j]-(-h[i]))*(j-i)令a[i]=h[i],b[i]=-h[i],
那么可以转化为计算(a[j]-b[i])*(j-i),
转化为(i,a[i]),(j,b[j])在二维坐标系中围成的矩形面积。本质就是在 y 轴上方选一点，y轴下方选一点，使得举行的面积最大。对于一个固定的(j,a[j]),选择的(i,b[i])显然位置左下越优.
那么对于(i,b[i])和(j,b[j]),如果i<j且b[i]>=b[j],
那么(i,b[i])完全可以删去。对于 a 数组也是同理（a数组中的数据，越靠近右上方越优）。
去掉b[]无用点之后,剩下的点一定是对于i<j,有b[i]<b[j],
同理a[]去掉无用点之后,剩下的点一定是对于i<j,有a[i]>b[j].对于a[1,n],设mid=(l1+r1)/2,
设点(mid,a[mid])在点(pos,b[pos])处获得最大值.
那么对于(mid,a[mid])左边的点(j,a[j]),
他们的最优解点(i,b[i])一定满足i<=pos,
可以用反证法证明,
大概就是如果i>pos,那么(mid,a[mid)的就不是(pos,b[pos])了,
画一下图应该也能证明出来.假设现在我们已经求出(mid,a[mid])和(pos,b[pos])配对最优,
根据我们上面的结论,我们只需要继续分别计算:
1.a[l1,mid-1]和b[l2,pos]匹配的最大值.
2.a[mid+1,r2]h和b[pos,r2]匹配的最大值.
同(mid,a[mid])与(pos,b[pos])的值,三者取max就是答案,
其中情况1和情况2是子问题,可以递归计算.

在这里插入图片描述

画了个图，可见在求解左边的子问题中，b数组对应的最优解一定不会在 pos 的右边。这个是可以参考上方图形证明的，用小矩形边之间的关系即可。
代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int maxn = 1000010;
int N, M;
typedef long long ll;
typedef pair<ll, ll> P;
P a[maxn], b[maxn];
bool del[maxn];
ll cal(int j, int i) {return (a[j].y - b[i].y) * (a[j].x - b[i].x);
}
ll solve(int l1, int r1, int l2, int r2) {if (l1 > r1 || l2 > r2) return 1e-18;int mid = (l1 + r1) / 2, pos = l2;ll res = cal(mid, pos);for (int i = l2 + 1; i <= r2; i++) {ll tmp = cal(mid, i);if (tmp >= res) {pos = i;res = tmp;}}return max(res, max(solve(l1, mid - 1, l2, pos), solve(mid + 1, r1, pos, r2)));
}
int main() {scanf("%d", &N);M = N;for (int i = 1; i <= N; i++) {scanf("%lld", &a[i].y);a[i].x = i;b[i] = { i, -a[i].y };}sort(a + 1, a + N + 1);sort(b + 1, b + N + 1);int cnt = 0, last = N;//删掉 a 中多余的点，越靠近右上方越优。for (int i = N - 1; i >= 1; i--) {if (a[i].y <= a[last].y) {del[i] = true;}else {last = i;}}for (int i = 1; i <= N; i++) {if (!del[i]) {//注意，这个地方不可以写成 ++cnt, a[cnt] = {cnt, a[i].y}，因为原本的位置信息必须要保留。a[++cnt] = a[i];}}N = cnt;//删掉 b 中左下方的点。memset(del, false, sizeof del);last = 1, cnt = 0;for (int i = 2; i <= M; i++) {if (b[i].y >= b[last].y) {del[i] = true;}else {last = i;}}for (int i = 1; i <= M; i++) {if (!del[i]) {b[++cnt] = b[i];}}M = cnt;printf("%lld\n", solve(1, N, 1, M));return 0;
}