欢迎访问本菜鸡的独立博客：Codecho
比赛名称
Educational Codeforces Round 61 (Rated for Div. 2)
比赛链接
/contest/1132
比赛情况
解题数：2 / 7 2/7 2/7
补题数：6 / 7 6/7 6/7
排名：1289 1289 1289
比赛总结
A题签到题，6min1A；
B题按照题意用前缀和计算答案，一开始没太读懂题意，最后17min1A，为什么不能控制在10min以内？？
C题又是早已有了心理阴影的的区间覆盖问题，赛后补完；
D题二分答案，判断正确性的思路没想好，赛后补完。
E题是大范围贪心，小范围背包dp，赛后补完。
F题是简单的区间dp，而且自己几个月前写过一模一样的代码，交了不同的题，赛后补完。
1132A - Regular Bracket Sequence（签到题）
题意
给你四种类型的一定数量的字符串：
( 1 ) (1) (1) c n t 1 cnt_1 cnt1 个((；
( 2 ) (2) (2) c n t 2 cnt_2 cnt2 个()；
( 3 ) (3) (3) c n t 3 cnt_3 cnt3 个)(；
( 4 ) (4) (4) c n t 4 cnt_4 cnt4 个))。
问这些字符串按照某种顺序排列，能否构成合法的括号序列（即满足左括号和右括号两两匹配）。
解题思路
显然()对答案没有任何影响。
若存在)(，则无论有多少个，都可以直接前后连接，只需配一个((在前和一个))在后即可。
而((和))显然需要一一对应，因此数量必须相同。
所以，我们的判断逻辑为：
若c n t 3 > 0 cnt_3>0 cnt3>0，则必须保证c n t 1 = c n t 4 cnt_1=cnt_4 cnt1=cnt4并且c n t 1 > 0 cnt_1>0 cnt1>0；
否则，也必须保证c n t 1 = c n t 4 cnt_1=cnt_4 cnt1=cnt4。
c n t 2 cnt_2 cnt2 的值任意。
除此之外的情况，都是不合法。
时间复杂度：O ( 1 ) O(1) O(1)。
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 1e5+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll cnt[10];int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);for(int i = 1; i <= 4; i++) scanf("%I64d", &cnt[i]);if(cnt[1] != cnt[4] || ((cnt[1] == 0 || cnt[4] == 0) && cnt[3] > 0)) printf("0\n");else printf("1\n");//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
1132B - Discounts（排序+前缀和）
题意
现在有 n n n 种商品，每种商品都有价格a i a_i ai。
你现在有 m m m 个优惠券，第 i i i 种优惠券可以允许你不用支付前 q i q_i qi 贵的商品中最便宜的那个的价格。
问你使用每种优惠券可以产生的最少花费。
解题思路
将商品价格从小到大排序，用前缀和维护商品价格。
之后按照题目要求计算即可。
时间复杂度：O ( n log n + n ) O(n \log n + n) O(nlogn+n)
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 3e5+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll a[maxn], prefix[maxn];int q[maxn];int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n, m;scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%I64d", &a[i]);prefix[i] = prefix[i - 1] + a[i];}sort(a + 1, a + 1 + n);for(int i = 1; i <= n; i++){prefix[i] = prefix[i - 1] + a[i];}scanf("%d", &m);for(int i = 1; i <= m; i++) scanf("%d", &q[i]);for(int i = 1; i <= m; i++){ll answer = prefix[n - q[i]];answer += prefix[n] - prefix[n - q[i] + 1];printf("%I64d\n", answer);}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
1132C - Painting the Fence（枚举+前缀和）
题意
给你长度为 n n n 的一维空间，再给你 q q q 个区间，每个区间覆盖范围[ l i , r i ] [l_i, r_i] [li,ri]。
现在要删掉 2 2 2 个区间，问可以产生的最大的覆盖长度。
解题思路
现在描述的是这道题比较优雅又比较简单的做法，不需要任何分类讨论。
首先，我们需要维护两个前缀和和一个变量的值。
设 p r e f i x [ 0 ] [ i ] prefix[0][i] prefix[0][i] 表示截止到第 i i i 个位置，出现次数为 1 1 1的点的个数；
设 p r e f i x [ 1 ] [ i ] prefix[1][i] prefix[1][i] 表示截止到第 i i i 个位置，出现次数为 2 2 2的点的个数；
设 t o t tot tot 表示在未删除区间的情况下，被覆盖的长度。
之后，暴力枚举所删除的两个区间 i i i 和 j j j，
将两个区间所覆盖的出现次数为 1 1 1 的点全部清除掉，
然后，将两个区间的公共部分所覆盖的出现次数为 2 2 2 的点全部清除掉，再与最终答案取最大值即可。
时间复杂度：O ( n + q 2 ) O(n + q^2) O(n+q2)
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 5e3+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlstruct node{int l, r;} interval[maxn];bool operator < (node a, node b){return a.l < b.l || (a.l == b.l && a.r < b.r);}int prefix[2][maxn], cnt[maxn];int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n, q;scanf("%d%d", &n, &q);for(int i = 1; i <= q; i++){scanf("%d%d", &interval[i].l, &interval[i].r);for(int j = interval[i].l; j <= interval[i].r; j++) cnt[j]++;}int tot = 0;for(int i = 1; i <= n; i++){if(cnt[i] == 1) prefix[0][i] = prefix[0][i - 1] + 1;else prefix[0][i] = prefix[0][i - 1];if(cnt[i] == 2) prefix[1][i] = prefix[1][i - 1] + 1;else prefix[1][i] = prefix[1][i - 1];if(cnt[i])tot++;}int answer = 0;for(int i = 1; i <= q; i++){for(int j = i + 1; j <= q; j++){int la = interval[i].l, ra = interval[i].r;int lb = interval[j].l, rb = interval[j].r;int temp = tot - (prefix[0][rb] - prefix[0][lb - 1]) - (prefix[0][ra] - prefix[0][la - 1]);int l = max(la, lb);int r = min(ra, rb);if(l <= r) temp -= (prefix[1][r] - prefix[1][l - 1]);answer = max(answer, temp);}}printf("%d\n", answer);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
1132D - Stressful Training（二分）
题意
现在有 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n(1 \le n \le 2 \cdot 10^5) n(1≤n≤2⋅105) 个学生，每个学生都有一个笔记本电脑，设其最初剩余a i ( 1 ≤ a i ≤ 1 0 12 ) a_i(1 \le a_i \le 10^{12}) ai(1≤ai≤1012) 的电量，每天耗电量为 b i ( 1 ≤ b i ≤ 1 0 7 ) b_i(1 \le b_i \le 10^7) bi(1≤bi≤107)。
现在要买一个每天能充 x x x 单位电量的充电器，这个充电器每天只能给一台电脑充电。
活动需要进行 k − 1 ( 1 ≤ k ≤ 2 ⋅ 1 0 5 ) k - 1(1 \le k \le 2 \cdot 10^5) k−1(1≤k≤2⋅105) 天，问可以达到所有笔记本使用需求的最小的 x x x。
如果这样的 x x x不存在，输出 − 1 -1 −1；否则输出 x x x 的值。
解题思路
很显然，二分 x x x，之后对 x x x 进行合法性验证。
验证的时候，我们需要维护一个数组 c n t i cnt_i cnti，表示在第 i i i 天需要充电的电脑个数。
之后，我们遍历每个笔记本电脑，计算它需要在哪些天进行充电，统计到 c n t i cnt_i cnti 中。
对于所有的笔记本电脑，我们一共只需统计 k k k(即 ( k − 1 ) + 1 (k-1)+1 (k−1)+1) 次即可。
之后，我们从 1 1 1 到 k − 1 k-1 k−1遍历每一天i i i，如果截止到这一天进行的总充电次数超过了 i i i，表明充电任务已无法完成，直接判不合法，返回false。
如果遍历完之后，未发现不合法的情况，证明合法，返回true。
时间复杂度：O ( ( n + k ) log 1 0 18 ) O((n+k) \log 10^{18}) O((n+k)log1018)
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 2e5+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlint n, k;struct node{ll a, b;} data[maxn];int cnt[maxn];bool check(ll x){memset(cnt, 0, sizeof(cnt));int time = k;for(int i = 1; i <= n; i++){ll temp = data[i].a;if(temp >= 1LL * k * data[i].b) continue;cnt[min((temp / data[i].b) + 1, (ll)k + 1)]++;while(temp < 1LL * k * data[i].b){if(!time) break;time--;temp += x;cnt[min((temp / data[i].b) + 1, (ll)k + 1)]++;}}int tot = 0;for(int i = 1; i <= k; i++){tot += cnt[i];if(tot > i) return false;}return true;}int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);scanf("%d%d", &n, &k);k--;for(int i = 1; i <= n; i++) scanf("%I64d", &data[i].a);for(int i = 1; i <= n; i++) scanf("%I64d", &data[i].b);ll answer = 0x3f3f3f3f3f3f3f3f;ll left = 0, right = 0x3f3f3f3f3f3f3f3f;while(left <= right){ll mid = (left + right) / 2;bool sgn = check(mid);if(sgn){answer = min(answer, mid);right = mid - 1;}else left = mid + 1;}if(answer == 0x3f3f3f3f3f3f3f3f) printf("-1\n");else printf("%I64d\n", answer);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
1132E - Knapsack（贪心+背包）
题意
给你一个容量为 W ( 0 ≤ W ≤ 1 0 18 ) W(0 \le W \le 10^{18}) W(0≤W≤1018) 的背包，然后给你若干件物品，每件物品的重量为[ 1 , 8 ] [1, 8] [1,8] 之间的整数。
设重量为 i i i 的物品的数量为 c n t i cnt_i cnti，求在不超过容量的情况下，书包最多能承载多少重量的物品。
解题思路
如果这道题直接按照多重背包问题来做的话，一定会TLE，因为数据范围很大很大~
设所有物品的总重量为 s u m sum sum，若 t o t ≤ W tot \le W tot≤W，则答案就是 s u m sum sum，无需考虑下面的过程。
我们可以考虑大范围用贪心来求解一个接近正确答案的答案，之后剩下的小范围直接当成背包问题来求解。
因为物品的重量只能在 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] [1,2,3,4,5,6,7,8] [1,2,3,4,5,6,7,8] 的范围内取值，而
lcm [ 1,2,3,4,5,6,7, 8 ] = 840 \text{lcm}\left[ \text{1,2,3,4,5,6,7,}8 \right] =840 lcm[1,2,3,4,5,6,7,8]=840
（即它是能整除所有可能出现的单个物品重量的最小的数），因此我们可以先假设需要进行背包问题求解的总重量范围为 840 840 840。
因此，贪心求解的最大总重量范围
t o t a l = max { 0, W − 840 } total=\max \left\{ \text{0,}W-840 \right\} total=max{0,W−840}
（因为有可能 W W W 本身就很小，这时直接进行背包问题求解就行）。
之后，我们计算每种物品i i i 在最后的背包问题中可能出现的最大数量l e f t i left_i lefti，
对于每个i i i，将 c n t i − = l e f t i cnt_i -= left_i cnti−=lefti，从而将新的 c n t i cnt_i cnti 用于贪心求解中。
设当前已经计算出的临时答案为 a n s w e r answer answer，最初a n s w e r = 0 answer=0 answer=0
从 1 1 1 到 8 8 8枚举重量（从小到大的原因是小的物品占地方少，可以尽可能多放），对于重量为 i i i 的物品，最多可以安排
a m o u n t i = min { c n t i , ⌊ t o t a l − a n s w e r i ⌋ } amount_i = \min \left\{ cnt_i,\lfloor \frac{total-answer}{i} \rfloor \right\} amounti=min{cnti,⌊itotal−answer⌋}
个，因此将 a n s w e r answer answer加上a m o u n t i ⋅ i amount_i \cdot i amounti⋅i。
由于c n t i cnt_i cnti 及向下取整的限制，我们不可能完美无缺地凑出
t o t a l = max { 0, W − 840 } total=\max \left\{ \text{0,}W-840 \right\} total=max{0,W−840}
来，因此实际需要进行背包问题求解的总重量范围会大于 840 840 840。
正确的背包范围是 W − a n s w e r W-answer W−answer，如果按最坏情况考虑，就是
∑ i = 1 8 ⌊ 840 i ⌋ = ∑ i = 1 8 840 i \sum_{i=1}^8{\lfloor \frac{840}{i} \rfloor}=\sum_{i=1}^8{\frac{840}{i}} i=1∑8⌊i840⌋=i=1∑8i840
我们索性将背包范围设置为 840 ⋅ 8 840 \cdot 8 840⋅8，这样复杂度并不会超（往多了设置，并不会影响答案的正确性）。
之后，按照传统的多重背包（可以认为将多个物品拆成 0 / 1 0/1 0/1 背包的单个物品的集合）的思路，进行**“重量可达性”求解**即可。
设 d p [ i ] [ j ] dp[i][j] dp[i][j] 为考虑重量范围为 [ 1 , i ] [1, i] [1,i] 的物品，总重量 j j j 是否可以凑成。
初始状态为 d p [ 0 ] [ 0 ] dp[0][0] dp[0][0]，转移方程可以参考下面的代码。
最后，从 0 0 0 到 W − a n s w e r W-answer W−answer 枚举最后的背包过程可能出现到的总重量i i i，若 i i i可达，则用其更新答案。
时间复杂度： O ( 8 ⋅ ( 840 ⋅ 8 ) ⋅ 840 ) O(8 \cdot (840 \cdot 8) \cdot 840) O(8⋅(840⋅8)⋅840)
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 1e5+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll cnt[10], lef[10];bool dp[10][100005];int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);ll W;scanf("%I64d", &W);ll sum = 0;for(int i = 1; i <= 8; i++){scanf("%I64d", &cnt[i]);sum += 1LL * i * cnt[i];}W = min(W, sum);for(int i = 1; i <= 8; i++){lef[i] = min(cnt[i], 840LL / i);cnt[i] -= lef[i];}//greedyll answer = 0;ll total = max(0LL, W - 840LL);for(int i = 1; i <= 8; i++){ll amount = min(cnt[i], (total - answer) / (1LL * i));answer += 1LL * amount * i;}memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= 8; i++){for(int j = 0; j <= 840 * 8; j++){for(int k = 0; k <= lef[i] && j - i * k >= 0; k++)dp[i][j] |= dp[i - 1][j - i * k];}}//dbg(W - answer);ll maxvalue = 0;for(ll i = 0; i <= W - answer; i++){if(dp[8][i]) maxvalue = max(maxvalue, answer + i);}printf("%lld\n", maxvalue);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
1132F - Clear the String（区间dp）
题意
给你一个长度为 n ( 1 ≤ n ≤ 500 ) n(1 \le n \le 500) n(1≤n≤500) 的字符串 s s s，你需要每次选择一个连续的且只含有同一种字母的子串删掉。
问最少操作几次，可以将整个字符串全部删除。
解题思路
设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示删掉区间 [ i , j ] [i, j] [i,j] 所需要的最小代价。
则转移方程为
d p [ i ] [ j ] = min i ≤ k < j { d p [ i ] [ k ] + d p [ k + 1 ] [ j ] − [ s k = s k + 1    ∣ ∣ s i = s j ] } dp\left[ i \right] \left[ j \right] =\min_{i\le k<j} \left\{ dp\left[ i \right] \left[ k \right] +dp\left[ k+1 \right] \left[ j \right] -\left[ s_k=s_{k+1}\,\,|| s_i=s_j \right] \right\} dp[i][j]=i≤k<jmin{dp[i][k]+dp[k+1][j]−[sk=sk+1∣∣si=sj]}
最终的答案为 d p [ 1 ] [ n ] dp[1][n] dp[1][n]。
时间复杂度：O ( n 3 ) O(n^3) O(n3)
代码
/*Written by NitrogensDesire for getting accepted!!*/#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#include <map>#include <bitset>#include <stack>#include <set>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef pair <int, int> pii;typedef pair <ll, ll> pll;typedef pair <ll, int> pli;typedef pair <db, db> pdd;const int maxn = 5e2+5;const int Mod = 1000000007;const int INF = 0x3f3f3f3f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const double e = exp(1);const db PI = acos(-1);const db ERR = 1e-10;#define Se second#define Fi first#define pb push_back#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlchar s[maxn];int dp[maxn][maxn];int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n;scanf("%d", &n);scanf("%s", s + 1);memset(dp, 0x3f, sizeof(dp));for(int i = 1; i <= n; i++) dp[i][i] = 1;for(int i = 1; i <= n; i++){for(int u = 1; u < n; u++){int v = u + i - 1;if(v > n) break;for(int k = u; k < v; k++){dp[u][v] = min(dp[u][v], dp[u][k] + dp[k + 1][v] - (s[k] == s[k + 1]||s[u] == s[v]));//dbg3(u, v, dp[u][v]);}}}printf("%d\n", dp[1][n]);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
