CODEFORCES ROUND 913 DIV.3

第一次的cf rated赛

打得依托构思

A.ROOK

给出国际象棋中的车在棋盘中的棋谱位置，求出其能移动到的所有地方。

水模拟

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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define int long long
// int a[100001];
int t;
signed main() {
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        for (int i = 1; i <= 8; i++) {
            if (i == s[1] - '0')
                continue;
            cout << s[0] << i << endl;
        }
        for (int i = 0; i < 8; i++) {
            if (i == s[0] - 'a')
                continue;
            cout << char(i + 'a') << s[1] << endl;
        }
    }
    return 0;
}

B.YetnotherrokenKeoard

给出几串输入字符串，当按下“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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
#define int long long
// int a[100001];
int t;
int m[1000010];
stack<int> upper;
stack<int> lower;
signed main() {
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != 'b' && s[i] != 'B') {
                if (isupper(s[i]))
                    upper.push(i);
                else if (islower(s[i]))
                    lower.push(i);
            } else {
                if (!lower.empty() && s[i] == 'b')
                    lower.pop();
                else if (!upper.empty() && s[i] == 'B')
                    upper.pop();
            }
        }
        while (!upper.empty()) {
            m[upper.top()] = 1;
            upper.pop();
        }
        while (!lower.empty()) {
            m[lower.top()] = 1;
            lower.pop();
        }
        for (int i = 0; i < s.length(); i++) {
            if (m[i])
                cout << s[i], m[i] = 0;
        }
        cout << endl;
    }
    return 0;
}

C.Removal of Unattractive Pairs

给出几串字符串，若某相邻的两个字符不同，则可以将它们从字符串中移除，求出每个字符串能达到的最小长度。

引理：若两个字符串除了排列顺序以外其余因素完全相同，则该两个字符串的最小长度及其对应的排列相同。

证明：考虑归纳证明，设 $a_i $为长度为 $i $的字符串 $a $所能达到的最小长度对应的字符串。

当 $n=1,2 $时显然成立；

假设当 $n=k $时成立，最平凡的情况即为每个字符相等，这种情况的正确性是显然的。假若非平凡，则有 $a_{k}=b_{k} $，其中 $b $为除 $a $以外的任意一种排列。当 $n=k+1 $时，对 $a,b $增添的字母必然一致，设为 $s $。考虑到 $a $的任意性，不妨让 $a $在其左端添上 $s $成为 $sa $，（这是因为若需要在中间插入，则可以由另外一串字符串来证明），那么对 $b $可以进行任意变换，使 $sa = b's $，则根据 $nk $的假设，引理得证。 $$

那么我们可以将每个字符串重排成一种形状：左端放满其包含最多的字符串，其余放在右端 $ LLLLLLx_1x_2$

那么我们可以从中间开始消消乐，关于最小长度的结论就是显然的了。

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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
using namespace std;
#define int long long
// int a[100001];
int m[30];
int t;
deque<char> p;
signed main() {
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        for (int i = 0; i < n; i++) {
            m[s[i] - 'a']++;
        }
        int tmp = 0;
        for (int i = 0; i <= 26; i++) {
            tmp = max(tmp, m[i]);
        }
        if (n % 2) {
            if ((n + 1) / 2  <= tmp)
                cout << 2 * (tmp - (n + 1) / 2) + 1 << endl;
            else
                cout << 1 << endl;
        } else {
            if ((n) / 2  <= tmp)
                cout << 2 *(tmp - n / 2) << endl;
            else
                cout << 0 << endl;
        }
        memset(m, 0, sizeof(m));
    }
    return 0;
}

D.Jumping Through Segments

按顺序给出一些区间，最小化每步都能跳到该步对应的区间中的步长的最大值，初始在零点。

容易知道是二分。

考虑chk的写法：每次跳至的位置设置成一个区间，区间下限、上限均为相对于题给区间合法的上下限，若区间不合法(l>k)即为false，否则为true。

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
#pragma GCC optimize(2)
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;
#define int long long
int n,t;
struct p{
    int l,r;
}a[1000001];

int chk(int x){
    int l = 0,r = 0;
    for(int i = 1;i <= n;i ++){
        l -= x,r += x;
        l = max(l,a[i].l);
        r = min(r,a[i].r);
        if(l > r) return 0;
    }
    return 1;
}

signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1;i <= n;i ++){
            scanf("%d%d",&a[i].l,&a[i].r);
        }
        int l = 0,r = 1e9 + 10;
        int ans = 0;
        while(l < r){
            int mid = (l + r) >> 1;
            if(chk(mid)) ans = mid,r = mid;
            else l = mid + 1;
        }
        cout<<ans<<endl;
    }
}

E.Good Triples

给定若干个数 $n $，求满足 $a+b+c=n $以及 $a,b,c $的各位和与 $n $的各位和相等的三元有序数对 $(a,b,c) $的个数。

命题：满足题述条件的数对个数 $ S=_{i=1}^{O(n)}() $

其中 $n_i $为 $n $的十进制数对应位数 $i $的数值， $O(n) $为 $n $的最高位数。

证明：注意到所有对于 $a,b,c,n $的各位和相等的等式均能拆成唯一一种按位排列的情形（位数不足时用0补足），即： $ a_1 +b_1+c_1=n_1,a_2+b_2+c_2=n_2,$

并且上式每位数按对应位数进位后完全契合 $a+b+c=n $，根据乘法原理，总情况数即为每位数对应分解情况数的乘积，即问题化归到求10以内的分解情况。

对0而言，只有唯一一种分解情况；当为 $1 $时，有三种分解情况；为2时，有六种分解情况；猜想对于 $n $，分解情况为 $_{i=1}^{1+n}i $，下面归纳证明。 $n=0 $情形已枚举；

假设 $n=k,n<9 $时成立，则当 $ n=k+1 $时，考虑对 $n=k $的每种情况的数对第一位加一，皆符合分解式，只缺少第一位为0的情况，即 $(0,x,y),x+y=k $，这样的数对共有0到 $k $共 $k+1 $种，这就完成了归纳证明，同时完成了命题的证明。 $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
using namespace std;
#define int long long
// int a[100001];
int t, n;
signed main() {
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int ans = 1;
        for (int i = 1e7; i >= 1; i /= 10) {
            ans *= ((n / i + 1) * (n / i + 2)) / 2;
            n %= i;
        }
        cout<<ans<<endl;
    }
    return 0;
}

F.Shift and Reverse

给出一些数列，考虑只用头尾翻转和用头接尾两种方法能不能将该数列按照非降序排序，并求出排序步数最小值。

引理：将该序列看成一个尾连头的环，即 $(a_1,a_2,,a_n,a_1,) $，若其中不重复的向右相邻的顺序与逆序的数量的最小值比1大，则无法做出排序。

证明：若能注意到顺序逆序总和为 $n $以及逆向构造：1.翻转让顺逆序数互换；2.尾接头最多构造出1个顺/逆序，那么结论是显然的。 $$

那么若能排序，则可以考虑逆向构造，在已排序环的第一第二节里截出满足与目标序列相同或只差一次翻转的序列后将需移动位置和反转次数相加，取极小即可。

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 <cmath>
#include <iostream>
using namespace std;
int t, n;
int a[100001];
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        int p = 0, q = -1, ans = 0x7fffff;
        for (int i = 0; i < n; i++) {
            if (a[i] > a[(i + 1) % n]){
                p++;q = i + 1;
            }
        }
        //cout<<p<<" ";
        if (p == 0)
            ans = 0;
        else if (p == 1) {
            int tmp = min(q + 2, n - q);
            ans = min(ans, tmp);
        }
        p = 0,q = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] < a[(i + 1) % n]){
                p++;q = i + 1;
            }
        }
        //cout<<p<<" ";
        if (p == 0)
            ans = 0;
        else if (p == 1) {
            int tmp = min(q + 1, n - q + 1);
            ans = min(ans, tmp);
        }
        if (ans == 0x7fffff)
            ans = -1;
        cout << ans << endl;
    }
    return 0;
}

G.Lights

给出一组灯的开关状态，以及一组数 $a_1,a_2,a_n $表示开关 $i $能改变 $i,a_i $两盏灯的状态，考虑能不能将灯全部关上，若能关上求出关上全部灯的最少步数。

注意到这里共有 $n $个开关， $n $个有向关系，可以建成一张有向图，且该图有且仅有一个环，其余的节点都为从环上衍生出去的链，那么可以考虑模拟将每个链上的灯的开关情况规整到环上，现在只需讨论环上的情况。很容易知道环上开灯的为奇数则无法关上，为偶数可以关上。

现在考虑怎么求最小值。其实只用求环上两个相邻开灯节点的距离最大值，然后避开这段反着扫一遍就是答案。

代码：改代码中