【CF】2022一二月CF之旅

太咕了，太咕了，人快没了.jpg

CodeForces - 1459D Glass Half Spilled(dp)

虽然考试上是第一道题，但应该第一时间想到DP(n100),然后列状态，前两维度很容易想到是前i个中选j个，经过思考后，我们要求在选定k个杯子，此时装水为L,然后选取的最大容积为多少的状态。之后列DP转移即可。（惭愧）

CF1257D

2e5数据范围很容易想到贪心，惭愧考场上没有做出来，然后用数组k[i]表示可以连着干掉i个时候的最大士兵武力，然后顺着模拟这个过程一路干人就可以了。

CF1260D

参考题解 

由于答案显然具有单调性，我们考虑二分，由于精妙绝伦的想法，一个点最多走三次(一个人走过去一次，回来一次，再带兵走一次)，于是我们模拟这个过程就可以了。

Co1635D - Infinite Set 巧妙的DP

我们可以发现对于变换第一种等于二进制后面加一位1，第二种等于二进制后面加两位0，故我们利用dp[i],表示数字表示为i位的有多少个数字，如果起始只有1，那么dp[i]=dp[i-1]+dp[i-2]。而有些初始数由于可以由其它表示，我们利用排序后用set除去可能表示的无用数后，设置g[i]表示初始表示i位的数字个数。然后dp[i]=dp[i-1]+dp[i-2]+g[i]，答案就等于dp[i]加和。

1635E - Cars 构造关系图

画画图后发现，无论是irrelevant还是distine他们的图都是方向相反的。于是乎我们先对关系连接无向边，二分图构造出它们每个的方向，如果无法构造则puts("NO")，然后再已经匹配好方向之后，利用关系，坐标位于左边的向右边的连边，构造有向图之后topsort，如果有环无解，否则坐标出。

1630A - And Matching

关于该题，比较容易想到构造。于是乎对于k=0，我们用0<->n-1,1<->n-2......一一对应即可。对于0c(k)(k的反二进制位即n-1-k),k<->n-1同样构造。而对于k=n-1,构造n-1<->n-2,n-3<->1,0<->2，于是n=4不行，除此外都可。

1644D - Cross Coloring

容易想到这道题最后的答案就是k^合法未被完全覆盖的涂色次数。于是乎，倒着考虑，如果一次涂色它的行列都被涂过或者所有行or所有列都被后续覆盖则不合法。

1644E - Expand the Path

虽然理解了，但不是完全理解(o.o)属于下次还错的，后续可能回看该题，大致就是找到一个上边界和下边界，其以外的部分就是不能走到的。具体做法参考jiangly大佬的代码。