Educational Codeforces Round 93 (Rated for Div. 2)

A - Bad Triangle 最小的两边和小于等于最大的边，那么就一定不会存在这个三角形。否则，一定存在。

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 5e4 + 10; int T, n; int a[N]; int main() { T = read(); while (T--) { n = read(); upd(i, 1, n)a[i] = read(); if (a[1] + a[2] <= a[n]) { printf("%d %d %d\n", 1, 2, n); } else { puts("-1"); } } return 0; }

---

B - Substring Removal Game 看着是博弈论，实际就是统计全1段的长度和个数。然后排序后贪心的从最大的开始取即可。

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 1e2 + 10; int T; char s[N]; int cnt[N]; int main() { T = read(); while (T--) { scanf("%s", s+1); int len = strlen(s + 1); upd(i, 0, len)cnt[i] = 0; stack<int >st; vector<int>vec; upd(i, 1, len) { if (st.empty()) { st.push(s[i]); cnt[1] = 1; } else { if (st.top() != s[i]) { st.push(s[i]); cnt[st.size()]++; } else cnt[st.size()]++; } } while (!st.empty()) { if (st.top() == '1')vec.push_back(cnt[st.size()]); st.pop(); } int ans = 0; sort(vec.begin(), vec.end()); int num = 1; for (int i = vec.size()-1; i>=0; i--,num++) { if (num & 1)ans += vec[i]; } cout << ans << endl; } return 0; }

---

C - Good Subarrays 连续子段的和是该子段的长度，我们就可以想到，把所有数字全部剪掉1，那么等价于子段和是零。 问题转化成求前缀和后，找有多少个前缀相等的即可。 注意单独计算前缀和是0的前缀。

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 1e5 + 10; int T, n; char a[N]; int aa[N]; ll sum[N]; map<int, ll>mp; int main() { T = read(); while (T--) { n = read(); upd(i, 0, n)aa[i] = sum[i] = 0; mp.clear(); scanf("%s", a + 1); upd(i, 1, n) aa[i] = a[i] - 1 - '0'; ll ans = 0; upd(i, 1, n){ sum[i] = sum[i - 1] + aa[i]; } upd(i, 1, n) { if (sum[i] == 0)ans++; mp[sum[i]]++; ans += mp[sum[i]] - 1; } printf("%lld\n", ans); } return 0; }

---

D - Colored Rectangles 可以看见的是，我们肯定会想到优先将数字更大的进行匹配，所以我们先进行排序，分别对三种颜色。那么现在就是，从大到小的取，该怎么取。 我们利用一个简单的$dp$即可。 $dp[i][j][k]$表示三种颜色分别取$i,j,k$个的时候的最大值。 就很容易想到，进行简单的转移即可。 $dp[i+1][j][k+1]=max(dp[i][j][k]+rr[i]\ast bb[k],dp[i+1][j][k+1]);dp[i][j+1][k+1]=max(dp[i][j][k]+gg[j]\ast bb[k],dp[i][j+1][k+1]);dp[i+1][j+1][k]=max(dp[i][j][k]+rr[i]\ast gg[j],dp[i+1][j+1][k]);$

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 210; int R, G, B; int r[N], g[N], b[N]; int dp[N][N][N]; vector<int>rr, gg, bb; bool cmp(int a, int b) { return a > b; } int ans = 0; int main() { R = read(), G = read(), B = read(); upd(i, 1, R)r[i] = read(), rr.push_back(r[i]); upd(i, 1, G)g[i] = read(), gg.push_back(g[i]); upd(i, 1, B)b[i] = read(), bb.push_back(b[i]); rr.push_back(0); gg.push_back(0), bb.push_back(0); sort(rr.begin(), rr.end(), cmp); sort(gg.begin(), gg.end(), cmp); sort(bb.begin(), bb.end(), cmp); upd(i, 0, R) { upd(j, 0, G) { upd(k, 0, B) { dp[i + 1][j][k + 1] = max(dp[i][j][k] + rr[i] * bb[k], dp[i + 1][j][k + 1]); dp[i][j + 1][k + 1] = max(dp[i][j][k] + gg[j] * bb[k], dp[i][j + 1][k + 1]); dp[i + 1][j + 1][k] = max(dp[i][j][k] + rr[i] * gg[j], dp[i + 1][j + 1][k]); ans = max(dp[i + 1][j][k + 1], ans); ans = max(dp[i][j + 1][k + 1], ans); ans = max(dp[i + 1][j + 1][k], ans); } } } cout << ans << endl; }

---

