题意
给出一个由 A,B,C,D,E 组成的字符串，每个字符分别代表 1,10,100,1000,10000。若该位置的后缀没有比它大的字符，其贡献为它所代表的数。否则，其贡献为负。现在可以修改一个位置上的字符，求可能的贡献最大值。
题解
我们修改一个位置有两种目的：
- 让该位置的字符变大，使得其贡献增加。
- 让该位置的字符变小，使得其前面的字符贡献增加。
对于第一种目的，我们选取每个字符第一次出现的位置；对于第二种目的，我们选取每个字符最后一次出现的位置。所以，需要枚举的量不太多，直接暴力计算取最大值就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
using namespace std;
int n,v[]={1,10,100,1000,10000};
vector<int> pos[5];
string s;
int solve()
{
int ans=0,mx=-1;
for(int i=n-1;i>=0;i--)
{
int c=s[i]-'A';
if(c<mx) ans-=v[c];
else ans+=v[c];
mx=max(mx,c);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
cin>>s;
n=(int)s.size();
for(int i=0;i<5;i++) pos[i].clear();
for(int i=0;i<n;i++)
{
int c=s[i]-'A';
pos[c].push_back(i);
}
int ans=solve();
for(int i=0;i<5;i++)
{
if(pos[i].empty()) continue;
for(int j=0;j<5;j++)
{
s[pos[i][0]]=char('A'+j);
ans=max(ans,solve());
s[pos[i][0]]=char('A'+i);
s[pos[i].back()]=char('A'+j);
ans=max(ans,solve());
s[pos[i].back()]=char('A'+i);
}
}
cout<<ans<<'\n';
}
return 0;
}
|
题意
给定一些线段 [li,ri]。要求删去一些线段，使得剩余的线段可以两两配对，且满足：
求删去线段的最小数量。
题解
考虑 [l1,r1] 和 [l2,r2] 相交，[l3,r3] 和 [l4,r4] 相交。如何检验其它的线段对不交呢？由于 [l1,r1] 和 [l2,r2] 相交，它们的并也是一条线段，即 [min(l1,l2),max(r1,r2)]。检验它与 [min(l3,r3),max(l4,r4)] 是否相交即可。
所以可以考虑先求出所有相交的线段对，将它们的并得到的线段保存下来，然后选取尽可能多的线段且彼此不相交即可。若两个线段对包含了同一条线段，它们的并一定彼此相交，所以答案是正确的。而最终的选出的每一条线段，就代表了一个线段对。
如何选取尽可能多的线段是一个经典问题。可以用一个贪心的策略：将所有线段按右端点升序排序，维护已选择线段的最大右端点。如果当前线段的左端点大于最大右端点，就选择它，否则就不选。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
int l[2005],r[2005];
struct node
{
int l,r;
bool operator < (const node x) const {return r<x.r;}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
vector<node> v;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(max(l[i],l[j])<=min(r[i],r[j])) v.push_back({min(l[i],l[j]),max(r[i],r[j])});
}
sort(v.begin(),v.end());
int ans=0,r0=-1,m=(int)v.size();
for(int i=0;i<m;i++)
if(v[i].l>r0)
{
ans++;
r0=v[i].r;
}
cout<<n-2*ans<<'\n';
}
return 0;
}
|
题意
给出一个 n×n 的网格，每一列的前 ai 个位置不能填数。要求将 1∼m 填入这些方格，要求有尽可能多的相邻的数在网格中左右相邻。求这样的数对的最大值。
题解
很容易发现，我们要在更长的线段中填入相邻的数。所以，我们需要维护长度为 i 的线段出现的次数。
我们倒过来遍历，一开始是一个长度为 n 的线段。然后可能有某一列将它分割为了两条短线段，我们维护线段的端点加入的时间，就可以得到它存在的时间（实际就是有几行这样的线段）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int tim[maxn];
ll cnt[maxn];
vector<int> pos[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=0;i<=n;i++) cnt[i]=0,pos[i].clear();
for(int i=1;i<=n;i++)
{
int x;cin>>x;
pos[x].push_back(i);
}
set<int> s;
s.insert(0),s.insert(n+1);
tim[0]=tim[n+1]=n;
for(int i=n;i>=0;i--)
{
for(auto x:pos[i])
{
auto it=s.lower_bound(x);
int pre=*prev(it);
int nxt=*it;
cnt[nxt-pre-1]+=min(tim[pre],tim[nxt])-i;
s.insert(x);
tim[x]=i;
}
}
ll m;cin>>m;
ll ans=0;
for(int i=n;i;i--)
{
ll x=min(cnt[i],m/i);
ans+=x*(i-1);
cnt[i]-=x;
cnt[i-1]+=cnt[i];
m-=x*i;
}
cout<<ans<<'\n';
}
return 0;
}
|