6的个数 题意： 问你从1到2021出现了多少个数字6 思路： 签到题，莽暴力就完辽 print(602) 小明的作业 题意： 小明同学正在学习一种新的语言。在该语言中，如果出现了一次wa或者一次aw，则代表出现了一个警告。如果出现了连续的wa或者连续的aw，则代表出现了一个错误。小明由于学习比较粗心，所以他想要知道自己刚刚写完的作业中一共出现了多少处警告和错误。下面是小明刚刚写完的作业，请你帮助小明找到他一共出现了多少次警告和多少次错误。 abcwaawawawa中出现了一次警告(wa)和一次错误(awawaw) abcdefg中没有出现一次警告和错误 waawwaawwawa中出现...

传送门 A M形字符 题意： M形字符串指的是由两个相同的回文串拼接而成 给你一个串S，问有多少个前缀是M形字符串 思路： M形是有两个相同的回文串构成的，所以这个M形串本身就是回文串，我们只需要判断一个串是回文串的同时，他的一半也是回文串即可 那如何判是不是回文串呢，这里我们使用哈希进行判断 如果一个串的正序哈希值等于其逆序哈希，则说明这个串是回文串 哈希的计算方法： pre[i] = pre[i - 1] * seed + s[i] - 'a' + 1; 对于中间取的一段的哈希值，我们可以利用类似于差分的方法 pre[r] - pre[l - 1] * base[r - l + 1]; 乘...

