A.Maximize(枚举)

题意

每次给定一个正整数x,寻找一个y()，满足gcd(x,y)+y的值最大；若有多个y满足条件，则输出一个即可.

数据范围

思路

由于t和x的值域都极小，只需要对y进行暴力枚举并维护最大值即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int gcd(int a,int b){
    return b == 0 ? a : gcd(b, a % b);
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int x;cin >> x;
        int ans = 0, idx;
        for (int i = x-1; i >= 1;i--){
            int res = gcd(x, i) + i;
            if(res > ans)
                ans = res, idx = i;
        }
        cout << idx << endl;
    }
    return 0;
}

B.Prefiquence(模拟)

题意

给定两个二进制字符串a和b（只含”0”和”1”）。确定最大可能数k，使得长度为k的字符串是a的前缀子串中，同时a的前缀又是字符串b的子序列。

数据范围

思路：

由于所求字符串长度是a的前缀，而且又是b的子序列，在遍历a的同时遍历b，直到两个字符相同，使用不需要维护任何信息的双指针即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
char a[200010],b[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n, m;cin >> n >> m;
        cin >> a + 1 >> b + 1;
        int cnt = 0;
        for (int l = 1, r = 1; l <= n; l++, r++)
        {
            while (r <= m && a[l] != b[r])r++;
            if (r == m + 1)break;
            cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

C.Assembly via Remainders(构造)

与其是构造题，不如说是偷鸡(bushi)

题意

给定一个正整数序列x=(,,…,),去寻找一个合法的数组a,满足以下条件：

  • mod ,其中

若有多个答案满足条件，则输出一个即可.

数据范围

思路

因为 mod ,其中;首先，必须要排除掉为零的可能，比如样例4，501 mod 1 500，因为两个数能整除，取余为零；所以不妨让非常大，以至于任何数取模都一定等于其两者差值。因为范围最高仅有500，所以设起始的为1e8,接下来,每个数递增增加，即 .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> x(n + 1), a(n + 1);
        for (int i = 1; i < n; i++)
            cin >> x[i];
        a[1] = 1e8;
        for (int i = 2; i <= n; i++)
            a[i] = a[i - 1] + x[i - 1];
        for (int i = 1; i <= n; i++)
            cout << a[i] << ' ';
        cout << endl;
    }
    return 0;
}

D.Permutation Game(贪心)

题意

Bodya 和 Sasha 找到了一个排列,,…,和一个数组,,…,.他们俩都选择了起始位置和,游戏持续k轮，在每一轮，每个玩家都会有两个动作：

  • 如果玩家当前位置是x,则他的得分增加
  • 然后玩家要么停留在当前位置x，要么从x移动到位置

两者都采用最佳策略，问经过k轮后，最终的赢家是谁?

数据范围

思路

    题目限定p数组是一个排列，所以如果每轮加完分不断选择往前走，最终一定是一个环（不一定能走完所有点），或者当遇到 p[i]=i 时，接下来只能堵死在该点；
    从贪心的角度考虑，因为每次走到一个位置都可以选择停留或者继续寻找最佳加分位置，容易想到，如果能够找到所有能遍历到的点的最大值，则接下来一定每轮停留在此处最优；但同时，如能到达最优点但所剩轮数极少，且中途经过好多加分很少的位置，那么可能还不如在加分较大点一直停留。
    所以我们遍历这个环，假设经过轮数是cnt,目前的总得分是res,当前位置是x,则走到当前位置的最大值应为 ,接下来，我们只需要对每个位置进行维护最大值的操作。同时，不能对每一轮进行遍历，因为k的范围高达，只需要开一个bool数组判断环上该点是否被遍历过.

