- 博客(45)
- 收藏
- 关注
RSS订阅原创 Educational Codeforces Round 92 (Rated for Div. 2) A. LCM Problem（思维）
LCM Problem：题目大意：（文末有原题）LCM（x, y）= x和y的最小公倍数；给出l，r，判断是否有一组x，y（l <= x < y <= r）使 LCM（x，y）属于[l, r];思路：x的最小公倍数一定是x的倍数，所以我们不妨假设这个最小公倍数就是他的二倍，则另外一个就是2*x，所以我们只需判断r与2*l的关系即可；代码：#include <iostream>using namespace std;int main(){ in
2020-07-30 16:38:54
293
2
转载 常用字符串库函数总结
本文转自https://blog.csdn.net/sharon_1987/article/details/50022855本文与原文内容没有差别，但是由于本人比较注重颜值还有阅读体验（自认为这样可能阅读起来会舒服点），就...又给排版了一下，也算参与博客创作了（重在参与重在参与）；本文主要是粗略的介绍了各个字符库函数的大致用法，总结感觉也挺详细，就分享给诸位，有许多说明不明确，如果相要详细理解，可以在博客搜索，后续有些可能我可能也会写博客总结，到时候会附上链接，有些可能会存在错误，望大佬们指出；.
2020-07-02 23:35:21
1048
原创 Educational Codeforces Round 90 (Rated for Div. 2) C. Pluses and Minuses（思维）
Pluses and Minuses题目大意：（文末有原题）给出一个有'+' '-'组成的字符串，读伪代码写程序；res = 0for init = 0 to inf（0到正无穷，其实就是判断条件为1） cur = init ok = true for i = 1 to |s| res = res + 1 （每进入一次循环，res++） if s[i] == '+' cur = cur + 1
2020-06-30 23:27:58
276
原创 Educational Codeforces Round 90 (Rated for Div. 2) B. 01 Game（思维博弈）
01 Game题目大意：（文末有原题）DA与NET玩游戏，给一个01串，他们只能删除 相邻的两个不同字符，DA先删，如果一个人没法删除，这个人就输了，判断最后谁会获胜；思路：因为是01串，所以能删多少次，与字符串的位置没有关系（只要既有1又有0，总会有相邻的01），所以只需判断有几个01对；代码：#include <iostream>#include <cstring>using namespace std;int main() { int t;
2020-06-30 23:02:32
303
原创 Educational Codeforces Round 90 (Rated for Div. 2) A. Donut Shops（思维）
Donut Shops题目大意：（文末有原题）有两种方案买甜甜圈：每个a元 每盒b个c元；给出a,b,c，输出 买多少个时，按方案1更划算，多少个时，按方案2更划算，如果不论多少个这个方案都不是更划算，就输出-1；思路：首先如果a > c的时候，按方案一肯定什么时候都不划算；其次如果每盒平均下来的单价 (c / b)>= a 时，肯定按方案一都比较划算；剩下的就是 平均单价 (c / b) < a 时，此时如果想要买的数量刚好是n盒，那肯定按盒买划算，否.
2020-06-30 22:41:12
223
原创 Codeforces Round #653 (Div. 3) D. Zero Remainder Array（思维）（map）
Zero Remainder Array题目大意：（文末有原题）给你n个整数，且x=0，每次要么x++，要么使ai++并且x++，判断最少通过多少次操作后，可以使任意ai % k = 0；思路：（暴力会TLE）因为不论哪个操作，x均会自增1，即x的每个值只能使用一次；所以对于每种余数，x每增加k，只会多一个数能整除k（设有n个ai 对k的余数是k-1，那么x每增加k，这个n变为n-1，具体看例子）；所以我们需判断出，在余数1~k-1中，数量最多的是哪个（假设最多的数量是s，并且这个
2020-06-30 19:19:09
222
原创 Codeforces Round #653 (Div. 3) C. Move Brackets（思维）
Move Brackets题目大意：（文末有原题）给出一个由 ')' 和 '(' 组成的字符串，我们可以将一个字符移动到字符串首或尾，输出最少通过多少次移动可以使每个')' 前都有与它匹配的'('；匹配规则：() 是对的(()) 也是对的(()()) 也是对的)( 是错的思路：因为要构成对，只需把 '(' 移动到 ')' 之前，所以说每有一个不成对的括号，就需要移动一次，所以只需判断有多少个还没有成对；代码：#include <iostream>.
2020-06-30 18:06:59
214
原创 Codeforces Round #653 (Div. 3) B. Multiply by 2, divide by 6（暴力、思维）
Multiply by 2, divide by 6题目大意：（文末有原题）给出一个整数，计算通过几次 *2 或者 /6 会得到1；思路：要求通过*2 或者 /6得到1，实际上其实是/3 或者 /6，如果可以则一定要满足含有因子3，所以就每次判断是否含有3即可，如果不含，则通过操作一定不会得到1，否则就暴力执行操作；代码：#include <iostream>using namespace std;typedef long long ll;int main(
2020-06-30 17:44:41
298
原创 Codeforces Round #653 (Div. 3) A. Required Remainder（思维）
Required Remainder题目大意：（文末有原题）给出一个整数n，输出0~n中 对x的余为y的最大整数；思路：要获得对x取余为y的最大整数，其实就是最多能包含多少个x（设最多为k个），并且n >= k * x + y，所以只需求出n/x再进行判断是否满足n >= k * x + y即可；代码：#include <iostream>using namespace std;typedef long long ll;int main() {
2020-06-30 16:56:46
235
原创 Codeforces Round #617 (Div. 3) D. Fight with Monsters（思维博弈）
Fight with Monsters：题目大意：（文末有原题）给出n个怪物的血量，你每次可以对他造成a点伤害，你的对手则能打b点，你先打，你的技能是让对手不能出招（能使用k次），判断你最多能造成几次致命一击；思路：（因为n和a，b都比较大，所以应该很大可能直接暴力会TLE（我也没试））因为要获得最大的致命一击，所以要尽可能多的在对手要造成最后一击的时候对他使用技能，这样就等于说之前对手是在给你打工；所以我们只要统计出 对于每个怪物如果你想要致命一击 需要使用多少次技能，最后再对次数排
2020-06-25 18:15:58
284
原创 Codeforces Round #627 (Div. 3) D. Pair of Topics（思维）（构造cmp）
Pair of Topics题目大意：（文末有原题）分别给出连个数组a[n] 和 b[n]，判断a中有几对整数使a[i] + a[j] > b[i] + b[j];思路：另外一个数组v[n]，v[i]来保存a[i] - b[i]，此时，只需判断v中有几个整数对的和大于0；首先 正数 + 正数 > 0、正数 + 0 > 0，所以 分别记录整数的个数k 和 零的个数m，一定会有(k * (k - 1)) / 2（即） + m * k；其次就是 一个负数 + 绝对.
2020-06-25 16:28:45
197
原创 Codeforces Round #651 (Div. 2) C. Number Game（思维博弈）
Number Game题目大意：（文末有原题）给出一个整数n，老A和小F在玩游戏：如果n能整除一个奇数，就整除奇数 n如果大于1，n -= 1；A先走，判断最后谁能得到1；思路：首先，判断特别的，n = 1 和 n = 2；其次，因为可以除奇数，所以如果这个数是奇数，直接除自身就可以得到1，直接获胜；第三种情况就是n是偶数：如果这个偶数没有可以整除的奇数，那么只能-1，那么就变为偶数，对手就能直接除自身获得1；否则，除于最大的奇数因子，得到的数，如果是偶数，并且不是
2020-06-24 22:04:13
238
原创 Codeforces Round #651 (Div. 2) B. GCD Compression（思维 构造）
GCD Compression题目大意：（文末有原题）给出2*n个数，首先从中拿走两个，然后再从2n-2个数中拿出n-1对整数，两个整数相加进入新数组，并且保证新形成的数组的所有元素的最大公约数>1;思路：因为要使新数组的所有元素的最大公约数 > 1，那么我们不妨假设最大公约数为2，因为每个数不是偶数就是奇数，并且 奇数 + 奇数 = 偶数，偶数 + 偶数 = 偶数，所以就是构造奇数对和偶数对；如果奇数的数量是偶数，就扔掉2个偶数（注意当偶数个数为0，只能扔掉两个奇数）；
2020-06-24 16:45:09
208
原创 Codeforces #651 A.Maximum GCD（思维）
Maximum GCD题目大意：（文末有原题）求1~n中任意两个数的最大公因数的最大值；思路：如果n是偶数 max = n / 2；如果n是奇数 max = （n - 1) / 2;代码：#include <iostream>#include <algorithm>using namespace std;int main() { int t; cin >> t; while(t--) { int n; cin &g
2020-06-23 22:56:58
264
原创 Codeforces Round #171 (Div. 2) B. Books (思维)
Books：题目大意：（文末有原题）给出n个整数，第i个数代表看第i本书所需时间，给出总时间t，从i本书开始看，直到时间用完，或者看到最后一本书（看完最后一本书如果还有时间不会再去看第一本）；求最多能够看几本书；思路：（代码②是直接暴力二重循环，会TLE）其实是求最多有几个连续数的和小于t；从第i本开始看，如果看到第x本时间超过t，则把第i本删去（等价于从第i+1本开始看；这样实现可以节省从i+1加到x的运行时间），再去加上第x本，如果仍然超过t，就继续删第i+2本，直到x=n；并且如
2020-06-23 10:26:25
129
原创 Educational Codeforces Round 35 (Rated for Div. 2) C. Three Garlands（思维）（打表）
Three Garlands：题目大意：（文末有原题）有三盏灯，给出三个亮灯间隔：a, b, c；亮灯规则是 i（开灯时间）、i+x(亮灯间隔)、i+2*x、...，在三盏灯都打开之后，如果能保证每一秒都有灯在亮，则输出“YES”，否则输出“NO”；思路：（应该也算是打表吧）因为只有三盏灯，所以最大的亮灯间隔是3，且必须要保证三个灯的亮灯间隔都是3；并且如果有一盏灯亮灯间隔是1（每秒都亮），则一定是可以的；剩下的就是两盏灯时候，经过验证可以知道，只有满足 2、2、x（任意数）或者
2020-06-22 18:53:21
199
原创 Codeforces Round #531 (Div. 3) B. Array K-Coloring（思维）（vector map）
Array K-Coloring：题目大意：（文末有原题）给出n个整数，用k种颜色给这n个整数着色，要求：1. 每个整数都有一种颜色；2. 每种颜色至少要涂一个整数；3. 每种颜色不能为相同的整数着色；判断能否为每一个整数都着色；思路：首先判断是否能够实现；不能实现的条件：存在有x个相同整数，并且x > k;（因为k个颜色，每个颜色不能涂相同的整数，如果x>k,代表会有x-k个该整数没法着色）如果能实现就进行下列操作：因为要每个颜色至少要涂.
2020-06-22 18:01:27
209
原创 Codeforces #295 (Div. 2) B. Two Buttons（逆向思维）（搜索）
Two Buttons:题目大意：（文末有原题）给出两个整数n和m，判断需要多少步能使n变为m；能进行操作：1. n *= 2； 2. n -= 1;思路一：逆向思维，从m向n推，最短的距离就是更多的/2；如果是奇数就先+1变成偶数；如果是偶数就/2；最后再如果m<n;加上n-m步（从m加1一直加到n）；代码：#include <iostream>using namespace std;int main() { int n, m, s = 0; c
2020-06-22 17:10:43
219
原创 Educational Codeforces 63 (Rated for Div. 2) B. Game with Telephone Numbers（思维博弈）
Game with Telephone Numbers：题目大意：（文末有原题）给出一个长度为n（n是奇数）的字符串s，Vasya 和 Petya 轮流从字符串删除一个字符直到字符串的长度变为11，Vasya先走，判断结束时获得的串是否是一个电话号码；电话号码：长度为11，并且第一个字符是'8'；思路：要判断最后能否是一个电话号码，实际上是判断最后一次操作后首位是否能为'8';因为P(Petya)不想让其成为电话号码，所以每次都会删除靠前的'8'直到'8'被删完 或者 长度变为11
2020-06-22 16:23:13
168
原创 Codeforces #560 (Div. 3) C. Good String（思维）
Good String题目大意：（文末有原题）给出一个字符串，判断需要删除多少个元素才能使串变成好串；好串：每一个奇数位（第i位）的字符与其下一位（第i+1位）的字符不相等；空串也是好串；思路：二重循环，第一重判断是否是奇数位与下一位是否相同，如果相同进入第二重循环，删去与奇数位相同的元素，直到遇到不同的；否则进入下一个奇数位；代码：#include <iostream>using namespace std;const int maxn = 2e5
2020-06-22 16:01:22
182
原创 Codeforces #531 (Div. 3) C. Doors Breaking and Repairing (思维博弈)
Doors Breaking and Repairing：题目大意：（文末有原题）给出n个整数，代表n个门的耐用度，玩家A每次会选择一个门，使这个门的耐用度减少x，玩家B每次会选择一个门，使这个门的耐用度增加y，A先操作，经过无限次操作后，判断会有几个门报废（耐磨度<=0）；思路：首先如果每次破坏的大于修补的（x > y），无限次之后，一定会报废；其次，因为破坏的小于等于修补的（x <= y），所以只有一次性直接使门报废，门才会报废，否则永远不会报废；代码：
2020-06-22 15:34:54
165
原创 Codeforce #541(Div.2) C. Birthday (思维、暴力)
Birthday题目大意：（文末原题）给出n个整数，使两两之间差值尽量小围成一个环，输出这个环；思路：将n个数排列，使最大的在中间，往两端减少，就可满足题意；（也可以直接隔一项输出，再从末尾开始隔一项输出）代码：#include <iostream>#include <algorithm>using namespace std;int main() { int n; cin >> n; int a[200], ans[200]
2020-06-22 14:19:25
160
原创 CodeForces #650 B. Even Array（思维）
B. Even Array题目大意：（文末有原题）给出一个长度为n的数组，如果每个位置的a[i] % 2 == i % 2；则是良好数组，如果不满足，输出需要交换几次能够使其成为良好数组，如果不能，输出“-1”；思路：（与Codeforces #644 C.Simple Pairs解决有些相似）如果是良好数组，则a[i]的奇偶性情况与i要相同，但是对于n，n固定，它的偶数情况就固定了：1. 如果n是奇数，则从0到n-1，偶数个数-奇数个数 = 1；2. 如果n是偶数，则从0到n-1
2020-06-18 17:20:18
489
原创 Codeforces #650 A. Short Substrings（思维）
A. Short Substrings题目大意：（文末有原题）一个字符串s，从s[0]开始到s[len-2]，每相邻两个字符（a[0]a[1]、a[1]a[2]）是一个子串然后排列下去；给出一个字符串，这个字符串是通过这样获得的，求原字符串；思路：原函数每两个相邻的都会构成一个子串都会输出，所以原字符串s从s[1]开始，都会存在重复的s[i]（除了最后一个），所以，我们只需保证每次都输出两个中的一个就可以得到原字符串，并且要保证能输出最后一个，所以i%2 == 1输出即可；代码：.
2020-06-18 16:38:02
317
原创 编译错误：expected = , asm, or, _attriblute_ before { token
今天在写链表时出现的错误；(不知道为什么把这个当标题会说我标题非法字符)Error:expected '=', ',', ';', 'asm' or '__attribute__' before '{' token这个错误给出的位置不太准确（我出现报错的位置是在一个函数之后与大括号交界的位置（... 函数名(...) (这里) { } ，所以在函数位置找不到错误，就去找函数声明，发现有一个函数声明后少了一个";"）；并且在网上找到了一些其他情况可能也会出现这个错误，在这里总结下来，与大...
2020-06-18 16:02:53
11449
1
原创 CodeForces #649 B. Most socially-distanced subsequence（思维、规律）
Most socially-distanced subsequence题目大意：（文末原题）给出一个长度为n的数组整型数组，输出使 相邻项的差 的绝对值 的和 最大，数组长度最小 的字串及其长度；思路：我们通过一个分析一个例子来得出思路，例： (1, 2, 3, 8, 7, 11, 13) 的 邻间项差的和是 1 + 1 + 5 + 1 + 4+ 4 = 2 + 5 + 1 + 8；我们不难理解，不论如何删去项，我们所得的 邻间项差的和 总是小于等于n个数间的 邻...
2020-06-16 08:47:14
336
原创 CodeForces #649 A. XXXXX（思维 双指针）
A. XXXXX题目大意：（文末原题）给出一个字符串，判断能否从 开头或末尾 删去部分元素，使这个子串的元素和不被x整除，输出最长字串长度；思路：双指针，一个循环删除开头的元素，另一个循环删除末尾的元素，每次判断能否整除；代码：#include <iostream>using namespace std;const int maxn = 1e5 + 10;int main() { int t; cin >> t; while(t--) {
2020-06-14 23:24:26
585
原创 kuangbin搜索专题 H - Pots（BFS）（需要记录和输出每一步的操作）
Pots题目大意：（文末有原题）给你两个空杯子的容积，问能否通过倒水使得其中一个杯子内水的体积变为n；如果可以，输出需要的最短步数和每一步的操作；倒水：1. FILL(i) : 将第i个杯子注满水；（1<=i, j <= 2 && i != j） 2. DROP(i) : 将第i个杯子的水倒掉； 3. POUR(i, j) : 将第i个杯子内的水倒向第j个杯子，倒的结果：一个满，另一个空 或一个满，另一个有剩余...
2020-06-09 22:23:31
166
原创 kuangbin搜索专题 G - Shuffle Up（暴力）
Shuffle'm Up题目大意：（文末原题）给出两个长度为c字符串a,b和一个长度为2c的s字符串，如果a,b通过x次洗牌（a，b依次较吵[a1, b1, a2, b2 ... ac, bc]）如果能得到s，则输出x，否则输出再发牌（a是s的前c项，b是s的后c项），如果最终不会得到s，则输出-1；思路：依据题意，循环每次都将a,b洗牌之后再判断，否则的话再发牌；代码：#include <iostream>#include <algorithm>#i
2020-06-09 20:23:03
195
原创 kuangbin 搜索专题 F - Prime Path （POJ - 3126）（BFS）（制表）（模拟队列）
模拟队列：运用两个整数（head、tail），分别做队首，队尾，来模拟queue中的入队，出队，取队首...void bfs() { // 0 int q[maxn]; //模拟一个int类型的队列进行基本的bfs // queue: // (head) int tail = 0, head = 0, x; // (tail) 此时是空队列 q[head] = x; // 0
2020-06-08 21:39:08
139
原创 kuangbin搜索专题 E - Find The Multiple (POJ - 1426)（BFS、DFS 或 同余数定理）
Find The Multiple题意：（文末有原题）给你一个数n，输出这个数的一个由0、1构成的倍数，即n*m的每一位都是0或者1；、思路（一）：利用同余数定理来解题；同余数定理： (a * b) % n = (a % n * b % n) % n; (a + b) % n = (a % n + b % n) % n;运用对a[i] = a[i / 2]+ i % 2; 模拟了双通道的bfs，例：a[2] = a[1] + 0，a[3]...
2020-06-08 16:43:18
185
原创 c++中lower_bound()与upper_bound()函数
要在<algorithm>头文件内；且要求数组或者容器在使用时已经排序;实际上是在有序数组中的二分查找；lower_bound(first, last, val)是查找在 [first, last) 间，大于等于 val 的第一个数；如果是数组返回指针，如果是位置返回迭代器；lower_bound(a, a + n, x) - a; 输出在a中大于等于x的第一个位置；upper_bound(first, last, val) 则是查找大于val的第一个数；用法同上；
2020-06-08 15:25:31
214
原创 kuangbin搜索专题 C - Catch That Cow（POJ - 3278）（BFS）（一条线上的BFS）
Catch That Cow:题目大意：（文末有原题）在一条线上，给出两个位置，每一步有两种操作：x + 1 或 x - 1; x *= 2;输出从第一个位置运动到第二个位置的最短距离思路：依旧是迷宫问题，不过是一条线上的迷宫问题（数轴），并要求输出最短的时间，三种运动方式的bfs；要注意考虑范围，剪枝；否则会TLE，并且要注意进行运动后的数据是否满足范围；代码：#include <iostream>#include <queue>#inclu
2020-06-05 18:11:24
156
原创 kuangbin搜索专题 B - Dungeon Master（POJ - 2251）（BFS）
BFS(宽度优先搜索)：应用队列（先进先出） 达到一层一层遍历的效果比如说第一步6个状态皆可走，则向对列中存入6个元素，之后再循环依次拿出6个状态，每个状态的情况都存入在这第一次的6个状态之后，然后依次往后放，以此来达到一层一层的操作；strchr()和strrchr():要在<cstring>头文件中strchr(char *str, int c) str是字符串，c是要查找的字符，从左开始查找，如果找到输出最先出现的位置，否则输出NULL；strrc.
2020-06-05 17:48:11
137
原创 kuangbin搜索专题 A - 棋盘问题（POJ - 1321）（DFS）
棋盘问题：题目大意：（原题在文末）给出一个棋盘，在允许的位置上放k个棋子，有几种放法；要求每一行每一列只有一个棋子；思路：因为要使每一行每一列的只有单独的一个，所以可以放完这一行就去放下一行，直到放完或者没地方放；然后再从这一行的下个位置开始放；深搜；代码：#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn =
2020-06-05 17:06:53
191
原创 Codeforces #647 C. Johnny and Another Rating Drop（思维，规律）
Johnny and Another Rating Drop题目大意：（文末有原题）给出一个数n，输出0~n相邻两个数间的差异位数的总和；思路：0 00001 00012 00103 00114 01005 01016 01107 01118 1000通过举例可得：对于第一位，变化为 010101010...周期为2；对于第二位，变化为 001100110...周期为4；对于第三位，变化为 000011110...周期为8；很容易发现第k
2020-06-05 16:04:24
246
1
原创 Codeforces #644 C.Simple Pairs(思维 双指针)
C.Simple pairs题目大意：（文末有原题）给出一个数组，判断能否构成对，对要满足：奇偶性相同，或者差1；输出“YES”or“NO”；思路：首先数组个数必须是偶数，其次如果奇数和偶数的个数均为偶数，则一定可以，否则，一定是多出来一个奇数或者一个偶数，则从后之前查找，如果有两个数满足 a - b = 1，则输出“YES”，注意要先排序后再查找！代码：...
2020-06-05 14:35:41
326
原创 Codeforces #646 A - Odd Selection(思维)
A - Odd Selection题目大意：（原题在文末）要从n个整数中取出x个数，判断是否能够使取出的x个数的和为奇数；思路：因为要使和为奇数，则要有一个单独的奇数，剩下的x-1个数加起来为偶数；所以要满足剩下的数，要么全部为偶数，要么奇数成对存在。（奇 + 奇 = 偶、偶 + 偶 = 偶、奇 + 偶 = 奇）代码：#include <iostream>using namespace std;int main() { int t; cin >>
2020-06-04 20:14:11
242
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人