对于构成最小环的点集{x1, x2, …}，其中必定存在一个最大点xk，那么最小环的长度可以由dis[i][j]+m[j][xk]+m[xk][i]来表示，其中i，j均在点集中且小于xk，dis[i][j]是i到j的最短路径。因为xk是点集中最大的那个点，所以i到j的最短路径没有经过编号比xk更大的点。那么要求最小环的长度就可以由小到大枚举一下xk就行了。我们知道，floyd算法最外层每循环一次，就是由一个中间节点k更新点i到j的最短路径。k从小到大枚举，就保证了循环到k的时候，当前i到j的最短路经过的最大节点只可能是k，这刚好满足上面提到的dis[i][j]的定义。所以我们就可以愉快的使用floyd来求最小环了。
题目大意：给你一个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
题目大意：给出一个4×4的用黑白两色棋子覆盖的棋盘状态，以及选择任意某一棋子以其为中心进行翻转的一个3×3的01翻转规则，1为翻转，0则不翻转，问能否经过若干次操作，是的整个棋盘变成同一种颜色。
其实题目比较简单，类似的题也做过几道了。显然每个棋子以其为中心最多翻转一次。这样总共16个棋子也就是有2ˆ16种状态，然后就直接枚举每一种情况。然后我居然因为一个数组开小了，一直WA。最近真的脑子有点乱乱的=_=，刚才终于让我De完bug了，所以写写题解放松一下。
Continue reading
虽然很多是水题，不过还是记录一下。。。。然后还有好多得做的题目都还没补TAT
Continue reading
题目大意：给一个N＊M(N, M均为偶数，且不超过100)的棋盘，该棋盘有两层，使用1*2的骨牌覆盖，现在给你第一层的覆盖方案，要你求出符合以下要求的任意一个完全覆盖第二层的方案：
题目链接：戳我（1053－1059）
题目还比较好理解，每次选两个数，大数减去小数，相等则合并，其实就是求出所有数的最大公约数，然后就是直接做了。
Continue reading
Write the code. Change the world
Student