题目大意：给你一个N (0 < N < 10^5)，把N分解成若干个不相同且值不超过10^5的整数的各个位数的和，例如：N＝17时有，17 ＝ 7 ＋ 1 ＋ 2 ＋ 4 ＋ 3，所以17可以分解成7， 12， 43，这三个不同的整数。
题目其实是比较简单的，解法也有很多种，我就说一个我认为比较有趣的解法。我们可以每次把N加到所求的整数集合里面，然后再把N减去自身各位数字的和得到新的N’，直到N等于零。正确性也很容易验证，注意到我们每次往集合里添加的数必然都是递减的，这就保证了无重复数字的出现，然后按照生成的规则可知，减到N为0的时候自然集合里的所有数的各位数字之和就为最初的N了。
Continue reading
博客好久没有更新了，自从打完补选赛之后就一直一副颓废状态，外加要期末考，得预习课内知识(虽然我到最后还是。。。)，不管怎么样，现在以及放假了，所以我打算兑现之前对自己的承诺，暑假好好做题，所以这段时间应该会比较经常更新一些水题的题解啦( ´ ▽ ` )ﾉ。昨天选拔赛第一场就爆零滚粗，作为一名候补选手，我只剩下今天这个最后一次机会了，好伤感的说T^T，希望写一写题解涨张RP。。。
Continue reading
题目大意：给一个无向图，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的骨牌覆盖，现在给你第一层的覆盖方案，要你求出符合以下要求的任意一个完全覆盖第二层的方案：
计算几何题的特点与做题要领：
1.大部分不会很难，少部分题目思路很巧妙
2.做计算几何题目，模板很重要，模板必须高度可靠。
3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。
4.注意精度控制。
5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快。
Continue reading
Write the code. Change the world
Student