题意： M形字符串指的是由两个相同的回文串拼接而成 给你一个串S，问有多少个前缀是M形字符串 思路： M形是有两个相同的回文串构成的，所以这个M形串本身就是回文串，我们只需要判断一个串是回文串的同时，他的一半也是回文串即可 那如何判是不是回文串呢，这里我们使用哈希进行判断 如果一个串的正序哈希值等于其逆序哈希，则说明这个串是回文串 哈希的计算方法： pre[i] = pre[i - 1] * seed + s[i] - 'a' + 1; 对于中间取的一段的哈希值，我们可以利用类似于差分的方法 pre[r] - pre[l - 1] * base[r - l + 1]; 乘base[r - l ...

E 捡贝壳 题意： 给你n个贝壳，每个贝壳有不同的质量，进行q次询问，询问的是区间[l, r]中的贝壳质量是x的倍数的有多少个 思路1： 一开始最暴力的方法是用个二维数组存因子的前缀和，然后就可以作差直接查询，但是空间不允许，就得放弃 所以，我们就可以采取分块的方法，将n个贝壳进行分块，每一块的大小不超过，然后像线段树求区间和一样一段段的求即可 分块操作：我这里选择的是输入的时候就直接分块，你也可以像其他人那样写个函数，等输入完了再分 分块的时候最好是从0这个数开始，比如0 1 2 3 4 5 6 7 8，块是3，前三个数除以3刚好是0，但如果你从1开始计数，那就不方便了 for(int...

C Game Map 题意： 给你一个无向连通图，每个点具有点边数为k，问你最长的k下降道路有多长 思路： 用vector数组来存每个点的后继，用sum数组记录每个点的边数k dp[i]数组表示从i开始的最长k下降的道路长度 写一个记忆化搜索即可 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #i...

滑雪 题意： 在二维数组中找到一条数字逐渐减小的最长的路径，输出路径长度 思路： 确定状态： dp[i] [j] 表示从（i，j）开始走的最长路径的长度 原问题： 从（1，1）到（n，m）任意一点开始走的最长路径的长度 状态转移方程： dp[i] [j] = max{dp[i - 1] [j] + 1, dp[i + 1] [j] + 1, dp[i] [j - 1], dp[i] [j + 1]} 显然for循环没法一次性解决，之前的题都是按一定顺序，如从1到n，而现在你有四个方向，循环跑i，j的时候，你需要知道[i - 1] [j], [i + 1] [j],[i] [j + 1], [i...

题意： n个同学围成一个圆圈进行传球游戏，一个同学传球时只能传给左右的同学，传m次最终回到第一个人手里，问你有多少种情况？ 思路： 第一步：确定状态——原问题是什么，子问题是什么？ 原问题：从1开始传球，第m步回到1号的情况数 子问题：从1开始传球第i步到达j号的情况数 dp[i] [j]表示第i次传球后在j位置的情况数 第二步：确定状态转移方程和边界 dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j + 1] dp[0] [1] = 1 ，初始条件一号开始的时候是1 是个环，需要对边界1和m进行讨论 #include <cstdio&g...

题意： 给你一个倒三角形，计算从顶部开始到底部某个地方的路径中所有数字总和的最大值，每次只能向左斜向下或者右斜向下走 思路： 使出秘技dp 根据雨巨的说法，有两种，我从哪里来？我到哪里去？ 对于我从哪里来，写状态方程的话是这样的： dp[i] [j] = max(dp[i - 1] [j] + tr[i] [j], dp[i - 1] [j - 1] + tr[i] [j]) 但是这样有i - 1，如果出现负数的的话就不好处理，所以我们可以写我到哪里去 对于第tr[i] [j]的数来说，他对tr[i - 1] [j] 和 tr[i - 1] [ j - 1] 有贡献 也就是说 dp[i + 1...

过河卒 题意： 对于n * m的棋盘，棋盘中有九个点不能走，问你一个大头兵从左上角走到右下角的路径有多少条 思路： 使出秘技dp 状态转移方程是：tr[i] [j] = tr[i - 1] [j] + tr[i] [j - 1] 有一些细节： 🐎走的八个点的坐标得找对，同时得判这八个点是否符合题意 别忘记马初试点也不可以走 边界位置i = 1或 j = 1的时候，状态转移方程得变，因为此时只有一条路 开long long！（不开longlong见祖宗！！！！！） #include <cstdio> #include <cstring> #include <s...

迷宫 题意: 有一个二维迷宫，需要从S点走到E点，每一步之能选择上下左右四个方向前进一格。W代表墙壁，D代表一扇门，需持有钥匙才能通过，K代表钥匙，经过该点钥匙就会自动进入你的口袋，'.'代表是空的，可以走。 问你从起点到终点最少需要几步？ 思路： 因为问的是最短路的长度，所以是bfs题 但是这个题介入了钥匙和门这俩恶心的玩意就比较坑！ 你不可能通过计算一次bfs就得到答案，因为bfs时每个点只能走一次，用完这个点就扔掉了，不会走回头路，这就会导致一种情况：如样例一 4 12 WWWWWWWWWWWW WE.W.S..W.KW W..D..W....W WWWWWWWWWWWW第三个就踩到门D...

题意： 对一堆价值为tr[i]的纪念品进行分组，每组最多两件，且每组的价值不能超过w，输出最少的分组数目 思路： 是个贪心，需要找到最少的数目，就得尽量让小的去找大的，还得是总和不超过w 我们可以取两个变量l和r，一个在数组头一个在数组尾，开始找，如果说tr[l] + tr[r]的值小于等于w，就说明找到一组，如果大于w了，就让右指针r左移一位，更新答案，然后继续找。 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostr...

传送门 题意： 有一个n行两列的矩阵，第一列放雷，第二列代表其周围八个方向的总雷数，现在给你第二列的数，求第一列雷有多少种摆法？ 思路： 对于第一个格子，只有有雷和没有雷的情况，而当第一个格子确定了，根据第二列的第一个和第二个数和第三个数就能确定第二个格子有没有雷，所以这个题只需要讨论第一个格子有没有雷，然后挨个判断合理不变合理即可 因为tr[i] = mine[i - 1] + mine[i] + mine[i + 1] 用i - 1代替i，并移向可得到： mine[i] = tr[i - 1] - mine[i - 1] - mine[i - 2] 可以用来判断i大于等于2的时候 只需要判...

传送门 题目描述： 帕秋莉掌握了一种土属性魔法 ，她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍， 土球有一个稳定性x，如果x < 0，它会立刻散架 ，每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性 帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？ 我抽象化一下：假设你是一个战士，你有初试血量，你需要去突破n个怪物，你和怪物互刀，你杀他会失去ai的血量，但因为你出了泣血之刃，所以你可以吸血，杀死他你才能吸bi的血，问你能不能找到一个杀怪物的顺序使得你能活下来 思路： 这个题是一个超级超级无敌究极贪...

定义： 尺取法，又称双指针法（此指针非彼指针）。双指针顾名思义，有两个“指针”，根据实际情况不断地移动，从而推进区间的左右端点以得出答案 适用性： 适用于移动方向确定(一般是从头到尾)、连续区间的最小或最大问题 板子 int r = 1, l = 1;//确定两个指针的初始位置 while(l <= n){//确定循环结束条件 while(){//括号中填右指针移动的条件 r++;//移动右指针，并更新数值 } if(){//根据题意确定更新答案的条件 //更新答案 } l++;//移动左指针...