E. 安 (思维/贪心)

时间复杂度 ：$O(n)$

题意

    ​$May$ 和 $Ray$ 分别拥有一支有 $n$ 个骑士的军队，第 $i$ 个骑士的血量分别为 $a_i$ 和 $b_i$ 。每次操作可以选择下标 $i$ ，指挥自己的军队去攻击对方下标为 $i$ 的军队，将对方骑士的血量值减一，当血量值为零时，该骑士被消灭。由 $May$ 作为先手，两人轮流交替操作，都会最大化自己幸存的骑士数量。请问最后$May$ 能幸存多少支骑士？

数据范围

  • $1 \le n \le 10^5 , \sum n \le 10^5$
  • $1 \le a_i,b_i \le 10^9$

思路

​    从贪心的角度考虑，当$May$ 作为先手时，设 $May$ 最终幸存的骑士数量为 $cnt$ ，由于攻击对象只会是下标相同的骑士，分三种情况考虑：

  • 当$a_i < b_i$ 的军队，$May$ 的攻击”无效”，因为 $Ray$ 作为后手一定会偿还伤害，无法摆脱 $a_i < b_i$ 的命运
  • 当$a_i>b_i$ 的军队，即使 $May$ 是后手操作，也会同上种情况击败 $Ray$ , 此时 $cnt$ ++
  • 当$a_i=b_i$的军队，不难想到，此时先手操作便决定了最终的胜负，两人交替时一定会优先选择$a_i = b_i$的军队进行攻击，若 $a_i=b_i$ 的军队数量为$x$ , 则 $cnt+=\lceil \dfrac{x}{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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
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> a(n + 1),b(n+1);
        for (int i = 1; i <= n;i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= n;i++)
            if(a[i]>b[i])
                cnt1++;
            else if(a[i]==b[i])
                cnt2++;
        cout << cnt1 + (cnt2 + 1) / 2 << endl;
    }
    return 0;
}

L. 知 (数学)

时间复杂度 ：$O(T \times n^2)$

题意

​    游戏有 $n$ 个级别，已知通过每个级别的概率分别为$\frac{a_1}{100},\frac{a_2}{100}…\frac{a_n}{100}$.

​    可以执行任意数量的操作，每次操作允许选择一个索引 $i (1 \le i < n,a_i<100，a_{i+1}>0)$ ,使 $a_i$ 的值加一， $a_{i+1}$ 的值减一。请问最后可能得最大通关概率是多少，输出该答案乘以 $100^n$ 并模上 $998244353$ 的结果。

数据范围

  • $1 \le T,n,a_i \le 100$

思路

​    由数学知识易得，题意求的是 $a_1 \times a_2 \times … \times a_n$ 的最大值，每次修改操作，两者的和是固定不变的！而根据均值不等式的性质可知，两者的和一定时，当且仅当两者相等时乘积最大，数值越接近，两数乘积一定越大。

​    所以每次操作，我们尽可能地将两者数值”抹平”以缩小差值，然而操作只能针对相邻前后两个，不难想到，我们不断地进行遍历，每次将相邻两者“抹平”，直至最终无法操作，进而形成一个非递增序列。而由于$n$ 的范围极小，最坏情况$O(n^2)$ 也能够通过 .

    由于要形成非递增序列，显然，当 $a_i$ 与 $a_{i+1}$ 前后两者起始值分别为 $x$ 和 $y$ 时，有：

$a_i=a_{i+1}= \dfrac{x+y}{2} \:\:\:\:\:\: a_i与a_{i+1}同奇偶 $
$a_i=\lceil \dfrac{x+y}{2} \rceil ,a_{i+1}=\lfloor \dfrac{x+y}{2} \rfloor \:\:\:\:\:\:a_i与a_{i+1}奇偶不同$

    使用while循环体进行若干次遍历，每次遍历完成后判断一遍该序列是否是非递增，最后计算结果记得开 $long \:\: long$ 并进行取模操作.

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
const i64 p = 998244353;
signed main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        auto check_sorted = [&]() -> bool
        {
            for (int i = 2; i <= n; i++)
                if (a[i] > a[i - 1])
                    return 0;
            return 1;
        };
        while(!check_sorted()){
            for (int i = 1; i < n;i++){
                if (a[i] >= a[i + 1])
                    continue;
                int dis = a[i + 1] - a[i];
                if(dis&1){
                    a[i] += dis / 2 + 1;
                    a[i + 1] -= (dis / 2 + 1);
                }else{
                    a[i] += dis / 2;
                    a[i + 1] -= dis / 2;
                }
            }
        }
        i64 ans = 1;
        for (int i = 1; i <= n;i++)
            ans = (ans * a[i]) % p;
        cout << ans << endl;
    }
    return 0;
}

