以后再卡构造我是狗

1227G. Not Same

给定 $n$ 个 $[1, n]$ 的数,要求操作至多 $n + 1$ 次数,每次操作将一个独特的下标集合的数减一,要求将所有数变成 $0$。

1110G. Tree-Tac-Toe

给一个树,树上有些点染了先手的颜色,其余点没染色。现在先后手轮流给没染色的点染黑白,如果某种颜色形成了一个大小不小于 3 的同色联通块则立刻获胜,如果染满了则平局。问最优策略下的游戏结果。




spolier 烂掉了,手动分割线




Solutions

Sol 1227G

我尝试的第一种构造是:第 $i$ 次操作强制删 $i$,不删 $i \bmod n+ 1$。但是这样对于

5
5 1 1 1 1

的数据就解掉了,因为会在输出两行 1 0 0 0 0。后来改成了 $i – 1$ 才行,Tommy 证了,是真的。

#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n;
int a[N], b[N][N];
pair<int, int> c[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) c[i] = {a[i], i};
    sort(c + 1, c + n + 1);
    memset(b, -1, sizeof b);
    for (int i = 1; i <= n; i++) {
        a[c[i].second]--;
        b[i][c[i].second] = 1;
        b[i + 1][c[i].second] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; a[c[i].second] && j <= n + 1; j++) {
            if (b[j][c[i].second] == -1) b[j][c[i].second] = 1, a[c[i].second]--;
        }
    }
    bool flag = 0;
    for (int i = 1; i <= n; i++) flag |= b[n + 1][i] == 1;
    printf("%d\n", n + flag);
    for (int i = 1; i <= n + flag; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", max(0, b[i][j]));
        }
        puts("");
    }
}

Sol 1110G

Tommy 太神啦!什么题都做过不愧是体重比我重 60 斤的 Tommmmmmmmmmmmy。 首先和井字棋相同,先手必不败,我不会直接证但是感受下外加后面的构造可以证明,我们先不考虑初始颜色,讨论如下:

  1. 存在度数为 4 的点,则先手必胜;
  2. 存在度数为 3 的点存在两个出度的度数不小于 2,则先手必胜。
  3. 存在两个距离为偶数的度数为 3 的点,则先手必胜,这一种情况可以看成 1 的拓展。
  4. 其余情况为平局,包括只有两个度数为 3 的距离为奇数的点以及链。

这么讨论很显然,我就差这么 一 点就想到第三个了,但是很可惜做不到。我是狗!

接下来还要处理有颜色的点,可以转化为:先手选择了这个点,那么后手必然要选择我新建的辅助节点。这其实可以通过外接一个根度数为 $2$ 的大小为 $3$ 的子树来做到。于是就做完了。

#include <bits/stdc++.h>
using namespace std;

#define N 2011111

int n, node;
vector <int> E[N];
char s[N / 4];
bool ans;
int dep[N];
bool vis[2];

void dfs(int x, int fa) {
    if (E[x].size() >= 4) ans = 1;
    else if (E[x].size() == 3) {
        int tot = 0;
        for (auto v : E[x]) tot += E[v].size() > 1;
        if (tot >= 2) ans = 1;
        if (vis[dep[x]]) ans = 1;
        vis[dep[x]] = 1;
    }
    for (auto v : E[x]) if (v != fa) dep[v] = dep[x] ^ 1, dfs(v, x);
}

void work() {
    scanf("%d", &n);
    node = n;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'W') {
            E[i].push_back(++node);
            E[node].push_back(i);
            node += 2;
            E[node - 2].push_back(node - 1);
            E[node - 1].push_back(node - 2);
            E[node - 2].push_back(node - 0);
            E[node - 0].push_back(node - 2);
        }
    }
    vis[0] = vis[1] = 0;
    ans = 0;
    dfs(1, -1);
    if (ans) puts("White");
    else puts("Draw");
    for (int i = 1; i <= node; i++) E[i].clear();
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) work();
}

那传说 忘却了我的寂寞
英雄名不堪得
何必较我混沌徒费口沫
这人间 毕竟我真正走过
一途平九百波 九千错
凌云渡成正果
但我 有九九八十一种不舍


Day -1

和 QWsin、wxh 还有一位绵阳小哥住在一间寝室里,还是比较 Excited 的。

七中爷爷们还有南山爷爷们都在左右隔壁,栋栋也不远。

食堂好评。

晚上和 Menci、zyz、Qizy(ZYQN)、Sengxian 等等打炸弹小分队。我好菜啊.jpg

Day 0

上午开幕式,蜜汁校长讲话,“泥萌都是 CCF NOI 的孩子!”。dzd 先生骚话连篇。

Qizy 真牛逼,这么快就撩到 chrt 了。

下午笔试 AK,试机只有传统题,感觉药丸。

晚上心态不太好,开了一道 splay,一道 fft,一道树上前缀和,只能瞎写。最后 fft 没写。

NOI2003 文本编辑器 30min 1A,本来是好事,但是这是我 day1 惨挂的伏笔。

做了做 wxh 的毒瘤题。真毒。

去隔壁四中爷爷们那里 gay 了一会儿,嘿嘿嘿。

晚上睡不着,突然接到初中和高中好朋友的电话,被人惦记着的感觉真幸福。

Day 1

早饭不太舒服。

T1,造计算机?

T2,卧槽,字符集很小的字符串题,怕是药丸。

T3,九老师的 DP,好难。

