避风港
0%

21级第二场排位赛题解

发表于 分类于

A. IP Checking（LightOJ - 1354）

送分题？
  • 不会有人连二进制转换都不会吧

参考代码：

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
#include<bits/stdc++.h>
using namespace std;
void StringSplit(string str, char split, vector<string>& rst) {
	int tot = 0;
	string str1 = "";
	for (int i = 0; i < str.length(); i++) {
		char c = str[i];
		if(c != '.') str1 += c;
		if (c == '.' || i + 1 == str.length()) {
			rst.push_back(str1);
			str1 = "";
			tot++;
			continue;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
    int T;
    int cnt = 0;
    cin >> T;
    while (T--) {
        string ipAddress;
        cin >> ipAddress;
        vector<string> ipAddressSplit;
        StringSplit(ipAddress, '.', ipAddressSplit);
        vector<string> ipAddressSplitBinary;
        cin >> ipAddress;
        StringSplit(ipAddress, '.', ipAddressSplitBinary);
        bool flag = true;
        for (int i = 0; i < 4; i++) {
            int tot1 = ipAddressSplit[i].length() - 1, tot2 = 7;
            int num1 = 0, num2 = 0;
            for (char c : ipAddressSplit[i]) {
                num1 += (c - '0') * pow(10, tot1--);
            }
            for (char c : ipAddressSplitBinary[i]) {
                num2 += (c - '0') * (1 << tot2--);
            }
            if (num1 != num2) {
                flag = false;
                break;
            }
        }
        cout << "Case " << ++cnt << ": ";
        if (flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

B. Alexey and Train（Codeforces - 1501A）

阅读理解签到题
  • 每次都是 $2$ 选 $1$，要不等到 $b_i$ ，要不就等待 $ \lceil \dfrac{b_i-a_i}{2} \rceil$ 的时间

参考代码：

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
#include<bits/stdc++.h>
using namespace std;
long long a[110], b[110], t[110];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> t[i];
        }
        for (int i = 1; i <= n; i++) {
            ans += a[i] - b[i - 1] + t[i];
            if (i != n)ans += (b[i] - a[i] + 1) / 2;
            if (i != n && ans < b[i]) ans = b[i];
        }
        cout << ans << endl;
    }
    return 0;
}

C. C+=（Codeforces - 1368A）

签到题

  • 每次将小的加上大的，易证这样操作一定是最优的

  • 每次一个数一定至少会翻倍，所以暴力模拟的复杂度为 $\log n$，直接模拟即可

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int a, b, n;
        cin >> a >> b >> n;
        int ans = 0;
        while (a <= n && b <= n) {
            ans++;
            a >= b ? b += a : a += b;
        }
        cout << ans << endl;
    }
    return 0;
}

D. Max and Mex（Codeforces - 1496B）

分类讨论
  • 如果 $mex(a)>max(a)$，那么每一次都会添加一个 $mex(a)$，之后 $mex(a)$ 和 $max(a)$ 都会加1，所以答案是 $ n+k$ 。
  • 否则$mex(a)$ 和 $max(a)$ 永远不变，答案最多只会加$1$。

参考代码：

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
#include<bits/stdc++.h>
using namespace std;
int a[100010];
map<int, int>mp;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        mp.clear();
        int n, k;
        cin >> n >> k;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mp[a[i]]++;
            if (mp[a[i]] == 1)ans++;
        }
        sort(a + 1, a + 1 + n);
        int mex = 0;
        for (int i = 0; i <= 1000000; i++) {
            if (!mp[i]) {
                mex = i;
                break;
            }
        }
        if (ans - 1 == a[n]) {
            cout << k + n << endl;
        }
        else {
            int nxt = (mex + a[n]) / 2;
            if ((mex + a[n]) % 2)nxt++;
            if (!mp[nxt] && k)ans++;
            cout << ans << endl;
        }
    }
    return 0;
}

E. AND 0, Sum Big（Codeforces - 1514B）

