目 录CONTENT
朋友圈
-
Anyeの小站
2019-11-13
【百题千解】题解 P5650 【基础字符串练习题】
建议 做此题前先去看看这道题：P1739 表达式括号匹配 这道题是作为入门题出现的，主要的思路是用 栈 解决，为什么这么讲呢，emmmm~ STL也算是我们 C++ 党的一大优势对吧 思路 进入正题 我们其实可以将相邻的两个不同的数字给消去，舍去开头的 1 ，例如样例中给的 0111100101 我们按照规则对其进行处理，得到 01 111 00 10 1 可以发现，这里最后就剩下两个 0 了，可能有人会问：为什么最后的那个 1 不取呢？ 这里解答一下，因为题目中未对子串进行要求，所以我们的子串可以取任意长度，只需使结果最大就可以了，如果这里把 1 取到了，就会使结果更小，所以这个 1 当然就会被舍去了。 对比 为什么说这道题很像 P1739 表达式括号匹配 呢，不知大家有没有发现，这里的 与 0 相邻的 1 可以看做是括号匹配中的 ‘ ）’，把 0 看做是‘（’，那么就会发现，其实这道题就是在寻找不能匹配的括号数。 那么我们就可以用栈来进行 0 1 的配对消除 if(a[i]=='0') cxk.push(1); if(a[i]=='1'&&(!cxk.empty())) cxk.pop(); maxx=max(maxx,k); 但是我们真的已经考虑到所有情况了吗？ 想一想，会有两种特殊情况，一种是全是 1 的情况，另一种是全 0 的情况，那么我们会发现，我们需要对全 1 的情况进行特判；只需要在扫描的过程中加入对 1 的计数即可（当 1 的个数==size时，输出 -1（全 1 的话 0 的个数为0，那么0-1=-1） ） 鉴于这个难度，那么最后附上 AC （chou） 代码 代码 #include<bits/stdc++.h> using namespace std; string a; int mn; long long maxx; signed main(){... -
Anyeの小站
2019-11-13
【百题千解】题解 P5650 【基础字符串练习题】
建议 做此题前先去看看这道题：P1739 表达式括号匹配 这道题是作为入门题出现的，主要的思路是用栈解决，为什么这么讲呢，emmmm~ STL也算是我们 C++ 党的一大优势对吧 思路 进入正题 我们其实可以将相邻的两个不同的数字给消去，舍去开头的 1 ，例如样例中给的 0111100101 我们按照规则对其进行处理，得到 01 111 00 10 1 可以发现，这里最后就剩下两个 0 了，可能有人会问：为什么最后的那个 1 不取呢？ 这里解答一下，因为题目中未对子串进行要求，所以我们的子串可以取任意长度，只需使结果最大就可以了，如果这里把 1 取到了，就会使结果更小，所以这个 1 当然就会被舍去了。 对比 为什么说这道题很像 P1739 表达式括号匹配 呢，不知大家有没有发现，这里的 与 0 相邻的 1 可以看做是括号匹配中的 ‘ ）’，把 0 看做是‘（’，那么就会发现，其实这道题就是在寻找不能匹配的括号数。 那么我们就可以用栈来进行 0 1 的配对消除 if(a[i]=='0') cxk.push(1); if(a[i]=='1'&&(!cxk.empty())) cxk.pop(); maxx=max(maxx,k); 但是我们真的已经考虑到所有情况了吗？ 想一想，会有两种特殊情况，一种是全是 1 的情况，另一种是全 0 的情况，那么我们会发现，我们需要对全 1 的情况进行特判；只需要在扫描的过程中加入对 1 的计数即可（当 1 的个数==size时，输出‘-1’ （全 1 的话 0 的个数为0，那么0-1=-1） ） 鉴于这个难度，那么最后附上**AC （chou） **代码 代码 #include<bits/stdc++.h> using namespace std; string a; int mn; long long maxx; signed mai... -
Anyeの小站
2019-11-10
【百题千解】题解 P5638 【【CSGRound2】光骓者的荣耀】
题解原因 这篇题解旨在帮助理解，dalao请忽视。 因为这是一道红题红题，所以我在这里讲述的详细一点。 题目简介 有 𝑛n 个城市，每两个城市之间有双向通路，耗费时间 𝑎𝑖ai (其实可以理解为长度为 𝑎𝑖ai ) ，小K从 1−𝑛1−n 走访 (可以理解为从1走到 n )。 但是小K可以从第 𝑖i 个城市直接跳转到第 𝑖−𝑘i−k 或 𝑖+𝑘i+k 。(只可使用一次) 注意：他可以不访问所有的城市，使用传送器不耗费时间 (这句话意味着上面的跳转方案的思路是正确的，比如我完全可以从城市 1 跳到城市 4 ，只要使小K走过的总长度最短就可以) 求最快的用时 (即求最短的走路长度)。 思路分析 结合样例，我们可以发现，我们最终走过的长度就是总长度-跳转的长度总长度-跳转的长度，输入的 𝑘k 即为我们跳转的范围。 总长度使一个固定值，即所有路径的长度和。 那么要使得最终走过的长度最短，只需使跳转的长度最大。 我们只需要在所给的 𝑎𝑖ai 中选取 𝑘k 个数，使得 ∑𝑖=𝑥𝑥+𝑘𝑎𝑖i=x∑x+kai 的值最大即可。 我们可以枚举每一个 𝑘k 的范围，求 ∑ ，在这里放一份实现代码： for (int i = 1; i <= n; i++) { long long ans2 = 0; for (int j = 0; j < k; j++) { ans2 += cxk[i + j]; } maxx = max(maxx, ans2); } 但是我们会发现这个毒瘤数据范围（注意看21~25） 显然这样循环会重复计算中间的一些值，21~25都会超时。 那么我们怎么优化呢？ 优化 我们可以在循环的基础上，去掉重复计算的值。 在从 𝑎1a1 到 𝑎𝑘ak 求和的基础上，加上第 𝑎𝑘+1ak+1 个数，减去 𝑎1a1 ，是不... -
Anyeの小站
2019-11-10
【百题千解】题解 P5638 【【CSGRound2】光骓者的荣耀】
题解原因 这篇题解旨在帮助理解，dalao 请忽视。 因为这是一道红题 红题，所以我在这里讲述的详细一点。 题目简介 有 𝑛n 个城市，每两个城市之间有双向通路，耗费时间 𝑎𝑖ai (其实可以理解为长度为 𝑎𝑖ai ) ，小K从 1−𝑛1−n 走访 (可以理解为从1走到 n )。 但是小K可以从第 𝑖i 个城市直接跳转到第 𝑖−𝑘i−k 或 𝑖+𝑘i+k 。(只可使用一次) 注意：他可以不访问所有的城市，使用传送器不耗费时间 (这句话意味着上面的跳转方案的思路是正确的，比如我完全可以从城市 1 跳到城市 4 ，只要使小K走过的总长度最短就可以) 求最快的用时 (即求最短的走路长度)。 思路分析 结合样例，我们可以发现，我们最终走过的长度就是总长度-跳转的长度 总长度-跳转的长度，输入的 𝑘k 即为我们跳转的范围。 总长度使一个固定值，即所有路径的长度和。 那么要使得最终走过的长度最短，只需使跳转的长度最大。 我们只需要在所给的 𝑎𝑖ai 中选取 𝑘k 个数，使得 ∑𝑖=𝑥𝑥+𝑘𝑎𝑖i=x∑x+kai 的值最大即可。 我们可以枚举每一个 𝑘k 的范围，求 ∑ ，在这里放一份实现代码： for (int i = 1; i <= n; i++) { long long ans2 = 0; for (int j = 0; j < k; j++) { ans2 += cxk[i + j]; } maxx = max(maxx, ans2); } 但是我们会发现这个毒瘤数据范围（注意看21~25） 显然这样循环会重复计算中间的一些值，21~25都会超时。 那么我们怎么优化呢？ 优化 我们可以在循环的基础上，去掉重复计算的值。 在从 𝑎1a1 到 𝑎𝑘ak 求和的基础上，加上第 𝑎𝑘+1ak+1 个数，减去 𝑎1a1 ，... -
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 10 4 按照贪心，单位重量的价值排序：A >... -
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）：无特殊限制。 那么正解也就出来了。我们可以结合前两种方案来得出最终的结果： 既然每...