over 2 years ago

前言

依然是省选题...

数学作业

设第个数有位,那么转移方程为,直接分段矩乘即可.
bzoj2326.cpp

勾股定理

首先我们知道勾股数的通式是.
如果当且仅当奇偶性不同,很容易看出互质的勾股数是的.
我们给所有的互质勾股数之间连边,然后对于环上的点枚举选还是不选,然后树形DP就好,但问题是这个复杂度反正我是算不出的...
bzoj2327.cpp

赛车游戏

我是用Mato No.1大爷的做法的...题解戳这里...
bzoj2328.cpp

括号修复

我们的问题其实就是给定一个括号序列如何用最少步数变成合法的,我们令( = 1 , ) = -1,记为前缀最小值,为总和,由于每改变一个括号会导致的变化,那么步数就是把变成正的,然后把变成的最小步数,也就是,即.
剩下的问题就是平衡树维护各种东西了,注意一下赋值标记会盖掉取反标记就好了。。。
bzoj2329.cpp

任务调度

据说是NPC问题,所以我们只能各种乱搞了。。。
可以观察出第一类的一定会先放在A,第二类的一定会先放在B,然后枚举第三类属于第一还是二类,模拟退火整个顺序即可,或者交换个1000次左右即可。
bzoj2336.cpp

XOR和路径

这种题一个很显然的思路就是利用高斯消元解出每一位为1的概率就好了,然而注意要倒着推。。。
bzoj2337.cpp

数矩形

据说有很多奇怪的做法,我的做法是先把所有的线段提出来,对于所有斜率和长度相同的线段,如果两条线段能构成矩形,那么它们必然在同一条与当前线段垂直的直线上,求出所有在同一直线上的线段,我们只要取这条直线上的两个端点计算答案即可,时间复杂度,然而我三关键字排序的常数极大。。。
bzoj2338.cpp

卡农

(我貌似之前做过一道这种题的加强版。。。)
表示前段的答案(注意这个是排列的个数),很显然如果我们确定了前段的状态,为了每个数出现次数为偶数,第个的状态就已经确定了,因此总数是,考虑有两种不合法的情况:
第一种是段是满足要求的,那么第段只能取空集,矛盾,因此减掉
第二种是第段取的集合与之前的重复了,那等价于在加上两个相同的集合,有种可能,考虑把一个集合插回去,有个位置,因此减掉
所以我们就搞定了。。。
bzoj2339.cpp

终于写完了。。。

← HNOI2010 About Recent Condition →
 
comments powered by Disqus