A.Two Towers
题目描述：
有 \(a,b\) 两座由红蓝色方块垒成的塔,其中 \(a\) 的高度为 \(n\) ； \(b\) 的高度为 \(m\) ，用 R 代表红色；用B代表蓝色。
你可以多次把其中一座顶端的方块移到另一座的顶端（可以不移动）。问有没有一种方法可以使两座塔中均没有连续的同颜色方块。
题目分析：
可以先全部将方块移动到一座塔上，这样我们的一种塔的方案数就相当于选择一个分界点将这一个序列分成两半。
所以有解显然当且仅当仅有一个位置，使得这个位置有连续两个相同颜色的数，或者所有颜色都不连续。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
char s[N],t[N];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%d",&T);
while(T--){
int n,m;scanf("%d%d",&n,&m);
scanf("%s%s",s+1,t+1);
for(int i=1; i<=m; i++) s[n+i] = t[m - i + 1];
int cnt = 0;
for(int i=1; i<=n+m; i++){
int pos = i;
while(s[pos] == s[i] && pos <= n + m) ++pos;
--pos;
if(pos - i + 1 == 2) ++cnt;
if(pos - i + 1 > 2) cnt = 2;
}
if(cnt <= 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
B.Ideal Point
题目描述：
在一条数轴上，有 \(n\) 条线段和一个点 \(k\)，问能否删去若干条线段使得 \(k\) 的被覆盖次数比其他所有点的被覆盖次数都大。
题目分析：
显然就是要让点 \(k\) 覆盖次数变多不可能，就是要让其他点的覆盖次数减少。
也就是如果一个线段没有覆盖了 \(k\)，那么将它删去一定是更优的，而如果一个线段覆盖了 \(k\) 那么将它删除一定是不会更优的。
删完了，判断一下即可。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int cnt[N];
int main(){
int T;scanf("%d",&T);
while(T--){
int n,k;scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++){
int l,r;scanf("%d%d",&l,&r);
if(k < l || k > r) continue;
for(int j=l; j<=r; j++) cnt[j]++;
}
bool flag = true;
for(int i=1; i<=50; i++){
if(i == k) continue;
if(cnt[i] >= cnt[k]) flag = false;
}
if(flag) printf("YES\n");
else printf("NO\n");
for(int i=1; i<=50; i++) cnt[i] = 0;
}
return 0;
}
C.Tea Tasting
题目描述：
有 \(n\) 个人和 \(n\) 杯茶，第 \(i\) 个人每次会喝 \(b_i\) 毫升的茶。第 \(i\) 杯茶有 \(a_i\) 毫升。总共会喝 \(n\) 轮茶，第 \(j\) 轮第 \(i\) 个人会尝试喝第 \(i+1-j\) 杯茶。喝的量为 \(\min(a_{i+1-j},b_i)\) 毫升，并且使 \(a_{i+1-j}\) 减少 \(\min(a_{i+1-j},b_i)\) 。问 \(n\) 轮后每个人喝了多少毫升茶。
\(1 \le n\le 2\times 10^5\)
题目分析：
因为茶会有喝完的时候，所以如果我们直接对于每一个人去统计茶对他产生的贡献，就很不好做。
所以考虑对于每一杯茶，统计它对每一个人造成的贡献，对于第 \(i\) 杯茶，在第 \(j\) 轮喝它的人就是 \(i + j - 1\)，所以可以考虑直接二分得到这一杯茶在哪个人那里被喝没了，这样对于这个人前面喝过这个茶的人都完全喝了 \(b\) 毫升，而对于这个人就是减一下就知道他喝了多少毫升。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int INF = 1e18+5;
int a[N],b[N],cnt[N],res[N];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%lld",&T);
while(T--){
int n;scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++) scanf("%lld",&b[i]),b[i] += b[i-1];
b[n+1] = INF;
for(int i=1; i<=n; i++){
int pos = upper_bound(b+i,b+n+2,a[i] + b[i-1]) - b;
cnt[i]++,cnt[pos]--;
res[pos] += a[i] - (b[pos-1] - b[i-1]);
}
for(int i=1; i<=n; i++) cnt[i] += cnt[i-1];
for(int i=1; i<=n; i++) printf("%lld ",cnt[i] * (b[i] - b[i-1]) + res[i]);
printf("\n");
for(int i=1; i<=n+1; i++) cnt[i] = 0,b[i] = 0,res[i] = 0;
}
return 0;
}
D.Triangle Coloring
题目描述：
一共有 \(n\) 条边（ \(n\) 是 \(6\) 的倍数） ，每连续三条边构成一个三角形（比如若 \(n=6\) 那么第 \(1,2,3\) 条边构成一个三角形， \(4,5,6\) 条边构成另一个三角形 ），每条边有一个权值 \(w_i\) ，现在你可以把所有三角形的顶点涂成蓝色或红色，且要求有 \(\frac{n}{2}\) 个蓝点和 \(\frac{n}{2}\) 个红点，定义总权值为所有两端点颜色不同的边的权值和，问有多少种涂色方案可以使总权值最大（答案模 \(998244353\) ）。
\(6 \le n \le 4 \times 10^5，1 \le w_i \le 1000\)
题目分析：
对于一个三角形，因为边权全部大于 \(0\)，所以全部染成蓝色和红色一定不是权值和最大的答案，而染成蓝蓝红和红红蓝最优的方案数显然是一样的，就是让某两条边的边权之和最大的方案数。
要求染一半的红点一半的蓝点，本质上就是选一半的三角形染蓝蓝红另一半的三角形染红红蓝，而对于每一种钦定每个三角形染色方案的方式，其实际方案数为定值，所以只需要求出选择染色方案的方案数即可。
而选择的方案数显然是：
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 1e6+5;
int a[N],fac[N],inv[N];
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int binom(int n,int m){
if(n < m || n < 0 || m < 0) return 0;
return fac[n] * inv[m] % MOD * inv[n-m] %MOD;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;scanf("%lld",&n);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
int res = 1;
for(int i=1; i<=n/3; i++){
for(int j=1; j<=3; j++) scanf("%lld",&a[j]);
int ans = 0,cnt = 0;
for(int j=1; j<=3; j++){
for(int k=j+1; k<=3; k++){
if(a[j] + a[k] > ans) ans = a[j] + a[k],cnt = 1;
else if(a[j] + a[k] == ans) cnt++;
}
}
res = res * cnt % MOD;
}
res = res * binom(n/3,n/6) % MOD;
printf("%lld\n",res);
return 0;
}
E.Explosions?
题目描述：
你在玩一个利用魔法杀怪物的游戏。具体地，有一排 \(n\) 个格子，第 \(i\) 个格子里有编号为 \(i\)、初始生命值为 \(h_i\) 的怪物。怪物生命值小于等于 \(0\) 则被杀死，所有怪物被杀死则游戏结束。
你有两种攻击方式：一种是普通攻击，你将消耗 \(1\) 点能量对选中的怪物进行 \(1\) 点伤害（也就是怪物的生命值减 \(1\)），你可以使用普通攻击任意次数。同时，你还可以使用恰好一次“爆炸”攻击。你想要游戏以“爆炸”攻击结束，也就是说，你会先进行若干次普通攻击（可以为 \(0\) 次），然后使用一次“爆炸”攻击结束游戏。
“爆炸”攻击的机制如下：你可以选择消耗的能量数 \(x\)，然后选中一个怪物 \(i\)，之后：
- 若怪物 \(i\) 当前的生命值 \(h_i > x\)，那么该怪物生命值减去 \(x\)；
- 若 \(h_i\le x\)，则该怪物被击杀，同时向两旁的怪物（即第 \(i-1\) 和 \(i+1\) 只怪物，如果有且还存活的话）造成 \(h_i - 1\) 的伤害；
- 若 \(h_i - 1\) 的伤害足以杀死第 \(i-1\) （或 \(i+1\)）只怪物，即 \(h_{i-1}\le h_i - 1\)（或 \(h_{i+1}\le h_i - 1\)），那么这只怪物同样被击杀并向两旁的怪物造成 \(h_{i-1} - 1\)（或 \(h_{i+1} - 1\)）的伤害。如此循环只到杀不死一直怪物为止。
你的目标就是先用普通攻击减少某些怪物的生命值或直接杀死某些怪物，然后用这样“链式”的“爆炸”攻击杀死所有怪物。注意怪物不会移动，例如第 \(i\) 只怪物和第 \(i+2\) 只怪物永远不会相邻。
你需要消耗最少的能量值来达成目标（包括普通攻击和“爆炸”攻击的），求出这个最小值。
\(1 \le n \le 10^5\)
题目分析：
考虑使用爆炸操作之前的状态一定是前面一段 \(0\) + 一个严格单峰的段 + 后面一段 \(0\)
所以可以考虑直接枚举这个峰在那里，那么就是要求前面严格单调递增后面严格单调递减，\(0\) 的问题其实可以理解为负数变成 \(0\)。
显然这两段问题是对称的，也就是解决一个问题即可，考虑解决前面的这个问题。
记 \(L[i]\) 表示让 \([1,i]\) 严格单调递增的最小操作次数，可以发现若存在 \(j < i\) 满足 \(a_j \le a_i - (i-j)\)，也就是 \(a_j\) 可以在不被操作的情况下爆掉，那么 \([1,j]\) 的贡献就是 \(L[j]\) 下面直接考虑 \([j+1,i]\) 的贡献即可，显然可以找到最大的一个 \(j\) 满足上述条件。
那么该怎么求这个 \(j\) 呢，显然上述条件可以转化为 \(a_j - j \le a_i - i\)，直接用单调栈就可以维护了。
对于 \([j+1,i]\) 的贡献，不妨假设 \(x \in [j+1,i]\)，则这个点的操作次数就是 \(a_x - [a_i - (i-x)]\)，如果放到这一整段来看的话，\(a_x\) 就是相当于区间和 \(a_i - (i-x)\) 就是一个等差数列求和，都很好维护。
要注意的细节就是，若 \(a_i - (i-x)\) 为负数，要认为是 \(0\)。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5+5;
const int INF = 1e18+5;
int a[N],L[N],R[N],sum[N];
int get(int x,int len){
int y = x - len + 1;
return (x + y) * len / 2;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%lld",&T);
while(T--){
int n;scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
stack<pair<int,int> > st;
for(int i=1; i<=n; i++){
while(!st.empty() && st.top().first > a[i] - i) st.pop();
int pos = 0;
if(st.empty()) pos = 0;
else pos = st.top().second;
//注意的细节：减成负的相当于减成 0
if(pos != 0) L[i] = L[pos] + sum[i] - sum[pos] - get(a[i],min(i-pos,a[i]));
else L[i] = sum[i] - get(a[i],min(i,a[i]));
st.push({a[i]-i,i});
}
reverse(a+1,a+n+1);
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
while(!st.empty()) st.pop();
for(int i=1; i<=n; i++){
while(!st.empty() && st.top().first > a[i] - i) st.pop();
int pos = 0;
if(st.empty()) pos = 0;
else pos = st.top().second;
//注意的细节：减成负的相当于减成 0
if(pos != 0) R[i] = R[pos] + sum[i] - sum[pos] - get(a[i],min(i-pos,a[i]));
else R[i] = sum[i] - get(a[i],min(i,a[i]));
st.push({a[i]-i,i});
}
for(int l=1,r=n; l<=r; l++,r--) swap(R[l],R[r]);
int ans = INF;
reverse(a+1,a+n+1);
for(int i=1; i<=n; i++) ans = min(ans,L[i] + a[i] + R[i]);
printf("%lld\n",ans);
}
return 0;
}