这道题是 Codeforces Round #107 (Div. 2) 中的 D 题。其题意是，给出 n, m, k 三个整数，问在字母表有 m 个元素的、长度为 n 的字符串中，存在多少个这样的字符串，其所有长度为 k 的子串是回文串。

一开始我理解错题意了，我当时以为是只要那个串含有回文子串，那么就把它算进去。其实我感觉还是挺傻的，因为长度为 1 的串也是回文串啊，那这样岂不是所有的都要算进去了？

阅读全文

这个比赛是在今天凌晨 1:05 开始的，感觉以后做这种还是需要先休息一下。

250 分的题，题意是，皮卡丘只会说三个音节：“pi”、“ka”、“chu”；给出一个只有小写字母的字符串，判断皮卡丘能不能说出这样的话。比如，“pikachu”、“pikapika”之类的要输出“YES”，反之输出“NO”。

我的办法比较笨，都是逐个字母来判断的。但是我感觉这种方法比较快，是 O(n) 的算法。在 Challenge 的时候看到一种方法，每次判断开头几个字母是不是“pi”、“ka”、“chu”，如果不是就直接返回“NO”了，如果是的话，就删除前面几个字母。但是这种方法似乎没法通过系统测试，不过在 Challenge 阶段这样的题解也没人敢动，所以这样错的原因可能是效率比较低。

阅读全文

几个月不参加 Codeforces 的比赛了，没有紧张的气氛，做得有点没感觉。前两题水过，第三题想复杂了，第四题当时没有想法，最后一题没心情看。比赛 URL: http://codeforces.com/contest/151 .

A 题 151A Soft Drinking 的背景是几个好朋友在一起喝饮料。其问题的实质是这样的：要制造一种物品，需要不同数量的不同原料；给出各种原料的数量和每件物品需要每种原料各多少，然后求最多能制造多少个这种物品。

阅读全文

这道题的题意是给出一个 N × N 的正方体，这个正方体是由 1 × 1 的小正方体垒成的。然后，输入数据会给出若干个命令，这些命令都表示一条平行于某坐标轴的直线，命令的效果是让这个直线上的所有方块消失掉。最后，问消失了多少小方块。

似乎这道题原题标题犯了个小小的语法错误……

阅读全文

这是在 Greenmoon55′s Blog 挖掘出来的水题一则。果断凑数。

思路是把每行的学生的列坐标分别排序，枚举左边一列的列号即可。

阅读全文

这道题的题意是，问一个由单位正方体垒成的 A × B × C 的长方体的体对角线穿过了这个长方体中的几个单位正方体。如果对角线与正方体擦肩而过的话不算穿过。

怎么说呢，这道题纠结了几天，网上没有题解，只有模糊地提到容斥原理。在昨晚出去逛街的时候想到了二维的情况，如果长方形的大小是 A × B 的话，如果 A 和 B 互质，那么可以看出来，对角线穿过了 A + B – 1 个小正方形。如果 A 和 B 不互质，就求最大公约数 G, 令 A’ = A / G, B’ = B / G, 这么说在对角线上有 G 个 A’ × B’ 的长方形，对角线穿过了 (A’ + B’ – 1) × G 个小正方形。

阅读全文

这道题算是一道模板题吧，思路是矩阵变换。一个问题是，怎样快速求矩阵的 n 次幂，这个可以通过分治搞定，在这题里我没有用递归的方式，而是用位运算。在遇到 repeat 命令的时候，可以用递归的方式，简化程序编写；需要注意 repeat 后面的数字只是非负的，有可能是 0. 还有记得输出的时候要判断会不会是 -0.00 这样的东西。

至于三种变换的矩阵，这里就不细说了，移动和缩放其实还是比较简单，旋转比较复杂，维基百科里有介绍。

这次在上面栽了两次，原因是 repeat 时我判断如果是 0 就直接返回了单位矩阵，而没有读到下一个 end 命令。后来为了改得方便，也没有在一开始特判 0, 所以遇到 0 的时候还是会“白算”比较多东西。不过有句话说，要避免不成熟的优化，呵呵……

阅读全文

这是一道模拟的题目。

我的思路是，用两个优先队列，一个是正在下载的文件的队列，另一个是等待下载的文件的队列。对于正在下载的文件队列，维护“所剩字节数最少的那个文件”在堆顶；对于等待下载的文件的队列，维护题目中所描述的那种最优先被下载的文件在堆顶。

然后循环，看正在下载的文件队列是否满，未满则将等待被下载的文件队列中的文件一个个弹出又插入到正在下载的队列。再看那个所剩字节最少的文件，让每个文件都减掉那么多字节，然后把那些字节为 0（即下载完了的）文件删掉，再把所需时间加到计数器。最后循环啊循环就好了。

阅读全文

图论题，思路就是，首先把每条边的两端的顶点数统计出来，并且取较小的那一个数，这个数的含义是，最多会有多少对 family 路过这条路。然后用这些数乘以它相应的权值，再乘以 2 就可以了。

由于极端情况下，节点数会达到 10⁵, 路径长度会达到 10⁶, 这已经明显超过 32 位整型了。所以需要用 long long. 需要注意的地方就是，如果两个 int 相乘，其结果可能会达到 long long 的话，那么先把两个 int 分别转换成 long long 再乘。至于为什么就不多解释了。

阅读全文

在做这题之前还不知道什么是 2-SAT 的。折腾了大半天的，终于写完了。这道题我是 2 次 AC, 问题出在判断剪刀石头布谁能赢的函数写错了……

有关 2-SAT 的资料网上挺多的，解决的方法可以是强连通分量，这道题重点在构图。网上有说每局状态用 6 个顶点代表的方法，也提到“官方”题解是用 2 个顶点的。

我使用的是每局用两个顶点代表状态的方法，其实也没有多复杂，用了一些 swap 小技巧，就只分了 4 类讨论。

还有一个就是判断两个顶点是否属于同一个强连通分量的时候，我居然用了并查集，这是杀鸡用牛刀了。

阅读全文