Educational Codeforces Round 143 (Rated for Div. 2)
Problem - B Ideal Point
给定n个线段区间\([l,r]\),我们定义\(f(x)\)为覆盖点\(x\)的线段数，我们每次操作可以删除任意一条线段，并且操作数不限，给出q次询问，每次询问点x能否通过操作使得\(f(x)\)严格最大
题解：贪心
我们通过模拟发现只要把不包含x的线段全部删除，那么仍然存在的线段都会限制\(f(x)\)，然后如果存在其他点y使得\(f(y)>=f(x)\)或者存在,那么说明我们无论如何都不能使得\(f(x)\)最大，反之一定可以，由于数据比较小，直接通过计数数组\(cnt\)判断即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, k;
pii a[55];
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i].first >> a[i].second;
vector<int> cnt(55, 0);
int ok = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i].first <= k && k <= a[i].second)
{
for (int j = a[i].first; j <= a[i].second; ++j)
cnt[j]++;
}
}
int maxx = -INF, num = 0;
for (int i = 1; i <= 50; ++i)
maxx = max(cnt[i], maxx);
for (int i = 1; i <= 50; ++i)
if (cnt[i] == maxx)
num++;
if (cnt[k] == maxx && num == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Problem - C Tea Tasting
给定n杯茶，每杯茶有\(a_i\)毫升，每杯茶面前都有一个品茶人，每次能够喝\(b_i\)毫升的茶，每一轮品茶结束后所有人都会往左移动，也就是说第一回合结束后第一个人不会再喝茶，第二回合结束后第二个人不会再喝茶，那么每个人在每回合能够喝到茶的数量为\(min(a_i,b_i)\)，请你求出所有人分别能够喝到的茶的数量
题解：二分+前缀和+差分
首先我们可以知道对于第\(i\)杯茶来说，只有\([i+1,n]\)这些人能够喝到，所以我们可以先求出每个人喝茶\(b_i\)的前缀和\(pre\)，对于每杯茶我们只需要二分前缀和找到后面第一个喝不满\(b_j\)这个茶的人\(j\)，那么我们只要让\(j\)喝完剩下所有茶，然后利用差分数组记录中间都能喝满自己能喝的茶的人即可；
注意：这边在二分前缀和的时候有个技巧，我们对于每个\(a_i\)都要去往\(i\)的后面找，也就是说所有\(i\)后面的前缀和都要减去\(pre[i-1]\),比较麻烦，那么我们这边大佬有个技巧就是我们直接\(a_i+pre[i-1]\)，这样效果也是一样，我只能说太秀
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int pre[N];
void solve()
{
cin >> n;
vector<int> ans(n + 10);
vector<int> a(n + 10), b(n + 10);
vector<int> dif(n + 10);
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + b[i];
for (int i = 1; i <= n; ++i)
{
int pos = upper_bound(pre + 1, pre + n + 1, a[i] + pre[i - 1]) - pre;
ans[pos] += a[i] - (pre[pos - 1] - pre[i - 1]);
dif[i]++;
dif[pos]--;
}
for (int i = 1; i <= n; ++i)
dif[i] = dif[i - 1] + dif[i];
for (int i = 1; i <= n; ++i)
{
ans[i] += b[i] * dif[i];
cout << ans[i] << " ";
}
cout << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Problem - D Triangle Coloring
给定n个节点和n条边，每条边存在权值，并且\(6|n\),将每三个节点变成一个三元组，并用三条边连接，现在需要将n个点中一半的点涂成红色，一半的点涂成蓝色，如果两个点颜色不一样，那么连接这两个点的边的权值会被记录在sum中，最后你需要使得sum最大，并且求出使得sum最大的方案数
题解：组合计数+思维
首先n个点中一半为红色，一半为蓝色，很明显在一个三元组内，我们只有两种涂色方式：
- 全为红色或蓝色；
- 一红二蓝或者一蓝二红；
显然后者对于sum的贡献更大，我们取后者
假设一个三元组需要涂一红二蓝，也就是说我们在每个三元组中会选择两条边，那么存在以下几种情况：
- 每条边的权值都不一样，我们肯定会选择最大的两条，那么只有一种选择
- 最小两条边的权值相同，那么我们肯定会选择最大的以及任意一条最小边，有两种选择；
- 如果三条边的权值都相同，我们任意选择两条边即可，有3种选择；
那儿我们还需要知道哪些三元组涂了一红二蓝，哪些涂了一蓝二红，答案乘上\(C_{n/3}^{n/6}\)即可
注意：因为取模运算没有除法，所以我们需要利用快速幂求出乘法逆元，\(C_{n/3}^{n/6} = \frac{A_{n/3}^{n/6}}{A_{n/6}^{n/6}}\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-9;
const int N = 3e5 + 10, M = 4e5 + 10;
int qpow(int x, int y)
{
int res = 1;
while (y)
{
if (y & 1)
res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
int A(int n, int m)
{
int res = 1;
for (int i = m; i > m - n; --i)
res = res * i % mod;
return res;
}
int n;
int a[4];
void solve()
{
cin >> n;
int ans = 1;
for (int i = 1; i <= n; i += 3)
{
cin >> a[1] >> a[2] >> a[3];
sort(a + 1, a + 4);
if (a[1] == a[2] && a[2] == a[3])
ans = ans * 3 % mod;
else if (a[1] == a[2])
ans = ans * 2 % mod;
}
ans = ans * A(n / 6, n / 3) % mod;
ans = ans * qpow(A(n / 6, n / 6), mod - 2) % mod;
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
Problem - E Explosions?
给定n个怪兽，每个怪兽血量为\(h_i\),你现在有两种魔法：
- 消耗1MP，对一个怪兽的血量减去1，可以释放无数次
- 消耗xMP，对于一个怪兽的血量减去x，如果该怪兽死亡，会引起连锁反应，他会对它相邻两边的怪兽产生爆炸伤害\(h_i-1\)，如果该伤害继续造成死亡，会继续往旁边造成爆炸伤害，直到没有造成死亡为止，只能在最后一次释放
注意：怪物的位置不能移动，即使怪物死了，也不会消失
请你求出最少需要多少MP才能消灭所有怪物
题解：维护二元单调栈+贪心 ：好题目
根据贪心思想，我们最好在最后一步爆炸解决掉所有的怪兽，所以我们可以枚举在每一个怪兽位置爆炸需要的MP，最后取min即可
那么为了实现最后的爆炸能够清除所有的怪兽，我们需要保证数组h要形成一个单峰，引爆位置左边严格递增，引爆位置右边严格递减，那么假设使得左边严格递增的花费为\(L[i]\),右边严格递减的花费为\(R[i]\)，那么选择i位置作为引爆点的全部花费为\(L[i]+R[i]+h[i]\)
现在的关键就是如何求出L[i]和R[i]，我们先对于L[i]进行讨论，R[i]可以同理得出：
我们可以维护一个单调递增栈，栈中元素是个二元组\((val,cnt)\)表示一个集合:val代表集合中最大值，cnt代表集合中有cnt个数，并且该集合是一个严格递增且差值为1的集合，那么很明显我们可以知道集合中的最小值为\(val-cnt+1\)
那么我们遍历数组\(h\)维护单调递增栈，我们讨论以下情况对单调栈内的集合进行合并和插入：
如果当前集合的最小值\(val-cnt+1>\)栈顶集合的最大值，直接将插入集合\((h[i],1)\)
如果当前集合的最小值\(val-cnt+1<=\)栈顶集合的最大值,那么我们需要将集合进行合并，合并的过程需要代价，并将栈顶不断出栈，直到不能合并为止，比如栈顶为(3,1)，待插入的集合为(2,1),那么合并后的集合应该为(2,2),所以花费应该为3-2=1,因为我们需要的是一个单调递增且差值为1的集合
再举个例子，(3,3)和(3,2)合并，也就是（1，2，3）和（2，3）合并，那么我们需要的代价就是为了方便先把（1，2，3）变为（0，0，0）然后再变成（0，0，1），所以需要的代价为（1+2+3-1），那么这个代价我们可以利用等差数列求和快速实现
根据这样的操作我们就能够计算出L[i],同理我们从后往前遍历维护单调递增栈，即可求出\(R[i]\)
下面给出一个样例，并附上图示，便于理解集合的合并和为什么这样能够得出L[i]和R[i]:
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 3e5 + 10, M = 4e5 + 10;
int n;
pii stk[N];
int h[N], L[N], R[N];
int tt;
int cal(int x, int n)
{
int p = max(0ll, x - n + 1);
return n * (p + x) / 2;
}
void solve()
{
cin >> n;
tt = 0;
for (int i = 1; i <= n; ++i)
cin >> h[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
{
int cnt = 1;
while (tt && h[i] - cnt + 1 <= stk[tt].first)
{
int minn = max(0ll, h[i] - cnt + 1); //防止最小值为负数
sum += cal(stk[tt].first, min(stk[tt].first, stk[tt].second));
sum -= cal(max(0ll, minn - 1), min(max(0ll, minn - 1), stk[tt].second));
cnt += stk[tt].second;
tt--;
}
L[i] = sum;
stk[++tt] = mpk(h[i], cnt);
}
tt = 0;
sum = 0;
for (int i = n; i >= 1; --i)
{
int cnt = 1;
while (tt && h[i] - cnt + 1 <= stk[tt].first)
{
int minn = max(0ll, h[i] - cnt + 1);
sum += cal(stk[tt].first, min(stk[tt].first, stk[tt].second));
sum -= cal(max(0ll, minn - 1), min(max(0ll, minn - 1), stk[tt].second));
cnt += stk[tt].second;
tt--;
}
R[i] = sum;
stk[++tt] = mpk(h[i], cnt);
}
int ans = INF;
for (int i = 1; i <= n; ++i)
ans = min(ans, h[i] + L[i] + R[i]);
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}