E - Two Types of Spells 问题的本质就是，找k个数字，乘以两倍，其他的数字乘以一倍。（k是闪电的个数） 我们利用两个集合进行操作。一个集合放两倍数，一个集合放置一倍数。 当插入的时候，我们优先判断是否能进行两倍，即当前数字大于一倍数集合的最大值的时候。 删除的时候直接进行集合之间的删除。 除此之外，我们继续维护一个k，表示当前闪电的个数，即集合-两倍数的大小。 所以我们每一次再统计答案的时候，先判断集合-两倍数是否是大小是k，如果不是，添加或者删除，从集合-一倍数中。 另外需要排除一种特殊情况，即集合-两倍数中，全是闪电，那么这个时候集合两倍数就需要将最小的闪电，和最大的火进行互换（如果可以的话，否则相当于从两倍数-集合中删除该数字）。 可以方便进行，我们直接维护所有数字的和-ans，然后再ans+=sum[两倍数集合]

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 2e5 + 10; int n; set<int >s1, s2, F; int main() { n = read(); int cnt_l = 0; int tp, d; ll ans = 0; upd(i, 1, n) { tp = read(), d = read(); ans += d; if (d > 0) { if (tp == 0) { F.insert(d); if (s2.size() && *s2.begin() <= d)s2.insert(d), ans += d; else s1.insert(d); } else { cnt_l++; if (s2.size() && *s2.begin() <= d)s2.insert(d), ans += d; else s1.insert(d); } } else { if (tp == 0) { F.erase(-d); if (s1.count(-d))s1.erase(-d); else s2.erase(-d),ans += d; } else { cnt_l--; if (s1.count(-d))s1.erase(-d); else s2.erase(-d), ans += d; } } while (s2.size() > cnt_l) { ans -= *s2.begin(); s1.insert(*s2.begin()); s2.erase(s2.begin()); } while (s2.size() < cnt_l) { ans += *s1.rbegin(); s2.insert(*s1.rbegin()); s1.erase(--s1.end()); } int x = 0; if (s2.size()) { if (F.size())x = min(x, *F.rbegin() - *s2.begin()); else x = -*s2.begin(); } printf("%lld\n", ans + x); } return 0; }

---

F - Controversial Rounds 题目的本质就是，给出一个长度len，判断最多有少个，不重叠的，长度是len的全$0$，或者全$1$字串。 我们进一步思考可以发现一个贪心的策略。当0，1串重叠的时候，当且仅当出现’?'的时候，我们如果将‘？’归入当前前面的数字中，情况不会变差，所以基于该贪心，我们可以： 维护一个后缀长度，$nxt[0][pos],nxt[1][pos]$,以$pos$结尾的，全$0$，全$1$串的长度。继续维护两个vector,$vec[0][len],vec[1][len]$存储，全$0$，全$1$的长度是$len$的所有左端点。 继而我们可以利用调和级数$n+n/2+n/3+n/4+...+1=n\ast \log (n)$进行暴力判断。其中还有一个二分的$log$，当每次找不到的时候，我们二分一个最小的左端点$>=nowpos$即可，没有的话，直接退出。

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<stack> #include<vector> #include<queue> #include<set> #include<bitset> #include<map> //#include<regex> #include<cstdio> #include <iomanip> #pragma GCC optimize(2) #define up(i,a,b) for(int i=a;i<b;i++) #define dw(i,a,b) for(int i=a;i>b;i--) #define upd(i,a,b) for(int i=a;i<=b;i++) #define dwd(i,a,b) for(int i=a;i>=b;i--) //#define local typedef long long ll; typedef unsigned long long ull; const double esp = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int inf = 1e9; using namespace std; ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } typedef pair<int, int> pir; #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lrt root<<1 #define rrt root<<1|1 const int N = 1e6 + 1l; char s[N]; int nxt[2][N]; vector<int> len[2][N]; int n; bool check(int pos,int ter) { if (s[pos] != '?'&&s[pos] != (ter + '0'))return 0; else return 1; } int main() { n = read(); scanf("%s", s + 1); dwd(i, n, 1) { if (s[i] == '1' || s[i] == '?')nxt[1][i] = 1 + nxt[1][i + 1]; if (s[i] == '0' || s[i] == '?')nxt[0][i] = 1 + nxt[0][i + 1]; } upd(bit, 0, 1) { for (int l = 1; l <= n;) { if (!check(l,bit))l++; else { int r = l; for (r = l; r <= n;) { if (check(r, bit)) { len[bit][r - l + 1].push_back(l); r++; } else break; } l = r + 1; } } } upd(x, 1, n) { int pos = 1; int ans = 0; while (pos <= n) { if (nxt[0][pos] >= x || nxt[1][pos] >= x)pos += x, ans++; else { int temp1 = lower_bound(len[0][x].begin(), len[0][x].end(), pos) - len[0][x].begin(); int temp2 = lower_bound(len[1][x].begin(), len[1][x].end(), pos) - len[1][x].begin(); int pos1 = INF, pos2 = INF; if (temp1 != len[0][x].size())pos1 = len[0][x][temp1]; if (temp2 != len[1][x].size())pos2 = len[1][x][temp2]; if (pos1 == INF && pos2 == INF)break; pos = min(pos1, pos2); } } printf("%d ", ans); } return 0; }