A. Closest Point

观察一下可以发现，只有当集合中的点数等于\(2\),并且这两个点的差值大于\(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
30
#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;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
    	for (int i = 0; i < n; i++) cin >> a[i];
    
    	if (n == 2 && abs(a[0] - a[1]) > 1) cout << "YES" << endl;
    	else cout << "NO" << endl;  
    }
	
    return 0;
}

B. Game with Doors

分情况讨论 - 当两个区间没有重合部分时，不需要关闭任何门。

  • 当两个区间有重合部分时，关闭重合区间内所有的门，并且在重合区间与两个区间合并后的最左端点和最右端点之间，各关闭一扇门。

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
#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;
int l1, r1, l2, r2;

bool cmp()
{
    if (l1 != l2) return l1 < l2;
    return r1 > r2;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> l1 >> r1 >> l2 >> r2;
		
        if (!cmp()) swap(l1, l2), swap(r1, r2);

        if (l2 > r1) cout << 1 << endl;
        else cout << min(r1, r2) - l2 + (l1 != l2) + (r1 != r2) << endl; 
    }
	    
    return 0;
}

C. Splitting Items

考虑贪心做法，\(Alice\)一定会拿当前数组中最大的数，所以\(Bob\)的最佳做法就是把次大的数补成和最大数一样大的数，若对数组中所有数操作完还有剩余操作数，则可以在一开始就把这些操作数平分给最大数和次大数

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
#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, m;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> a[i];
		
        sort(a, a + n);
        reverse(a, a + n);
		
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0) res += a[i];
            else
            {
                int x = min(m, a[i - 1] - a[i]);
                res -= a[i] + x;
                m -= x;
            }
        }
		
        cout << res << endl; 
     }
	
    return 0;
}

D. Colored Portals

手玩一下可以发现，两个能够相互到达的城市之间最多只用中转一次，根据题意来看最多只有六种城市类型，对于每两种城市类型进行具体分析如何到达，若需要中转，则使用二分来查找中转城市类型中使得总距离最小的城市，如果没有可以中转的城市，则无法到达

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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, m;
int a[N];
vector<int> s[6];
map<string, int> p;

int check(int x, int y, int id)
{
    int res = 1e9;
    int l = 0, r = s[id].size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (s[id][mid] < x) l = mid + 1;
        else r = mid;
    }
    int t = s[id][l];
    if (t >= x) res = min(res, max((int)0, t - y));

    l = 0, r = s[id].size() - 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (s[id][mid] <= x) l = mid;
        else r = mid - 1;
    }
    t = s[id][l];
    if (t <= y) res = min(res, max((int)0, x - t));

    return res;
}

int calc(int x, int y)
{	
    int res = 1e9;
    for (int i = 0; i < 6; i++)
    {
        if (i == a[x] || i == a[y]) continue;
        if (!s[i].size()) continue;
        res = min(res, check(x, y, i));
    }

    return res == 1e9? -1 : res * 2 + y - x;
}

signed main()
{
    p["BG"] = 0;
    p["BR"] = 1;
    p["BY"] = 2;
    p["GR"] = 3;
    p["GY"] = 4;
    p["RY"] = 5;

    cin >> T;
    while (T--)
    {
        for (int i = 0; i < 6; i++) s[i].clear();
        
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            string k;
            cin >> k;
            a[i] = p[k];
            s[p[k]].push_back(i); 
        }
        
        while (m--)
        {
            int x, y;
            cin >> x >> y;
            
            if (a[x] + a[y] != 5) cout << abs(x - y) << endl;
            else
            {
                int res = 1e9;
                if (x > y) swap(x, y);
                cout << calc(x, y) << endl;
            }
        }
    }
	
    return 0;
}

E. Not a Nim Problem

\(nim\)博弈论+\(sg\)函数，但是对所有互质的数建边的话会超时，所以只能对点进行分类讨论：

  1. \(sg(0)=0\)，\(sg(1)=1\)
  2. 通过递推可以发现，所有偶数的\(sg\)值都是\(0\)
  3. 对于每个奇合数，它的\(sg\)值等于\(mex\){它的质因子的\(sg\)值}
  4. 对于每个奇素数，结合第\(3\)点可以看出它的\(sg\)值等于它在所有质数中的排名
  5. 结合\(3\)、\(4\)点可以推出对于每个奇合数\(x\)，\(s(x)=s(d(x))\)，\(d(x)\)为\(x\)的最小质因子

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

using namespace std;

const int N = 10000010;

int T;
int n;
int a[N];
int p[N], d[N], cnt;
int f[N];

void init()
{
    for (int i = 2; i <= (N - 10); i++)
    {
        if (!d[i]) p[cnt++] = i;
        for (int j = 0; p[j] <= (N - 10) / i; j++)
        {
            d[p[j] * i] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

int dp(int x)
{
    if (~f[x]) return f[x];
    if (x <= 1) return x;
    if (x % 2 == 0) return 0;
    if (d[x]) return f[x] = dp(d[x]);
    else
    {
        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (p[mid] < x) l = mid + 1;
            else r = mid;
        }
        return f[x] = l + 1;
    }
}

int main()
{
    init();

    memset(f, -1, sizeof f);

    cin >> T;
    while (T--)
    {
        cin >> n;
        
        int res = 0;
        while (n--)
        {
            int x;
            cin >> x;
            res ^= dp(x);
        }
        
        if (res) cout << "Alice" << endl;
        else cout << "Bob" << endl;
    }

    return 0;
}

F. Make a Palindrome

对于每个区间，把它变成回文区间的最大次数为\(r-l\)，也就是把区间的大小变为\(1\)，考虑到所有区间，每两种相同区间和的区间和对答案的贡献为\(-1\)
证明：

  • 对于每两个不相交的区间和相同的区间\(s1\)和\(s2\)，他们的最左和最右边界组成了一个新的区间，对于这个新的区间，如果\(s1\)和\(s2\)之间没有区间，则可以把新区间合并为三个点，\(s1\)和\(s2\)分别合并为一个点，对答案的贡献为\(-1\)；反之再把中间的区间合并为一个点，对答案的贡献为\(-2\)，但是这个新区间也可以分割出一个相交的区间和相同的区间，并且对答案的贡献为\(0\),平均下来贡献就为\(-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
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

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

using namespace std;

const int N = 2010;

int T;
int n;
int a[N];
int pre[N];
map<int, int> p;

signed main() 
{
    cin >> T;
    while (T--) 
    {
        p.clear();
        
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
        
        int res = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                res += j - i, p[pre[j] - pre[i - 1]]++;
        
        for (auto it: p) res -= it.y * (it.y - 1) / 2;
        
        cout << res << endl;		
    }

    return 0;
}