A 串 题目描述 长度不超过 ，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对 取模。所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us" 输入描述: 一个正整数 （） 输出描述: 一个正整数，为满足条件的字符串数量对 取模的值 分析： 设 表示长度为 且不包含 'u','s' 这两个字符的字符串个数. 表示长度为 且不包含 'u' 这个字符的字符串个数. 表示长度为 且不包含...

A A｜B 题目大意 给定两个正整数 ，统计满足以下条件的 的个数： 1. 2. 分析 说明 与 的二进制表示中 的位置互斥. 这里很***道地用了数位 dp（说好的 小白 呢？ 代码实现 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = (int)1e6; const int N = (int)1e5; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const ll mod = (ll)1...

A 牛牛的mex运算 一.题目大意 给出 个数 ， 次询问，每次给出 并询问 . 且 互异. 二.分析 赛时用的莫队，看题解才发现自己写麻烦了. 根据题目条件不难得 是 的一个排列. 因此 . 三.代码实现 1. 莫队 #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const int M = (int)1e5; const int N = (int)5e5; const int inf = 0x3f3f3f3f; c...

A B-Suffix Array 一.题目大意 对于字符串 ，定义 如果存在 且 ，则 . 否则，. 给出字符串 ，求 的后缀所生成的函数 的后缀数组. . 二.分析 PPT题解做法自然不是我这等菜鸡能想到的，在这里讲一个我能想出来的做法吧. 首先，很容易想到： 的所有后缀的 函数的结果中 都为 . 不失一般性，针对 的第 个后缀再延伸一下，不妨设 . 记 ，那么对于 的第 个后缀来说， . 因此，我们把 的第 个后缀的函数 的结果分为两部分 ，其中 ，. 于是，当我们要比较 与 的字典序大小时，我们可以先比较 和 ，若两者相同再去比较 和 . 由于 ...

一.题目链接 管道取珠 二.题目大意 原生题目极佳. 三.分析 这道题上来一手转化很妙，学到了~~ 题目中设 a[i] 为最终序列的某种方案数，而让我们求解的却是 ，很明显我们需要找出两者的关系. 假设我们有两个完全相同且独立的系统，两个人同时进行操作，不难证明，对于某个最终序列 F，两个人操作完成后得到的序列都与 F 相同的方案数即为 经过这一步转化后，我们就可以愉快进行 dp 辣~~（然鹅并不是...） 我们设 dp[i][j][k][l] 为第一个人从管道一取了 i 个球，第一个人从管道二取了 j 个球，第二个人从管道一取了 k 个球，第二个人从管道二取了 l 个球，...

一.题目链接 Protecting the Flower 二.题目大意 有 n 头牛，每头牛有两个属性 t[i] 和 d[i]，代表从原点走到第 i 头牛所花的时间，d[i] 代表第 i 头牛每单位时间吃花的个数，当牛被选中后，牛便不再吃花.你的初始位置在原点，每次只能牵一头牛，求把所有牛牵到原点后，所有牛吃花总和的最小值. 三.分析 贪心临项交换的经典题目. 假设最优的选择顺序为 ...AB...，那么交换 AB 的顺序这一操作不会对其他牛产生任何影响. 由于我们已经假设最优选择顺序为 ...AB...，所以 ...BA... 的结果不应该比之前的好. 即 AB 应该不比 BA ...

一.题目链接 货币系统 二.题目大意 给 n 种面值的硬币，每个硬币的面值为 a[i]，求最少用多少枚硬币能表示原先硬币能表示的所有面值. 三.分析 题目即求最多选出多少硬币可以被其他硬币表示，直接暴力求就行了，同时用 f[i] 表示面值为 i 的硬币能否被表示出来优化. 四.代码实现 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = (int)25000; const ll mod = (ll)1e9 + 7; const int inf = 0x3f3f3...

一.题目链接 [JSOI2007]建筑抢修 二.题目大意 n 个物品，每个物品有修理时间 t1，截止时间 t2，只有修完物品后时间仍未超过截止时间才算成功修理. 求最多能成功修理多少件物品. 三.分析 很经典的优先队列时光倒流大法贪心（口胡 首先对截止时间排序，建立大根堆（优先队列），对 n 件物品从前到后依次扫描，如果当前物品可成功修理，那就修理，并把其修理时间放到大根堆中；否则，如果当前物品的修理时间小于大根堆的根，那就互换这两件物品. 简单来说就是：能修则修；不能修则尝试找一个之前修理过且最差的物品，与当前物品替换，因为这样操作后，答案不会变差而且总的花费时间减少. 四.代码...

一.题目链接： 小AA的数列 二.题目大意： 给 n 个数，求区间长度为偶数，且区间长度在 [L, R] 的区间异或和的加和. 三.分析 众所周知，异或题的一种经典解法就是按照分别按照位权计算贡献. 假设当前枚举到二进制位 i，那么当前二进制位 i 对答案的贡献就是 2^i * 异或和第 i 位为 1 的区间个数. 那么问题转化为求解异或和第 i 位为 1 的区间个数. 记 c[i, j] 表示 第偶/奇(i=0/1)个数，前缀异或和为 j 的方案数. 四.代码实现 #include <bits/stdc++.h> using namespace std; typed...

一.题目链接： 矩阵距离 二.题目大意： 给你一个 n × m 的 01 矩阵 A，现求矩阵 B. 三.分析： 每个点 BFS 肯定会 T. 一开始想的是从 （1,1）开始搜，记一下曼哈顿距离，之后二分查找做差，写完之后发现思路根本不对。。。 正解是把每个 1 在一开始加到队列里去，然后 BFS 即可. （wsl） 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include...

一.题目链接： POJ-3322 二.题目大意： 翻砖块：体验 三.分析： 题目不难，把所用东西搞清楚就行了. 这里多写了一个打印路径的，供以后 玩 学习. 四.代码实现： 一.AC 版本 #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include <...

一.题目链接： 送礼物 二.题目大意： 大容量背包问题. 三.分析： 直接搜会 T 掉，那么就双向搜索. 先搜一半，把答案记录下来，再搜后一半，二分查找即可. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include <cstdio&g...

一.题目链接： POJ-2248 二.题目大意： 序列 x 有如下性质： ① x[1] = 1 ② x[m] = n ③ x[1] < x[2] < ... < x[m - 1] < x[m] ④ 对于每个 k （2 ≤ k ≤ m），都存在 两个整数 i，j （1 ≤ i，j ≤ k - 1），使得 x[k] = x[i] + x[j]. 题目给出 n，要求构造出序列 x. 三.分析： 迭代加深裸题. 对当前的x[cur] 枚举前面的 i 和 j 即可. 剪枝： ① 优化搜索顺序： 从大到小枚举 i，j，使得序列中的数尽快逼近 n. ② ...

一.题目链接： 生日礼物 二.题目大意： 目标为做一个体积为 πn 层数为 m 的蛋糕. 并使得蛋糕从上到下，半径与高度均递增. 现往蛋糕上抹奶油（覆盖蛋糕表面，最底层的底面除外） 为了使花费最小，找出一种制作蛋糕的方法，使得奶油的覆盖面积最小. 输出奶油的最小覆盖面积 / π. 三.分析： 将蛋糕的层数从上到下编号为 1,2 ... m，记答案为 ans. 搜索时所需的状态有 当前的层数 i，当前的侧面积 s，当前的体积 πv. 易得：蛋糕的侧面积 == 蛋糕各层圆柱的侧面积 + 最底层圆柱的底面积. 由于层之间的半径...