于是怼 T1。先写了一发暴力,然后再找了好久规律,直到发现一位加一可以看做是一个 xor 和一个区间翻转。复杂度好像超了,想了一会儿发现可以在线段树上 dfs,对 32 位做暴力,然后再区间翻转复杂度就比较对了,算了算内存开得下。

时间已经过去 2h,不过我大概 20 min 就写完了,过了编译直接 1A。退役了想想,还是挺佩服自己在考场上的代码能力的,毕竟 200+ 行代码能够完美无缺地在 20 min 内写完,也可以说挺厉害的了吧。

把对拍写完,赛程过半,心有点慌。T2 因此看题不仔细,把 K 看做了一个 1e5 级别的数,然后怎么想都不行,把脑子里出现的 hash 正解给枪毙了。于是我只能先写 24 分暴力。

这个时候,我做出了一个改变我一生的决定。因为头天晚上 splay 很顺手,我居然没有继续认真看条件,特 么 在 考 场 上 准 备 用 L C T 维 护 链!

然后 1h 过去,写挂。

这个时候是真的慌了。看 T3,本来暴力挺好想的,愣是想了 40 min。

最后当然只能交交最简单的暴力了。


100 + 32 + 10,看成绩还不算太惨,rk 100 左右,还能翻。

wxh MLE,惨惨,不过还是比我高,这才是真正的大佬.jpg。

栋栋崩崩。QWsin 崩崩崩。


发了条说说,说 day2 AK 还能翻。

其实不用 AK 就能翻,不过我是傻子。

本来他们在打 deeeep.io,wxh 在栋栋的带领下开始打东方,毒瘤。

想打三国杀,结果大家都不打,我网页版三国杀也被盗号,找回真麻烦(10 月才找回成功)。

Day 1.5

早上忘记在干嘛了。

下午三国杀。

wxh:连营,AK,杀!

身份证掉了,去办了个临时的。

晚上不想写题,想着 Day 2 需要 AK 心态就比较崩。

Day 2

比 Day 1 有了更重的心理压力。

T1 是一道被我一眼看出来的 2-SAT,但我不会。

T2 是一道看起来像网络流的题。

T3 是防 AK (假)动态凸包。

因为不会 2-SAT,所以很慌,自己 YY 出来的 2-SAT 无法正常工作,骗分也没太有正常工作的可能。

有点崩。

T2,先写暴力网络流。

然后挂大样例,发现从第 29 天开始自己的输出就错了。

知道是建图挂了,但检查不出来。

心态崩了。

这时去把 T3 暴力写了,发现自己可能对向量排序不太熟练,希望有分。

调 T2。
调 T2。
调 T2。
看 T1,没啥好想到的。
调 T2。
调 T2。
调 T2。

时间一分一秒过去。

我终于知道,我要退役了。

看见时间,每跳一次心凉一次。

写了个大家都看不见的 AFO。

游戏结束了。

哭得有点累。


55 + 40 + 20。

下午讲题时,因为分低,连题都听不完,就被叫出去填面试表。

身不由己。

之前的成绩还可以,所以拿到了 sjtu 一本。

尬笑拍了个照,尬笑和张老师握了个手,和进了队的凯爷以及让我潜入四中听课,愿意替我背锅的文老师尬打招呼。

啊,然后在一个少有人看见的地方哭了一会儿。

天真蓝。阳光挺刺眼的,不过过一会儿太阳就落山了。

没去和爸妈老师吃饭,丢脸。

QWsin 似乎比我惨,好像没有签到约。


下午晚上三国杀,吼了一声,只有我不是 THU,全场沉默。

这可是八人局啊。

Day 3

上午错过早饭,和 QWsin 去下象棋。

Qizy 在和 Chrt 下跳棋,哼。

下午拿了个惨白色的牌子,提前回去了。

机场办临时身份证真麻烦。

金中 yylidiw 爷爷告诉我我的图怎么挂了。哦,原来我的“优化”这么厉害。


就这么退役了啊。

day1 如果 T2 没挂,我就 Au 了呀。

或者,day2 我能写出一个 O(nm) 的 2-SAT,并且不“优化”建图,也行呀。

或者,我 day1 没挂,day2 哪怕写不出 2-SAT,只要写对网络流,就能进队啊。

或者,我 day1 被卡常,day2 不失误,也能进队啊。

……

哪有那么多如果,可笑。

wxh 挂了两天 T1,照样能够在 Au 线边上。

栋栋 day1 雪崩,day2 还不是能翻回来。

人家 yql 还不是 day2 翻回了集训队。

哪有那么多如果,实力不济才是最大原因;发挥失常才是常态。

毕竟靠着运气走到现在,也比大多数人好运了吧。

不过,我可能与 thu 无缘了啊。

在二月对自己实力高估后,现在与 pku 也无缘啦。

也罢,这些都不重要,至少还有大学上。退役才是真的不甘心。

该怪谁呢?

怪学校辣鸡,支持竞赛非常晚,比别人少 x >= 1 年学习时间,进队后没有队友?

不吧,人家 LCA 还不是一年集训队。

只能说自己努力不够吧,省选后因为各种原因太水了。

太水了。

没有再来一年的机会,为什么我还要水呢?

后悔,没用啊。你高二了,没有重来的机会了。

你说 Never say die,也只能呐喊到游戏的最后一刻呀。现在,游戏结束了。

那就在这止步吧,永远不要再给自己留下这种尴尬的局面。

那一年我们望着星空
有那么多的灿烂的梦
以为快乐会永久
像不变星空陪着我