Code:

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<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int p[200010], a[200010];
bool vis[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n, k, pa, pb;
        cin >> n >> k >> pa >> pb;
        for (int i = 1; i <= n;i++)cin >> p[i];
        for (int i = 1; i <= n; i++)cin >> a[i];
        int ans1 = 0, ans2 = 0, res = 0, cnt = 0;
        while (!vis[pa] && cnt < k){
            vis[pa] = 1, cnt++;
            res += a[pa];
            ans1 = max(ans1, res + (k - cnt) * a[pa]);
            pa = p[pa];
        }
        for (int i = 1; i <= n;i++)vis[i] = 0;
        res = 0, cnt = 0;
        while (!vis[pb] && cnt < k){
            vis[pb] = 1, cnt++;
            res += a[pb];
            ans2 = max(ans2, res + (k - cnt) * a[pb]);
            pb = p[pb];
        }
        for (int i = 1; i <= n; i++)vis[i] = 0;
        //cout << ans1 << ' ' << ans2 << ' ' << endl;
        if(ans1 > ans2)
            cout << "Bodya" << endl;
        else if(ans1 < ans2)
            cout << "Sasha" << endl;
        else
            cout << "Draw" << endl;
    }
    return 0;
}

E.Cells Arrangement

本人观察样例得到的取巧做法，个人感觉比较麻烦，不过代码确实能AC过本题。解题思路主要是从题目所给的样例n=6得到启示.

题意

给定一个整数n，在网格的网格中选择n个不同单元格，最大化任意单元格之间的不同曼哈顿距离，如下图所示.

数据范围


  • Image

    思路1

        首先，一张网格的最大曼哈顿距离一定是处于对角两边形成的唯一最大值，所以曼哈顿距离的种类数最大也是加上本身的零。以n=6为例，其符合条件的距离为0,1,2,3,4,5,6,7,8,9,10.当我们放置对角两个以及某一角落的相邻两个时，剩下需要找的距离为0,1,2,3,4,5,6,7,8,9,10.

        正是因为有临接在角落的三个，所以我们每次按三格单位距离向下倒推退，就一定会有三个从小到大的距离满足！如图，假设现有的棋子位居(1,1),(1,2),(1,3),(6,6)，那我们现在右下移动{2,1}格距离，也就是(3,4)格放置，此时剩下要找的距离为0,1,2,3,4,5,6,7,8,9,10.同理，再在(5,5)格放置棋子，此时所有距离均能满足，且棋子数正好达到6，实现了最大化的要求.

        然而，当n增加时，因为每次向下跨越两格，极有可能在纵向无法摆放的情况下，棋子数尚未使用完，同时也未能满足所有的曼哈顿距离；所以我们可以对剩余的棋子从(n,n)处往上开始摆，往左上移动{-2,-1}的距离，这样既能够摆完所有的棋子（因为纵向大约有2*n的空间），又能满实现曼哈顿距离从大到小的满足，恰好与前者进行互补.

    Code1:

    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<bits/stdc++.h>
    #define int long long
    #define endl '\n' 
    using namespace std;
    signed main(){
        std::ios::sync_with_stdio(false);cin.tie(0);
        int t;cin >> t;
        while(t--){
            int n;cin >> n;
            if(n==2){
                cout << "1 1" << endl;
                cout << "2 1" << endl;
                continue;
            }else if(n==3){
                cout << "2 3" << endl;
                cout << "2 1" << endl;
                cout << "3 1" << endl;
                continue;
            }else if(n==4){
                cout << "4 4" << endl;
                cout << "4 3" << endl;
                cout << "1 3" << endl;
                cout << "1 1" << endl;
                continue;
            }
            cout << "1 1" << endl;
            cout << "1 2" << endl;
            cout << "1 3" << endl;
            cout << n << ' ' << n << endl;
            int m = n;
            m -= 4;
            int x = 1, y = 3 ,i;
            for(i = 1; i <= m; i++){
                x += 2, y++;
                cout << x << ' ' << y << endl;
                if(x + 2 > n)break;
            }
            if(i == m + 1)continue;
            x = n, y = n;
            for (int j = i + 1; j <= m; j++){
                x -= 2, y--;
                cout << x << ' ' << y << endl;
            }
        }
        return 0;
    }

    思路2（极简）

        在的棋盘中摆放n个棋子，可以试着摆满对角线，即(1,1),(2,2),…,(n,n),不难发现，此时所有偶数的曼哈顿距离全部满足，只需要对其中一个棋子进行距离为1的移动即可构造出奇数的距离，我们将(2,2)向上移动到(1,2)的位置，此时一定满足所有的情况.
        不过需要注意的是，当时，网格实在太小，直接打表即可.

    Code2:

    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>
    #define int long long
    #define endl '\n' 
    #define INF 1e15
    using namespace std;
    typedef pair<int,int>pii;
    signed main(){
        std::ios::sync_with_stdio(false);cin.tie(0);
        int t;
        cin >> t;
        while(t--){
            int n;
            cin >> n;
            if (n == 2){
                cout << "1 1" << endl;
                cout << "2 1" << endl;
                continue;
            }
            else if (n == 3){
                cout << "2 3" << endl;
                cout << "2 1" << endl;
                cout << "3 1" << endl;
                continue;
            }
            cout << "1 1" << endl;
            cout << "1 2" << endl;
            for (int i = 3; i <= n;i++)
                cout << i << ' ' << i << endl;
        }
        return 0;
    }

    F.Equal XOR Segments

    待补

    G1.Division + LCP (easy version) (二分+字符串哈希)

    题意

    给定一个字符串 s，对于固定的 k（本题k=l=r），考虑将s划分为恰好k个长度任意的连续字符串。求可能的最大公共前缀的长度.

    数据范围

