Educational Codeforces Round 143 (Rated for Div. 2)_WQhuanm

网络 02-07 7304

Educational Codeforces Round 143 (Rated for Div. 2)

D. Triangle Coloring 思路：每个环都需要取最大值，那么我们讨论一个环获得最大值选的两条边的可能取法：? ? ? ? ? ? ? 显然：如果三边相等，这个环有3种取法。如果有两条小边相等，这个环有两种取法。其余情况都只能取一种之后把每个环都看成一个点，就是从n个环选n/2个蓝色（红色），求组合数。所以其实就是考逆元乘法逆元（费马小定理，拓欧，线性dp） #include <bits/stdc++.h> using namespace std; #define ll long long #define int ll typedef unsigned long long ull; typedef pair<long long, long long> pll; typedef pair<int, int> pii; //double 型memset最大127，最小128 //std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); const int INF = 0x3f3f3f3f; //int型的INF const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF const int N = 2e5 + 10; const int mod = 998244353; int a[3]; ll fastmi(ll base, ll power)//快速幂求逆元 { ll ans = 1; while (power) { if (power & 1)ans = ans * base % mod; base = base * base % mod; power >>= 1; } return ans; } int32_t main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n;//n从表示一个点转化为表示一个环 n /= 3; ll ans = 1; for (int i = 1; i <= n; ++i) { cin >> a[0] >> a[1] >> a[2];//3点一个环 sort(a, a + 3);// if (a[0] == a[2])ans = (ans * 3) % mod;// else if (a[0] == a[1])ans = (ans * 2) % mod; } ll tmp = 1; for (int i = 1; i <= n / 2; ++i)//求组合数C(n/2,n) { ans = (ans * (n / 2 + i)) % mod; tmp = tmp * i % mod; } ans = (ans * fastmi(tmp, mod - 2)) % mod; cout << ans << endl; return 0; } E. Explosions? 思路：我们枚举每个点作为爆炸点，显然，爆炸连续的前提就是左边生命值严格单调增，右边严格单调减。由于我们需要消耗的生命值总和是恒定的，所以，那个点爆炸造成总伤害高，显然耗费魔法值更少我们考虑爆炸时左边（右边）的邻居(j)与爆炸点(x)的大小关系(a[i]表示生命值,l[i]表示i对左边可以造成的伤害和（包括炸死自己））：会发现，如果a[j]>=a[x]-1,是无法爆炸的，不过，我们可以用单位魔法把j生命值变为a[x]-1，所以无影响所以对于x左边任意点j，如果a[j]>=a[x]-(x-j),我们可以用单位魔法操作到其生命值为a[x]-(x-j)。对于a[j]<a[x]-(x-j),那我们下一次爆炸的威力就减少了，而且我们发现，后续产生的伤害等于l[j]，所以我们加上l[j]就不用再往左了因此，我们得出，每次求l[x]，只需要找到第一个点j满足a[j]<a[x]-(x-j），那么? ? ? ? ? ? ? ? ? ? l[x]=(x-j)*(a[x]+(a[x]-(x-j)+1)/2+l[j]然而，每个点都回溯太费时间了，我们中间那些不满足a[j]<a[x]-(x-j)的点j只要没用一次就一直没用，我们能不能舍去他，为这个数组减肥呢。观察发现，不等式可以表示为a[j]-j<a[x]-x,所以我们可以另开一个数组记录这个信息。然后从左往右遍历，每次求当前点l[x]，只需要把a[j]-j>=a[x]-x的前面点舍去，最后就可以立刻求取答案，显然，舍去这个功能让我们想到可以开一个栈（先进后出）爆炸右边也是同理 #include <bits/stdc++.h> using namespace std; #define ll long long #define int ll typedef unsigned long long ull; typedef pair<long long, long long> pll; typedef pair<int, int> pii; //double 型memset最大127，最小128 //std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); const int INF = 0x3f3f3f3f; //int型的INF const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF const int N = 3e5 + 10; int a[N], l[N], r[N], a1[N], n; void cnt(int *f) { stack<int>s; s.push(0);//放入左边边界外面0 for (int i = 1; i <= n; ++i)a1[i] = a[i] - i; //记录比较数组 for (int i = 1; i <= n; ++i) { while ((int)s.size() > 1 && a1[s.top()] >= a1[i])s.pop(); //从最靠近右边的点（堆顶）开始比较，不满足的点全部舍去，后面也没用了 int len = min(a[i], (ll)i - s.top()); //爆炸可持续范围最长是a[i]（伤害不断递减），不是直接取遇到满足条件的j点（你可能到不了那个点） f[i] = f[s.top()] + len * (2 * a[i] - len + 1) / 2; s.push(i);//不断给栈存入新的点 } } int32_t main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while (t--) { cin >> n; ll sum = 0; for (int i = 1; i <= n; ++i)cin >> a[i], sum += a[i]; cnt(l); reverse(a + 1, a + 1 + n); //反转一下求右边爆炸 cnt(r); reverse(r + 1, r + 1 + n); //r获得的是反转过的，要反转回来 reverse(a + 1, a + 1 + n); ll ans = 0; for (int i = 1; i <= n; ++i)ans = max(ans, l[i] + r[i] - 2 * a[i]); //l与r都记录了a[i]造成的伤害，然而这个伤害是魔法产生的，不是被波及的 cout << sum - ans << endl; } return 0; }