Educational Codeforces Round 143 (Rated for Div. 2)

Educational Codeforces Round 143 (Rated for Div. 2)

D. Triangle Coloring

思路：

1. 每个环都需要取最大值，那么我们讨论一个环获得最大值选的两条边的可能取法：              显然：如果三边相等，这个环有3种取法。如果有两条小边相等，这个环有两种取法。其余情况都只能取一种
2. 之后把每个环都看成一个点，就是从n个环选n/2个蓝色（红色），求组合数。
3. 所以其实就是考逆元乘法逆元（费马小定理，拓欧，线性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?

思路：

1. 我们枚举每个点作为爆炸点，显然，爆炸连续的前提就是左边生命值严格单调增，右边严格单调减。
2. 由于我们需要消耗的生命值总和是恒定的，所以，那个点爆炸造成总伤害高，显然耗费魔法值更少
3. 我们考虑爆炸时左边（右边）的邻居(j)与爆炸点(x)的大小关系(a[i]表示生命值,l[i]表示i对左边可以造成的伤害和（包括炸死自己））：
   1. 会发现，如果a[j]>=a[x]-1,是无法爆炸的，不过，我们可以用单位魔法把j生命值变为a[x]-1，所以无影响
   2. 所以对于x左边任意点j，如果a[j]>=a[x]-(x-j),我们可以用单位魔法操作到其生命值为a[x]-(x-j)。
   3. 对于a[j]<a[x]-(x-j),那我们下一次爆炸的威力就减少了，而且我们发现，后续产生的伤害等于l[j]，所以我们加上l[j]就不用再往左了
   4. 因此，我们得出，每次求l[x]，只需要找到第一个点j满足a[j]<a[x]-(x-j），那么                    l[x]=(x-j)*(a[x]+(a[x]-(x-j)+1)/2+l[j]
   5. 然而，每个点都回溯太费时间了，我们中间那些不满足a[j]<a[x]-(x-j)的点j只要没用一次就一直没用，我们能不能舍去他，为这个数组减肥呢。
   6. 观察发现，不等式可以表示为a[j]-j<a[x]-x,所以我们可以另开一个数组记录这个信息。然后从左往右遍历，每次求当前点l[x]，只需要把a[j]-j>=a[x]-x的前面点舍去，最后就可以立刻求取答案，显然，舍去这个功能让我们想到可以开一个栈（先进后出）
   7. 爆炸右边也是同理

#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);//放入左边边界外面0for (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;
}