当前位置：首页 > news >正文

Codeforces Round 1032 (Div. 3)

news 2025/6/20 10:40:11

卡题卡题疯狂卡题，还刚好卡在中间题了，好好研究一下咋卡题了

A. Letter Home

思路：在一维空间给定一堆散点和当前点位，求经过所有点位所需要的最小步数。首先处理散点的左右边界，所要走的步数就是先走到左右边界的近点，再走一下左右边界的距离即可。9min搞定

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n, s;cin >> n >> s;int st = 101, en = 0;for (int i = 0; i < n; i++) {int x;cin >> x;st = min(x, st);en = max(x, en);}int dst = s - st;if (dst < 0) {dst = -dst;}int den = en - s;if (den < 0) {den = -den;}int re = en - st + min(dst, den);cout << re << endl;}return 0;
}

B. Above the Clouds

思路：给定一个小写字母串，要求拆成三个子串，且中间的串要是左右串合并后的子集。这题看起来很麻烦，其实也很简单，因为中间的串完全可以只有一个字母，这题瞬间就降级成，求除两头外，字母串中是否有重复的字母。那么直接用一个数组统计每个字母出现的次数，如果出现某个字母出现两次，则成功。注意特判一下，如果收尾两个字母相同，则该字母必须至少出现3次才算成功。13min搞定

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;string s;cin >> s;int a[26];memset(a, 0, sizeof(a));bool yes = false;for (int i = 0; i < n; i++) {int now = s[i] - 'a';a[now]++;if (i == n - 1 && s[0] == s[n - 1]) {if (a[now] > 2) {yes = true;}} else {if (a[now] > 1) {yes = true;break;}}}if (yes) {cout << "YES" << '\n';} else {cout << "NO" << '\n';}}return 0;
}

C. Those Who Are With Us

思路：卡题的罪魁祸首来了。给定一个矩型数阵，任取一个点，将该点同行同列的数都减一。求减完后矩阵中最大的点最小是多少。

重新抽象一下这题，就是给定多个点，判断这些点是否在十字型区域内。于是开始思维混乱了。首先的思路就是寻找十字型区域的中心，统计x，y坐标，若x坐标重复出现，则x坐标即为十字型区域的x坐标，同理若y坐标重复出现，则y坐标即为十字型区域的y坐标。那么想几种异常case。

首先，case1：重复的x坐标和y坐标不能有多个；Case2：若x坐标出现3个及以上不同时，必须要找到y坐标，同理也是一样。但是很快发现了Case3，这时，用原算法是可以找到第二行第三列为中心位置，但是这时最下方的点其实无法被覆盖，方法破产。于是直接摆烂，在用初始方法找到中心位置后，再把每个点带进去验算。这样居然过了，但总计写了84分钟，逆天啊，再加上没考虑到Case3所带来的10分钟的错误罚时，这题总计消耗了将近一百分钟。

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 5;int x[MAXN];
int y[MAXN];
int a[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n, m;cin >> n >> m;int maxa = 0;memset(x, 0, sizeof x);memset(y, 0, sizeof y);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i * m + j];maxa = max(maxa, a[i * m + j]);}}bool de = true;int xcount = 0;int ycount = 0;int dx = -1;int dy = -1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i * m + j] == maxa) {x[i]++;y[j]++;if (x[i] == 1) {xcount++;} else {if (dx == -1) {dx = i;} else if (dx != i) {de = false;break;}}if (y[j] == 1) {ycount++;} else {if (dy == -1) {dy = j;} else if (dy != j) {de = false;break;}}if ((ycount > 2 && dx == -1) || (xcount > 2 && dy == -1)) {de = false;break;}}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i * m + j] == maxa) {if (dx != -1 && i != dx && dy != -1 && j != dy) {de = false;break;}}}}if (de) {maxa--;}cout << maxa << endl;}return 0;
}
// 1
// 3 4
// 1 1 100 1
// 1 100 1 1
// 1 1 100 100

这题虽然做出来了，但总感觉不是很踏实，于是去看看大佬都是怎么做的

