目录
写在前面
比赛地址：https://codeforces.com/contest/1922
D 没调出来亏炸了，第一次体验赛后五分钟过题的快感。
痛苦的大二上终于结束了，本学期一半的痛苦都来自于傻逼大物实验。
下学期课少了好多，而且早八和晚八都少的一批，集中上一波分了就。
A
题面太长不看怒吃两发呃呃
分别考虑每个位置，当 \(a_i = c_i\) 或 \(b_i = c_i\) 时该位置必定不合法。当且仅当所有位置均不合法时无解。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
std::string a, b, c, d;
int flag = 1, n;
std::cin >> n >> a >> b >> c;
for (int i = 0; i < n; ++ i) {
if (a[i] == c[i] || b[i] == c[i]) continue;
flag = 0;
}
printf("%s\n", (flag == 0) ? "YES" : "NO");
}
return 0;
}
B
典中典之 \(2^{i - 1} + 2^{i - 1} = 2^i\)，则组成的三角形合法当且仅当等边，或者等腰且底比腰短。
组合数搞下就好了。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], cnt[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
LL C2(int x_) {
if (x_ < 2) return 0;
return 1ll * x_ * (x_ - 1) / 2ll;
}
LL C3(int x_) {
if (x_ < 3) return 0;
return 1ll * x_ * (x_ - 1) / 2ll * (x_ - 2) / 3ll;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 0; i <= n; ++ i) cnt[i] = 0;
for (int i = 1; i <= n; ++ i) {
a[i] = read();
cnt[a[i]] ++;
}
LL ans = 0;
int num = 0;
for (int i = 0; i <= n; ++ i) {
ans += C3(cnt[i]);
ans += num * C2(cnt[i]);
num += cnt[i];
}
printf("%lld\n", ans);
}
return 0;
}
C
不懂为啥这题有个贪心的标签。
对于一次询问显然只会在相邻城市之间移动，仅需求一路上可以减小的代价之和即可。则对于任意询问 \(x<y\)，记 \(\operatorname{sum0}(i)\) 表示从城市 1 移动到城市 \(i + 1\) 一路上可以用第二种旅行减小的代价之和，答案即为 \(a_y - a_x - \operatorname{sum0}(y - 1) - \operatorname{sum0}(x - 1)\)。\(x > y\) 的询问同理，预处理 \(\operatorname{sum1}(i)\) 表示从城市 \(n\) 移动到城市 \(i - 1\) 一路上可以用第二种旅行减小的代价之和即可。
求每个城市的最近城市预处理即可，总时空复杂度 \(O(n + m)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL kInf = 2e9 + 2077;
//=============================================================
int n, m;
LL a[kN], sum[2][kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read();
a[0] = -kInf, a[n + 1] = kInf;
sum[0][0] = sum[1][n + 1] = 0;
for (int i = 1; i <= n; ++ i) a[i] = read(), sum[0][i] = sum[1][i] = 0;
for (int i = 1; i <= n; ++ i) {
LL d1 = a[i] - a[i - 1], d2 = a[i + 1] - a[i];
sum[0][i] = sum[1][i] = 0;
if (d1 < d2) {
sum[1][i] = -d1 + 1;
} else {
sum[0][i] = -d2 + 1;
}
}
for (int i = 1; i <= n; ++ i) sum[0][i] += sum[0][i - 1];
for (int i = n; i >= 1; -- i) sum[1][i] += sum[1][i + 1];
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
int m = read();
while (m --) {
int x = read(), y = read();
LL ans = abs(a[x] - a[y]);
if (x < y) {
ans += sum[0][y - 1] - sum[0][x - 1];
} else {
ans += sum[1][y + 1] - sum[1][x + 1];
}
printf("%lld\n", ans);
}
}
return 0;
}
D
没调出来妈的，赛后五分钟发现是偷懒直接用置零 \(a_i\) 表示把 \(i\) 杀了影响到同一轮其他的判断了呃呃，我是飞舞一个好相似、、、
发现当某一轮没有怪物挂掉则之后也不会有任何怪物挂掉；对于每一轮游戏，有可能会挂掉的怪物尽可能是在上一轮挂掉的怪物两侧的怪物。于是直接模拟给定的过程，用链表维护相邻的怪物，并且每一轮仅需考虑在上一轮中挂掉的怪物相邻的怪物即可。
注意某一轮没有怪物挂掉则停止模拟并输出若干个 0。另外注意写法，由规则可知需要在判断完所有怪物是否似掉之后才能修改链表，求下一轮影响到的怪物之前要更新完链表。
总时间复杂度 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], d[kN], dead[kN];
int pre[kN], next[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Solve() {
std::queue <int> q1, q2, q3;
int len = 0;
for (int i = 1; i <= n; ++ i) q1.push(i);
for (int i = 1; i <= n; ++ i) {
int ans = 0;
while (!q1.empty()) {
int x = q1.front(); q1.pop();
if (dead[x] || x <= 0 || x > n) continue;
if (d[x] < a[pre[x]] + a[next[x]]) {
if (!dead[x]) ++ ans, dead[x] = 1;
q2.push(x);
}
}
printf("%d ", ans);
++ len;
if (ans == 0) break;
while (!q2.empty()) {
int x = q2.front(); q2.pop();
q3.push(x);
next[pre[x]] = next[x];
pre[next[x]] = pre[x];
}
while (!q3.empty()) {
int x = q3.front(); q3.pop();
q1.push(pre[x]), q1.push(next[x]);
}
}
for (int i = len + 1; i <= n; ++ i) printf("0 ");
printf("\n");
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
a[0] = a[n + 1] = 0;
d[0] = d[n + 1] = 0;
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) {
dead[i] = 0;
pre[i] = i - 1, next[i] = i + 1;
}
for (int i = 1; i <= n; ++ i) d[i] = read();
Solve();
}
return 0;
}
E
好玩构造，一开始写了个上限是 900 个数的直接硬吃两发，然后莫名其妙地手玩了下直接出来了，最人类智慧的一集。
首先发现一个长度为 \(n\) 的递增数列中有 \(2^{n}\) 个递增子数列（含空数列），于是想到能不能二进制分解 \(X\)。
一开始的想法是发现有两个递增数列 \(a_1\sim a_n\) 和 \(b_1\sim b_m\)，且满足 \(a_1>b_m\)，则数列 \(a_1\sim a_n, b_1\sim b_m\) 中递增子数列数量即为 \((2^{n} - 1) + (2^{m} - 1) + 1\)，于是考虑用 \(2^{x} - 1\) 凑 \(X-1\)，然而这样搞所需数量上限为 \(\sum_{i=1}^{\log_2 X} i \approx 10^3\)，过不去呃呃吃了三发
于是开始手玩。一个思考方向是为了最小化所需数量至少要有一个长度为 \(\left\lfloor\log_2 X\right\rfloor\) 的递增数列，考虑能否复用这个递增数列中的某些元素来凑出其他 2 的幂出来。发现可以通过在左侧添加一些数来满足上述要求。比如：1 2 3 4 有 \(2^4\) 个递增子数列，1 1 2 3 4 有 \(2^4 + 2^3\) 个递增子数列，2 1 2 3 4 有 \(2^4 + 2^2\) 个递增子数列，2 1 1 2 3 4 有 \(2^4 + 2^3 + 2^2\) 个递增子数列。
通过上面的例子，构造方案已经呼之欲出了。具体地：首先构造递增数数列 \(0, 1, \cdots, \left\lfloor \log_2 X \right\rfloor - 1\)，对 \(X\) 进行二进制分解后从高位到低位枚举，若第 \(i(0\le i<\log_2 X)\) 位为 1 则在数列最左侧添加 \(\left\lfloor \log_2 X \right\rfloor - 1 - i\)。该构造方案至多需要 \(2\times \left\lfloor \log_2 X \right\rfloor - 1 \le 120\) 个数，所以不会出现无解的情况。
F
看着像好玩 DP，之后补一下。
写在最后
学到了什么：
- B：虽然这题不会溢出……求 \(C(x, 3)\) 的时候最好写成
1ll * x_ * (x_ - 1) / 2ll * (x_ - 2) / 3ll。 - D：发现每轮会发生改变的元素有限，且总数是确定的，则仅需考虑总复杂度并且每轮对会发生改变的元素进行操作即可。
- E：发现数量与 2 的幂有关考虑二进制分解。