-->

Codeforces 比赛训练计划

打多点 Codeforce 还是可以提升素养的
不管打得怎样都总结一下
至少back到E题!!


Virtual participation

  • 2017.10.18 Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017)
  • 2017.10.19 Codeforces Round #428 (Div. 2)
  • 2017.10.22 Codeforces Round #429 (Div. 2)

  • Contest

  • 2017.12.16 Codeforces Round #451 (Div. 2)
  • 2017.12.17 Codeforces Round #452 (Div. 2)

  • 一些打Codeforces奇怪的姿势

    1.打Div2不用考虑太多,以速度为主,map,set,vector要善用,来提高代码简洁速度
    2.时不时可以用c++14里面的auto 偷下懒,还有一行头文件

    1
    #include<bits/stdc++.h>

    3.往简单里想,即使有些题是裸题也不要用太多奇怪的算法去写,切忌装逼
    4.当做法很复杂的时候看看能不能换种做法和角度去思考
    5.string 支持+操作,还有string.size()
    6.变量名尽量都是小写,并且数组从0开始读入,可能会减少一些细节问题?
    7.看到一些像要处理链表的问题先想到能不能并查集
    8.不要在一些细节犹豫太久,尽量使用输出调试比较快
    9.心要大,不要怕Wrong Answer On test 1
    10.开题顺序很重要,如果看到情况不妙,处于下层状态,应该选择题目比较短的题开始跳题做
    正常顺利的是 A-B-C-D-E
    不妨可以 A-C-D-B-E
    英文不好选题意短分值高的题先做


    Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017)

    2/5

    只出了A,B题好气啊 其实D差不多想了出来 E的话就是写的SG姿势有点不对啊
    A.看样例懂了嘛 这是一个递增 然后平 然后递减的函数 直接就是 tN 判断一下就好了 一开始还WA了一发…
    B.考虑A->B B->C 而且是旋转 就有点像三个在圆上的点一样 所以充要条件就是弧长相同也就是弦长相同 且不在一条直线上,用向量什么的判一下就好了
    C.好蠢啊考虑到一个点在2D平面内最多也就有其他4个点存在(四个点互相垂直)多一个都不要合法
    那么3D就有其他6个点 简单点就是多一个坐标轴多了两条垂直线
    所以5D就有其他10个点 所以满足题目要求的充要条件是N<=11 O(N^3) 判断即可
    D.这道题是一道好题 首先我们想枚举质数 我们可以考虑把质数和质数的倍数变成一条条直线
    然后使在序列里面的数通过增加或者删除到达这些线
    考虑怎么维护这些东西 一开始想卧槽不会算啊每次都要N
    其实后来做回的时候发现只要维护两个前缀就好了

    num[i] 表示数为i前面包括i有多少个数在序列中出现
    sum[i] 表示数为i前面包括i在序列中出现的数的总和

    然后判断一下分界点就AC了
    E.想到了啊但是SG打错了 一眼就可以知道题目的每一个数分解的质数 假设为p
    它们每个数的次幂k可以使p[i]|(1<<(k-1)),为什么可以这样做 因为次幂相同的出现一次就够了 消的方法是一样的
    而每一次的操作 对于SG函数来说 假设取走k个p 转移就是 (p[i]>>k)|(p[i]&(1<<(k-1)-1))
    顺便附上这题的代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #include <bits/stdc++.h>
    using namespace std;
    const int Maxn=110;
    int N,A[Maxn]; map<int,int>K,dp;
    int SG(int x)
    {
    set<int> S;
    if(dp.count(x)) return dp[x];
    if(x==0) return 0;
    for(int i=1;i<=30;i++) // 取i个
    {
    int y=(x>>i)|(x&((1<<(i-1))-1) );
    if(y!=x) S.insert(SG(y));
    else break;
    }
    int p=0;
    while(!S.empty())
    {
    int now=*S.begin();
    if(now==p) p++;
    else if(now>p) return dp[x]=p;
    S.erase(S.begin());
    }
    return dp[x]=p;
    }
    int main()
    {
    scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    for(int i=1;i<=N;i++)
    {
    int x=A[i];
    for(int j=2;j*j<=x;j++)
    {
    int k=0;
    while(x%j==0)
    {
    x/=j; k++;
    }if(k) K[j]|=(1<<(k-1));
    }if(x!=1) K[x]|=1;
    }
    int tmp=0; dp[0]=0;
    for(auto i:K) tmp^=SG(i.second);
    if(tmp==0) printf("Arpa\n");
    else printf("Mojtaba\n");
    return 0;
    }


    Codeforces Round #428 (Div. 2)

    2/5

    也是只出了两题 而且这次有点不应该的
    第二题出的时候好像不是很顺利 最后也没调出来 果然大讨论是写不好的
    第四题在赛后想出来了 发现还是可以做的 但是在两小时内出来还是实力之外
    A.模拟 每一天拿完Ai个就去送 假设剩下last个 那么就送出min(last,8) 最后统计送出的有没有K个就好
    B.贪心大讨论 可以发现 能四个一起的尽量四个一起 能两个一起的尽量两个一起
    这样跑完后 如果还有四个及其以上 显然就是NO了 因为这种情况有空位的肯定放进去了
    剩下的就是三个,两个,一个的其中一种情况
    对于四个一排的 我们可以依次放下面所述情况

    1.放43的 占3排 竖着放
    2.放1
    3的 占1排 横着放
    3.放2+1 或者 1+1 隔一个横着放
    4.放3*2的 占2排 两个竖着一个横着
    5.还剩下的虽然浪费 但是还是要放满4个一排的 就单独放1和2

    对于两个一排的 我们可以又考虑下面的情况

    1.单独放一个1

    C.好水啊 就从最后面往前做一次裸的期望dp就好了哦
    $$ dp[x] = (dp[y]+1) * (1/D[x])$$

    D.经典好题 但是很可惜 没有在模拟比赛的时候打出来

    首先按照前面的经验 可以枚举因数
    假设一个因数为u 那么序列中元素拥有u这个因数的个数 就定义为cnt[u]

    然后发现直接组合就有点问题 因为可能算多了 算多了的原因是有可能这些数的gcd为u的倍数
    我们观察答案 对于每个gcd来说 Ans就是:
    $$ Ans=\sum\limits_{i}^{} i\times gcd为i序列长度\times gcd为i的这个序列长度的个数 $$

    这样我们很直观 我们如果可以维护序列的长度和个数的乘积 我们就可以解决问题
    而且我们发现这个长度和个数的乘积其实是可以通过相减然后去掉算多了的
    原因在于每个序列都不一样
    然后我们化一下式子 定义i的长度和个数的乘积为 sum[u]
    $$ sum[u] = \sum\limits_{i=1}^{cnt[u]} \binom{cnt[u]}{i} \times i $$

    $$ sum[u] = \sum\limits_{i=1}^{cnt[u]} \frac{cnt[u]!}{(cnt[u]-i)! (i-1)!} $$

    $$ sum[u] = cnt[u] \times \sum\limits_{i=1}^{cnt[u]} \binom{cnt[u]-1}{i-1} $$

    $$ sum[u] = cnt[u] \times 2^{cnt[u]-1} $$

    然后要减去多算的

    $$ sum[u] = sum[u] - \sum\limits_{i\times u<=limit} sum[u \times i] $$

    最后的答案就是

    $$ Ans = \sum\limits_{i=1}^{limit} i \times sum[i] $$

    E.这道题讲道理什么鬼啊
    我们可以画图发现一个结论

    答案就是给一个极大团的点平均标上权值即可

    下面我们来证明这个结论:

    首先我们来证明假如不是团 一定不优:

    假设一个多项式答案为A 为团大小为k的极大团上的点平均标上权值 总权值为m
    $$ A=\frac{k \times (k-1)}{2} \times (\frac{m}{k})^2 $$
    假设加一条点 多了k-1条边 就是不是极大团 接近与极大团 显然边加的越多越优
    $$ B=(\frac{k \times (k-1)}{2} + k - 1) \times (\frac{m}{k+1})^2 $$
    化简后得
    $$ B=\frac{m^2}{2} \times \frac{(k-1)(k-2)}{(k+1)^2}$$
    A-B 得
    $$ A-B = \frac{m^2}{2} \times \frac{k-1}{(k+1)^2} \geq 0$$
    假设不止一个团 有p个相同的团 设答案为多项式C
    $$ C= p \times \frac{k \times (k-1)}{2} \times \times (\frac{m}{pk})^2 $$
    $$ C=\frac{m^2}{2p} \times \frac{k-1}{k} < A $$

    然后我们要怎么求一个最大团:
    我直接上别人的搜索说明了

    1. 剪枝1:常用的指定顺序, 即枚举第i个顶后, 以后再枚举时枝考虑下标比大它的, 避免重复。
    2. 剪枝2:自己开始从前往后的枚举顶点, TLE两次. 后来从后往前枚举顶点,发现可以利用顶点之间的承袭性.我用num[i] 记录的可选顶点集合为 V[i, i+1, … , n] 中的最大团数目, 目标是求num[1].
      分析易知, num[i] = num[i+1] 或者 num[i]+1 (num[1…n] 具有非降的单调性,从后往前求)
      由这个式子以及num[]信息的记录,使得我们可以增加两处剪枝:
      3.上/下剪枝:假设当前枚举的是顶点x, 它的第一个邻接顶是i (标号一定比x大,即num[i]已经求出) 我们可以知道, 若 1 + num[i] <= best, 那么是没没要往下枚举这个顶点x了,因为包含它的团是不可能超过我们目前的最优值的。
    3. 立即返回剪枝: 由于num[i]最大可能为num[i+1]+1, 所以在枚举顶点i时,只要一更新best,可知此时的num[i]就为num[i+1]+1了,不需要再去尝试找其他的方案了,所以应立即返回.

    就是倒着来做 然后用一个num数组剪枝

    附上代码吧:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <vector>
    using namespace std;
    const int Maxn=50;
    int G[Maxn][Maxn]; int N,C;
    int num[Maxn]; //[i,N] the maxinum size of the Clique
    int best=0;
    bool DFS(vector<int> V,int cnt) // cnt: the size of the Clique
    {
    if(V.size()==0)
    {
    if(cnt > best){best=cnt; return 1;}
    return 0;
    }
    vector<int> T;
    for(int i=0;i<V.size();i++)
    {
    if(cnt + (V.size()-i) <= best) return 0;
    if(cnt + num[V[i]] <= best) return 0;
    T.clear();
    for(int j=i+1;j<V.size();j++)
    if(G[V[i]][V[j]]) T.push_back(V[j]);
    if(DFS(T,cnt+1)) return 1;
    }
    return 0;
    }
    int main()
    {
    scanf("%d%d",&N,&C);
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) scanf("%d",&G[i][j]);
    //MaxinumClique
    vector<int> V;
    for(int i=N;i>=1;i--)
    {
    V.clear();
    for(int j=i+1;j<=N;j++) if(G[i][j]) V.push_back(j);
    DFS(V,1); num[i]=best;
    }
    double ans=(double)C*(double)C*(double)(num[1]-1)/(double)(num[1])/2.0;
    return printf("%.10lf\n",ans),0;
    }
    /*
    3 1
    0 1 0
    1 0 0
    0 0 0
    */


    Codeforces Round #429 (Div. 2)

    3/5

    A.数一下每个字母就好了哦
    B.只要不是全偶情况都是可以第一个赢的 原因很简单 如果全部是奇数就立刻取光 否则先取1个奇数段
    然后留下给后手 后手肯定只能选偶数段或者输掉 剩下的还是奇数段
    C.结论题 看样例就知道是把A的元素倒序=B中的升序
    D.好强的一道题啊 我没有当场想到 首先想到的是 可以把1和-1 和1的匹配掉 然后剩下的是1和0的
    然后发现有传递性
    比如说原来是1和0的两个标号的点 一条边 1->0 可以把两个标号变成0->1
    所以对于两个标号1和1的点 通过连一条边 可以变成0 0
    所以我们只要发现 一对1联通即可 但是问题来了 怎么输出边数
    因为是联通图 我们考虑将它建成一颗树 它就可以使标志具有传递性 就不用建成一个图
    那么一个树就很好做了 只要treedp就知道下面要不要连边上来了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int Maxn= 1234567;
    int A[Maxn],B[Maxn]; pair<int,int> pr[Maxn];
    priority_queue<int>Q;
    bool Cmp(const pair<int,int> &x,const pair<int,int> &y)
    {
    return x.first <y.first;
    }
    int ans[Maxn];
    int main()
    {
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]),Q.push(A[i]);
    for(int i=1;i<=N;i++) scanf("%d",&B[i]),pr[i].first=B[i],pr[i].second=i;
    sort(pr+1,pr+N+1,Cmp);
    for(int i=1;i<=N;i++)
    {
    ans[pr[i].second]=Q.top(); Q.pop();
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
    return 0;
    }

    E.不会做 有空填坑


    Codeforces Round #451 (Div. 2)

    4/6

    现在的比赛都是6题啊,很高级
    可惜这场失误了,才出了4题,5题算是大众水平?
    总体来说最亏的是第二题出太久了

    A.看最后一位是什么就直接判断是向上取整还是向下取整

    B.我好sb啊,一开始写了exgcd好像是裸题?发现写起来过不了大的那组样例,然后才写两个for过了,就是ax+by=n ,枚举分别枚举x到1000w,枚举y到1000w就好了

    C.我是最后才写C题的,因为题意很长然后没看,但是很可惜没在规定时间调出来,导致少了一题
    赛后看了下别人写这种题怎么写的,为什么自己写这么慢,然后涨了点姿势,原来string支持+和+=操作
    每次把每个串的后缀塞进map就好了

    D.一开始写错了一点发现有点慌啊,其实就是某个时间段要关掉一些闹钟,很显然如果当前时间点要关掉闹钟的话,肯定关掉对于当前点来说最近的,因为最近的闹钟对以后的影响的范围比较大啊,然后一个set的事

    E.就是注意一点trick 0变成不是平方数要走两步,然后分平方数的个数是大于N/2还是小于N/2,然后用set维护调整这些数就好了


    Codeforce Round #452 (Div. 2)

    3/6

    这场比赛发现自己垃圾到爆炸?
    大众水平是4,5题,我才出了3题
    主要是出C出的比较慢,然后后面B被hack掉心态就很炸
    A.首先把1和2的给用完,剩下的就是1的

    B.就是几个平年和闰年的数组拼起来算一下就好了,好像很多人不注意顺序就被卡掉了?我是被Hack掉的

    C.我好蠢啊一开始头尾指针往内缩跑了一遍,发现错了,然后分成两堆分别是奇数和偶数,进行调整,然后记奇数和为s1,偶数和为s0
    s1>s0 的话 那么就要3和2换 5和4换
    s0>s1 的话 那么就是1和2换 3和4换
    好像题解是4个4个一组这样,然后暴力把前面n%4个数给分到两组去就好了….
    这道题花了不少时间

    D.写D写了很久又是赛后AC,发现次次比赛都没有充足的时间
    我的做法好像很麻烦 f[i][0/1/2][0/1/2] 表示到第i位,两个数分别对于上限的情况
    0是比上限小,1是和上限一样,2是比上限大,然后从低位到高位大力转移
    好像有种做法是,假设你已经知道是以什么结尾了,比如说99,那么你只要枚举199,299。。。899产生的贡献就好了

    E.好像应该当时先写E再写D比较好,E其实很简单,维护一个set和带权并查集,每次删除就在带权并查集里面看看左右两边是否能合并
    然后用set维护最多出现和出现位置就好了,并查集还可以当作链表来使用的其实,而且更方便