致歉 因为出题人的疏忽，T6 造了 n 不是 4 的倍数的数据。同时 T8 因为多次重造数据，被暴力碾过去了。真抱歉 qaq 。 T1 回文括号序列计数 记串为 ，由于回文所以 ，由于括号序列所以 。 因此不存在长度 的串。当 时存在一个空串。 T2 系数 做法一 ，求的即为 。 这个就是个简单的组合数，易知是 。 做法二 赛时也有部分人打表来观察解出此题，这里给出一种比较简洁的打表观察做法： 将前一些数打印出来： int dp[105][105]; int main() { dp[0][0] = 1; for (int i = 1; i <= 30; i++...

T1 奇怪的计算器 按顺序扫过去，把每个数抠出来，然后先把连续的异或操作算出来，然后从左到右加减即可。 时间复杂度 T2 最小的指数 暴力枚举所有的 ，算出指数min，记除去这些质因子剩下的数为 。 对于 ，指数一定 。 若指数min ，显然 ，只需检验 即可。 若指数min ，显然 ，只需检验 即可。 若指数min ，显然 或 ，所以依旧只需检验 即可，注意需要满足 不是完全平方数，否则这个其实是指数min=4 。 时间复杂度 ，常数 左右。 参考代码 T3 排列 先考虑如何处理长为 ，逆序对数 的排列数。 用 表示长为 逆序对数为 的排列数，...

如题。

牛客练习赛67题解 出题人： T1 牛牛爱字符串 Solution 直接从头到尾扫一遍，抠出每一段连续的数字块。 如果这个数字块开头是零，则需要去除前导0，但注意别把数字0给去了。 注意一下首和尾的细节，即可通过本题。 Code #include <bits/stdc++.h> using namespace std; const int N = 100005; char s[N]; int n; int main() { while (gets(s + 1)) { n = strlen(s + 1); int flag = 0; for (int ...

牛客练习赛67题解 出题人： T1 牛牛爱字符串 Solution 直接从头到尾扫一遍，抠出每一段连续的数字块。 如果这个数字块开头是零，则需要去除前导0，但注意别把数字0给去了。 注意一下首和尾的细节，即可通过本题。 Code #include <bits/stdc++.h> using namespace std; const int N = 100005; char s[N]; int n; int main() { while (gets(s + 1)) { n = strlen(s + 1); int flag = 0; for (int ...

Description 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。 Solution 我们假设选定的两个区间，靠左的为左区间，靠右的为右区间。注意到异或的性质：， 于是我们只需要左区间异或值等于右区间异或值即可。我们固定右区间的左端点，记为，那么我们要做的，就是记录所有左区间的区间异或值，用一个桶存储。显然，这个桶可以动态存储，并且每次扫一遍右区间的右端点进行计数即可。复杂度 代码 // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include &l...

换根dp 一般来说，我们做题的树都是默认 为根的。但是有些题目需要计算以每个节点为根时的内容。朴素的暴力：以每个点 作为 暴力dfs下去，复杂度；正确的做法：换根dp，复杂度。 执行步骤 第一次扫描，先默认 ，跑一遍 ； 第二次扫描，从 开始，每次从 到 节点时，计算根从 转移到 时的贡献变化。很显然，换根dp是在两个中完成的，下面我们介绍一下如何运用它。 例题1 Accumulation Degree 题目链接：South Central China 2008 Accumulation Degree Description 给你一颗有 个节点的树，每一条边连接 和 ...

树 题目链接：牛客13611 树 Description 给定一颗有 个节点的树，有 种颜料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对 ，满足到的路径上所有点的颜色相同（包括和）。统计方案数，答案对取模。数据范围 Solution 这是一道结论题。如果直接做，显然不好做，我们考虑切换视角。在树上求点对路径，其实可以通过序转换到链上。我们先跑一次，记下每个点的 。我们会发现，如果当前遍历到了点 ，那么 的祖先们肯定都已经遍历过了，它的兄弟们有部分被遍历过。我们规定和的排列顺序是按照排列的，那么我们枚举的时候，已经上色了。如果想要遍历到，那么无论如何都要经过它的父...

Subarray Cuts 题目链接：CF513E2 Subarray Cuts Description 给定一个长度为 的数组，你需要从中按顺序选出个不重复、不相交的子串，定义 为第 个子串的和，你需要最大化。数据范围 Solution 我们考虑拆开绝对值，对于一段单调递增/递减的子串，结果只与其中的峰值和谷值有关，中间的数会因为或而连锁抵消掉。于是，我们定义表示在第个数时，总共选了个子串时的状态。其中，第三维的意义依次为：当第三维为时，表示当前子串位于谷值；当第三维为时，表示当前子串在谷值到峰值之间；当第三维为时，表示当前子串位于峰值；当第三维为时，表示当前子串在峰值到谷值之间。注...

旗鼓相当的对手 题目链接：牛客 旗鼓相当的对手 Description 给定一个 个点的树，每个节点有点权。如果 为 和 的，并且 和 不等于 且树上距离为 ，那么点 的答案就会加上 。求所有点的答案。数据范围。 Solution 长链剖分板子。 表示子树深度为的节点数 表示子树深度为的节点权值和 Code // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define ...

题目链接：二分图染色 Description 给定一个完全二分图，图的左右两边顶点数目相同。每条边我们都要染成红、绿、蓝中的一种。要求满足任意两条红边不共享端点，任意两条蓝边不共享端点。求出所有满足条件的染色方案数，答案对取模。注：表示二分图其中一边的点数目。数据范围 Solution 我们切换思路，先默认所有的边都是绿色的，这些边的端点没有任何限制。接下来，我们尝试将部分边给染成红、蓝色。我们定义 表示二分图其中一边有个点，并且边只有绿色和红色时的答案。显然，边界条件为 。我们考虑如何递推这个 序列， 注意到 从 转移过来会新增两个点。我们分五种情况讨论： 1 这两个点出度为，那...

Steps to One 题目链接：CF1139D Steps to One Description 给定一个数列，每次随机选一个 到 之间的数加到数列的末尾，数列中的所有数的 时停止，求期望长度。答案对取模。数据范围 。 Solution 考虑概率dp我们定义表示当前所有的数 时，还需要加入的数才能使得的期望个数。 显然，并且有 解释一下，是因为第一个数没有考虑在内，所以需要枚举第一个数是几，显然~都有的概率。 转移式： 这样复杂度是的，过不了此题。 我们考虑优化转移，首先想到的是枚举： 我们考虑优化上面这一团式子。 令，将提前，得到原式$$ 带回原式，得到$$ 我们令，如果我们计算...

https://ac.nowcoder.com/acm/problem/51180 Description 给你一颗有 个节点的树，每一条边连接 和 ，流量为 ，你需要找出一个点作为 ，并最大化从该点出发到所有叶子节点的流量最大值。多组数据。（PS：题意读不懂的可以结合题目中的图理解，类似网络流的流法）数据范围 ，并且 时间限制 Solution 我们先默认这棵树以 为根，跑一次 。定义 表示以 为根的子树中流量最大值。那么， 节点从儿子 得到的流量为：1.若为叶子节点，那么（可以直接流过来）；2.若为非叶子节点，那么（和相连的边有流量限制）。这样，我们得到了以 为根时的答案...