bzoj乱刷计划2 5/50

前言

话说第一个乱刷计划很顺利地完成了
感觉写成一个题表的形式还是很支持的
于是我决定再开一个。。

打算

依然是可以做自己没做过的题,也可以复习做过的。同时尽量学一些自己不会的吧

乱刷计划2

3158: 千钧一发

很简单的网络流吧。。以前一直以为很难
其实不难发现,偶+偶,和奇+奇都是合法的
因此你可以建立一个二分图,最小割就可以了
要注意的是,平方的时候会爆int

1449: [JSOI2009]球队收益

其实和之前剪刀石头布那道题是差不多的
但是这题多了一个东西,就是输了也有奖
那么这里就用到一个小技巧,就是先假设他全部输掉
然后慢慢赢回来,代价就减去输的那个,这样就和之前那题一样了
然后一开始我吧一开始win的也当做输掉,然后必须要他赢回来,但是发现这样非常慢。。T掉了,改了之后才A。。

2560: 串珠子

先是看错了一发题目,以为要是一棵树。。
然后很高兴地打了一个矩阵树定理。。还觉得数据才16,特别水。。然后发现死活过不了样例,才发现是连通图QAQ
然后就考虑容斥
用总的减去不合法的
表示两个状态 f[i] , g[j]
第一个是里面的是一定合法的,g是不合法的
然后枚举子集转移
怎么知道他不合法呢?
固定一个点,让他在其中一个块里面,这个状态为 f[a] ,然后不在另外一个里面,就是 g[b] ,两个乘起来即可

3240: [Noi2013]矩阵游戏

这题的话, nm 给的是指数的形式,显然不是想让你一个矩乘就过了。。那么他应该给个 1018 就差不多了
于是我们要考虑优化
还是从矩阵出发
我们知道,行的矩阵大概是这样的:
a0b1
在若干次乘法之后,会变成这样
an0b(a+a2+a3+a4+.....+an)1
显然,后面的是一个等比数列
然后你会发现,最后都是乘方的形式
这让我们想起了费马小定理
虽然他是一个矩阵,但是我们从他的数的构成可看出,他也是可以用费马小定理来优化的
另外的矩阵也是同理,于是就成功吧时间复杂度降下来了
有一个小问题,就是当a=1的时候,他的形式是与膜数不互质了,那么费马小定理就不成立了,那怎么办呢?我们发现,如果这样的话,就退化成一个等差数列的形式了,于是其实他每隔 mod 个也是一样的,于是将 mod1 次幂调为 mod 即可

4865: [Ynoi2017]由乃运椰子

明显地,方案肯定是放入单调上升的序列
那么问题就是问你有多少个单调上升的序列。。
那就是区间众数啊。。
但是考虑到空间只给了10M
所以传统的可能不太行
考虑压空间
1.调节块的大小,开 shortint 2.考虑到每个数,至少会有一次,所以全部如果只出现一次的数,都删掉好了。。其实出现的第一次都删掉也可以,然后最后答案+1就可以了 考虑到代码恶心,所以不想打了。。精神AC QAQ

相关文章
相关标签/搜索