【LGR-187-Div.4】洛谷入门赛 #23

来源：二三四教育网

原题链接：

B3970~B3977为A~H题

A. 数字取模

直接模拟即可。将数字x的每一位都开一个变量存起来，再分别让每个变量对k取余，最后拼接在一起。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int x, k; cin >> x >> k;
	int a = x / 1000, b = x / 100 % 10, c = x / 10 % 10, d = x % 10;
	a %= k, b %= k, c %= k, d %= k;
	int ans = a * 1000 + b * 100 + c * 10 + d;
	cout << ans << endl;
	return 0;
}

B. 闰年

按照题意判断输出即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int y; cin >> y;
	if (y % 4 != 0||(y%100==0&&y%400!=0)||(y%3200==0&&y%172800!=0)) {
		cout << "No" << endl;
	}
	else if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0 && y % 3200 != 0) || (y % 172800 == 0)) {
		cout << "Yes" << endl;
	}
	return 0;
}

C. 二进制

写个while循环，每次输出除以2的商和余数即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	while (n) {
		cout << n / 2 << " " << n % 2 << endl;
		n /= 2;
	}
	return 0;
}

D. 小 S 大战小 Q

开两个vector数组a和b，分别记录小S一组人的战力和小Q一组人的战力，再开两个变量x1和x2，并初始化为0。从1遍历到n，如果a[i]>b[i]，x1++，否则x2++。最终判断x1和x2的大小进行相应输出即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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 x1 = 0, x2 = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] > b[i]) x1++;
		else if (a[i] < b[i]) x2++;
	}
	cout << x1 << " " << x2 << endl;
	if (x1 > x2) cout << "S" << endl;
	else if (x1 < x2) cout << "Q" << endl;
	else cout << "Tie" << endl;
	return 0;
}

E. 放行李

直接暴力模拟了。pos变量表示小S在数组的位置（先初始化为-1避免对后续遍历产生干扰），f判断是否有空位置放行李（如果f为1有空位置放，否则没有），t表示在左列还是在右列放行李（t为1放在左列，t为0放在右列）。

mi表示能放行李的位置和小S的最小距离，先初始化为一个比较大的数1000000。从1~n分别变量两个数组，更新mi的值，并记录是在左列（t=1）还是右列(t=2)。

因为用了两个if，所以如果左列和右列同时有空位置距离小S的最小距离一样，那么t=1就会被t=2覆盖，所以输出答案时要特判一下这种情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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 p, q; cin >> p >> q;
	int mi = 1000000, f = 0, pos = -1, t = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] == 0) {
			f = 1;
			if (abs(i - q) <= mi) {
				mi = min(mi, abs(i - q));
				pos = i;
				t = 1;
			}
		}
		if (b[i] == 0) {
			f = 1;
			if (abs(i - q) <= mi) {
				mi = min(mi, abs(i - q));
				pos = i;
				t = 2;
			}
		}
	}

	if (!f) cout << -1 << endl;
	else {
		if (a[pos] == 0 && b[pos] == 0) {
			cout << 0 << " " << abs(pos - q) << endl;
		}
		else if (t == 1) {
			cout << 0 << " " << abs(pos - q) << endl;
		}
		else if (t == 2) {
			cout << 1 << " " << abs(pos - q) << endl;
		}
	}
	return 0;
}

F. 最大的和

感觉是这场比赛最难的一题，赛时只通过了部分测试点，赛后看了题解补出来的。

开一个二维的int数组a，开一个变量ans记录答案，并初始化为-INF，开一个变量sum记录暂时的和。

分别求每一行累加的元素最大值、每一列累加的元素最大值，和主对角线（左上到右下）平行的直线（也可以是主对角线）上累加的元素的最大值，和副对角线（右上到左下）平行的直线（也可以是对角线）上累加的元素的最大值。取这四个值中最大的即可。

行和列的很好求。关键是两个对角线。

我们通过画图观察可以知道：

从左上到右下的对角线。对于任意一条与这个对角线平行的直线，其经过的所有格子的行数与列数之差一定相同。