重新看一下满足规则的Case，可以发现其实任何一个点都满足一个规律，就是其要么在十字型区域的行上，要么在十字型区域的列上。如果某点在十字型区域的行上，那么所有不在这行的点一定在同一列。反之如果某点在十字型区域的列上，那么所有不在这列的点一定在同一行上。基于这个性质，一切都豁然开朗了。先随机找定一个点（假设即为第一个点），然后枚举后面的点，记录下所有行不相同的点，判断列是否相同。再记录下所有列不同的点，判断行是否相同。两者只要有一个满足即可

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 5;int a[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n, m;cin >> n >> m;int maxa = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i * m + j];maxa = max(maxa, a[i * m + j]);}}bool dex = true;bool dey = true;int x1 = -1;int x2 = -1;int y1 = -1;int y2 = -1;for (int i = 0; (dex || dey) && i < n; i++) {for (int j = 0; (dex || dey) && j < m; j++) {if (a[i * m + j] == maxa) {if (x1 == -1) {x1 = i;} else if (i != x1) {if (y2 == -1) {y2 = j;} else if (j != y2) {dey = false;}}if (y1 == -1) {y1 = j;} else if (j != y1) {if (x2 == -1) {x2 = i;} else if (i != x2) {dex = false;}}}}}if (dex || dey) {maxa--;}cout << maxa << endl;}return 0;
}

D. 1709

思路：给定两个数串，可以将某个串中的相邻数交换，或者将两个串中相同位置的数交换。要求给定一个方案，使得两个串都由小到大排列且每一位下面的串都对应大于上面的串。

由于这题没要求最优方案，因此给定任意一种方案即可。那么最简单的方式就是先上下交换，确保下面大于上面，再将两个串分别冒泡排序。算一下最坏情况下的步骤数。首先上下交换最坏有 $n$ 次，即为40次，冒泡排序，最坏交换 $\frac{n \times (n-1)}{2}$ 次，即为780次，于是最坏的方案次数即为 $40+780\times2=1600$ ，完全小于1709，于是，该方案可行。此题耗时28min

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 41;
const int MAXM = 1709;int a[MAXN];
int b[MAXN];int o[MAXM];
int oi[MAXM];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}int k = 0;for (int i = 1; i <= n; i++) {if (a[i] > b[i]) {o[k] = 3;oi[k] = i;k++;swap(a[i], b[i]);}}for (int i = 0; i < n; i++) {for (int j = 1; j < n - i; j++) {if (a[j] > a[j + 1]) {o[k] = 1;oi[k] = j;k++;swap(a[j], a[j + 1]);}if (b[j] > b[j + 1]) {o[k] = 2;oi[k] = j;k++;swap(b[j], b[j + 1]);}}}cout << k << endl;for (int i = 0; i < k; i++) {cout << o[i] << " " << oi[i] << endl;}}return 0;
}

E. Sponsor of Your Problems

思路：给定两个数，在两个数中间任选一个数，使得该数和两个数相同位的数量最少。其实这题只要想明白的思路也很简单。针对两个数，可以进行按位判断，如果两个数某位相同，则任意一个数一定的该位和两个数一定均相同，即当前位必定带来两个相同位。如果两个数仅相差了1，则至少与其中一个数相同，即必定贡献一个相同位，除此之外，别的情况并不会额外带来相同位数。最后要注意一下，要从高位往低位进行判断，因为如果高位的两个数不相等的话，其实可以往低位进位给足低位足够的空间。当然，如果只近一位都不够。比如0和9，当0进一位后成为10，和9仅相差1，还是可能走到特殊逻辑。而当仅为2或更多时，对于20甚至更大和9作差，则能妥妥保证不会带来新的相同位。27min搞定

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 10;int al[MAXN];
int ar[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int l, r;cin >> l >> r;int n = 0;while (l > 0) {al[n] = l % 10;l /= 10;ar[n] = r % 10;r /= 10;n++;}int re = 0;int addNum = 0;for (int i = n - 1; i >= 0; i--) {if (addNum > 0) {ar[i] += addNum * 10;}if (al[i] == ar[i]) {addNum = 0;re += 2;} else if (al[i] + 1 == ar[i]) {addNum = 1;re++;} else {addNum = 2;}}cout << re << endl;}return 0;
}

查看全文

http://www.lryc.cn/news/572272.html