魔法学院
题目描述：
亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。
目前她已经收集了n个不包括空格的可见字符，第i个字符为Si。可是她想要把自己收集的n个字符的价值和最大化，因此去请求了戴安娜的帮助。
戴安娜有m种魔法，第i种魔法可以将[li,ri]区间的一个字符替换为ci。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。
请问戴安娜使用完若干次魔法后，亚可收集的n个字符的最大价值和可以是多少？
思路1: 差分 + 贪心
对于每个字符，我们更新他能影响的所有的点的答案，最后计算所以点的答案和即可
方法是差分前缀和，搞一个差分数组d，
++d[l],--d[r + 1]，然后前缀和加起来，如果sum[i] > 0则说明这个点会被该字符影响到，更新这个点的答案就行复杂度是
O(94 * n)能解决
easy版本，但是对于hard版本就不行了
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m;
int l, r;
char p;
vector<pii>tr[200];
int ans[MAX];
int d[200050];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> p;
ans[i] = (int)p;
}
for(int i = 1; i <= m; ++i){
cin >> l >> r >> p;
tr[(int)p].push_back(m_p(l, r));
}
for(int i = 33; i <= 126; ++i){
mem(d, 0);
for(auto [l, r] : tr[i]){
++d[l];--d[r + 1];
}
for(int j = 1; j <= n; ++j){
d[j] += d[j - 1];
if(d[j])ans[j] = max(ans[j], i);
}
}
ll sum = 0;
for(int i = 1; i <= n; ++i)sum += ans[i];
cout << sum << endl;
}
int main(){
io;
work();
return 0;
}
思路2:贪心 + 线段树区间覆盖
我们可以把字符串的每个字符拆成一个
[i, i]的区间，和输入的m个区间放在一起，按照价值从小到大的顺序排序，然后开始区间覆盖，不难发现这样的贪心显然正确复杂度
O((n + m)log(n))也是只能过easy版本，过不了hard版本
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
//不改范围见祖宗!!!
#define MAX 500000 + 50
int n, m, k, op;
struct ran{
int l, r, val;
bool operator <(const ran &x)const{
return val < x.val;
}
}ar[MAX];
ll sum[MAX];
int la[MAX];
inline void pushup(int p){
sum[p] = sum[ls] + sum[rs];
}
inline void built(int p, int l, int r){
if(l == r){
sum[p] = la[p] = 0;
return;
}
int mid = (l + r) / 2;
built(ls, l, mid);
built(rs, mid + 1, r);
pushup(p);
}
inline void cal_lazy(int p, int len, int x){
la[p] = x;
sum[p] = 1ll * len * x;
}
inline void pushdown(int p, int len){
if(la[p]){
cal_lazy(ls, len - len / 2, la[p]);
cal_lazy(rs, len / 2, la[p]);
la[p] = 0;
}
}
inline void update(int p, int l, int r, int s, int t, int x){
if(l >= s && t >= r){
cal_lazy(p, r - l + 1, x);
return;
}
pushdown(p, r - l + 1);
int mid = (l + r) / 2;
if(mid >= s)update(ls, l, mid, s, t, x);
if(mid < t)update(rs, mid + 1, r, s, t, x);
pushup(p);
}
inline ll getsum(int p, int l, int r, int s, int t){
if(l >= s && t >= r){
return sum[p];
}
pushdown(p, r - l + 1);
ll sum = 0;
int mid = (l + r) / 2;
if(mid >= s)sum += getsum(ls, l, mid, s, t);
if(mid < t)sum += getsum(rs, mid + 1, r, s, t);
return sum;
}
void work(){
cin >> n >> m;
char p;
for(int i = 1; i <= n; ++i){
cin >> p;
ar[i].l = ar[i].r = i;
ar[i].val = (int)p;
}
for(int i = 1; i <= m; ++i){
cin >> ar[i + n].l >> ar[i + n].r;
cin >> p;
ar[i + n].val = (int)p;
}
sort(ar + 1, ar + 1 + m + n);
built(1, 1, n);
for(int i = 1; i <= n + m; ++i){
update(1, 1, n, ar[i].l, ar[i].r, ar[i].val);
}
cout << getsum(1, 1, n, 1, n) << endl;
}
int main(){
work();
return 0;
}
思路3: 贪心 + 并查集
先不管那个字符串，直接将
m个区间按照价值从大到小的顺序排好，对于高价值字符覆盖过的区间，低价值字符就没有必要去遍历了，所以我们可以使用并查集来解决最后再用每一位的最大值和字符串的对应位置比大小，取最大的，求和
复杂度是：
O(max(n, mlogm))
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m;
char p;
char c[MAX];
int fa[MAX];
inline int getfa(int x){
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
struct ran{
int l, r, p;
}tr[MAX];
bool cmp(ran a, ran b){
return a.p > b.p;
}
int ans[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)cin >> c[i];
for(int i = 1; i <= m; ++i){
cin >> tr[i].l >> tr[i].r >> p;
tr[i].p = (int)(p);
}
for(int i = 1; i <= n + 1; ++i)fa[i] = i;
sort(tr + 1, tr + 1 + m, cmp);
for(int i = 1; i <= m; ++i){
auto [l, r, z] = tr[i];
l = getfa(l);
while (l <= r) {
ans[l] = max(ans[l], z);
fa[l] = l + 1;
l = getfa(l + 1);
}
}
ll cnt = 0;
for(int i = 1; i <= n; ++i){
cnt += max(ans[i], (int)c[i]);
}
cout << cnt << endl;
}
int main(){
io;
work();
return 0;
}
思路4：珂朵莉树 + “玄学优化”
和方法2的思路差不多，但是方法2用线段树只去进行区间覆盖就很浪费时间，而珂朵莉树可以很好的处理区间覆盖问题
但是有一点需要注意，不要像方法2的线段树一样把字符串的每个点一起处理了，如果一起处理了，可能会导致珂朵莉初始的大小是n，就会T，解决方法就是在最后统计答案的时候便利珂朵莉树的set的每个区间的每个数，和字符串对应位置的数值取一个最大值，求和就行
复杂度是
O(能过)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define it set<ran>::iterator
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 20000000 + 50
int n, m;
int l, r;
vector<pii>s[130];
char ss[MAX];
struct ran{
int l, r;
mutable int val;
ran(int L, int R = -1, int Val = 0){
l = L;r = R;val = Val;
};
bool operator <(const ran &x)const{
return l < x.l;
}
};
set<ran>tr;
it split(int pos){
if(pos > n)return tr.end();
it itt = tr.lower_bound(pos);
if(itt != tr.end() && itt->l == pos)return itt;
--itt;
int l = itt->l, r = itt->r, v = itt->val;
tr.erase(itt);
tr.insert(ran(l, pos - 1, v));
return tr.insert(ran(pos, r, v)).first;
}
void emerge(int l, int r, int v){
it itr = split(r + 1), itl = split(l);
tr.erase(itl, itr);
tr.insert(ran(l, r, v));
}
ll getans(){
ll ans = 0;
for(auto [l, r, v] : tr){
for(int i = l; i <= r; ++i){
ans += max(v, (int)ss[i]);
}
}
return ans;
}
void work(){
scanf("%d%d", &n, &m);
scanf("%s", ss + 1);
tr.insert(ran(1, n, 0));
for(int i = 1; i <= m; ++i){
char p[3];
scanf("%d%d", &l, &r);
scanf("%s", p);
s[(int)p[0]].push_back(m_p(l, r));
}
for(int i = 33; i <= 126; ++i){
for(auto [l, r] : s[i]){
emerge(l, r, i);
}
}
printf("%lld\n", getans());
}
int main(){
work();
return 0;
}
京公网安备 11010502036488号