Codeforces Round 913 Div. 3 题解

发表于 更新于 分类于 ，

题目链接：https://codeforces.com/contest/1907

A. Rook

难度：800

根据输入，循环输出行和列并跳过棋子所在位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int t,a;
char c;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        scanf("\n%c%d",&c,&a);
        F(i,1,8)
            if (i!=a) CO c<<i L;
        F(i,97,104)
            if (i!=c) CO (char)i<<a L;
    }
    return 0;
}

B. YetnotherrokenKeoard

难度：1000

遇到字符b时，删除其前面离他最近的一个小写字母，如果没有就不删除。遇到字母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
39
40
41
42
43
44
45
46
int t,ans[1000006];
string s;
stack<int> A,a;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI s;
        F(i,0,s.size()-1)
        {
            if (s[i]=='b')
            {
                if (!a.empty()) a.pop();
            } 
            elif (s[i]=='B')
            {
                if (!A.empty()) A.pop();
            }
            else
            {
                if (s[i]>='A'&&s[i]<='Z') A.push(i);
                else a.push(i);
            }
        }
      
        clear(ans);
        int t=0;
        while (!a.empty())
        {
            ans[t++]=a.top();
            a.pop();
        }
        while (!A.empty())
        {
            ans[t++]=A.top();
            A.pop();
        }
        sort(ans,ans+t);
        F(i,0,t-1)
            CO s[ans[i]];
        CL
    }
    return 0;
}

C. Removal of Unattractive Pairs

难度：1200

用桶来统计每个字母出现的次数，如果没有字母超过总数的一半，则总会被消除掉，如果超过了一半，则肯定有一部分该字母无法被消除掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int t,n,a[26];
string s;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        clear(a);
        CI n;
        CI s;
        F(i,0,n-1)
            a[s[i]-97]++;
      
        int m=0;
        F(i,0,25)
            m=max(m,a[i]);
        CO max(n%2,2*m-n) L;
    }
    return 0;
}

D. Jumping Through Segments

难度：1400

本题需要用二分查找，来找到一个最小的k。对于二分查找中的检查函数，可以求出人在当前k值下的移动范围与目标范围的交集，下一次以该交集为基础，求出人的最大移动范围与目标范围的交集并不断进行该步骤，如果其中任意一次求交集时发现并不存在交集，即人无法移动到目标位置，则当前k值无法得到答案。

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
LL t,n,a[200005],b[200005];

int check(LL k)
{
    LL l=0,r=0;
    F(i,1,n)
    {
        l=max(l-k,a[i]);
        r=min(r+k,b[i]);
        if (l>r) return 0;
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        F(i,1,n)
            CI a[i]>>b[i];
        LL l=0,r=1e9;
        while (l<=r)
        {
            LL mid=(l+r)/2;
            if (check(mid)) r=mid-1;
            else l=mid+1;
        }
        CO l L;
    }
    return 0;
}