牜牜练习赛129 C-E 题解

题解发布于 CSND 😋 奉上 C++ 代码 #include <bits/stdc++.h> using i64 = int64_t; using u64 = uint64_t; using f64 = double_t; using i128 = __int128_t; template<class T> constexpr T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; } template<int P&g...

这里有几组数据 test #1: 58 5813 good: no 187 bad: no 186  test #2: 79 8569 good: no 227 bad: no 226  test #3: 69 9828 good: no 243 bad: no 242  我用的产生 good 输出的代码是下面这份，也就是相当于把一对情侣扩张成 2 x 3 放置 #include <bits/stdc++.h> using i64 = int64_t; using u64 = uint64_t; using f64 = double_t; using i128 = __int128...

CSDN版本 把 sum 初始化写错了找了恁久错。。。 Solution 把题中  的定义改为 ，即令 ，如下式所示，其中 ，表示  的前缀和  再令 ，化简得  设  表示将前  个数分为  段的最小值。 考虑其转移  根据斜率优化 ，我们将纯变量放到左边称为 ，将带有“临时常量”系数的放到右边称为 ，最终得到（这里默认是依赖于上一维，所以省略  和 ）  上式中，有如下对应关系  对于  这条直线，我们最终要的就是截距  最小，而且这里随着  增加， 严格增加，所以维护一个关于  点对的下凸包即可。 对于 ，从下往上逼近凸包的直线斜率为 ，当这条直线第一次碰到凸包上的点，截距就是最小的。 ...

由于牛牛的 markdown 有点小问题，所以发在 CSDN 了。

CSDN 版本 A. 广告位招租中 Solution 首先数组内一定只要留下  的 ，然后开一个数组  记录一下  每个位置有多少数。 考虑枚举最大公约数 ，接着我们只要枚举  的倍数即可。对于 ， 是数组  中出现过的，我们要把这些  取 ，看最终是否是 ，如果是说明这些数的  为 ，否则是  的倍数。 这样的总时间复杂度是 。 C++ Code #include <bits/stdc++.h> using i64 = int64_t; using u64 = uint64_t; using f64 = double_t; using i128 = __int128_t; int...

题很显然可以打表，打表代码如下 #include <bits/stdc++.h> using i64 = int64_t; using u64 = uint64_t; using f64 = double_t; using i128 = __int128_t; void solve() { int n, k; std::cin >> n >> k; std::vector<int> sg(k + 1, -1); sg[k] = 0; auto SG = [&](auto self, int n) -> int { if (~sg[n...

突然做到这题，心血来潮写个题解。 首先把题目条件放宽，也就是允许  和  是非法括号序列，例如 )))((())) 和 )))。 然后考虑 ，设  表示是否存在一种方案，使得  的前  个字符通过删除一些 () 和  的前  个字符完全相同。   若   ，那么这个最后的字符可以不用考虑，即   。   若 ，考虑删除以  结尾的一个最短合法括号序列，得到下标 ，那么   。但是删除有可能非法，接下来考虑什么情况是合法的。由于合法括号序列反着看也是合法的（左右括号的地位 交换 一下），所以可以从  开始往左统计 右括号数量与左括号数量之差，记为 ，一旦  就退出，且只有  才更新状态。   关...

B 题公式为啥是下面这个呀（n⩾3n \geqslant 3n⩾3 的时候） ans=∑i=1n−2(i+2)×Cni×Cn−3i−1ans = \sum\limits_{i = 1}^{n - 2}{(i + 2) \times C_n^i \times C_{n - 3}^{i - 1}}ans=i=1∑n−2​(i+2)×Cni​×Cn−3i−1​ 有无大跌帮忙推推（悲）

，要是 了注意一下最长上升子序列也是可以修改的，只要是没有长度到 的都可以修改一次让这个上升子序列变得更长 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define endl '\n' using namespace std; typedef long long LL; const int N = 100010, INF = 0x3f3f3f3f; int n; int w[N]; int l[N], r[N]; int main()...