考察对位运算的理解，沾点高中数学
  • 由于 $and$ 运算对于每一个二进制位都是独立的，所以我们每一位都分开考虑。注意这是大部分位运算题目的解题思想
  • $and$ 为 $0$，说明这 $n$ 个数对于单独的一个二进制位来说，至少有一个是 $0$
  • 要求和最大，说明对于一个二进制位，只有一个数是$0$
  • 利用乘法原理，容易得出答案

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		long long ans = 1;
		for (int i = 1; i <= k; i++)ans = ans * n % mod;
		cout << ans << endl;
	}
	return 0;
}

F. Constanze’s Machine（Codeforces - 1195C）

听说有同学不喜欢读题也不喜欢DP？
  • 考虑动态规划：$f[i][0/1/2]$ 表示选取了编号在 $i$ 及以前的球员，所能得到的身高总和最大值
  • 其中，第二维的 $0$ 表示编号为 $i$ 的球员一个都不选；$1$ 表示只选上面一个；$2$ 表示只选下面一个。（显然没有上下都选的情况）
  • 状态转移方程：
    • $f[i][0]=max(f[i−1][0],f[i−1][1],f[i−1][2])$
    • $f[i][1]=max(f[i−1][0],f[i−1][2])+h[i][1]$
    • $f[i][2]=max(f[i−1][0],f[i−1][1])+h[i][2]$

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int n;
long long h[100005][3];
long long f[100005][3];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i][1];
    for (int i = 1; i <= n; i++) cin >> h[i][2];
    f[1][0] = 0;
    f[1][1] = h[1][1];
    f[1][2] = h[1][2];
    for (int i = 2; i <= n; i++) {
        f[i][0] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
        f[i][1] = max(f[i - 1][0], f[i - 1][2]) + h[i][1];
        f[i][2] = max(f[i - 1][0], f[i - 1][1]) + h[i][2];
    }
    cout << max(f[n][0], max(f[n][1], f[n][2]));
    return 0;
}

G. Pair of Topics（Codeforces - 1324D）

解法不唯一，给出二分解法
  • 设 $c[i]=a[i]-b[i]$，并将其按照从小到大排序
  • 对于每个 $i$，二分寻找满足条件最小的 $j$，统计答案
  • 答案要开 $long long$

参考代码：

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
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010], b[200010];
int c[200010];
long long ans = 0;
signed main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) c[i] = a[i] - b[i];
	sort(c + 1, c + 1 + n);
	c[n + 1] = 2e9;
	for (int i = 1; i <= n; i++) {
		int need = -c[i] + 1;
		int l = i + 1, r = n + 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (c[mid] >= need)r = mid;
			else l = mid + 1;
		}
		ans += (n + 1 - l);
	}
	cout << ans << endl;
	return 0;
}

H. Fox And Two Dots（Codeforces - 510B）

题目中的手机游戏链接：https://www.taptap.com/app/2221?hreflang=zh_CN
  • 题意很简单，连通块找环，注意细节即可
  • $DFS$ 或 $BFS$ 均可，这里给出 $DFS$ 写法

参考代码：

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>
using namespace std;
int n, m;
char s[60][60];
int check[60][60];
char X[] = { 0, 0, 1, -1 };
char Y[] = { 1, -1, 0, 0 };
bool flag;
void dfs(int x, int y, int lastx, int lasty) {
	check[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nextx = x + X[i];
		int nexty = y + Y[i];
		if (nextx < 1 || nextx > n || nexty < 1 || nexty > m) continue;
		if (nextx == lastx && nexty == lasty) continue;
		if (s[x][y] != s[nextx][nexty]) continue;
		if (check[nextx][nexty]) flag = true;
		else dfs(nextx, nexty, x, y);
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> s[i] + 1;
	flag = false;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (flag) break;
			if (check[i][j]) continue;
			dfs(i, j, 0, 0);
		}
		if (flag) break;
	}
	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}
------ THEEND ------

欢迎关注我的其它发布渠道