分析 我们可以利用递归求解。 我们枚举每个串中心，对于一个区间，如果它包含了串中心，我们就把它分解成两个串，另一个区间也这样做，然后就是最多种情况。 如果一个区间包含了另一个区间，直接返回小的那个区间的长度。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int maxn = 2e5+7...

写在前面 没给出数据范围，差评。 补充一下数据范围： 「数据规模」对于50%的数据， N≤10000；对于80%的数据， N≤800000；对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。 分析 考虑尺取法，说白了就是双指针。 先对 x 排个序，然后利用一个数组记录当前区间每个颜色的出现次数，然后我们不断推进左端点，当左右端点区间颜色种类达到 k 的时候，再推进右端点，一直推进到左右端点区间颜色种类数恰好不是 k 个，一直重复这个过程就好了。 #include <bits/stdc++.h> using namespace std; #def...

A Clam and Fish 贪心，有鱼的时候肯定是直接抓鱼，没鱼的时候，制作诱饵抓鱼。 考虑 1 和 0 出现的次数，0 出现的次数的有效值会小于等于 1 出现的次数， 最后再把多余的 1 ，分一半去钓鱼。 code B Classical String Problem 只需要维护好第一个字符所在的位置就行了，询问的时候加上这个位置取个模就行了。 code C Operation Love 判断是左手还是右手，因为长度是固定不变的，所以我们可以找到6 , 9 , 8这三条边，然后如果是左手的话，6 这条边沿 9 这条边绕 90° 之后是是在 9 这条边上面的。 code E Two Mat...

分析 二分图匹配，对于第 i 个装备两个属性 x 和 y ，建立两条边，x -> i ，y -> i 。 然后利用匈牙利算法，从 1 开始往后匹配，当匹配不成功的时候就结束。 正常的匈牙利算法可能会因为要 memset 很多次可能超时，虽然没有超时，可能数据水或者我理解有问题之类的。 然后可以利用时间戳来避免 memset 的操作。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #de...

All with Pairs 求 其中表示的前缀可以匹配的后缀的最长长度。 考虑，先对后缀，求出某个值的后缀有多少个，用存。 然后对每个字符串求一个前缀，计算匹配的个数，然后乘以长度的平方。 但是有一个问题，有一些部分是重复计算的。 比如 我们算的时候会把的贡献也算进去，所以要减去的贡献。 具体来说就是求一个数组，把重复计算的部分删去。 code Boundary 因为圆要固定过原点，然后枚举剩下两个点，利用三个点确定圆心，用记录圆心坐标。 code Cover the Tree 这题数据好像有点水，不少水做法都可以过。 我们考虑 u 的子树，如果 u 的子树有两个以上...

题意 用 的骨牌去填充 的矩阵，问有几种方法。 分析 手算一下前五项，可以得到这么一个序列：1,5，11，36，95 设 表示拼完前 i 列的方案数。这时考虑 OEIS 。可以得到递推式： 然后利用矩阵快速幂就可以解决了。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define int long long struct mat { int a[4][4]; mat(){mem(a,0);} }; mat mul(mat a,ma...

题意 有30000个岛屿，某些岛屿上有一些宝石，第一次跳到了d号岛上，每次跳跃的距离与上一次跳跃的距离之差不超过1，问你最多可以收集多少宝石。 分析 我们可以定义 dp[i][j] 表示为跳到第 i 个岛屿，且上一次跳跃距离为 j ，那么显然有 但是这样做，显然时间和空间都不够。 我们可以发现，第一步和最后一步的差值不会超过 250 ，因为1+2+3+...+250 > 30000 那么我们可以定义 dp[i][j] 表示跳到第 i 个岛屿，且与第一次跳跃距离的差值为 j-250 。 #include <bits/stdc++.h> using namespace std;...

题意 一个矩阵，每次可以消除一行或者一列，问最大可以消除的和是多少。 分析 由于矩阵比较小，所以我们可以先枚举消去了哪些行，之后贪心的消去剩下的列（也就是选择列的和更大的），可以利用 dfs 实现。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int maxn = 20; const ...

分析 显然横向通道和纵向通道的放置是相互独立的，所以我们可以只考虑放一种通道应该怎么放， 贪心的放，优先放更多对的地方，可以拆分的对数会更多。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int maxn = 2110; const int M = 1e9+7; int n,m,k,l...

分析 简简单单最短路。 只是要记录一下走了几天罢了，定义为从 1 到 i 走了 j 天的行程花费和欠债人挥霍的钱的最小总和。 。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> const int inf = 0x3f3f3f3f; const int maxn = 1110; const int M = 1e9+7; int n,m,k; int a[maxn],dp[maxn][20]; ...

题意 给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。 分析 我们定义表示为i的子树的所有联通块大小不超过k，并且i所在联通块大小为j的方案数。 对于每条边，假设为 u —— v ，我们都有两种选择，删与不删，如果删去的话，u的联通块大小不会变，如果不删的话，u的联通块大小就会变成两个联通块大小之和。 树形dp+背包 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(...

A 小K的疑惑 显然我们选的三个点必须是两两之间的距离之差是偶数，我们选定一个参考点（也就是根），求出其他点到这个点的距离，然后距离为偶数的为一组，奇数的为一组，答案就是偶数的个数的三次方加上奇数的个数的三次方（可以重复选） #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int m...

首先假设我们不考虑 u 和 v 两点的缆车，那么 x 和 y 之间的路程就是 x 和 y 的深度减去他们的 lca 的深度。 接下来我们考虑使用缆车，无非也就两种情况： x -> u -> v -> y x -> v -> u -> y 我们对上面三种情况取一个 min 就行了。 加快读的话可以跑到 600 ms #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int>...

做完今天的N1，然后发现这不是一样的题目吗？？？ 题意 我们每天可以最多购买m个糖果，连续买 k 个需要额外支付 。保证每天吃一个糖，求买n个糖果的最少代价。 分析 我们定义dp[i][j]，表示前i天买了j颗糖的代价。 我们对 m 颗糖可以贪心一下，一定是买更便宜的糖。 然后枚举今天买几颗即可。 然后为了保证每天都有糖吃，第 i 天从 dp[i-1][i-1] 开始转移就行了。 具体看代码实现。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define...