2021 ICPC Southeastern Europe Regional Contest（更新至五题）

2021 ICPC Southeastern Europe Regional Contest

A题签到

A. King of String Comparison

题意：给两个字符串，找出有多少对（l，r），满足在l到r区间内，s1的子串字典序小于s2的子串字典序。

思路：一眼题，首字母满足字典序小后面拼上的都小，格外注意前方有好多字母字典序一致的情况。
比如:
aaaabcd
aaaacde

维护一个l和一个r，l到r为可以选择的左端点，r到n为可以选择右端点，双指针扫描即可。
特别要注意不要让你选择区间重复。

#include
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5+100;

char s[N],t[N];
signed main()
{
    int n;
    cin>>n;
	cin>>(s+1)>>(t+1);
	int ans=0ll;
	for(int l=1,r=1;r<=n&&l<=n;r++)
    {
        if(s[r]<t[r])
        {
            ans+=(r-l+1)*(n-r+1);
            l=r+1;
        }
        if(s[r]>t[r])
        {
            l=r+1;
        }
    }
    cout<<ans;
	return 0;
}
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

F. to Pay Respects

题意：勇者斗恶龙

进行n回合，每回合按如下顺序进行
1.恶龙可以吟唱治疗魔法
2.勇者可以吟唱伤害魔法
3.勇者物理攻击
4.所有魔法生效.

对于魔法：
1.双方吟唱一次魔法，使得对应的效果层数加一
2.勇者吟唱魔法后，如恶龙有治疗魔法效果，则还会让治疗魔法效果层数减一

最终每轮造成的伤害为: 物理伤害+伤害魔法层数 * 伤害魔法数值-治疗魔法层数 * 治疗魔法数值

我们还会给出一个01串
如果此串第i项为1代表恶龙第i回合吟唱治疗魔法

问最大造成多少伤害

思路：唯一的一个点就是要知道，伤害魔法低效的治疗魔法的治疗效果可以视为伤害魔法造成的伤害。

所以第i回合魔法造成的伤害就是（n-i+1）*（p+r *（s[i]==‘1’））

#include 
#include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e6+100;

char s[N];
int ans[N];
bool cmp(const int &a,const int &b)
{
    return a>b;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n,x,r,p,k;
    cin>>n>>x>>r>>p>>k;
    cin>>(s+1);
    int res=x*n;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
        {
            ans[i]=(n-i+1)*(p+r);
            res-=(n-i+1)*r;
        }
        else
        {
            ans[i]=(n-i+1)*p;
        }
    }
    sort(ans+1,ans+n+1,cmp);
    for(int i=1;i<=k;i++)
    {
        res+=ans[i];
    }
    cout<<res<<endl;
    return 0;
}
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

G. Max Pair Matching

题意：给定2n个二元组，从里面调出n对二元组，每对的贡献是
求n对二元组的贡献总值最大是多少

思路：我们不妨先把max(…)里面的绝对值拆了，也就是二元组内部变得有序，满足a

然后如何使得n对的贡献最大呢？

我们知道如果让i去减j的二元组，那么如果想要保证取得较大的价值(相对于j减去i来讲)
就要满足bi-aj>bj-ai移项后就是bi+ai>bj+aj
所以排序后让前n个的b减去后n个的a即可。

#include 
#include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;

struct node
{
    int a,b;
};
bool cmp(const node &a,const node &b)
{
    return a.a+a.b<b.a+b.b;
}
node a[N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    n<<=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].a>>a[i].b;
        if(a[i].a>a[i].b)
            swap(a[i].a,a[i].b);
    }
    sort(a+1,a+n+1,cmp);
    int res=0;
    n>>=1;
    for(int i=1;i<=n;i++)
    {
        res+=a[i+n].b-a[i].a;
    }
    cout<<res<<endl;
    return 0;
}
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

J. ABC Legacy

括号排序好题
题意：给定一个仅包含’A’,‘B’,'C’的长度为2n的字符串，并且有如下配对规则‘AB’，‘BC’，‘AC’。
问整个字符串能否划分为n对。

思路:我们将A视为左括号，C视为右括号。B视为特殊括号。

统计A的个数，如果个数小于n，那么说明前n-cnta个B要变成特殊的左括号（对于括号匹配，我们有贪心结论：左括号越是靠左越容易匹配成功）

然后分别用两个栈来维护括号匹配即可。在匹配的过程中，如果还有需要变成左括号的B就进入到sb栈，碰到a进入sa站。如果已经不需要b变成做括号了，那么碰到B就用sa中的a去匹配，碰到c先用sb中的b去匹配，再用sa中的a去匹配，

#include 
#define endl '\n'
using namespace std;
const int N = 2e5+100;

