从蓉的博客

原题链接 题目设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。 分析首先可以知道，如果使用两次dp去求解的答案肯定是有问题的。走一次的情况来说，dp只有两个状态，即横坐标和纵坐标。下面，应该来思考两次走的时候会有什么性质： 两条路径可能会有重合点，也可能没有。有重合点的块的值只能算一次。 两条路径的总长度是一样的。 当然，这个性质是显而易见的，但问题的关键就在于如何处理重合点。 对于两次dp来说，不能很好解决问题的原因在于每次只能考虑一个人的最优情况，会出现一个人最优，却让另一个人得到的值小于预期值的情况。 考虑完基本性质和解决难点后，那么可以想到我们要实现的dp是综合考虑两条路径以及重合点的dp。关于重合点，可以发现如果两条路径有重合点，那么从起点到重合点的路径应该是相同的。如果每秒走一步，那么应该同时经过这个重 ...

基本情况：一题没A，比较遗憾的是最后一题知道是怎么做，但是只剩下二十分钟打代码，调试过程中发现有些细节没有考虑好就匆匆忙忙交了上去，不知道会不会有问题。 本次涉及到的知识点有Nim游戏，动态规划，图算法，数学知识，还有几题我没有想到用什么方法做。直观来看这些都是我之前算法学到的内容，但由于并没有巩固基础，导致一道题都没有A出来…具体来说，虽然我学了动态规划的求期望，但在考场上完全忘了怎么打，并且那题还是加上了数学知识的取模定理，看完题目脑子就一片空白。我觉得这也是在短期学了这么多内容一下次来了输出机会的一些缺陷吧，由于没有时间去巩固学过的内容，说着说去刷对应题目培养算法思维，真的很难在考场上凭空想出一个百分的解法。 打算还是继续把算法基础巩固一遍，把所有的笔记都整理出来，整理出来继续去学习算法提高的内容，以后要规定在时间内不能看解析，一定要自己想一个思路，把代码打出来。但短时间学算法和刷大量题实在是比较矛盾的事情呜呜。 比较遗憾的是虽然在考前一直提醒要以拿最多分为追求，但真正打代码之后总觉得一道题只写出来暴力算法，或者说甚至连暴力都不会写实在是过于丢脸的事，然后就一直盯着一道题也没想出 ...

原题链接给定一个长度为$N$的数列，$A_1,A_2,…A_N$，如果其中一段连续的子序列 $A_i,A_{i+1},…A_j$之和是$K$的倍数，我们就称这个区间$[i,j]$是$K$倍区间。 你能求出数列中总共有多少个$K$倍区间吗？ 分析暴力做法套两个循环，每个循环使用sum去求和然后取余，时间复杂度为$O(n^3)$ 前缀和使用前缀和可以优化到重复的求和部分，但是这样也需要两层循环遍历，时间复杂度为$O(n^2)$ 优化前缀和在基本前缀和的两层循环中，判断某一范围之和是否余数为0实际上是使用$a[i]-a[j] \ mod\ K \equiv 0$来判断的，再进一步思考实际上就是$a[i]$和$a[j]$同余才可以。这样完全可以再开辟一个数组，用来存放$a[i]\ mod\ K$的值，这样只需要遍历这个数组一遍即可，时间复杂度为$O(n)$。 代码实现123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N ...

原题链接 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;int num, res = inf;void p(int x) { for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { printf("%d", (x >> (4 * i + j)) & 1); } printf("\n"); } printf("\n");}int main() { #ifndef ONLINE_JUDGE freopen("in.txt", &quo ...

除了第一行之外，每一行的操作都由上面一行决定。根据题目所给的限制可以知道，每一个开关只需要操作一次。如果每次从第一行开始操作，第一行的操作种类有$2^5$，那么下一行必须操作，也是只能操作的就是上一行对应列为暗的块。代码实现： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>using namespace std;const int N = 6;int m[N][N], backup[N][N];int dx[4]= {1, 0, -1, 0};int dy[4] = {0, -1, 0, 1};void p() { for(int i = 1; i <= 5; ++i){ for(int j = 1; j <= 5; ...

原题链接 分析一堆可以变成两堆，对于每堆的一种子情况来说都有：$$sg(a,b)\rightarrow sg(a)\ xor\ sg(b)$$只需要遍历a,b的所有情况就可以了。 代码实现12345678910111213141516171819202122232425262728293031323334#include <bits/stdc++.h>using namespace std;const int N = 101;int n;int f[N];int sg(int x) { if(f[x] != -1) return f[x]; unordered_set<int> S; for(int k = x - 1; k >= 0; --k) { for(int j = x - 1; j >= 0; --j) { S.insert(sg(k) ^ sg(j)); } } for(int i = 0; ; ++i) ...

原题链接 为了能够找出该Nim游戏的必胜方法，应该从最基本的样例中找到规律： 如果石子都在第一层，那我全部拿下去就获胜了。 如果石子全部在偶数层，对手拿下来多少个石子，我就把这石子都移到下面一层，这样保证我最后把所有石子都放在了最底下。这说明了偶数层并不会对胜负有影响。 终结情况是全0 伴随着每一次移动，会有相邻两个台阶的石子数发生变化。一个变大，一个变小。 私以为Nim游戏最难理解的地方就在于为什么要使用异或，但是异或是最简练也是最为准确地能够描述每次状态变化地结果量。我们可以猜测，是奇数台阶异或为0时是必胜情况。那么怎么进行证明呢？可以这么去理解。当奇数台阶结果异或为0时，下一次操作时候异或结果肯定不为0，下下次的结果肯定又能回到0。由于石子的数目肯定是逐渐变少的，因此这个结果肯定会归到0，必胜结果一定为0。 结论计算奇数台阶石子的异或，异或为0说明必胜。 代码实现123456789101112131415#include <bits/stdc++.h>using namespace std;int main() { int n; int re ...

数论质数质数判定方法：试除法 分解质因数：试除法 试除法本来需要将i从2循环到x，但由于大于sqrt(x)的x的质因子最多只有一个，因此只需要将i从2循环到x/i即可。同时，若x在经过除法后仍然大于2，说明其本身就是一个质因子。这样可以由原来的$O(n)$复杂度降为$O(\sqrt n)$。 注意：优化后算法的最佳时间复杂度为$O(\log n)$ 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;int main() { int n; scanf("%d", &n); while(n--) { int x; scanf("%d", &x); for(int i = 2; i <= x / i; ++i) { int s = 0; while(x % i == ...

原题链接 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>using namespace std;const int N = 102;int M[N][N];int n;int res[N];int gauss() { int c = 0; for(int i = 1; i <= n; ++i) { bool change = false; for(int j = i; j <= n; ++j) { if(M[j][i] == 1) { for(int k = 1; k <= n + 1; ++k) swap(M[j][k], M[i][k]); ...

农民约翰的N头奶牛（编号为$1..N$）计划逃跑并加入马戏团，为此它们决定练习表演杂技。 奶牛们不是非常有创意，只提出了一个杂技表演： 叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。 奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。 这$N$头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度$S_i$。 一头牛只撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。 您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。 输入格式第一行输入整数$N$，表示奶牛数量。 接下来$N$行，每行输入两个整数，表示牛的重量和强壮程度，第$i$行表示第$i$头牛的重量Wi以及它的强壮程度$S_i$。 输出格式输出一个整数，表示最大风险值的最小可能值。 数据范围$1≤N≤50000$,$1≤Wi≤10,000$,$1≤Si≤1,000,000,000$ 输入样例： 1234310 32 53 3 输出样例： 12 重点是推公式，下面给出分析方法： 对于第$i$头牛，它的 ...