文章目录
D-前缀和思想+dfsF-贪心GH-双指针+dp题意思路代码I-追及问题+裴蜀定理J-可持久化线段树K-前缀和+积分的定义题意思路参考链接传送门
本文CSDN
本文juejin
难度：G < F < K < D < I < H < J < M。
作者：hans774882968以及hans774882968
D-前缀和思想+dfs
题意：直接看题干，易懂。
去年比赛的时候觉得这是个规律题，发现可以用n小的答案生成n大的答案，写了2小时以上，200多行代码，却wa了。因此不想再尝试这种令人伤悲的做法。
dfs做法：首先，统计区间内1的个数，很容易联想到前缀和。因为只要求s[r]和s[l-1]奇偶性不同，所以前缀和可以改成前缀异或，s[0] = 0。设前缀异或数组有x个0（则有n+1-x个1），试求下标对个数表达式。只考虑枚举左或右端点很难得到式子，因此考虑一个点既可以当左也可以当右。对于i = 0，只能作为l-1，贡献为1的个数；对于i = n，只能作为r，贡献为num[!s[n]]；对于其他i，左侧的num[!s[i]]使它作为r，右侧的num[!s[i]]使它作为l-1，因此贡献仍为num[!s[i]]。综上，总贡献2*num[0]*num[1]，但每个区间都被统计2次，所以除以2，下标对个数为x*(n+1-x)。求这个函数的最值是初中数学，n为奇数时，x = (n+1)/2 = n/2 + 1；否则x = up(n+1,2) = n/2 + 1或(n+1)/2，up表示向上取整。
于是我们得到一条关键性质：前缀异或数组的0和1的个数都不超过n/2 + 1。结合题目要求的，字典序最小的100个解，于是可以考虑dfs，用关键性质剪枝。
坑：
需要小心MLE，建议找到100个答案后直接调exit(0)退出，而不是return，占用更多栈空间。另外字符串要使用外部空间，而非传参。
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> pii;#define rep(i,a,b) for(int i = (a);i <= (b);++i)#define re_(i,a,b) for(int i = (a);i < (b);++i)#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e5 + 5;int n;char s[N];void dbg() {puts ("");}template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);}template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;}void read() {}template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);}void dfs (int cur, int sum, int v0, int v1, int &out_n) {if (v0 > n / 2 + 1 || v1 > n / 2 + 1) return;if (cur >= n) {puts (s);if ( (++out_n) >= 100) exit (0);return;}s[cur] = 'b';dfs (cur + 1, sum, v0 + !sum, v1 + sum, out_n);s[cur] = 'r';dfs (cur + 1, !sum, v0 + sum, v1 + !sum, out_n);}int main() {read (n);printf ("%lld\n", n % 2 ? 1LL * (n + 1) * (n / 2 + 1) / 2 : (1LL * n * (n + 2) / 4) );int out_n = 0;dfs (0, 0, 1, 0, out_n);return 0;}
F-贪心
题意：把数组划分为若干个区间，使得区间内部升序排序后，整个数组是升序的。问最多能划分多少个区间。
整体思路为当前数组与升序排序的数组进行比对，并贪心。需要注意，可能有多个相同的数，贪心原则就按输入顺序排序，这样就确定每个下标的数的期望排名rk数组。对于新区间的开头i，有rk[i] >= i，就向右找到最小的点j，使得max(rk[i~j]) <= j，这样这个新区间才满足要求。
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> pii;#define rep(i,a,b) for(int i = (a);i <= (b);++i)#define re_(i,a,b) for(int i = (a);i < (b);++i)#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e6 + 5;int n, a[N];void dbg() {puts ("");}template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);}template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;}void read() {}template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);}int main() {read (n);vector<pii> b (n + 1);vector<int> rk (n + 1);rep (i, 1, n) read (a[i]), b[i].first = a[i], b[i].second = i;sort (b.begin() + 1, b.end() );rep (i, 1, n) rk[b[i].second] = i;int ans = 0;for (int u = rk[1], i = 1;;) {while (i < u) {++i;u = max (u, rk[i]);}++ans;if (i >= n) break;u = rk[++i];}printf ("%d\n", ans);return 0;}
G
签到，代码略。
H-双指针+dp
题意
你需要租借自行车。直接租用一辆自行车的花费为r <= 1e9。现在给你n <= 500种折扣卡：
每种折扣卡的有效期为d天，即第t天购入，t ~ t+d-1天有效。每种折扣卡可以让从购买时刻开始的k个自行车免费。折扣卡价格为c。1 <= d,k,c <= 1e9。
接下来输入m <= 1e5行，每行两个数p和q，表示第p天要租借q个自行车。保证p两两不同。0 <= p <= 1e9, 0 <= q <= 3e5, sum(q) <= 3e5。输出一个整数，表示最小总花费。
思路
3e5 * 500 = 1.5e8，故显然可以先展开出q个p再排序，表示以一个自行车的租借为单位来决策，然后再考虑dp。我首先考虑的是二维dp，即dp[i][j]表示第i次租借使用第j种折扣的最小总花费。但这样即使用上线段树也是n * 3e5 * log(n * 3e5)，过不了。那就考虑一维dp，并在转移方程中体现有效期和有效次数。定义dp[i]表示前i次租借的最小总花费，则dp[sum(q)]为答案（下面设n0 = sum(q)），显然dp[0] = 0。
转移：考虑朴素的转移方程的伪代码：
for i = range(1,n0+1):dp[i] = dp[i-1] + rfor j in range(1,n+1):for k in range(x[j][i],i):dp[i] = min(dp[i],dp[k-1]+c[j])
x[j][i]表示购买的是第j种折扣卡，且满足第i次租借时还有效的最小的租借下标，用代码表示就是i <= x + k[j] - 1 && a[i] <= a[x] + d[j] - 1。dp[k-1]+c[j]表示买卡后，第k次就开始免费。
因为dp定义有单调性，所以第3层循环可以去掉，直接取dp[x[j][i]-1]+c[j]，这样复杂度就对了。
x[j][i]求法：j不变，x[j][i]随i单增。因此可以用双指针。
代码
看着是银牌题，算法其实不难理解，AC代码也不长。不要真的开x[j][i]数组，取址太多，会TLE。只有把求x的过程和dp转移耦合在一起，减少取址，才能过。#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> pii;#define rep(i,a,b) for(int i = (a);i <= (b);++i)#define re_(i,a,b) for(int i = (a);i < (b);++i)#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 3e5 + 5, M = 502;int m, n, r;int a[N], d[M], k[M], c[M], tmp[M];LL dp[N];void dbg() {puts ("");}template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);}template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;}void read() {}template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);}int main() {read (m, n, r);rep (i, 1, m) read (d[i], k[i], c[i]);int n0 = 0;rep (_, 1, n) {int x, y;read (x, y);re_ (i, 0, y) a[++n0] = x;}n = n0;sort (a + 1, a + n + 1);rep (i, 1, m) tmp[i] = 1;rep (i, 1, n) {dp[i] = dp[i - 1] + r;rep (j, 1, m) {int x = tmp[j];while (! (i <= x + k[j] - 1 && a[i] <= a[x] + d[j] - 1) ) ++x;dp[i] = min (dp[i], dp[x - 1] + c[j]);tmp[j] = x;}}printf ("%lld\n", dp[n]);return 0;}
I-追及问题+裴蜀定理
题意：给你一个钟，有H小时，每小时有M分钟。问从0点开始，时钟转完一圈的时间内（即到H*M-1分钟），分钟和时钟的夹角小于等于2*pi*A/(H*M)的分钟有几个。
以分钟为单位，时针和分钟在t ∈ [0, H*M-1]分钟的角度分别为2*pi*t/(H*M)和2*pi*t/M。列出所求不等式：|(2*pi*t/(H*M) % (2*pi)) - (2*pi*t/M % (2*pi))| <= 2*pi*A/(H*M)。因为只关注整数分钟，2*pi是无关紧要的，两边同时乘H*M/(2*pi)得：
|t % (H*M) - (H*t) % (H*M)| <= A
故：-A <= (t*(H-1)) % (H*M) <= A，即：
(t*(H-1)) % (H*M) <= A(t*(H-1)) % (H*M) >= H*M-A，两边同时加上H*M同余而得。
约定down(x,y)为x向下整除y。如down(-2,3) = -1。这里用到的性质：
down(x+k*y,y) = down(x,y) + k，k ∈ Z。
两边同时除以g = gcd(H-1,H*M)，构造互质性，1式变成：(t*(H-1)/g) % (H*M/g) <= down(A,g)（3）。
由裴蜀定理，当gcd(x,m) = 1，t*x = y (mod m)的每个y都能解出同余意义下唯一的t。所以3式的解数为down(A,g)+1。2式转化为小于等于H*M-A-1，再两边同除以g的解数为down(H*M-A-1,g)+1。
注意除以g后的一个解对应原式的g个解，因此还要乘g。得1式的解数g*(down(A,g)+1)；3式的解数H*M - g*(down(H*M-A-1,g)+1) = g*(H*M/g - 1 - down(H*M-A-1,g)) = g*(-1-down(-A-1,g))（由向下取整性质1可得）。由向下取整性质1，只需要验证A = 0~g-1的情况下，该式子都等于g*down(A,g)（即可推广到任意A了），验证没问题。
最终答案g*(2*down(A,g)+1)。
坑：
当2*A = H*M，1式和2式算重了A = H*M/2的部分，所以需要特判。此时每个整数分钟都满足。x负数y正数的时候，别忘了cpp的除法是逼近0的，不是向下取整。
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> pii;#define rep(i,a,b) for(int i = (a);i <= (b);++i)#define re_(i,a,b) for(int i = (a);i < (b);++i)#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e6 + 5;LL h, m, a;void dbg() {puts ("");}template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);}template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;}void read() {}template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);}LL down (LL x, LL y) {if (x >= 0) return x / y;return x / y - (x % y < 0);}int main() {read (h, m, a);if (2 * a == h * m) printf ("%lld\n", h * m);else {LL g = __gcd (h - 1, h * m);LL v1 = a / g + 1, v2 = -1 - down (-a - 1, g);printf ("%lld\n", g * (v1 + v2) );}return 0;}
J-可持久化线段树
网上缺乏这题的题解，为了方便被搜到，独立写了一篇。传送门：CSDN、juejin
K-前缀和+积分的定义
题意
机器学习中，真正例TP、真负例TN、假正例FP、假负例FN，则TPR = TP / (TP + FN), FPR = FP / (FP + TN)。FPR为自变量，TPR为因变量的曲线叫做ROC曲线，其定积分为AUC，定义式如下：
AUC=∫01maxθ∈R{TPR(θ)∣FPR(θ)<=r}drAUC=\int_0^1 max_{\theta \in R} \{TPR(\theta)\ |\ FPR(\theta)<=r\}\ dr AUC=∫01maxθ∈R{TPR(θ)∣FPR(θ)<=r}dr
给你一个分类器对n个样本的分类结果，+ / -表示样本实际为正负例，s表示置信度分数。你选择一个阈值theta，大于等于该阈值即预测为正例，否则预测为负例，于是每个theta对应一个TPR和FPR。求AUC。
思路
显然theta只在置信度分数的点附近变化才对TPR和FPR有影响。因此排序+枚举每个样本，s[i]表示取下标大于等于i的为预测正例，小于i的为预测负例。i变化时需要快速得到左侧和右侧的'+'、'-'数目，可以维护差值或前缀和，这里我们选择了不容易写错的前缀和。
观察int tp = sump[n] - sump[i - 1], fn = sump[i - 1], fp = sumn[n] - sumn[i - 1], tn = sumn[i - 1]，可得结论：i加1，tpr和fpr中至多只有一个变化。因此算积分的时候直接算每个矩形的面积和即可。
坑：
注意AUC的积分式要取最大TPR(theta)，即最大化TP最小化FN，所以升序排序分数相同时，要把'+'排'-'的左边。
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> pii;#define rep(i,a,b) for(int i = (a);i <= (b);++i)#define re_(i,a,b) for(int i = (a);i < (b);++i)#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e6 + 5;int n, sump[N], sumn[N];void dbg() {puts ("");}template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);}template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;}void read() {}template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);}struct Node {bool po;int s;} a[N];bool cmp (Node &x, Node &y) {if (x.s ^ y.s) return x.s < y.s;return x.po > y.po;}int main() {read (n);rep (i, 1, n) {char po[5];scanf ("%s%d", po, &a[i].s);a[i].po = (po[0] == '+');}sort (a + 1, a + n + 1, cmp);rep (i, 1, n) {sump[i] = sump[i - 1] + a[i].po;sumn[i] = sumn[i - 1] + (!a[i].po);}double ans = 0, l_fpr = -1;rep (i, 1, n + 1) {int tp = sump[n] - sump[i - 1], fn = sump[i - 1], fp = sumn[n] - sumn[i - 1], tn = sumn[i - 1];double tpr = 1.0 * tp / (tp + fn), fpr = 1.0 * fp / (fp + tn);if (l_fpr != -1) {ans += 1.0 * tpr * (l_fpr - fpr);}l_fpr = fpr;}printf ("%.10lf\n", ans);return 0;}
