codeforces 401div2 b Game of Credit Cards

就是一道类似田忌赛马的题。如何能让自己输的局最少,如何能让对方输的局最多。其实排个序扫一下就好了。然而为了偷懒用set直接查前驱和后继,然后因为重复元素GG掉了。换了multiset就好了。如果想让自己输的最少,就对于队手的每个元素用自己的lower_bound对战。如果想让队手输的最多,就用自己的[……]

Read more

codeforces 401div2 a Shell Game 找周期

枚举一下开始位置。然后我们模拟一下最终位置,看是否与输入相同。我们通过观察发现。无论开始位置在哪,周期都为6。我们只需要%6之后暴力模拟一下就可以了。

注意写题的时候明确一下,周期是棋子回到原先位置,且下部交换的地方也回到原先位置。要保证每个周期内的操作和结果完全相同。

不要吝啬局部变量[……]

Read more

1588: [HNOI2002]营业额统计 set

我们只要有办法快速查找之前第一个>=的数,和第一个<=的数就行了。那么我们可以建立两个set,一个正常,一个为负值。这样子就可查询<=的情况了。

bzoj 1007: [HNOI2008]水平可见直线 维护下凸

我们可以考虑一下,最后我们能看到的部分一定是一个类似与二次函数的样子,由很多个线段和两条射线组成一个类似二次函数的模样的东西。所以我们可以考虑,先按照斜率排序,然后从小到大,每次我们如果发现当前这个元素和栈顶元素前一个的交点在栈顶元素和栈顶前一个元素的交点的左侧。那么我们可以得出栈顶元素必将无法被看[……]

Read more

bzoj1015 星球大战starwar JSOI2008

离线后倒序并查集即可,注意一下,被占领的星球不再计入联通块。当时没想到这点,怎么看样例都不对……

bzoj1051 HAOI2006 受欢迎的牛 tarjan缩点

tarjan随便缩一下点就可以了。然后出度为0的强连通分量一定为唯一的受所有其他分量都欢迎的分量。输出这个分量的大小即可。模板题。

bzoj 1002 FJOI2007 轮状病毒 高精度递推

看了题解之后我的内心是崩溃,一个奇妙的什么矩阵。然后我得出一个结论,恩这是一个打表找规律题…..f[i] = 3 * f[i – 1] – f[i – 2] + 2; 然后拿高精度递推一下就好了。

bzoj1031 jsoi2007 字符加密Cipher 后缀数组

这题只要把原串复制一遍放到结尾然后跑后缀数组,用得到的sa[i]算一下就可以。然而这题数据有毒。莫名re,数组开数据范围10倍就A了。debug了一晚上……

AC代码:

bzoj1003 ZJOI2006 物流运输 dp + spfa

这题数据范围很小,我们可以任意瞎搞。首先我们先考虑有这么一个数组cnt[i][j],表示[i,j]这些天保持同一计划每天运输的最小代价。(如果不存在显然这是无穷大)那么我们可以搞出这么一个转移方程f[i] = min(f[j – 1]+ cnt[j][i] * (i -j + 1) + k)。我们相[……]

Read more