Contest CF719 div3 补题
[TOC]
CF719 div3 补题
A
题目大意：看字串中是否有重复出现的，连续一段出现可以，中间隔着其他的，然后再次出现就不行了。
思路：用map来维护前面所出现过的所有字符，看是否存在
#include <bits/stdc++.h>
using namespace std;
int t, n;
#include <map>
map<char, int> m;
char s[55];
int main() {
scanf("%d", &t);
while (t--) {
int flag = 0;
m.clear();
scanf("%d%s", &n, s);
m[s[0]] = 1;
for (int i = 1; i < strlen(s); ++i) {
if (s[i] != s[i - 1] && m.count(s[i])) flag = 1;
else m[s[i]] = 1;
}
if (flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
B
题目大意：找1～n范围中，所有数都相同的数（1 2 88 444是，101 67 1239不是）
思路：直接打表，然后遍历，看看第多少个比他大，此时的索引就是个数
注意：一定要看数据范围，这个题的数据范围是1e9，就不可以用int了，要用longlong
#include <bits/stdc++.h>
using namespace std;
long long t, n;
long long a[82] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777,
888, 999, 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 11111, 22222, 33333, 44444, 55555,
66666, 77777, 88888, 99999, 111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999,
1111111, 2222222, 3333333, 4444444, 5555555, 6666666, 7777777, 8888888, 9999999, 11111111, 22222222,
33333333, 44444444, 55555555, 66666666, 77777777, 88888888, 99999999, 111111111, 222222222,
333333333, 444444444, 555555555, 666666666, 777777777, 888888888, 999999999, 1111111111};
int main() {
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
for (int i = 0; i < 82; ++i)
if (n < a[i]) {
printf("%d\n", i);
break;
}
}
return 0;
}
C
题目大意：填矩阵，相邻的上下左右的差值不能为1。
思路：利用横纵坐标的和呈现斜对角线的奇-偶-奇-偶，然后沿对角线网上开始排布即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int t, n, ans[maxn][maxn], idx;
int main() {
scanf("%d", &t);
while (t--) {
idx = 0;scanf("%d", &n);
if (n == 2) {printf("-1\n");continue;}
for (int b = 0; b < 2; ++b)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if ((i+j)%2 == b) ans[i][j] = ++idx;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
printf("%d ", ans[i][j]);
}
printf("\n");
}
}
return 0;
}
D
题目大意：找A-B = A_idx-B_idx
思路一：直接O(n^2)暴力，2e5数据，tle
思路二：用两个指针，实质上还是思路一
思路三：找相同的等差的，然后选为同一集合，然后从每个集合中挑出两个组合起来（注意这里是确定挑两个的组合数，所以没必要用combo公式，不然会tle）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, tem, ans;
#include <map>
map<ll, ll> m;
int main() {
scanf("%lld", &t);
while (t--) {
ans = 0;m.clear();
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &tem);
m[tem-i]++;
}
for (auto [k, v] : m) ans += v*(v-1)/2; // 遍历map利用[k, v]遍历的方法是在C++17中的方法，C++11/13都没有的
printf("%lld\n", ans);
}
return 0;
}