A. Sakurako's Exam

签到，优先考虑\(2\)之间互相加减，所以只会剩下最多一个\(2\)，用\(2\)个\(1\)来消除，最后判断剩下\(1\)的个数即可

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

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int a, b;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> a >> b;
        b %= 2;
        a -= b * 2;
        if (a < 0 || a % 2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

B. Square or Not

根据题意，输入的\(01\)串实际上就是把矩阵按行拼接到一起，手动模拟是否符合要求即可

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
string s;

void solve()
{
    cin >> n >> s;

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (mid * mid < n) l = mid + 1;
        else r = mid;
    }

    if (l * l != n)
    {
        cout << "No" << endl;
        return;
    }

    for (int i = 0; i < l; i++)
        if (s[i] == '0')
        {
            cout << "No" << endl;
            return;
        }
    for (int i = n - 1 - l; i < n; i++)
        if (s[i] == '0')
        {
            cout << "No" << endl;
            return;
        }

    int id = l;
    while (id + l != n)
    {
        for (int i = 0; i < l; i++)
        {
            if (i == 0 || i == l - 1)
            {
                if (s[id] == '0')
                {
                    cout << "No" << endl;
                    return;
                }
            }
            else
            {
                if (s[id] == '1')
                {
                    cout << "No" << endl;
                    return;
                }
            }
            id++;
        }
    }

    cout << "Yes" << endl;
}

signed main()
{
    cin >> T;
    while (T--) solve();	

    return 0;
}

C. Longest Good Array

题目要求构造一个严格单调递增的序列，并且增加的幅度越来越大

为了使这个序列最长，考虑增幅从\(1\)开始，每次只增加\(1\)，当序列末尾元素大于\(r\)时停止

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

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int l, r;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> l >> r;
        
        int res = 0, cnt = 1;
        while (l <= r)
        {
            res++;
            l += cnt++;
        }
        
        cout << res << endl;
    }

    return 0;
}

D. Sakurako's Hobby

赛时写了个\(tarjan\)不知道为啥\(tle\)了

先对\(i\)和\(a[i]\)建有向边，手玩一下发现，这些边组成了若干个环，每个环内的元素能够到达的黑色整数的数量就是这个环中黑色整数的数量，用\(bfs\)就能维护

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
59
60
61
62
63
64
#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
 
int T;
int n;
int a[N];
string s;
int ne[N], f[N];
bool st[N];

void bfs(int u)
{
    vector<int> c;
    queue<int> q;
    c.push_back(u), q.push(u);
    st[u] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        int x = ne[t];
        if (st[x]) continue;
        c.push_back(x), q.push(x);
        st[x] = true;
    }

    int res = 0;
    for (int i = 0; i < c.size(); i++)
        if (s[c[i] - 1] == '0')
            res++;
    for (int i = 0; i < c.size(); i++) f[c[i]] = res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        cin >> s;
        
        for (int i = 1; i <= n; i++) ne[i] = a[i];
        
        for (int i = 1; i <= n; i++)
        {
            if (!f[i]) bfs(i);
            cout << f[i] << ' ';
        }
        cout << endl;
        
        for (int i = 1; i <= n; i++) f[i] = st[i] = 0;
    }

    return 0;
}

E. Alternating String

转化题意，可以把字符串拆成两个子串，把每个串中的元素替换成相同的字母，统计最小操作次数

如果\(n\)为偶数，则两个串分别只包含奇数位和偶数位，只需要分别统计两个串中出现最多的字母，把整个串都变成这个字母即可

如果\(n\)为奇数，还需要删除一个元素，假设删除元素的位置是\(i\)，因此\(i\)之前的偶数位和\(i\)之后的奇数位组成一个子串，\(i\)之前的奇数位和\(i\)之后的偶数位组成一个子串，因此当遍历到第\(i\)个字母时，分别考虑当前两个串中出现次数最多的字母，统计操作次数

遍历整个字符串，尝试删除每一个位置，对操作次数取\(min\)

由于\(n\)为奇数时，删除不同位置的元素会对字串产生影响，因此可以用分别用前后缀和记录\(i\)左右奇数位和偶数位字母的数量

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
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
string s;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> s;
        
        if (n % 2 == 0)
        {
            map<char, int> p1, p2;
            for (int i = 0; i < s.size(); i++)
            {
                if (i % 2 == 0) p1[s[i]]++;
                else p2[s[i]]++;
            }
            
            int res = 0, maxv = 0;
            for (auto it: p1) maxv = max(maxv, it.y);
            res += n / 2 - maxv;
            maxv = 0;
            for (auto it: p2) maxv = max(maxv, it.y);
            res += n / 2 - maxv;
            cout << res << endl;
        }
        else
        {
            map<char, int> p1, p2, rp1, rp2;
            for (int i = 0; i < s.size(); i++)
            {
                if (i % 2 == 0) rp2[s[i]]++;
                else rp1[s[i]]++;
            }
            
            int res = 1e9;
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0) rp2[s[i]]--;
                else rp1[s[i]]--;
                int r1 = 1e9, r2 = 1e9;
                for (char j = 'a'; j <= 'z'; j++)
                {
                    r1 = min(r1, n / 2 - p1[j] - rp1[j]);
                    r2 = min(r2, n / 2 - p2[j] - rp2[j]);
                }
                res = min(res, r1 + r2 + 1);
                if (i % 2 == 0) p1[s[i]]++;
                else p2[s[i]]++;
            }
            cout << res << endl;
        }
    }

    return 0;
}

