文档章节

【codeforces】Codeforces Round #366 (Div. 2)

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:58
字数 1069
阅读 3
收藏 0

简直中了不能A C题的诅咒了……
md这次二十分钟做完B结果还是没能A C题
药丸……

B

题目大意

进行n局游戏,每一局规则如下
两名玩家以次选一个大于一数字进行拆分,将他拆成k和a[i]-k,先手胜输出1否则输出2
第i局为在第i-1局的基础上增加一个a[i]


小博弈?
本着不增加环的原则,我们将环拆成a[i]-1和1(不知道这样好不好……),那么就只和奇偶性有关了
然后恩恩
随便异或一下……
凑过样例也就凑过了所有数据……
mdzz
不过博弈论我实在是不想想……
233333333

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
int n;
int ans,tmp;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&tmp);
        tmp = (tmp + 1) % 2;
        ans ^= tmp;
        if(ans)
            puts("1");
        else
            puts("2");
    }
    return 0;
}

C

题目大意

有n个应用Q个操作,每个操作格式如下
1、1 x 应用x发来了一条消息
2、2 x 阅读应用x的所有消息
3、3 t 阅读前t条消息

……
蛮水的题,模拟就好
但是要注意这个和手机的不同点是 阅读完了之后消息不会消失
本来是想着每一个点开一个队列……
╮(╯▽╰)╭
复杂度算错了
嘛嘛
就这样了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 300000 + 5;
vector <int> app;
int num[MAXN];
int old[MAXN],older;
int n,Q;
int q,x;
int killed = -1;
int main()
{
    scanf("%d %d",&n,&Q);
    while(Q --)
    {
        scanf("%d %d",&q,&x);
        switch(q)
        {
            case 1:
                app.push_back(x);
                num[x]++;
                break;
            case 2:
                old[x] += num[x];
                older += num[x];
                num[x] = 0;
                break;
            case 3:
                for(int i = killed + 1;i < x;i ++)
                {
                    if(old[app[i]])
                    {
                        old[app[i]] --;
                        older--;
                        killed ++;
                    }
                    else
                    {
                        num[app[i]]--;
                        killed ++;
                    }
                }
                break;
        }
        printf("%d\n",app.size() - killed - older - 1);
    }
    return 0;
}

D

题目大意

//蚁人可以变大变小且不花费时间
现在有n张编好号的椅子,蚁人在椅子上跳来跳去,他想从s跳到e上并且在这个过程中每个椅子都需要到达并且只到达一次
他只能在椅子上变大/变小(就是不能飞到一半突然变化)
蚁人有个习惯,如果他想往左跳(就是往小的编号跳的话),他必须变小,反之必须变大
将每一次跳跃分成三步
1、跳起来
2、平动
3、落下
在大的时候到某个椅子上降落的时间是 ai
在小的时候到某个椅子上降落的时间是 bi
在大的时候从某个椅子上跳起的时间是 ci
在大的时候从某个椅子上跳起的时间是 di
平动的时间是 xixj

先输入n,s,e
第二行是a
第三行是b
第四行是c
第五行是d


完全没有头绪的题……
我试着翻译题解吧

将它简化为TSP是容易的,我们需要找到从s到e的最短哈密顿路
考虑到要优化答案,因此这个图是一个有向图
考虑由前i把椅子构成的生成图(生成子图?导图?图论的属于真不懂……),在这个子图中,有一些部分,每一个部分都形成了一条有向路径,在这些图中,有这样三条情况
1、未来(i右边的椅子)的点,可以进入这个集合,也可以从这个集合出去到未来的节点上
2、未来(i右边的椅子)的点,只能进这个集合,但是从这个集合出不去(包含了终点e)
3、未来(i右边的椅子)的点,只能从这个集合出去不能从这个集合进来

……
什么玩意……
就这个意思……
然后
dp[i][j][k][l] = 前i个点,有j个1类路径,有k个2类路径,有l个三类路径时候遍历前i个点用的最短时间
要注意这里会包含比仅仅获得答案更多的信息,举例来说,当我们添加一个新的节点i进入dp时,我们计算d[i]或者-x[i],而不是j(如题目描述,当i

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
Codeforces Round #500 (Div. 2) BC

CodeForces 1013B And CodeForces 1013C Photo of The Sky B 可以发现只有一次与操作是有意义的,所以答案只有-1,0,1,2四种情况 2 #define show(a) cout << #a << " = " << a << endl; 3 ......

cjc7373
2018/07/30
0
0
Codeforces Round #510 (Div. 2) A - Benches

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82757408 Codeforces Round #510 (Div. 2) A - Ben...

bryce1010
2018/09/18
0
0
【水题】Codeforces Round #510 (Div. 2) B. Vitamins

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82757470 Codeforces Round #510 (Div. 2) B. Vita...

bryce1010
2018/09/18
0
0
Codeforces积分系统介绍

一、艾洛积分系统(Elo Ranking System) 请参考 https://blog.csdn.net/haishu_zheng/article/details/80480284 二、Codeforces积分系统 类似于艾洛积分系统,但是具体算法没公布。 详情请参考...

海天一树X
2018/05/28
0
0
Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/83062179 A:Make a triangle! (水) B:Equations of Mathematical Magic(异或+规律)...

张松超
2018/10/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vmstat命令详解

https://www.cnblogs.com/ggjucheng/archive/2012/01/05/2312625.html

流光韶逝
14分钟前
0
0
如何理解算法时间复杂度的表示

先从O(1) 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键 字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执...

yky20190625
30分钟前
2
0
分布式架构 实现分布式锁的常见方式

一、我们为什么需要分布式锁? 在单机时代,虽然不需要分布式锁,但也面临过类似的问题,只不过在单机的情况下,如果有多个线程要同时访问某个共享资源的时候,我们可以采用线程间加锁的机制...

太猪-YJ
今天
7
0
GitLab Docker 安装记录

安装环境 环境Centos7.4 64 1.拉取镜像文件 docker pull gitlab/gitlab-ce:latest 2.docker 安装 git.zddts.com 为访问域名或换成可以访问的IP docker run -d --hostname git.***.com -p ......

侠者圣
今天
0
0
EfficientNet: 再论 CNN 的网络规模

由于这里公式无法正常显示,所有内容以图片内容上传,如有需要,可提供 pdf 版。

爱吃草莓的皮卡丘
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部