A. Primary Task

暴力判断即可

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

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

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;
        
        string s;
        while (n > 10)
        {
            s += n % 10 + '0';
            n /= 10;
        }
        
        int x = 0;
        if (s.size() && s.back() != '0')
            for (int i = s.size() - 1; i >= 0; i--) 
                x = x * 10 + s[i] - '0';
        
        if (n == 10 && x >= 2) cout << "YES" << endl;
        else cout << "NO" << endl; 
    }

    return 0;
}

B. Seating in a Bus

判断当前座位左右有没有空座位，开个数组记录

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

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

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 = 1; i <= n + 1; i++) a[i] = 0;
        
        bool flag = false;
        for (int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            a[x]++;
            if (!i) continue;
            if (!a[x - 1] && !a[x + 1]) flag = true;
        }
        
        if (flag) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

C. Numeric String Template

模拟，开两个\(map\)分别记录当前数字对应的字母和字母对应的数字，如果有冲突，则返回\(NO\)

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

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

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, m;
string s;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        cin >> m;
        while (m--)
        {
            cin >> s;
            if (s.size() != n)
            {
                cout << "NO" << endl;
                continue;
            }
            
            map<char, int> p1;
            map<int, char> p2;
            bool flag = false;
            for (int i = 0; i < s.size(); i++)
            {
                if (!p1.count(s[i]) && !p2.count(a[i])) p1[s[i]] = a[i], p2[a[i]] = s[i];
                else if (p1.count(s[i]) && p2.count(a[i]))
                {
                    if (p1[s[i]] != a[i] || p2[a[i]] != s[i])
                    {
                        flag = true;
                        break;
                    }
                }
                else
                {
                    flag = true;
                    break;
                }
            }
            
            if (!flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

    return 0;
}

D. Right Left Wrong

用前缀和\(pre\)来快速计算区间和，每拿走一对\(l\)，\(r\)所获得的分数为\(pre[r] - pre[l - 1]\)， 其中\((l < r)\)，因此可能获得的最大分数和为\(max(\sum{pre[r]})-min(\sum{pre[l-1]})\)，由于前缀和具有单调性，因此可以从前往后选\(l\)，从后往前选\(r\)，直到\(l>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
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
int a[N];
int pre[N];
string s;

signed main()
{
    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++) pre[i] = pre[i - 1] + a[i];
        
        int l = 1, r = n, res = 0;
        while (l < r)
        {
            while (s[l - 1] != 'L' && l <= n) l++;
            while (s[r - 1] != 'R' && r > 0) r--;
            if (l < r) res += pre[r] - pre[l - 1];
            l++, r--;
        }
        
        cout << res << endl;
    }

    return 0;
}

E. Photoshoot for Gorillas

预处理出每个单元格会被扫过的次数，排序后从大到小安置猩猩，对于每个单元格，需要分别考虑左右扫和上下扫，不论左右扫还是上下扫，判断的方式是一样的，假设当前要扫的长度为\(len\)，那么这\(len\)个单元格中单个单元格能被扫的最大次数\(c\)为\(min(k,len-k+1)\)，并且能被扫\(c\)次的单元格的范围为\((c，len-c+1)\)，接着从\(c-1\)到\(1\)次, 单元格数都为\(2\)，自己模拟一下即可

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

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

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, m, k, l;
int a[N];
int c1[N], c2[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k >> l;
        for (int i = 0; i < l; i++) cin >> a[i];
        
        sort(a, a + l);

        int x = min(k, n - k + 1), y = min(k, m - k + 1);
        c1[x] = n - (x - 1) * 2, c2[y] = m - (y - 1) * 2;
        for (int i = x - 1; i > 0; i--) c1[i] = 2;
        for (int i = y - 1; i > 0; i--) c2[i] = 2; 
        
        map<int, int> p;
        for (int i = x; i > 0; i--)
            for (int j = y; j > 0; j--)
                p[i * j] += c1[i] * c2[j];
        
        int id = l - 1, res = 0;
        map<int, int>::reverse_iterator it;
        for (it = p.rbegin(); it!= p.rend(); it++)
        {
            if (id < 0) break;
            int x = it -> x, y = it -> y;
            while (~id && y)
            {
                res += a[id] * x;
                id--, y--;
            }
        }
        
        cout << res << endl;
    }

    return 0;
}

F. Color Rows and Columns

背包问题，需要具体讨论对于每个矩形如何填充

  • 当矩形为长方形时，需要先填充为正方形
  • 当矩形为正方形时，假设正方形的边长为\(x\),那么第一次需要填充\(x\)块，接下来分别是\(x-1,x-1,x-2,x-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
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>

using namespace std;

const int N = 1010, M = 110;

int T;
int n, m;
int a[N], b[N];
int f[N][M];

int calc(int id, int k)
{
	int x = a[id], y = b[id];
	if (x > y) swap(x, y);
	
	if (k <= y - x - 1) return k * x;
	if (k >= x + y - 1) return x * y;
	
	int res = (y - x - 1) * x;
	k -= y - x - 1;
	res += (x * 2 - k / 2 + 1) * (k / 2);
	if (k % 2) res += x - k / 2;
	return res;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
        
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++)
            {
                f[i][j] = 1e9;
                for (int k = 0; k <= min(a[i] + b[i], j); k++)
                {
                    if (j - k && !f[i - 1][j - k]) continue;
                    f[i][j] = min(f[i][j], f[i - 1][j - k] + calc(i, k));
                }
            }
        
        if (f[n][m] == 1e9) cout << -1 << endl;
        else cout << f[n][m] << endl;	
    }

    return 0;
}

G. Call During the Journey

考虑用\(dijkstra\)解决问题，但是由于答案求的是最晚出发时间而非最早到达时间，为了不影响打电话的时间，需要从\(n\)到\(1\)求最短路，对于无法坐公交车的时间段，需要考虑选择等到打电话结束坐公交车或者步行，假设当前时间是\(t\)

  • 当\(t - l1 >= t2\)或者\(t <= t1\)时，代表当前时间可以坐公交车，选择坐公交车
  • 当\(t - l1 < t2\)并且\(t > t1\)时，代表当前时间在打电话或者坐公交车的途中会打电话，这时需要考虑是等待电话结束坐公交车还是直接步行，判断到下一个路口的时间即可

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

#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

struct edge
{
	int x, l1, l2;
};
int T;
int n, m;
vector<edge> h[N];
int t0, t1, t2;

int dijkstra()
{
    int d[N], st[N];
    for (int i = 1; i <= n; i++) 
    {
        d[i] = -1e18;
        st[i] = 0;
    }
    d[n] = t0;
    priority_queue<PII, vector<PII>, less<PII>> heap;
    heap.push({t0, n});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int time = t.first, ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = 0; i < h[ver].size(); i++)
        {
            int x = h[ver][i].x, l1 = h[ver][i].l1, l2 = h[ver][i].l2;
            int tt = (time - l1 >= t2 || time <= t1)? l1 : l2;
            if (tt == l2) tt = min(tt, time - t1 + l1);
            if (d[x] < d[ver] - tt)
            {
                d[x] = d[ver] - tt;
                heap.push({d[x], x});
            }
        }
    }

    if (d[1] < 0) return -1;
    else return d[1];
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        cin >> t0 >> t1 >> t2;
        while (m--)
        {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            h[a].push_back({b, c, d}), h[b].push_back({a, c, d});
        }
        
        cout << dijkstra() << endl;
        
        for (int i = 1; i <= n; i++) h[i].clear();
    }

    return 0;
}