Part 2: $[140, 180)$
acm.sgu.ru@CodeForces
Tag: Competitive Programming
Constructive – 极道加训
以后再卡构造我是狗
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。 首先和井字棋相同,先手必不败,我不会直接证但是感受下外加后面的构造可以证明,我们先不考虑初始颜色,讨论如下:
- 存在度数为 4 的点,则先手必胜;
- 存在度数为 3 的点存在两个出度的度数不小于 2,则先手必胜。
- 存在两个距离为偶数的度数为 3 的点,则先手必胜,这一种情况可以看成 1 的拓展。
- 其余情况为平局,包括只有两个度数为 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();
}
acm.sgu.ru-[100, 140)
呐,人总是要有点梦想,万一实现了呢。
acm.sgu.ru@CodeForces
Part 1: $[100, 140)$
100. A+B
print(sum(map(int, input().split())))
NOI 2017 退役
那传说 忘却了我的寂寞
英雄名不堪得
何必较我混沌徒费口沫
这人间 毕竟我真正走过
一途平九百波 九千错
凌云渡成正果
但我 有九九八十一种不舍
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,也只能呐喊到游戏的最后一刻呀。现在,游戏结束了。
那就在这止步吧,永远不要再给自己留下这种尴尬的局面。
那一年我们望着星空
有那么多的灿烂的梦
以为快乐会永久
像不变星空陪着我
BZOJ 代码 (latest update: 20170807)
退役记坑了好久了……但还是不想写
然后这几天想玩RNN,于是预处理了一下自己BZOJ上的AC代码:
- 删去除 C/C++ 的其他语言
- 删去多余空行
- 将题目名称变为注释
于是,你可以点这里下载我的BZOJ AC代码。