24OJ #33. 【2017省选模拟】物品 贪心

考场上写了个nlogn^2的算法,感觉本机只能40。QAQ 3 * 10^4都过不去,然后忽然发现自己水到70分。貌似评测机比较快,然后数据有点水,然后貌似可能大数据对于cpu的缓存机制稍快一点。

考试的时候写的二分时间答案,然后nlogn暴力判断能否可行,一个物品自己涨够就认为其多余的时间在[……]

Read more

24OJ #27. 【2017省选模拟】方程

这题考场上感觉身体被掏空,没啥想法。。QAQ。。看了题解好像还是没啥想法,随便写点…..

我们考虑一下。

如果b == 1。我们考虑一下,如果a,c也都是1,那么显然有无穷组解,非常显然,可以任意一位的系数为1.其余的为0.

然后我们考虑一下,b > 1。我们考虑从a,b[……]

Read more

24OJ #28. 【2017省选模拟】取石子 DP

应OJ要求,题面已删除。

考试的时候并没有想到是dp,然后题答宛如一个智障在写模拟退火,然后调了半天参数放弃治疗了。然后就没啥时间了。GG

我们首先可以大概认为k是没有什么用处的。因为每个人最多一次只会取一个石头,因为每个人可能取到的位置是确定的,自己的嘛,当然拿的越少越好。

最小[……]

Read more

poj1941 The Sierpinski Fractal

递归把图存数组里输出就行了,多case。case间回车。用printf惨遭卡常。

poj2286 The Rotation Game 迭代加深搜索

迭代加深爆搜一下就好了,记得剪一下支,不同个数多于步数必定不会成功。输出记得如果不用移动也要输出最终形态是什么。

bzoj 1257: [CQOI2007]余数之和sum 等差数列 二分查找

我们考虑一下,最终要求的就是 n * k – sum(i * (k / i))。然后我么考虑一下,必然会有很长的一个区间他们k去除他们得到的值相同。那么我们就可以堆这个区间进行统一的处理,用等差数列公式求解。对于查询这个区间具体是什么,可以使用二分查找。
[crayon-5bcf4237a7e78[……]

Read more

bzoj 2005: [Noi2010]能量采集 容斥原理

我们先得出一个显然的结论,一个点被遮挡的掉的能量是(gcd(i,j)  – 1) * 2 + 1。

这个非常显然,自己理解。

我们考虑用g[i] 表示 gcd为i的对数。然而我们发现直接求不太容易,我们考虑容斥原理。用f[i] 表示 因数为i的对数。我们考虑g[i] = f[i] – s[……]

Read more

bzoj 1934: [Shoi2007]Vote 善意的投票 最小割 最大流 dinic

先说一下建图方式,然后说一下为什么这样子是对的。

对于每一个赞同的,我们从S连一条边到这个人,流量为1。对于每个不赞同的,我们从他连一条边到T,流量为1。对于每个PY关系我们都连一条双向边!注意是双向,然后流量都为1。然后对于这个图求一下最小割就是答案了。

我们来考虑一下为什么这么做是对[……]

Read more