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

原创
2016/10/30 09:58
阅读数 18

简直中了不能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

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部