char s[N];
pair<int,int> ans[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n;
    cin>>n;
    n<<=1;
    cin>>(s+1);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='A')
            cnt++;
    }
    cnt=n/2-cnt;
    if(cnt<0)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    stack<int> sa,sb,sc;
    int con=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='A')
        {
            sa.push(i);
        }
        if(s[i]=='B')
        {
            if(cnt)
            {
                cnt--;
                sb.push(i);
            }
            else
            {
                if(sa.empty())
                {
                    cout<<"NO"<<endl;
                    return 0;
                }
                ans[++con]={sa.top(),i};sa.pop();
            }
        }
        if(s[i]=='C')
        {
            if(sa.empty()&&sb.empty())
            {
                cout<<"NO"<<endl;
                return 0;
            }
            else if(!sb.empty())
            {
                ans[++con]={sb.top(),i};sb.pop();
            }
            else
            {
                ans[++con]={sa.top(),i};sa.pop();
            }
        }
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=con;i++)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<'\n';
    }
    return 0;
}
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

N. A-series

题意：有n种纸片，每种纸片的大小是下一种的两倍长，所以我们可以通过一次折叠将一张纸变成两张下一种纸。
现在给出现有的n中纸片个数和需要的n种纸片个数。
问：需要至少操作几次才能满足需求。（如果不能满足求则输出-1）

思路：没啥好讲的吧，非要说就是利用了减法的思维，这题其实可以改编成二进制减法。

#include 

using namespace std;
#define int long long
const int N = 2e5+100;
int a[N];
int b[N];
signed main()
{
    int n;
    cin>>n;
    n++;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    int cnt=0;
    for(int i=n;i>=1;i--)
    {
        if(b[i]>a[i])
        {
            if(i==1)
            {
                cout<<-1<<endl;
                return 0;
            }
            else
            {
                cnt+=(b[i]-a[i])/2+(b[i]-a[i])%2;
                b[i-1]+=(b[i]-a[i])/2+(b[i]-a[i])%2;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}
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

L. Jason ABC（前缀和+双指针)
题意：给定一个只由有ABC三种字母构成的字符串，你每次可以选择一段区间让这段区间的所有字母都变成某一个字母，问最少几次操作能够使得字符串中ABC三种字母的数目都是n

输出：一个正整数n
第二行：一个长度为3*n的字符串。

输出：第一行一个整数x代表需要的次数
接下来x行每行两个数字l r代表本次操作修改的区间，然后一个字母代表要变成什么字母。

思路：首先对于一个字符串到底需要几次才能变成符合要求的呢。
如果只修改一次那么必定就有这样一段区间满足如下条件
1.修改的这段区间字母变为 ‘X’（X为任意字母）
2.修改这段区间之后，区间之外的另外两个字母的出现次数一定是n（我们没有必要判断修改的这段区间是否是n长度，因为只要另外两个是n就能保证第三者是n）

如果修改两次，我们找到第一个位置pos，这个位置满足如下条件
1.从1到pos的区间内，某一个字母出现了n次

只要满足这个条件，我们就能把从pos到n的区域划分成两块来满足另外两个字母出现n次的条件。

分析之后发现并不需要再多的操作步骤了。
具体实现：利用前缀和+双指针维护区间即可。

#include 
 
using namespace std;
const int N = 3e6+100;
char s[N];
int cnt[3][N];
int n;
bool change(int c)
{
    int ans=c;
    for(int l=1,r=1;l<=n&&r<=n;)
    {
        if(l>r)
            r=l;
        while((cnt[(ans+1)%3][r]-cnt[(ans+1)%3][l-1]<cnt[(ans+1)%3][n]-n/3||cnt[(ans+2)%3][r]-cnt[(ans+2)%3][l-1]<cnt[(ans+2)%3][n]-n/3)&&r<=n)//必须满足这个区间包含的另外两个字母数量不能低于多出来的数值
            r++;
        if(cnt[(ans+1)%3][r]-cnt[(ans+1)%3][l-1]==cnt[(ans+1)%3][n]-n/3&&cnt[(ans+2)%3][r]-cnt[(ans+2)%3][l-1]==cnt[(ans+2)%3][n]-n/3)
        {
            cout<<1<<endl;
            cout<<l<<" "<<r<<" "<<(char)('A'+ans);
            return 1;
        }
        else
            l++;
    }
    return 0;
}
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>n;
    n*=3;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        cnt[0][i]=cnt[0][i-1]+(s[i]=='A');
        cnt[1][i]=cnt[1][i-1]+(s[i]=='B');
        cnt[2][i]=cnt[2][i-1]+(s[i]=='C');
    }
    if(cnt[0][n]==cnt[1][n]&&cnt[1][n]==cnt[2][n])
    {
        cout<<0<<endl;
        return 0;
    }
    else if(change(0)||change(1)||change(2))
    {
        return 0;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=2;j++)
            {
                if(cnt[j][i]==n/3)
                {
                    cout<<2<<endl;
                    cout<<i+1<<" "<<i+n/3-cnt[(j+1)%3][i]<<" "<<(char)('A'+(j+1)%3)<<endl;
                    cout<<i+n/3-cnt[(j+1)%3][i]+1<<" "<<n<<" "<<(char)('A'+(j+2)%3)<<endl;
                    return 0;
                }
            }
        }
    }
    return 0;
}

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

K. Amazing Tree（DFS+树）
待补
C. Werewolves（树形背包）
待补