比赛链接：Dashboard - 3.10 周赛 - Codeforces

A

题意：给出两个长为 $n$ 的字符串 $s$ ，$t$ ，找出满足如下的整数对 $(i,j)$ 的个数：子串 $s_is_{i+1}…s_l$ 字典序严格小于 $t_it_{i+1}…t_l$ 。

若在某一位满足 $s_i<t_i$ ，那么以 $i$ 为开头的所有整数对都满足；

若在连续多位 $s_i=t_i$ ，如果往后第一位不同的位上 $s_j<t_j$ ，那么以 $i$ 开头，至少以 $j$ 结尾是可行的。

那么只需要统计 $s_i=t_i$ 是下一个最近的不等位的情况即可。

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
#include<bits/stdc++.h>
using namespace std;
int p[200005];
int nxt[200005];
int main()
{
    int n;
    char s[200005],t[200005];
    cin>>n;
    cin>>s>>t;
    long long ans=0;

    for(int i=0;i<n;i++)
    {
        if(s[i]==t[i])p[i]=0;
        if(s[i]<t[i])p[i]=1;
        if(s[i]>t[i])p[i]=-1;
    }
    
    int tmp=0;
    for(int i=n-1;i>=0;i--)
    {
        if(p[i]==1)tmp=i;
        if(p[i]==-1)tmp=0;
        if(p[i]==0)nxt[i]=tmp;
    }

    // for(int i=0;i<n;i++)cout<<p[i]<<" ";cout<<endl;
    // for(int i=0;i<n;i++)cout<<nxt[i]<<" ";cout<<endl;

    for(int i=0;i<n;i++)
    {
        if(p[i]==-1)continue;
        if(p[i]==1)ans+=n-i;
        if(p[i]==0)
        {
            if(nxt[i]==0)continue;
            else ans+=n-nxt[i];
        }
    }
    cout<<ans;
    return 0;
}

F

题意：每轮游戏中有以下情况发生：

  1. BOSS可以选择吟唱Regeneration咒语
  2. 你可以选择吟唱Poison咒语
  3. 你可以用剑进行攻击，并造成XXX点伤害
  4. 所有负面效果生效

每层Regeneration可叠加一层回复r，每层Poison可叠加一层毒p，若在boss发动Regeneration时发动Poison可以时Regeneration层数减一。告诉回合数与每回合BOSS是否Regeneration以及可以发动Poison的总次数，求BOSS减少的最大血量。

太妙的贪心辣

以BOSS是否回血进行分段，可以得出以下结论：

  1. 在BOSS回血的当回合采用Poison比在以后任一回合采用Poison更优；
  2. 在BOSS回血后的第一回合采用Poison比在第二回合采用Poison更优；

故采用双指针，head指向第一个BOSS没回血的回合，tail指向第一个BOSS回血的回合，比较在哪个回合下毒贡献最大。后续head往后移到下一个回合，tail移到下一个BOSS回复的回合。多余的次数从头依次下毒。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,X,r,p,k;
int ans;
int cnt,bos[N];
char s[N];
signed main(){
    scanf("%lld%lld%lld%lld%lld",&n,&X,&r,&p,&k);
    scanf("%s",s+1);
    ans=n*X;
    for(int i=1;i<=n;++i) if(s[i]=='1')  ans-=(n-i+1)*r;  
    int x=1,y=1;
    while(s[y]=='0'&&y<=n)  ++y;
    while(s[x]=='1'&&x<=n)  ++x;
    for(int tot=1;x<=n+1&&y<=n+1&&tot<=k;++tot){
        // cout<<x<<" "<<y<<" "<<(n-x+1)*p<<" "<<(n-y+1)*(p+r)<<" "<<tot<<endl;
        if((n-x+1)*p<(n-y+1)*(p+r)){
            ans+=(n-y+1)*(p+r);
            ++y;
            while(s[y]=='0'&&y<=n)    ++y;
        }
        else{
            ans+=(n-x+1)*p;
            ++x;
            while(s[x]=='1'&&x<=n)  ++x;
        }
    }
    printf("%lld",ans);
}

greedy，双指针

G

题意：有 $2n$ 个点，每个点表示为 $(a_i,b_i)$ ，把它们分成 $n$ 对，使得 $\sum max(|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|$ 最大。

真是 蠢死辣

保证每个点的 $a$ 大于 $b$ ，那么两个点的最大值即为 $max(a_i-b_j,a_j-b_i)$ ，若前项大于后项，移项得 $a_i+b_i>a_j+b_j$ ，故按照和排序，前 $n$ 个点选 $a$ ，后 $n$ 个点选 $b$ 。

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
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 200010;
int n;
struct node
{
    LL a, b;
    LL sum;
}f[N];

bool cmp(node x, node y)
{
    if(x.sum > y.sum) return 1;
    return 0;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n * 2; i ++)
    {
         scanf("%lld%lld",&f[i].a, &f[i].b);
         if(f[i].a < f[i].b) swap(f[i].a, f[i].b);
         f[i].sum = f[i].a + f[i].b;
    }

    sort(f + 1, f + 1 + 2 * n, cmp);
    //for(int i =1; i <= 2 * n; i ++) cout << f[i].a << ' ' << f[i].b << ' ' << f[i].sum << endl;
    LL suma = 0, sumb = 0;
    for(int i = 1; i <= n; i ++) suma += f[i].a;
    for(int i = n + 1; i <= 2 * n; i ++) sumb += f[i].b;

    printf("%lld\n", suma - sumb);
    return 0;

}

greedy

J

题意： 将一个长 $2n$ 的只包含 $ABC$ 串分成 $n $ 个子串，相对顺序不变，但是分出来的子串只能是 $AB,BC,AC$ 三者之一。求是否可行并求分解方案。

