杂题乱做 PART 4

ps:主要是把之前做的有点意思的题总结一下

• luogu P5892 [IOI2014]holiday 假期
  思维难度: (5)
  代码难度: (5)

sol:
不难看出来经过的一定是先向右再向左，或者反过来，只用考虑前一种，后一种把序列反过来再做一遍即可
对于一个确定的区间 [ l , r ] [l,r] [l,r]相当于是移动完后选区间的前 k k k大
考虑左端点单调递增，右端点也一定是单调递增的，显然具有决策单调性
分治优化即可

code

• CF1225F Tree Factory
  思维难度: (5.5)
  代码难度: (4) 还是有一点点细节

sol:
考虑将 *** 作反过来做即可

code

• CF901C Bipartite Segments
  思维难度: (5.5) 有点意思，不过vp的时候看完大概就会了，还是偏套路
  代码难度: (5.5)

sol:
因为没有偶环，所以只要有环就一定是奇环，并且画一下发现一定是个仙人掌，不会存在环套环的情况，不然必定出现偶环
于是对于每个环，求出最靠左的和最靠右的 [ l , r ] [l,r] [l,r]，表示选的区间不能包含这个区间，这样就是一个简单的线段树能解决的问题了

code

• CF757F Team Rocket Rises Again
  思维难度: (5.5)
  代码难度: (5.5)

sol:

首先把最短路 D A G DAG DAG建出来，发现就是要求个支配树，直接上 D A G DAG DAG上求支配树即可
code

• AT3981 [ARC093D] Dark Horse
  思维难度: (8.5) 还是挺难想到的吧，可能是我没见过类似的
  代码难度: (4)

sol:
首先可以发现不管自己在哪个叶子结点，其实都是一样的，所以可以钦定在第一个叶子结点，最后乘上 2 n 2^n 2n即可。

我们来画 一下图

发现自己必须要赢过这些点，对应的区间长度是 2 k 2^k 2k,直接做不好做，考虑容斥

设 f ( S ) f(S) f(S)表示长度集合在 S S S以内的区间里最小值都在 A A A里面，即如果第 i i i位是 1 1 1,表示上面那个图，长度为 2 i 2^i 2i的区间胜者在 A A A之中
答案就是 ∑ S ( − 1 ) ∣ S ∣ f ( S ) \sum_{S}(-1)^{|S|}f(S) ∑S​(−1)∣S∣f(S)

可以考虑从大到小填数，先把 A A A排序，从后往前处理
设 d p [ i ] [ S ] dp[i][S] dp[i][S]表示考虑了后 i i i个，长度集合为 S S S的答案
手推一下不难得到转移方程
最后 f ( S ) = d p [ 1 ] [ S ] ∗ ( 2 n − S − 1 ) f(S)=dp[1][S]*(2^n-S-1) f(S)=dp[1][S]∗(2n−S−1)表示钦定完后剩下的随便放的方案数
code

• luogu P3584 [POI2015] LAS
  思维难度: (9) 挺有启发性的，学到许多
  代码难度: (4)

sol:
不要考虑人，考虑每个食物被选的状态
D P DP DP,设 n x t [ i ] [ 0 / 1 / 2 / 3 ] nxt[i][0/1/2/3] nxt[i][0/1/2/3]表示第 i i i个食物，不被选/被左边选/被右边选/被两边选之后，上一个食物的状态
转移较为简单，分8中情况讨论一下即可
然后根据 D P DP DP数组得到方案

int check(int o) {
    memset(f, -1, sizeof f); f[1][o] = 114514;
    for(int i = 2; i <= n + 1; i ++) {
        if(f[i - 1][2] != -1 && a[i - 1] >= a[i]) f[i][0] = 2;
        if(f[i - 1][3] != -1 && a[i - 1] / 2.0 >= a[i]) f[i][0] = 3;
        
        if(f[i - 1][0] != -1 && a[i - 1] <= a[i]) f[i][1] = 0;
        if(f[i - 1][1] != -1 && a[i - 1] / 2.0 <= a[i]) f[i][1] = 1;
        
        if(f[i - 1][2] != -1 && a[i - 1] >= a[i] / 2.0) f[i][2] = 2;
        if(f[i - 1][3] != -1 && a[i - 1] / 2.0 >= a[i] / 2.0) f[i][2] = 3;
        
        if(f[i - 1][0] != -1 && a[i - 1] <= a[i] / 2.0) f[i][3] = 0;
        if(f[i - 1][1] != -1 && a[i - 1] / 2.0 <= a[i] / 2.0) f[i][3] = 1;
    }
    return f[n + 1][o] != -1;
}

code

• CF1091H New Year and the Tricolore Recreation
  思维难度: (7)
  代码难度: (4)

sol:
没想到能用bitset干过去
不难发现，把前两个棋子向右移动相当于把第三个棋子向左移动
那么就可以转换为 b − a − 1 , c − b − 1 b-a-1,c-b-1 b−a−1,c−b−1的两堆石头的问题
考虑如何求 s g sg sg函数
直接暴力会寄，猜一手 s g sg sg函数的值不会很大，那么同样是记录一个转移数组 n x t [ j ] [ i ] nxt[j][i] nxt[j][i]表示对于 i i i,它的所有可以转移到的状态， s g sg sg值为 j j j的是否存在，这样就可以暴力求出 s g [ i ] sg[i] sg[i]了
那么用 b i t s e t bitset bitset优化后更新一次的复杂度是 200000 / w 200000/w 200000/w的，虽然但是就是过了
code

• luogu P1446 [HNOI2008]Cards
  思维难度: (7.5)
  代码难度: (4)

sol: