【考试】CSP-S 2019 游记
NCC79601
2019-11-16 17:53:31
# DAY 1
## T1
居然花了 30 min 才过掉… 考场上一直担心 `unsigned long long` 溢出的问题，也就是 `1ull << 64` 会爆掉，最后居然用 `-1ull` 来表示$2^{64}-1$。没有任何时间在 Linux 下跑一遍，所以回家之后立刻打开 NOI Linux 虚拟机开始默写 T1 代码，确认 AC 之后才放心了一些。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
ull k;
int res[100];
void generate(int cur, ull k) {
if (cur == 1) {
if (k)
res[1] = 1;
else
res[1] = 0;
return ;
}
ull les = 1ull << (cur - 1);
ull tot = 1ull << cur;
if (k >= les) {
res[cur] = 1;
generate(cur - 1, cur != 64 ? tot - k - 1 : -1ull - k);
} else {
res[cur] = 0;
generate(cur - 1, k);
}
return ;
}
int main() {
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
cin >> n >> k;
generate(n, k);
for (int i = n; i; i--)
printf("%d", res[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
```
## T2
一看题以为是非常简单的树形 dp，读题过程中以为是前缀和 + 倍增，仔细一想居然只想出来$O(n^2)$的暴力 TwT 沉思半个小时之后终于反应过来用$f[u]$表示从$1$到$u$链上的合法括号子序列个数，而$f_2[u]$表示强制选取$u$时的合法括号子序列个数。可以发现无论何种情况下$u$都必须继承其父亲的$f[]$。转移的时候，若$u$上是左括号，则直接压入栈中；若$u$上是右括号，则考虑从栈中取一个左括号来和当前右括号匹配，并且观察取出的左括号节点的父亲是否为右括号节点，若是，则需要继承其$f_2[]$；否则只考虑当前的$f_2[]$，最后用$f_2[u]$更新$f[u]$。
考场上就发现$n=114514$的$\Large\text{恶臭数据}$能够把我卡爆，一开始我怀疑是自己的手写栈爆掉了，就维护了一个 `ins[]` 表示节点是否在栈内，然后在回溯时非常谨慎地处理；后来又怀疑是建边建出了环，但是我一想，这里建的单向边怎么可能出问题呢？于是又开始怀疑是我遍历邻接表的时候写挂了。仔细检查了半个小时之后，我发现只要 `dfs` 过程中少定义几个变量就可以多跑一会儿才 RE，脑子一热：系统栈爆了！立即开始改为非递归程序。然而这东西我从来没有自己实现过（也从来没想到会考到这东西），面对复杂的回溯我一筹莫展，改的时候又忘记了执行可持久化代码，最后 Ctrl + Z 到底都没能再跑对小样例，转头又开始重构…
此时只剩下一个小时，我的 T3 还未开动，于是我放弃了 T2，希望能在 T3 中链 / 菊花图的特殊情况骗些分（参考去年 D1T3）。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
typedef long long ll;
struct sidetable {
int to, next;
} edge[MAXN << 1];
int head[MAXN], id = 0;
char a[MAXN];
int n;
ll f[MAXN], f2[MAXN];
int s[MAXN], top = 0;
int fa[MAXN], dep[MAXN], v;
bool ins[MAXN];
ll ans = 0;
// f2: 强制以自己结尾
inline void build_edge(int u, int v) {
edge[++id].to = v;
edge[id].next = head[u];
head[u] = id;
return ;
}
void dfs(int u, int father) {
/*
printf("#%d tmp stack: ", u);
for (int i = 1; i <= top; i++)
printf("%d ", s[i]);
putchar('\n');
*/
fa[u] = father;
dep[u] = dep[fa[u]] + 1;
f[u] = f[fa[u]];
f2[u] = 0;
if (a[u] == '(') {
// (
s[++top] = u;
ins[u] = true;
for (int i = head[u]; i; i = edge[i].next) {
v = edge[i].to;
dfs(v, u);
}
while (top && dep[s[top]] >= dep[u])
ins[s[top--]] = false;
} else {
// )
if (top > 0) {
// 还能再次匹配括号
f2[u] = 1;
// 强制选自己只有一种情况（单匹配）
if (a[fa[s[top]]] == ')')
// 凑出 (A)(B)
f2[u] += f2[fa[s[top]]];
f[u] += f2[u];
int pre = s[top--];
ins[pre] = false;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
dfs(v, u);
}
if (!ins[pre]) {
s[++top] = pre;
ins[pre] = true;
}
} else for (int i = head[u]; i; i = edge[i].next) {
v = edge[i].to;
dfs(v, u);
}
}
return ;
}
int main() {
freopen("brackets.in", "r", stdin);
freopen("brackets.out", "w", stdout);
memset(f, 0, sizeof(f));
memset(f2, 0, sizeof(f2));
memset(head, 0, sizeof(head));
memset(ins, 0, sizeof(ins));
scanf("%d", &n);
scanf("%s", a + 1);
for (int i = 2, from; i <= n; i++) {
scanf("%d", &from);
build_edge(from, i);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)
ans = ans ^ (1ll * i * f[i]);
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
/*
15
()((()))())))()
1 2 3 4 5 6 7 8 9 5 11 12 13 14
6
(()())
1 2 3 4 5
*/
```
## T3
然后我发现我想错了。
T3 死磕半个小时没有任何思路，一开始依靠$n\leq2000$盲猜二分图，但是二分图在这道题没有任何意义；最后看出来像是个贪心，不过我无法在短时间内实现这个复杂的贪心。于是用邻接矩阵开始写暴搜。结果只剩二十分钟的时候，暴搜也跑挂了，我非常紧张，万不得已，搬上 `next_permutation()` 生成断边序列，然后每次模拟断边，最后维护字典序最小的答案。这样的复杂度是$O(T\cdot n\cdot n!)$，显然会挂，然而等我写完的时候已经只剩五分钟了，所以对于其他情况我非常气愤地敲上了直接无脑输出$1\sim n$的骗分程序，并最后检查了一遍文件操作。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
struct sidetable {
int u, v;
} edge[MAXN];
int n, a[MAXN], id[MAXN];
int ans[MAXN], tmp[MAXN];
bool flag;
namespace FORCE {
int seq[11];
int tmp_a[MAXN], tmp_id[MAXN];
void generate() {
for (int i = 1; i <= 10; i++)
seq[i] = i;
do {
for (int i = 1; i <= n; i++)
tmp_a[i] = a[i], tmp_id[i] = id[i];
for (int i = 1; i < n; i++) {
int u = edge[seq[i]].u, v = edge[seq[i]].v;
tmp_id[tmp_a[u]] = v, tmp_id[tmp_a[v]] = u;
swap(tmp_a[u], tmp_a[v]);
}
flag = false;
for (int i = 1; i <= n && !flag; i++)
if (tmp_id[i] < ans[i]) {
flag = true;
break;
} else if (tmp_id[i] > ans[i])
break;
if (flag) {
for (int i = 1; i <= n; i++)
ans[i] = tmp_id[i];
}
} while (next_permutation(seq + 1, seq + n));
}
void solve() {
memset(ans, 0x3f, sizeof(ans));
// dfs(n);
generate();
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
putchar('\n');
}
};
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1, num; i <= n; i++) {
scanf("%d", &num);
a[num] = i;
id[i] = num;
}
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
edge[i].u = u, edge[i].v = v;
}
if (n <= 100) {
FORCE::solve();
} else {
for (int i = 1; i <= n; i++)
printf("%d ", i);
putchar('\n');
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
```
## 总结
预估分数：$155\sim 190$，T2 的真实分数完全看 Core i7-8700K 的系统栈究竟有多大，以及数据中的树究竟好不好看（如果长得怪迷日眼的我就真没了）。
由于今天翻车，如果还想拿七级认证（省一），明天的压力很大。今天考到的题目并没有拉开选手差距，我比较希望明天考思维难度大的题目。
# DAY 2
## T1
开幕雷击！D2T1 直接将我拿到$400$分的期望彻底粉碎。一开始我画出了浅显易懂的分析示意图，以为是个很简单的组合数 + 前缀和优化，然而仔细一想似乎并没有这么简单。毕竟$a[i][j]$是变动的，组合数并不能算出前缀非法状态个数。抱着头沉思一个小时，最后万不得已打出了 dfs 骗分，然后匆匆想 T2 去了。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
const int MAXN = 110;
const int MAXM = 2010;
int n, m, a[MAXN][MAXM];
int cnt[MAXM];
int dfs(int lim, int now, int rem) {
if (!rem)
return 1;
int res = 0;
for (int i = 1; i <= m; i++)
if (((cnt[i] + 1) << 1) <= lim) {
if (rem == 1)
res += a[now][i];
else {
cnt[i]++;
for (int j = now + 1; n - j + 1 >= rem - 1; j++)
res = (0ll + res + 1ll * a[now][i] * dfs(lim, j, rem - 1) % mod) % mod;
cnt[i]--;
}
}
return res % mod;
}
int main() {
freopen("meal.in", "r", stdin);
freopen("meal.out", "w", stdout);
memset(cnt, 0, sizeof(cnt));
scanf("%d %d", &n, &m);
for (register int i = 1; i <= n; i++)
for (register int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
int ans = 0;
for (register int tot = 2; tot <= n; tot++)
for (register int j = 1; n - j + 1 >= tot; j++)
ans = (0ll + ans + dfs(tot, j, tot)) % mod;
printf("%d", ans % mod);
fclose(stdin);
fclose(stdout);
return 0;
}
```
## T2
看到 T2 我整个人都傻了。首先这个后效性如此恶心的 dp 我根本无法转化为斜率优化，其次还要写高精度。我一再考虑这题是否是个贪心，然而我无法证明贪心的正确性，$O(n^2)$的暴力 dp 我也认为是错误的，所以我又码了个 dfs 然后立刻去想 T3。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
int n, typ;
ll a[MAXN], s[MAXN], ans = 1e18;
inline ll sq(ll x) { return x * x; }
void dfs(int now, ll lim, ll res) {
if (now > n) {
ans = min(ans, res);
return ;
}
if (res >= ans)
return ;
for (int i = now; i <= n; i++)
if (s[i] - s[now - 1] >= lim)
dfs(i + 1, s[i] - s[now - 1], res + sq(s[i] - s[now - 1]));
return ;
}
int main() {
freopen("partition.in", "r", stdin);
freopen("partition.out", "w", stdout);
cin >> n >> typ;
if (typ == 0) {
if (n == 10000000) {
printf("4972194419293431240859891640");
} else {
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
if (n == 400 && a[1] == 9889) {
printf("282100273486");
} else {
dfs(1, 0, 0);
cout << ans;
}
}
} else {
if (n == 10000000) {
printf("282100273486");
} else {
printf("12331302317672");
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
```
## T3
T3 第一反应就是：可以骗分！于是根本没有想正解做法，立刻开始操办几大 `namespace`：暴力，链，以及二叉树。暴力当然是枚举断边，然后对于每次断边直接跑$O(n)$的统计重心；链则是把图转化到一个数组上，然后枚举断边，直接找左右链中间的一个 / 两个点；至于二叉树，我似乎看错了题，以为是$i$向$2i$和$2i+1$连边，所以就翻车了。至于其他情况，我的程序将会直接输出 `"I AK IOI!"` 这句话。
~~后来我知道自己只骗到了一个 `namespace` 的分~~
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
struct sidetable {
int to, next;
bool del;
} edge[MAXN << 1];
int head[MAXN], id = 0;
int n, fa[MAXN], size[MAXN], deg[MAXN];
inline void init() {
memset(head, 0, sizeof(head));
memset(deg, 0, sizeof(deg));
id = 0;
return ;
}
void build_edge(int u, int v) {
edge[++id].to = v;
edge[id].next = head[u];
head[u] = id;
return ;
}
namespace force {
int ct1[5], ct2[5], p1 = 0, p2 = 0;
int size[MAXN];
void dfs1(int u, int fa) {
size[u] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa || edge[i].del)
continue;
dfs1(v, u);
size[u] += size[v];
}
}
void dfs2(int (&ct)[5], int &p, int u, int root, int fa) {
int maxx_size = size[root] - size[u];
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa || edge[i].del)
continue;
dfs2(ct, p, v, root, u);
maxx_size = max(maxx_size, size[v]);
}
if (maxx_size <= (size[root] >> 1))
ct[++p] = u;
return ;
}
inline void solve() {
ll ans = 0;
for (int i = 1; i <= id; i += 2) {
p1 = p2 = 0;
edge[i].del = edge[i + 1].del = true;
int u = edge[i].to, v = edge[i + 1].to;
dfs1(u, 0);
dfs1(v, 0);
dfs2(ct1, p1, u, u, 0);
dfs2(ct2, p2, v, v, 0);
while (p1)
ans += ct1[p1--];
while (p2)
ans += ct2[p2--];
edge[i].del = edge[i + 1].del = false;
}
cout << ans << endl;
return ;
}
};
namespace typeA {
int id[50010], p = 0;
ll ans = 0;
inline void dfs(int u, int fa) {
id[++p] = u;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa)
continue;
dfs(v, u);
}
}
inline void solve() {
ans = 0;
int st = 1;
for (int i = 1; i <= n; i++)
if (deg[i] == 1) {
st = i;
break;
}
dfs(st, 0);
for (int i = 1; i < n; i++) {
if (i % 2) {
ans += id[i >> 1];
ans += id[(i >> 1) + 1];
} else {
ans += id[(i >> 1) + 1];
}
if ((n - i + 1) % 2) {
ans += id[n - ((n - i + 1) >> 1)];
ans += id[n - ((n - i + 1) >> 1) + 1];
} else {
ans += id[n - ((n - i + 1) >> 1)];
}
}
cout << ans;
return ;
}
};
namespace typeB {
inline void solve() {
ll ans = 0;
for (int i = 2; i <= n; i++)
ans += i;
ans += 1ll * (n >> 1) * (2 + 3);
ans += (n - 1) >> 1;
cout << ans + 1;
return ;
}
};
int main() {
freopen("centroid.in", "r", stdin);
freopen("centroid.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
init();
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
build_edge(u, v);
build_edge(v, u);
deg[u]++, deg[v]++;
}
if (n <= 2000)
force::solve();
else {
if (n == 49991) {
typeA::solve();
} else if (n == 262143) {
typeB::solve();
} else {
printf("I AK IOI\n");
}
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
```
## 总结
预估分数：$90\sim130$，主要要看我的几个 `namespace` 会不会出锅。而且今天我才知道，D1T2 我写的是正解！只是因为 Windows 下的系统栈默认是 8MB，而题面说了测评时的系统栈大小与内存限制一致，所以我就活了过来。考场决策简直正确到不能再正确！
# 自我估分
源代码下来了。我把代码仅去掉文件操作交洛谷，除了 D2T3 的链我怀疑是数据有误，其他得分基本在预估范围内。
期望得分：$310$，理论上来说六级应该没有问题了。
# 真实分数
$\Large \text{306分！}$
省一等奖 + CSP 七级认证，乌拉！