思路

    由于求的是最值，考虑二分答案，发现答案确实具有单调性。假设公共前缀长度为x，只需要满足对于字符串s,从下标开始至少出现过k-1次，其余多余或无效的部分当做有效前缀字符串的后缀即可。但是此时使用二分的复杂度已经达到O（ ）,所以判断长度为x的字符串必须用O(1)的复杂度进行查询.这题就演变为了字符串哈希求区间子串的模板题.
    注意：字符串哈希最好使用大质数取模的双哈希，单哈希或自然溢出极容易被卡，笔者就被在第82个测试点被卡了

Code:

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
char s[200010];
int Hash1[200010], Hash2[200010], pw1[200010],pw2[200010];
const int base1 = 1313131, base2 = 233333;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while (t--){
        int n, l, r;
        cin >> n >> l >> r;
        cin >> s + 1 ;
        int len = strlen(s + 1);
        pw1[0] = pw2[0] = 1;
        Hash1[0] = Hash2[0] = 0;
        for (int i = 1; i <= len; i++){
            Hash1[i] = (Hash1[i - 1] * base1 % p1 + (s[i] - 'a' + 1)) % p1;
            Hash2[i] = (Hash2[i - 1] * base2 % p2 + (s[i] - 'a' + 1)) % p2;
            pw1[i] = (pw1[i - 1] * base1) % p1;
            pw2[i] = (pw2[i - 1] * base2) % p2;
        }
        auto getHash1 = [&](int a, int b) -> int{
            return (Hash1[b] - Hash1[a - 1] * pw1[b - a + 1] % p1 + p1) % p1;
        };
        auto getHash2 = [&](int a, int b) -> int{
            return (Hash2[b] - Hash2[a - 1] * pw2[b - a + 1] % p2 + p2) % p2;
        };
        int L = 1, R = len, ans = 0;
        auto check = [&](int x) -> bool{
            int val1 = Hash1[x] % p1, val2 = Hash2[x] % p2;
            int cnt = 1;
            for (int i = x + 1; i + x - 1 <= len;i++){
                if (getHash1(i, i + x - 1) == val1 && getHash2(i, i + x - 1) == val2){
                    cnt++;
                    if(cnt==l)return 1;
                    i += x - 1;
                }
            }
            return 0;
        };
        if(l==1){ //此时整个字符串就是最大公共前缀长度
            cout << len << endl;
            continue;
        }
        while(L <= R){
            int mid = L + R >> 1;
            if(check(mid))
                L = mid + 1, ans = mid;
            else
                R = mid - 1;
        }
        cout << ans << endl;
    }
    return 0;
}