题目大意：给一个无向图，N个顶点(n<=100,好小的样子。。)，要求把这N个顶点分成两组，使得对任一个组中的每个顶点，都至少存在一条边连接到另一组中的某个顶点，要求给出任一满足条件的分组，输出其中一个组的顶点编号。
话说一开始看完题目我想到的是二分图，应该是可以做的，不过本题似乎不必那么麻烦。因为题目给的条件相当宽松，我们可以对每个顶点进行染色，从某个为染色的顶点出发，把跟它相邻同时还没有染色的顶点染色跟它相反的颜色，然后就这样一直搜下去好了，要注意的就是整个图可能存在多个联通块，然后应该就没有然后了吧。。。
Continue reading
因为题目的编号是2^10，所以决定写一下题解。
题目大意：给出一个n阶的置换P，问P的多少次幂等于单位元E。n <= 1000，保证答案不超过1e9.
如果有一点置换群的知识的话就很好解决了，其实题目也就清楚的告诉你是怎么置换了。我们知道在置换群中有这样一个定理
关于循环的概念，相信应该不难理解，简单点说就是根据题目，_P_k(x) ＝ x，__则在置换过程中得到的k个数便构成一个k阶的循环。题目要求的答案便是k1, k2…..kn的最小公倍数。显然，对于1～n，每个数字仅会出现在一个循环当中，同一个循环中的数对于的k便是一样的。这样复杂度就可以做到O(nlogn)，由于n只有1000，我就懒得去标记什么的了，直接用O(n^2 logn)的做法。
Continue reading
题目大意：给出一个4×4的用黑白两色棋子覆盖的棋盘状态，以及选择任意某一棋子以其为中心进行翻转的一个3×3的01翻转规则，1为翻转，0则不翻转，问能否经过若干次操作，是的整个棋盘变成同一种颜色。
其实题目比较简单，类似的题也做过几道了。显然每个棋子以其为中心最多翻转一次。这样总共16个棋子也就是有2ˆ16种状态，然后就直接枚举每一种情况。然后我居然因为一个数组开小了，一直WA。最近真的脑子有点乱乱的=_=，刚才终于让我De完bug了，所以写写题解放松一下。
Continue reading
虽然很多是水题，不过还是记录一下。。。。然后还有好多得做的题目都还没补TAT
Continue reading
题目大意：给一个M给节点，N条边的无向图。问是否存在长度 >= S的一条路径。每条边一旦被选择，就只能从固定的一个方向通过。1 ≤ M ≤ 100; 1 ≤ N ≤ 10000; 1 ≤ S ≤ 10^6.
显然，如果存在回路必然可以，且注意可能存在重边。那么我们就可以对每个节点做一遍dfs。在dfs的过程中判断是否存在回到该点的回路，如果不存在就能得到由该点出发的最长路了，注意更新答案就行了。
Continue reading
题目大意：给一个N＊M(N, M均为偶数，且不超过100)的棋盘，该棋盘有两层，使用1*2的骨牌覆盖，现在给你第一层的覆盖方案，要你求出符合以下要求的任意一个完全覆盖第二层的方案：
可以理解为2663的加强版，多了些状态，代码基本参考了别人的，各种位运算。。。。因为N比较大，所以，矩阵乘法的优势就体现出来了，不过这个代码感觉速度还不是很快啊
Continue reading
题目链接：戳我（1053－1059）
题目还比较好理解，每次选两个数，大数减去小数，相等则合并，其实就是求出所有数的最大公约数，然后就是直接做了。
Continue reading
给定一个序列，要求出一段连续的子序列，是的其和最大或最小。
这是一个很经典的问题，最近做了相关的题目，在这里总结一下。
Continue reading
简要题意：给定n，m，n (1 ≤ n < 10ˆ18) and m (1 ≤ m ≤ 100).求满足以下要求的数x有多少个。
一开始我被10ˆ18给吓到了，但是其实这里也是一个突破口来着，仔细想想，如果是2ˆ18的话那该多好。
如果你往这个方向开始去想了，就会发现很多东西了，然后就是个DP，然后再去一下重，当然，你也可以在DP的过程中去重。
不过，感觉我的DP水平实在是不济，这个是赛后搞出来的。。。
Continue reading
Write the code. Change the world
Student