目 录CONTENT
朋友圈
-
Anyeの小站
2019-11-06
【百题千解】题解 P2871 【[USACO07DEC]手链Charm Bracelet】
声明 先粘一波代码，首先声明一下 这份代码是在 OI-wiki 的错误的示例代码 （错误有点多，我就不一一指出了） 上进行修改的，我知道有些人是从 OI-wiki 上跳转过来的，但是无奈于不会修改 OI-wiki ，所以在这里发一篇题解来帮助大家理解。 #include<bits/stdc++.h> using namespace std; const int maxn = 13010; int n,M, W[maxn], v[maxn], f[maxn]; int main() { cin>>n>>M; for (int i = 1; i <= n; i++) cin >> W[i] >> v[i]; for (int i = 1; i <= n; i++) for (int l = M; l >= W[i]; l--) if (f[l - W[i]] + v[i] > f[l]) f[l] = f[l - W[i]] + v[i]; std::cout << f[M]; return 0; } 简述题目 有 n 个物品和一个容量为 W 的背包，每个物品有重量 wi 和价值 vi 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。 思路 以下是错误思路（是部分背包问题的解法） 其实这道题我一开始想成贪心问题了，可能是因为小米的超高性价比手机感染了我 ~~（雷军：？？关我什么事~~~ 我先计算出了每个物品的重量价值比（性价比），然后优先向背包内存放性价比高的物品， 然而后来我才意识到，，因为会产生很多情况，比如： 设背包最多可容纳50kg的重量 物品 重量(kg) 价值 性价比 A 10 60 6 B 20 100 5 C 30 120 4 按照贪心，单位重量的价值排序：A... -
Anyeの小站
2019-11-01
【百题千解】题解 P2730 【魔板 Magic Squares】
思路分析 这道题是一道非常典型的 BFS 题目， BFS 所面临的最大问题是判断重复。显然，如果每次判断重复都扫描一次队列，搜索的效率会非常低，会提高一个指数级，所以一般宽度搜索的判断重复都是运用数组来实现的。那么数组下标就需要用一个 Hash 函数来计算。因此，设计 Hash 函数就显得非常重要。 本题 Hash 函数的设计：我们很容易想到将 8 个数字按顺时针顺序组合成 8 进制（每个数字都减 1 ）的 8 位基数。但是，这里最大的八进制数 76543210 ，转换成十进制数就是 16434824 ，也就是说要开大小为 16434824 的数组，如果题目强制空间限制，那么，数组下标会越界。 这里我们引入康托展开，即将一个排列对应成它在全排列中的序数，这样就不会 MLE 了。 如 { 1，2，3，4，···，n } 表示 1，2，3，4，···，n的一个排列，如 {1，2，3} 按从小到大排序，一共有6个： 1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1，分别代表数字 1，2，3，4，5，6，也就是把 10 进制数与一个排列对应起来。它们之间的对应关系可有康托展开来找到。如果想知道 321 时 {1，2，3}中第几大的数，可以这样考虑：第一位是 3 ，当第一位的数字小于 3 时，对应的排列数都小于 321，如 123，213.则小于 3 的数有 1，2，所以有 2×2! 个;再看小于第二位的数 2 ，小于 2 的数只有一个就是 1 ，所以有 1×1！=1。因此小于 321 的 {1，2，3} 排列数共有 2×2！+1×1！=5个，所以 321 是第六大的数。 再如 1324 是 {1，2，3，4} 排列数中第几大的数？ 第一位数字是 1 ，小于 1 的数没有，是 0 个，即 0×3！；第二位数字是 3 ，小于 3 的数有 1，2，但 1 已经在第一... -
Anyeの小站
2019-11-01
【百题千解】题解 P2730 【魔板 Magic Squares】
思路分析 这道题是一道非常典型的 BFS 题目， BFS 所面临的最大问题是判断重复。显然，如果每次判断重复都扫描一次队列，搜索的效率会非常低，会提高一个指数级，所以一般宽度搜索的判断重复都是运用数组来实现的。那么数组下标就需要用一个 Hash 函数来计算。因此，设计 Hash 函数就显得非常重要。 本题 Hash 函数的设计：我们很容易想到将 8 个数字按顺时针顺序组合成 8 进制（每个数字都减 1 ）的 8 位基数。但是，这里最大的八进制数 76543210 ，转换成十进制数就是 16434824 ，也就是说要开大小为 16434824 的数组，如果题目强制空间限制，那么，数组下标会越界。 这里我们引入康托展开，即将一个排列对应成它在全排列中的序数，这样就不会 MLE 了。 如 {1,2,3,4,···,n } 表示 1,2,3,4,···,n 的一个排列，如 {1,2,3} 按从小到大排序，一共有6个： 1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1，分别代表数字 1,2,3,4,5,6，也就是把 10 进制数与一个排列对应起来。它们之间的对应关系可有康托展开来找到。如果想知道 321 时 {1,2,3} 中第几大的数，可以这样考虑：第一位是 3 ，当第一位的数字小于 3 时，对应的排列数都小于 321，如 123,213，则小于 3 的数有 1,2，所以有 2×2! 个；再看小于第二位的数 2 ，小于 2 的数只有一个就是 1，所以有 1×1!=1。因此小于 321 的 {1,2,3} 排列数共有 2×2!+1×1!=5 个，所以 321 是第六大的数。 再如 1324 是 {1,2,3,4} 排列数中第几大的数？ 第一位数字是 1，小于 1 的数没有，是 0 个，即 0×3! ；第二位数字是 3，小于 3 的数有 1,2，但 1 已经在第一... -
Anyeの小站
2019-11-01
【百题千解】题解 P2243 【电路维修】
思路引导 我们可以把电路板上的每个格点 (横线与竖线的交叉点) 看作无向图的结点。若两个顶点 x 和 y 之间的连边。若该方格中的标准件(对角线)与 x 到 y 的线段重合，则边权为 0 ；若垂直相交，则边权为 1 (说明需要旋转 1 次才能连通 )。然后，我们在这个无向图中求出从左上角到右下角的最短距离，就得到了结果。 这是一个边权要么是 0，要么是 1 的无向图。在这样的图上，我们可以通过双端队列广度搜索来计算。算法的整体框架与一般的广度搜索类似，只是在每个节点上沿分支扩展时稍作改变。如果这条分支是边权为 0 的边，就把沿该分支到达的新节点从队头入队；如果这条分支是边权为 1 的边，就像一般的广度搜索一样从队尾入队。这样一来，我们就仍能保证任意时刻广度搜索队列中的结点对应的距离值都具有“两段性”和“单调性”，每个结点从队头出队时，就能得到左上角到该节点的最短距离。 因为每个结点只需要访问一次，所以算法的时间复杂度为 O (R×C）。 代码解释 #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int cap = 500010; int dist[510][510]; char map[510][510]; bool proc[510][510]; pair<int, int>queue[cap * 2]; int r, c, li, ri; inline bool valid(int x, int y) { return x >= 0 && x <= r && y >= 0 && y <= c; } inline void que_add(int x, int y, int v) { if (dis... -
Anyeの小站
2019-10-23
【百题千解】题解 P5594 【【XR-4】模拟赛】
我来写一篇大家都能看懂的，很好理解的算法。 这道题比赛时考虑的是可以用桶排的思想，但是比赛时想多了，按照横排去遍历了。 （太***了 经过我赛时的思考以及赛后的努力，我想出了 非常好理解 的方法。看到楼上的 dalao 们用的 STL 大法，我一个蒟蒻瑟瑟发抖~~ 我们先来理解一下这道题目 观察数据特征+思路解析 Subtask 1（13 points）：n = m = k = 1。 这是送分。。 //附上代码 cout<<"1"; 不用解释吧 QWQ Subtask 2（24 points）：n = 1。 在这里我们思考一下，当 n = 1 时，意味着只有一个人参加模拟赛，那么直接输出一组数，使这个人有空的日数为 1 即可，其余为 0，这里运用到桶排的思想。 cin >> n >> m >> k; memset(pp, 0, sizeof(pp)); for (int i = 0; i < n * m; i++) { cin >> f; pp[f]++; } for (int i = 1; i <=k; i++) { cout << pp[i]<<" "; } Subtask 3（24 points）：m = 1。 继续向下看，m = 1 时，每个人只有一天做模拟题，那么从上到下遍历，去重，得到结果。 for (int i = 0; i < n * m; i++) { cin >> f; pp[f]++; } for (int i = 1; i <= k; i++) { if (pp[i] != 0) cout << "1 "; else cout << pp[i] << " "; } Subtask 4（39 points）：无特殊限制。 那么正解也就出来了。我们可以结合前两种方案来得出最终的结果： 既然每... -
Anyeの小站
2019-10-21
【百题千解】题解 P5595 【【XR-4】歌唱比赛】
这道题在月赛的时候我本来是 想用 string 稳过的，结果发现看不懂题，没理解不合法的情况，看了看题解没有 dalao 用 string 解，我就来用 string 解一下这道题。 这道题完全可以用字符串来解决，我在这里 @文·和 可以参考一下。 思路 首先，这道题其实我们完全可以自定义它高出的分数，那么我们就以 0 和 1 为例。 先完成合法情况： 合法情况很简单，只需要判断给定的字符串中出现的 X,Y,Z； 那么 74 分代码就出现了 for (int i = 0; i <= f.size(); ++i) { if (f[i] == 'Z') { a += '0', b += '0'; } if (f[i] == 'X') { a += '1', b += '0'; } if (f[i] == 'Y') { a += '0', b += '1'; } } 然后 我们来考虑一下不合法的情况，共有3种。 当Z位于字符串最后一位且前面没有出现Z的时候，是合法的。 当Z存在于字符串中间的时候，不合法。 当Z存在于字符串中间但其后面全都是Z的时候，合法。 那么我们可以写出 判断函数 bool canot() { int len = f.size(), cnt = 0; for (int i = len - 1; i >= 0; i--) if (f[i] == 'Z') can[++cnt] = i; for (int i = len - 1; i >= len - cnt; i--) if (f[i] != 'Z') return false; return true; } 这里参考了 Morbid 大佬的题解思路 那... -
Anyeの小站
2019-10-20
【百题千解】题解 P1242 【新汉诺塔】
看了楼上大佬的解法，应该都没有想到 汉诺塔 与 二进制 还有一层微妙的关系，所以我来介绍一种 二进制解汉诺塔 的思路。 找规律 我们可以观察到这样一种规律： 二进制：需要前面全都变成 1 才能进位 汉诺塔：需要上面的盘子全都移走才能移动。 而这有相似之处。所以我们就可以想，可不可以用二进制来模拟圆盘的移动？ 我们先来考虑一种简单的情况 来我们观察一下，假设汉诺塔的圆盘都在 A 柱上，我们从 0 数起（0000） 当我们把末位数从 0 变成 1 时，就把 0 号盘移动到右边的柱子上（如下图） 如果 0 已经在 C 柱上了 就把它移回 A 柱 要是在二进制计数中 已经进到了二位，也就是把末尾的两位数从 01 变成 10 的话 就移动 1 号圆盘 然而显然不能把它移到 B 柱上，所以就剩下 C 柱可以 当数到 11，只需要个位加一，所以只需移动 0 号圆盘 然后二进制中进到四位，所以移动 2 号圆盘 接下来以此类推： 个位加一，移动 0 盘； 二位加一，移动 1 盘； 三位加一，移动 2 盘； ... 动画演示就像这样 证明 我们来证明一下这种思路的可行性。 汉诺塔的最少移动数的方案可以看作是要先把A柱上，最底面的圆盘以上的塔先移开，倒数第二盘要移动就要先把以上的圆盘移开，也就是一个递推的过程，而二进制的进位就是一个最简的递推方案。所以我们完全可以用二进制来模拟圆盘的移动。 关于此题 我们会发现，其实每一种汉诺塔的排列都会对应一个二进制数，二进制数转换成十进制数就是从 0000 推到现在这种排列的最少步数，那么这道题我们就可以先把给定初始状态的 A、B、C柱上的圆盘转换成二进制数，然后模拟二进制数一直加 1 的过程，得到目标状态。我们就可以很简单的解决这道题了。 提醒 A、B、C 三柱其实可以认为是不固定的，所以完全可以将初始状态的 A、B、C 柱上的圆盘进行交换以获取一个二进制... -
Anyeの小站
2019-09-03
【百题千解】A-道路铺设 题解（2018NOIP提高组复赛）
分析 首先来分析示例数据 这是按照示例数据画出来的示意图， 那么填过之后就变成了这样 这样太麻烦了，仔细观察图 2，有没有发现一个规律： 其实我们可以这样子： 先把第 1 列的道路先填起来，记到天数 sum 中，然后将第一列下陷的深度后面的深度相比较，若后面的有一个小于它，则整条道路上都被填满了最浅的那个坑的深度的土，如图。 然后我们通过使用 for 循环遍历整条道路，在前一步的基础上，增加天数 sum，如图 图片颜色标记错了，第5列的5也是红色 继续 图片颜色标记错了，第5列的5也是红色 最后 我们的算法应该这样实现 至此这道题就算完成了！ 最后贴上完整代码 #include<bits/stdc++.h> using namespace std; int main() { //freopen ("road.in","r",stdin); //freopen ("road.out","w",stdout); int n,sum=0,l=0; scanf("%d",&n); for(int i=1;i<=n;++i) { int a; scanf("%d",&a); if(a>l) sum+=(a-l); l=a; } printf("%d\n",sum); return 0; }