全是贪心哈哈

首先考虑把 $B$ 分配完。注意到条件特征， $B$ 既可以和 $A$ 结合，也可以和 $C$ 结合，那么当 $B$ 全部分配后剩下的 $A$ 和 $B$ 数量应该相等。将 $A$ ，$B$ ，$C$ 出现的下标分别储存下来，因为最后 $A$ ，$C$ 结合时要保证 $A$ 的下标要比 $B$ 小，故在处理 $B$ 时贪心策略如下：

  1. 与 $A$ 结合时应尽量消去 $A$ 较大的元素，即用 $B$ 最大的元素去消去能消去的 $A$ 最大的元素。
  2. 与 $C$ 结合时应尽量消去 $C$ 较大的元素，即用 $B$ 最大的元素去消去能消去的 $C$ 最小的元素。
  3. 最后 $AC$ 依次配对。
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# include <bits/stdc++.h>
# pragma GCC optimize(3)
using namespace std;
const int N = 200010;
char str[N];
vector<pair<int,int>>ans;
int n;

int main()
{
    set<int>A,B,C;
    scanf("%d%s", &n, str + 1);
    for(int i = 1; i <= n * 2; i ++)
    {
        if(str[i] == 'A') A.insert(i);
        else if(str[i] == 'B') B.insert(i);
        else C.insert(i);
    }
    
    int cnt1 = A.size(), cnt2 = B.size(), cnt3 = C.size();
    if(cnt1 > n || cnt3 > n) printf("NO\n");
    else
    {
        int b1 = n - cnt1, b2 = n - cnt3;
        for(int i = 0; i < b1; i ++)
        {
            int t = *(B.begin());
            auto it = C.lower_bound(t);
            if(!C.empty() && it != C.end())
            {
                int k = *it;
                B.erase(t), C.erase(k);
                ans.push_back({t, k});
            }
            else 
            {
                printf("NO\n");
                return 0;
            }
        }

        for(int i = 0; i < b2; i ++)
        {
            int t = *(--B.end());
            auto it = A.lower_bound(t);
            if(!A.empty() && it != A.begin())
            {
                int k = *(-- it);
                B.erase(t), A.erase(k);
                ans.push_back({k, t});
            }
            else
            {
                printf("NO\n");
                return 0;           
            }
        }

        int ss = A.size();
        for(int i = 0; i < ss; i ++)
        {
            int t = *(A.begin());
            auto it = C.lower_bound(t);
            if(it != C.end())
            {
                int k = *(it);
                A.erase(t), C.erase(k);
                ans.push_back({t, k});
            }
            else
            {
                printf("NO\n");
                return 0;
            }
        }

        printf("YES\n");
        for(auto c : ans) printf("%d %d\n", c.first, c.second);
    }
    return 0;
}

greedy

L

题意：给一个长度为 $3n$ 的只含有 $ABC$ 的字符串，现要得到的字符串中每个字母出现的次数均为 $n$ 次，可以进行如下操作：选择某个连续子串并将这个子串所有字母变成同一个字母。求最小操作方案。

贪死我辣

首先可以想到最多操作两次。首先预处理某一位置之前每个字母出现次数。分为以下情况：

  1. 不需要操作。
  2. 操作1次：将某一段子串变成某一字母后，另两种字母的数量均为 $n$ ，可以用双指针处理。
  3. 操作2次：当第一次某一字母出现 $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
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n;
int cnt[N][4];
char s[1000006];

bool change1(char c)
{
    int x = (c - 'A' + 1) % 3 + 1, y = (c - 'A' + 2) % 3 + 1;
    for(int l = 1, r = 1; l <= 3 * n; ){
        if(l > r) r = l;
        while((cnt[r][x] - cnt[l - 1][x] < cnt[3 * n][x] - n || cnt[r][y] - cnt[l - 1][y] < cnt[3 * n][y] - n) && r <= 3 * n) r++;
        if(cnt[r][x] - cnt[l - 1][x] == cnt[3 * n][x] - n && cnt[r][y] - cnt[l - 1][y] == cnt[3 * n][y] - n){
            return cout << 1 << endl << l << ' ' << r << ' ' << c << endl, true;
        }
        else l++;
    }
    return false;
}

void change2 (char c, int maxc)
{   
        int x = (c - 'A' + 1) % 3, y = (c - 'A' + 2) % 3;
        char X = x + 'A', Y = y + 'A';
        cout << 2 << endl;
        cout << maxc + 1 << ' ' << maxc + n - cnt[maxc][x + 1]  << ' ' << X << endl;
        cout << maxc + n - cnt[maxc][x + 1] + 1 << ' ' << 3 * n << ' ' << Y << endl;

}

int main()
{
    cin >> n;
    
    for(int i=1;i<=3*n;i++)cin>>s[i];

    for(int i = 1; i <= 3 * n; i++)
    {
        for(int j = 1; j <= 3; j++) cnt[i][j] = cnt[i - 1][j];
        if(s[i] == 'A') cnt[i][1]++;
        if(s[i] == 'B') cnt[i][2]++;
        if(s[i] == 'C') cnt[i][3]++;
    }

    if(cnt[3 * n][1] == cnt[3 * n][2] && cnt[3 * n][2] == n)
    {

        cout << "0\n";
        return 0;
    }

    if(change1('A') || change1('B') || change1('C')) return 0;
    // int maxc = 0;
    // char maxch;
    // for(int i = 1; i <= 3 * n; i++) if(!maxc && cnt[i][s[i]-'A' + 1] == n) maxc = i, maxch = s[i];
    // change2(maxch, maxc);
    for(int i = 1; i <= 3 * n; i++) if(cnt[i][s[i]-'A' + 1] == n){change2(s[i], i);break;}
    return 0;
}
 

双指针