//这里 i 代表正在枚举的行数与列数的差（左上到右下）
//行和列的最小值都是 1，最大值都是 n，所以这个差值最小就是 1-n，最大是 n-1
for(int i = 1-n; i <= n-1; i++) {
    sum = 0;
    //然后枚举这条线上所有格子的行数 j
    //那么此时列数就等于 j-i
    for(int j = 1; j <= n; j++)
    //这里 j-i 还要判断范围，是因为要保证这个格子不能出界
        if(1 <= j-i && j-i <= n) sum += a[j][j-i];
    ans = max(ans, sum);
}

从右上到左下的对角线。对于任意一条与这个对角线平行的直线，其经过的所有格子的行数与列数之和一定相同。

//这里 i 代表正在枚举的行数与列数的和（右上到左下）
//行和列的最小值都是 1，最大值都是 n，所以这个和值最小就是 2，最大是 n+n=2*n
for(int i = 2; i <= 2*n; i++) {
    sum = 0;
    //然后枚举这条线上所有格子的行数 j
    //那么此时列数就等于 i-j
    for(int j = 1; j <= n; j++)
        //这里 i-j 还要判断范围，是因为要保证这个格子不能出界
        if(1 <= i-j && i-j <= n) sum += a[j][i-j];
    ans = max(ans, sum);
}

完整代码实现：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 2010;
const int INF = 0x3f3f3f3f;
int n, a[N][N];

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	int ans = -INF, sum = 0;

	for (int i = 1; i <= n; i++) {
		sum = 0;
		for (int j = 1; j <= n; j++) {
			sum += a[i][j];
		}
		ans = max(ans, sum);
	}

	for (int i = 1; i <= n; i++) {
		sum = 0;
		for (int j = 1; j <= n; j++) {
			sum += a[j][i];
		}
		ans = max(ans, sum);
	}

	for (int i = 1 - n; i <= n - 1; i++) {
		sum = 0;
		for (int j = 1; j <= n; j++) {
			if (j - i >= 1 && j - i <= n) sum += a[j][j - i];
		}
		ans = max(ans, sum);
	}
	
	for (int i = 2; i <= 2 * n; i++) {
		sum = 0;
		for (int j = 1; j <= n; j++) {
			if (i - j >= 1 && i - j <= n) sum += a[j][i - j];
		}
		ans = max(ans, sum);
	}

	cout << ans << endl;
	return 0;
}

G. 交题解

直接读入一个字符串，然后遍历字符串，如果是小写字母(s[i] >= 'a' && s[i] <= 'z')或者大写字母(s[i] >= 'A' && s[i] <= 'Z')直接输出字符即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s; getline(cin, s);
	for (int i = 0; i < s.size(); i++) {
		if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
			cout << s[i];
		}
	}
	return 0;
}

H. 更好的交换

这场比赛倒数第二难的题。

如果直接按题意用循环遍历交换两行元素或者交换两列元素，会TLE。

需要进行优化，我们可以观察发现，行和列之间的修改是无关的。也就可以将行和列的操作分开处理。

假设只有行操作：我们可以开一个一个数组 b[i] 来表示当前第 i 行里所存储的是初始的哪一行。那么，对于一次交换 x 行和 y 行的操作，我们只需要交换 b[x] 和 b[y] 即可：

假设只有列操作：我们可以以开一个 c[i] 数组，表示当前第 i 列里存储的是初始的哪一列，然后也只需要交换 c[x] 和 c[y] 即可。

由于行和列的操作互不相干，所以以上两个方法可以同时进行。也就是说，我们只要用数组 b 和 c 来代替每次的修改就可以了。

最后遍历二维数组，输出a[b[i]][c[j]]即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1010;
int n, m;
int a[N][N],b[N],c[N];

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		b[i] = c[i] = i;
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) swap(b[x], b[y]);
		else if (op == 0) swap(c[x], c[y]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << a[b[i]][c[j]] << " ";
		}
		cout << endl;
	}
	return 0;
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文