首页 > 其他分享 >2022 icpc 沈阳站 记录(非题解)

2022 icpc 沈阳站 记录(非题解)

时间:2022-11-10 11:01:34浏览次数:59  
标签:ha tem int 题解 2022 学妹 沈阳站 idb ida

赛前

大概是赛前三周才突然知道拥有了比赛机会。

赛前训练和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;
}

标签:ha,tem,int,题解,2022,学妹,沈阳站,idb,ida
From: https://www.cnblogs.com/re0acm/p/16876374.html

相关文章

  • 题解 SP11198 【IPAD - Ipad Testing】
    postedon2021-06-0220:59:42|under题解|sourceSP11198是个神题,它考察了选手们的记忆、乱搞、找规律、压行能力。本题题解是乱搞题解,没有证明。下面就由我来解......
  • 题解 P7724 【远古档案馆(Ancient Archive)】
    postedon2021-07-1419:19:57|under题解|source首先我们先算一下网格最多可能有多少种状态,很显然是\(5^4=625\),完全可以暴力搜索。那怎么实现呢?可以使用bfs,以初......
  • 题解 P7775 【[COCI 2009-2010 #2] VUK】
    postedon2021-08-0316:20:45|under题解|sourcebfs+二分。首先算出一个数组\(w_{i,j}\),表示\((i,j)\)这个格子与离它最近的树的距离。这个过程可以参考P133......
  • 2022.11.10
    P5226小yue解密码反正我觉得这题挺毒瘤的(我太菜了),根本想不到第一篇题解的二分的思路(我太菜了)。但主要还是调代码调的我快逝世了,样例和Hack都过了但永远0pts。还好......
  • 题解 P2482 【[SDOI2010]猪国杀】
    postedon2021-04-1619:58:01|under题解|source想看代码的直接跳Day6这题不能发题解,所以这是做题记录做题原因:499AC,教练推荐我切这题遗言前言:早就听说了这个......
  • P2474 题解
    前言题目传送门!更好的阅读体验?差分约束。思路预处理维护两个数组\(mn_{i,j}\)与\(mx_{i,j}\),表示砝码\(i\)与砝码\(j\)重量差值的最小最大。我们分类讨论:......
  • LeetCode 题解 394. 字符串解码
    题目描述给定一个经过编码的字符串,返回它解码后的字符串。编码规则为:k[encoded_string],表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。......
  • 题解 LGP7071 【 [CSP-J2020] 优秀的拆分】
    postedon2020-11-1217:22:31|under题解|source本题正解是二进制or位运算理解题目P7071优秀的拆分(民间数据)题目链接:https://www.luogu.com.cn/problem......
  • 题解 LGP7909 【[CSP-J 2021] 分糖果】
    postedon2021-10-2322:52:47|under题解|source分类讨论。一句话题意:求\(\max\limits_{i=l}^{r}\{i\bmodn\}\)首先画个数轴,按除以\(n\)向下取整的商把这些整......
  • 题解 LGP8819【[CSP-S 2022] 星战】
    postedon2022-10-3011:39:14|under题解|sourceproblem一个\(n\)个点\(m\)条边的有向图,\(q\)次操作:删除一条边,保证存在;增加一条边,保证不存在;删除一个点......