ctsc2017

时间:2023-03-09 06:48:44
ctsc2017

就看了几道题目。。

day1t1 良心题啊。。

经过一波转化就变成了求某一个数后面有几个比它大的 并且是有长度的(固定的)

然后这样暴力是nlogn的 再写个后面的部分分大概就有70了

其实100也很简单。。 发现每个数只会+1 -1,那么就开个数组维护一下每个数的个数就可以了

day1t2我可能只会写暴力

day2t1 不错的题啊

发现就是要求每个组合数都是奇数

然后n^2dp显然

然后打了一波表求x,y何时满足组合数为1

发现有点规律但是我看不出来啊。。

看了一发题解发现好简单啊。。。就是x&y==x

那就变成枚举子集了啊。。 然后就过了

day2t2 不错的题啊。。

满分可能跟我不是很相关就没有看

5档部分分

可能我下面说的下降都是不升。。。

pits 1 :树状数组优化最长下降子序列(竟然不是完全的暴力)

pits 2:能发现就是求两个下降子序列并

然后这个东西是可以dp的

f[i][j]表示两个串最后的位置分别在i,j

转移的时候,假设j是后面那个,我们就枚举j的前一个状态

为什么是这么做?因为要避免重复,如果枚举i的前一个,那我们就不知道i是否在j的子序列中出现过

而枚举i的话,由于i在j后面,所以一定没有出现过

pits3:状压dp

用状压表示出当前为i的最长上升子序列的个数

这一位是1代表比前一个多1,是0代表和前一个一样

pit4:如果想到网络流这个就非常简单了

高的向低的连边,自己拆点限流,费用-1,跑最小费用最大流就行了