F. Sakurako's Box

每两个球相互组合的方案数\(Q=\frac{n*(n-1)}{2}\)

每两个球相互组合的乘积和\(P=a_1*a_2+a_1*a_3+...+a_1*a_n+a_2*a_3+...+a_{n-1}*a_n\) 该式可以化简为\(P=\sum_{i=1}^{n}{a_i*\sum_{j=i+1}^{n}{a_j}}\)，对于\(\sum_{j=i+1}^{n}{a_j}\)，可以用前缀和来维护

由于\(Q\)与\(MOD\)互质，因此\(qmi(Q,MOD-2)\)即为\(Q\)在\(mod\ MOD\)情况下的逆元

需要注意的是，前缀和\(sum\)有可能因为\(mod\ MOD\)导致出现负数，需要特别处理

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

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010, mod = 1e9 + 7;

int T;
int n;
int a[N];

int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int sum = 0;
        for (int i = 0; i < n; i++) sum = (sum + a[i]) % mod;
        
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            sum = (sum - a[i] + mod) % mod;
            res = (res + a[i] * sum % mod) % mod;
        }
        
        int q = (n - 1) * n / 2 % mod;
        res = res * qmi(q, mod - 2) % mod; 
        
        cout << res << endl;
    }

    return 0;
}

G. Sakurako's Task

数组中任意两数相减或者相加，能够转换成的\(n\)个数中最小间距为\(gcd(a_1,a_2,a_3,···a_n)\)，显然，数组内元素间距越小，能够组成的\(mex_k\)越大

构造好新序列后，对于\(mex_k\)的值，手动模拟即可

对于最小间距就是\(gcd\)的证明：首先两数辗转相减能够产生的除了\(0\)以外最小数一定是这两个数的\(gcd\)，因为相减不会消除两数的公因数，因此多个数辗转相减能够产生的除了\(0\)以外的最小数也会是他们的\(gcd\)

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

#define int long long

using namespace std;

const int N = 200010;

int T;
int n, k;
int a[N];

int gcd(int a, int b)
{
	return b? gcd(b, a % b) : a;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        if (n == 1)
        {
            if (a[0] < k) cout << k << endl;
            else cout << k - 1 << endl;
            continue;
        }
        
        int g = 0;
        for (int i = 0; i < n; i++) g = gcd(g, a[i]);
        
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            if (k <= g - 1 || i == n - 1)
            {
                res = g * i + k;
                break;
            }
            else k -= g - 1;
        } 
        
        cout << res << endl;
    }

    return 0;
}

H. Sakurako's Test

为了使数组\(a\)的中位数最小，\(a\)内的元素也应该做到最小，数组内的任意位置\(i\)的可以变成的最小值为\(a_i\ mod\ x\)

考虑朴素做法，遍历整个数组，把数组内的所有位置的元素都变成\(a_i\ mod\ x\)，此时数组的中位数即为最小中位数，但是每给出一个\(x\)都要遍历一遍数组，这样的做法显然超时，因此要考虑更优的解法

观察数据范围，\(1<=a_i<=n\)，因此可以开一个权值数组\(s\)，\(s_i\)为\(i\)在数组\(a\)中的个数，这时可以考虑二分答案，在\(check\)函数中，可以把数组\(s\)分成\(\lceil\frac{n}{x}\rceil\)段，每一段中相同的位置对于\(x\)的模数都相同，并且单调，因此可以用前缀和快速统计出每一段中模数小于等于\(mid\)的个数和，判断个数和是否大于等于\(\lceil\frac{n}{2}\rceil\)

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 

using namespace std;

const int N = 100010;

int T;
int n, q;
int a[N];
int x;
int s[N];

bool check(int k)
{
	int cnt = 0;
	for (int i = 1; i <= n; i += x)
	{
		int l = i, r = min(i + k - 1, n);
		cnt += s[r] - s[l - 1];	
		if (i + x - 1 <= n) cnt += s[i + x - 1] - s[i + x - 2];
	}
	
	return cnt >= n / 2 + 1;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> q;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        for (int i = 1; i <= n; i++) s[i] = 0;
        for (int i = 0; i < n; i++) s[a[i]]++;
        for (int i = 1; i <= n; i++) s[i] += s[i - 1];
        
        while (q--)
        {
            cin >> x;
            
            int l = 0, r = x - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (!check(mid)) l = mid + 1;
                else r = mid;
            }
            
            cout << l << ' ';
        }
        cout << endl;
    }

    return 0;
}