【cf比赛记录】Educational Codeforces Round 78 (Rated for Div. 2)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

比赛传送门

A. Shuffle Hashing

题意：加密字符串。可以把字符串的字母打乱后再从前面以及后面接上字符串。问加密后的字符串是否符合加密规则。

题解：字符串的长度很短，直接暴力搜索所有情况

// https://codeforces.com/contest/1278/problem/A #include<iostream> #include<cstdio> #include<cstring> using namespace std;int T; char p[102], h[102]; int pnum[30], hnum[30];int main() { scanf("%d", &T); while(T--){ memset(pnum, 0, sizeof(pnum)); // memset(hnum, 0, sizeof(hnum)); scanf("%s %s", p, h); int plen = strlen(p); // 原字符串长度 int hlen = strlen(h); // 加密后的长度 for(int i = 0; i < plen; i++){ pnum[p[i] - 'a']++; // 记录原字符串的字母个数 } bool flag = false; for(int i = 0; i < hlen; i++){ bool ok = true; memset(hnum, 0, sizeof(hnum)); // hnum 记录机密后的字符串字母的个数 if(hlen - plen < i || flag) break; for(int j = 0, k = i; j < plen && k < hlen; j++, k++){ int who = h[k] - 'a'; hnum[h[k] - 'a']++; if(hnum[who] > pnum[who]) { ok = false; break; } } if(ok) flag = true; } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }

B. A and B

题意：第 \(i\) 步可以给A或者B加上 \(i\) ，求使得他们相等的最少步数

题解：数学题。先打表 f(i) = (i + 1) * i / 2；(f(1) < 1e9)。然后求 | A - B | ，当 f(x) >= |A - B| 时判断它们的差的奇偶性，如果是偶数则输出 x, 如果是奇数则分情况讨论：如果 x 为奇数，则输出 x+2；否则输出 x+1。

为什么呢？我们先把所有的数都加到较小的那个数（假设这里是a）里，当操作一轮后a的和比b要大，则说明此时需要把一部分a的操作数加到b那边去，其实b+i == a-i。此时 a + f(x) >= b 。假如当 a + f(x) - b == 2 时，我们只需要把 a 当时的 +1 改为 -1 即可，所以操作数是没有变化的（如果是 == 4 则把 +2 改为 -2，以此类推）。而当 a + f(x) - b == k（k是奇数时），且 x 此时是奇数时，则 a 加上下一个数的时候是加上一个偶数，偶数加奇数还是奇数，所以还要再操作一次；如果当前操作数是偶数时同理。a + f(x) - b 等价于 f(x) - (b - a) 分别对应打表的f(i) 与一开始两数的差。

// https://codeforces.com/contest/1278/problem/B // Thanks for my gf. #include<iostream> #include<cstdio> #include<cmath> using namespace std;int T, a, b; int num[1000006]; int cnt = 1;void build(){ int x = 1, i = 1; while(x <= 1000000000){ x = (i + 1) * i / 2; num[cnt++] = x; i++; } }int main() { build(); scanf("%d", &T); while(T--){ scanf("%d %d", &a, &b); int sub = abs(a - b); if(sub == 0) { printf("0\n"); continue; } // printf("cnt:%d\n", cnt); for(int i = 1; i <= cnt; i++){ if(num[i] >= sub){ if((num[i]-sub) % 2 == 0) { printf("%d\n", i); break; } else { if(i % 2 == 0){ printf("%d\n", i + 1); } else printf("%d\n", i + 2); break; } } } } return 0; }