赛前
大概是赛前三周才突然知道拥有了比赛机会。
赛前训练和vp频率很高,有一段时间cf上都是绿的。比赛的那一周只有一天没在vp,到了周六热身赛我人都有点麻木。(可能正赛也是类似的状态吧)
比赛的过程be like:
首先是吃饭时间有点赶,回来之后马上开始登录比赛,登录之后只有几分钟就要开始了。
11:55
发现忘了准备摄像头,而且笔记本上的USB接口不够用,需要拓展坞
于是赶紧叫队长去找摄像头和拓展坞,好在很快都找到了
接入摄像头后屏幕仍然是黑的,这时候已经 11:58 了,于是又紧急呼叫志愿者冯老师,他上来一通操作,经一队提醒,幸运地在开赛之前(或许是恰好)开启了摄像头。
12:00
我坐在电脑前,队友拿着纸质题面看题。
开赛一分钟不到就有人过了 D ,我也赶紧点开这题的题面。发现确实签到,就开始写。
(小插曲:一队看到有人过D后说:“de(轻声)是签到”,然后学妹听错了,对另一个队友说J是签到,队友赶紧看J题去了,读完发现并不是) 笑死
写完让学妹也看了看,交了,一发过签到。
12:10
一段时间内都没有其他题通过,学妹看了B,是构造。我看了A,完全不会。
12:15
学妹跟榜去开C,说了个做法就先上机写了,我和另一队友讨论了下,觉得没问题。
学妹在26min的时候过了C。
12:30 (大概是)
开场很久才有人过了F,这期间内我们随便地开题,没发现可做的
F也是构造,我觉得学妹应该会,就把题意讲给学妹
13:00
学妹继续想F,这时候L也有人过了,qyy读了题,给我讲题意。
我很快想到了是暴力,做法没太细想,学妹在调F,我就先上机写L,调了一会发现不对,就又下来改。
这时候可能受到了一些场内声音的干扰,也可能是读题不仔细,L本来题就比较长,我们漏掉了一个关键的信息,这导致模拟样例结果不一致,所以我们就怀疑是题读错了,
曲解了另一条关键信息,改来改去都发现过不了样例。代码两位队友都帮我看过了,我们都觉得很对。
于是我们就开始了双向卡题。直到比赛结束,坐牢四小时
感想
最后的结果是L过了400多人,我们rk420+,2题。
看了榜。其实如果L三小时之内出的话,就能有牌了。
拿牌一点也不难啊
反省一下原因,我觉得主要原因是在我的。
1.队友第一遍读完题之后,说不是很确定,于是我又读了一遍,然而根本读不进去,大致读了一下意思,依然略过了细节。
2.代码写的比较慢。我以为不能直接遍历每个人,认为会超时,所以用了很多状压、二进制的写法,然而是根本用不着的。
3.受场外声音的干扰,容易听信其他队的声音,少了自己的思考。
想放一下我复杂的写法:(修改后能过样例版)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 8;
int n, m;
int ATKa[N], ATKb[N], ha[N], hb[N], ca[N], cb[N];
double A, B, T;
inline int lowbit(int x) {
return x & (-x);
}
// alice 0 bob 1
inline void dfs(int round, int Sa, int Sb, double p) {
// printf("%d %d %lf\n", Sa, Sb, p);
int cnta = __builtin_popcount(Sa);
int cntb = __builtin_popcount(Sb);
if(cnta == 0 || cntb == 0) {
if(cnta == 0 && cntb == 0) T += p;
else if(!cnta) B += p;
else A += p;
return;
}
if(round == 0) {
int mn = 1e9, ida;
for(int i = 0; i < n; i++) {
if(ha[i] > 0 && ca[i] < mn) {
mn = ca[i];
ida = i;
}
}
int tem = Sb;
while(tem) {
int tailb = lowbit(tem);
int idb = __lg(tailb);
tem -= tailb;
ha[ida] -= ATKb[idb];
hb[idb] -= ATKa[ida];
if(ha[ida] <= 0) Sa = (Sa & (~(1 << ida)));
if(hb[idb] <= 0) Sb = (Sb & (~(1 << idb)));
ca[ida] += 1;
// cb[idb] += 1;
dfs(round ^ 1, Sa, Sb, p / cntb);
if(ha[ida] <= 0) Sa = (Sa | ((1 << ida)));
if(hb[idb] <= 0) Sb = (Sb | ((1 << idb)));
ha[ida] += ATKb[idb];
hb[idb] += ATKa[ida];
ca[ida] += -1;
// cb[idb] += -1;
}
}
if(round == 1) {
int mn = 1e9, idb;
for(int i = 0; i < m; i++) {
if(hb[i] > 0 && cb[i] < mn) {
mn = cb[i];
idb = i;
}
}
int tem = Sa;
while(tem) {
int taila = lowbit(tem);
int ida = __lg(taila); // a 队头
tem -= taila;
ha[ida] -= ATKb[idb];
hb[idb] -= ATKa[ida];
if(ha[ida] <= 0) Sa = (Sa & (~(1 << ida)));
if(hb[idb] <= 0) Sb = (Sb & (~(1 << idb)));
// ca[ida] += 1;
cb[idb] += 1;
dfs(round ^ 1, Sa, Sb, p / cnta);
if(ha[ida] <= 0) Sa = (Sa | ((1 << ida)));
if(hb[idb] <= 0) Sb = (Sb | ((1 << idb)));
ha[ida] += ATKb[idb];
hb[idb] += ATKa[ida];
// ca[ida] += -1;
cb[idb] += -1;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &ATKa[i]), ha[i] = ATKa[i];
for(int i = 0; i < m; i++) scanf("%d", &ATKb[i]), hb[i] = ATKb[i];
if(n >= m) dfs(0, (1 << n) - 1, (1 << m) - 1, 1.0 / (1 + (m == n)));
if(m >= n) dfs(1, (1 << n) - 1, (1 << m) - 1, 1.0 / (1 + (m == n)));
printf("%.10f\n%.10f\n%.10f\n", A, B, T);
system("pause");
return 0;
}