B. 珑 (模拟)

时间复杂度 ：$O(T)$

题意

​    现在有一个 $n \times m$ 的矩形，使用各种 $1 \times 2$ 或 $2 \times 1$ 的骨牌。每个位置都必须被完整地覆盖，并且放置骨牌不能超出边界.

​    另外，有两种类型的限制：

  1. 骨牌的短边不能相邻，即边长为1的边不相邻
  2. 骨牌的长边不能相邻，即边长为2的边不相邻

​    给定$n,m,a,b$ ，代表矩形的尺寸和是否存在限制，当 $a=0/1$ 时，表示该限制存在/不存在，$b$ 同理。请问最终能否实现完全覆盖？

数据范围

  • $1 \le T \le 10^5$
  • $1 \le n,m \le 10^9$
  • $0 \le a,b \le 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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int t;cin>>t;
	while(t--){
		int n, m, a, b;
		cin >> n >> m >> a >> b;
		if(n+m==3){
			cout << "Yes" << endl;
			continue;
		}
		if((n & 1) && (m & 1)){
			cout << "No" << endl;
			continue;
		}
		if(b == 0 && a == 1){
			if(n == 1 || m == 1){
				cout<< "Yes" <<endl;
				continue;
			}
			else{
				cout << "No" << endl;
				continue;
			}
		}
		else {
			if(a == 0 && b == 1){
				if(n == 1 || m == 1){
					cout << "No" << endl;
					continue;
				}
				else{
					cout << "Yes" << endl;
					continue;
				}
			}
			if(a == 0 && b == 0){
				cout << "No" << endl;
				continue;
			}
		}
		cout << "Yes" << endl;
	}
	return 0;
}

H. 入 （思维/图论）

题意

​    给定一个无向图，每一个顶点都有权重 $a_i$ ，起初将棋子放在一顶点上，每次移动中棋子都会选择相邻顶点中权重最小的，如果所有相邻顶点的权重都大于当前顶点，则立即停止。

​    可以自由分配各个顶点的权重（保证他们都是唯一的）并选择棋子的初始位置，求棋子能访问的顶点数的最大可能值。

数据范围

  • $1 \le n \le 40$
  • $1 \le m \le \binom{n}{2}$
  • $1 \le u,v \le n$

思路

​    题目所求的是从某点出发的链长度，但权重可以人为地制定，所以就是求最大的链长。

​    仔细考虑限制条件，由于选择的顶点是相邻权重最小的，显然，当选择一个节点移动后，其余节点往后必不可能选择，因为选择的权重是依次递减的。

​    由于题设中 $n$ 和 $m$ 的范围极小，可以枚举每个点作为起始点，移动时使用“ dfs+回溯 ”的方式依次标记和记录相邻节点以限定顶点路线，最终维护访问节点数的最大值即可 .

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 endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1);
    vector<vector<int>> g(n + 1); // 每一个点当前可走到的相邻边
    vector<bool> vis(n + 1);
    while (m--){
        int u, v;cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    int ans = 0;
    auto dfs = [&](auto dfs, int u, int fa, int depth) -> void
    {
        ans = max(ans, depth);
        for (auto x:e[u])
            if(x!=fa&&!vis[x])
                vis[x] = 1, g[u].emplace_back(x);
        for(auto x:g[u])
            if(x!=fa)
                dfs(dfs, x, u, depth + 1);
        for(auto x:g[u])
            vis[x] = 0;
        g[u].clear();
    };
    for (int i = 1; i <= n;i++){
        fill(vis.begin(), vis.end(), 0);
        dfs(dfs, i, 0, 1);
    }
    cout << ans << endl;
    return 0;
}