我悟了 我只有div3-的水平
A. Digits Sum
数1~n中有多少个数的末位是9
直接把n+1然后除10即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int n, m, k, T, a[maxn];
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) {
if (c == ‘-‘) f = -1;
c = getchar();
}
while (c >= ‘0‘ && c <= ‘9‘) {
s = s * 10 + c - ‘0‘;
c = getchar();
}
return s * f;
}
int main() {
T = rd();
while (T--) {
n = rd();
if (n == 1) {
puts("0");
continue;
}
printf("%d\n", (n + 1)/ 10);
}
return 0;
}
B. Reverse String
给你一个原始字符串和操作过程中经过的字符组成的字符串，操作为选定原始字符串中的一个位置作为起点后先向右走>=0步，再向左走>=0步，问操作字符串是否合法。
sol：场上交的是直接for一遍判断下一位是否合法，是就接着向右走，否就掉头，算法不仅假了还得加一堆判断。
正解是在每个位置枚举是否掉头，大力搜索即可。
注意操作序列的长度可能是原始序列的两倍，越界得到的结果是WA。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1007;
char s[maxn], t[maxn];
int q, n, m, flag;
/*
要搜索 每个点可能变向也可能不变向
*/
void dfs(int cur, int pos, int f) {
if (pos == m) {
flag = 1;
return;
}
if (cur < 0 || cur >= n || flag == 1 || s[cur] != t[pos]) return;
dfs(cur + f, pos + 1, f);
if (f == 1)
dfs (cur - f, pos + 1, -f);
}
int main() {
cin >> q;
while (q--) {
scanf("%s%s", s, t);
n = strlen(s);
m = strlen(t);
flag = 0;
for (int i = 0; i < n; i++) {
if (s[i] == t[0]) {
dfs(i, 0, 1);
dfs(i, 0, -1);
}
}
puts(flag == 1 ? "YES" : "NO");
}
return 0;
}
C. Penalty
给出0，1，？组成的长度为10的序列，两队分别取奇数和偶数位置，问最少从前往后取几个数，才能确定其中一方不会被另外一方超过。
扫一遍用各个字符的个数和剩下的局数判断，注意未遍历到的位置的字符应当全部看成？
题意里写的是确定不超过，但样例是确定某一方能够取得胜利，这里搞了半天呃呃，，
所以程序里判断条件要写>或者<
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+7;
int n, m, k, T;
char s[maxn];
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) {
if (c == ‘-‘) f = -1;
c = getchar();
}
while (c >= ‘0‘ && c <= ‘9‘) {
s = s * 10 + c - ‘0‘;
c = getchar();
}
return s * f;
}
int main() {
T = rd();
while (T--) {
int cnt11 = 0, cnt10 = 0, cnt1 = 0, cnt21 = 0, cnt20 = 0, cnt2=0, ans = 10;
scanf("%s", s+1);
//printf("%s", s+1);
for (int i = 1; i <= 10; i++) {
if (i & 1) cnt10 += (s[i] == ‘?‘);
else cnt20 += (s[i] == ‘?‘);
}
for (int i = 1; i <= 10; i++) {
if (i & 1) {
if (s[i] == ‘1‘) cnt11++;
else if (s[i] == ‘?‘)
cnt1++, cnt10--;
if (cnt1 + cnt11 > (10-i+1)/2 + cnt21) {
ans = min(ans, i);
//puts("1");
break;
}
if (cnt11 + (10-i)/2 < cnt2 + cnt21) {
ans = min(ans, i);
//puts("2");
break;
}
} else {
if (s[i] == ‘1‘) cnt21++;
else if (s[i] == ‘?‘)
cnt2++, cnt20--;
if ((10-i)/2 + cnt11 < cnt2 + cnt21) {
ans = min(ans, i);
//puts("3");
break;
}
if (cnt21 + (10-i)/2 < cnt1 + cnt11) {
ans = min(ans, i);
//puts("4");
break;
}
}
//printf("i == %d cnt1==%d cnt2==%d cnt11==%d cnt21==%d\n", i, cnt1, cnt2, cnt11, cnt21);
}
printf("%d\n", ans);
}
return 0;
}
D. Backspace
给你一个全是小写字母的字符串，你要对着打一遍，可以把按下键盘上对应按键的操作改成按退格键，再给你最终打出的字符串，问是否能和原始字符串对应。
两个给出的字符串最大长度均为1e5，1e5组数据，所有数据字符串长度和不超过2e5
sol:如果合法，第二个字符串一定是第一个字符串的子序列，并且这个子序列的相邻字符在第一个字符串中对应的位置之差一定是偶数（每次退格少俩个字符，前导部分除外）
记第一个字符串长为n，第二个长为m，如果n-m为奇数，那么要多删去一个前导字符，
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int q, n, m;
char s[maxn], t[maxn];
bool check() {
int j = 0, flag = 0;
for (int i = (n-m)%2; i < n; i++) {
if (j < m && s[i] == t[j]) j++;
else i++;
}
return j == m;
}
int main() {
cin >> q;
while (q--) {
scanf("%s%s", s, t);
n = strlen(s), m = strlen(t);
if (n < m) {
puts("NO");
continue;
}
puts(check()?"YES":"NO");
}
return 0;
}
E. Permutation Shift
长为n的原始排列是\([1,2,3,\cdots,n]\)，对其进行以下操作：
首先将其向右循环移位\(k\)位，\(0\le k\le n-1\), 且\(k\)未知。然后执行最多\(m\)次以下操作：每次选出两个元素然后交换他们的位置。
给出\(n,m\)和操作后的最终排列，找出所有可能的\(k\)值.
\(t\le1e5\)组数据，\(3\le n \le 3e5,0\le m\le \frac{n}{3}\)
所有数据中的n的和不超过\(3e5\).
sol：
我不会做，大受震撼
官方题解：循环移位用从0开始的数字和模运算表示比较易于描述，所以先将所有数减个1
用\(p_i\)表示原始排列右移\(k\)位后，位于第\(i\)位的元素值，
然后计算从一个排列\(a\)到另外一个排列\(b\)所需的最小交换次数，这是一个经典问题，具体做法是：连接无向边\((a_i,b_i)\)，在建出的无向图中统计连通分量的个数\(c\)，那么最小的交换次数是\(n-c\).（因为每个连通分量是个环，每条边表示要进行一次交换，最终目的是每个点自己构成一个连通分量。每次交换会使得一条边从原先的环中断开）。那么一个\(k\)个点的环就需要\(k-1\)次交换。
这样就能对特定的k，在O(n)时间内检验其是否合法了，但总复杂度还是\(O(n^2)\)，无法通过。
注意到\(m\)次交换最多使得\(n-2\times m\)个数不在移\(k\)位后应该在的位置——\((i-k+n)\mod n\)上，我们可以对于每个\(k\)统计有多少个数没有发生交换,记为\(cnt_k\)，以此来判断对于该\(k\)是否有解。
对于所有的\(k\)，就位的数字个数\(cnt_k\)之和为\(n\)，并且我们只计算满足\(cnt_k\ge n- 2\times m\)的\(k\)，这些\(k\)最多有\(\frac{n}{n-2\times m}\le3\)个。所以可以在\(O(n)\)的时间内完成本题。
注意多组数据不要瞎memset
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 7;
int n, t, k, m, a[maxn], b[maxn], cnt[maxn], ans[4], top, vis[maxn];
vector<int> adj[maxn];
void dfs(int u) {
vis[u] = 1;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!vis[v]) dfs(v);
}
}
bool check(){
int c = 0;
for (int i = 0; i < n; i++) vis[i] = 0;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n; i++) {
a[i] = (i-k+n)%n;
//printf("a[%d]==%d\n", i, a[i]);
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
c++;
dfs(i);
}
}
return n - c <= m;
}
int main() {
scanf("%d", &t);
while (t--) {
top = 0;
scanf("%d%d", &n,&m);
for (int i = 0; i < n; i++) {
scanf("%d", &b[i]);
b[i]--;
cnt[(i-b[i]+n)%n]++;
}
for (k = 0; k < n; k++) {
if (cnt[k] >= n - 2*m) {
if (check()) {
// puts("err");
ans[++top] = k;
}
}
}
printf("%d", top);
for (int i = 1; i <= top; i++) {
printf(" %d", ans[i]);
}
printf("\n");
}
}
[Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)]