序
cf--全球最大的在线对战平台，1亿鼠标的枪战梦想，你还在等什么，快来加入吧，滑稽。
作为一只很久没打cf的1400分弱鸡，只能打打div3这个样子维持一下生活。
每次打cf都不容易，时断时续卡卡的网络疯狂劝退，特此纪念。
A. Divisibility Problem
已知：$(a+x)\%b=0,\quad 1\leq a,b\leq10^9$。
求：$x$的最小非负整数值，共$t(1\leq t \leq 10^4)$次询问。
解：$x=(b-a\%b)\%b$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;
int t;
int a, b;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &a, &b);
printf("%d\n", (b - a % b) % b);
}
return 0;
}B. K-th Beautiful String
已知：长度为$n(3\leq n\leq 10^5)$的字符串由$n-2$个'a'和2个'b'构成。
求：字典序第$k$小的字符串，共$t(1\leq t \leq 10^4)$次询问。
解：前缀和+二分。
- 如上图所示，将所有字符串按最左边一个'b'所在的位置分块。
- 设$s[i]$表示第$i$个块有的字符串个数，显然$s[i]=i$。
- 二分求出第$k$小的字符串在哪个块，并计算右边的'b'所在的位置。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 4e5 + 117;
int t;
int n, block, endid;
LL k, cnt[MAXN];
int main() {
for(int i = 1; i < MAXN; i++) cnt[i] = cnt[i - 1] + i;
scanf("%d", &t);
while(t--) {
scanf("%d%lld", &n, &k);
block = lower_bound(cnt, cnt + n, k) - cnt;
endid = cnt[block] - k;
for(int i = 0; i < n; i++) {
if(i == n - 1 - block) putchar('b');
else if(i == n - block + endid) putchar('b');
else putchar('a');
}
putchar(10);
}
return 0;
}C. Ternary XOR
已知：一个长度为$n(1\leq n \leq 5\cdot10^4)$的三进制数$c$，第一个数一定为2，$a\bigodot b=c$。
求：没有前导0的$a$和$b$满足$max(a,b)$尽可能的小，共$t(1\leq t \leq 10^4)$次询问。
解：贪心+构造。
考虑所有可能的情况
- $0=0+0$或$0=1+2$或$0=2+1$。
- $1=0+1$或$1=1+0$。
- $2=1+1$或$2=0+2$或$2=2+0$。
- 无论怎么样，$0=0+0$始终选用。
- 没有1的时候$a=b$，贪心$a$和$b$都尽可能的小，选用$2=1+1$。
存在1的时候假设$a>b$，贪心$a$尽可能的小。
- 出现1之前，选用$2=1+1$。
- 第一次出现1，选用$1=1+0$。
- 出现1之后，选用$1=0+1$和$2=0+2$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 4e5 + 117;
int t;
int n;
char a[MAXN], b[MAXN], c[MAXN];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%s", &n, c);
bool flag = false;
for(int i = 0; i < n; i++) {
if(c[i] == '0') a[i] = b[i] = '0';
else if(c[i] == '1') {
if(flag) a[i] = '0', b[i] = '1';
else a[i] = '1', b[i] = '0', flag = true;
} else {
if(flag) a[i] = '0', b[i] = '2';
else a[i] = b[i] = '1';
}
}
a[n] = b[n] = '\0';
puts(a);
puts(b);
}
return 0;
}D. Carousel
已知：$n(3\leq n \leq 2 \cdot 10^5)$个数字围成一个圈，对每个数字涂上一种颜色，满足不存在两个不同的数字相邻且颜色相同。
求：任意一种合法的涂色方案，共$t(1\leq t \leq 10^4)$次询问。
解：构造。
- 如果所有数字都相同，全部使用同一种颜色即可。
- $n$是偶数，颜色1和颜色2交替使用即可。
$n$是奇数：
- 如果$a[0]=a[n-1]$，则颜色1和颜色2交替使用即可。
- 否则在序列中寻找一处$a[i-1]=a[i]$，前$i-1$项颜色1和颜色2交替使用，第$i$项跳一次继续交替，例如：1212122121或121212112121。如果不存在$i$满足条件，则最后一项必须使用颜色3。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;
int t;
int n, a[MAXN];
int f() {
for(int i = 1; i < n; i++)
if(a[i] == a[i - 1]) return i;
return -1;
}
int main() {
scanf("%d", &t);
while(t--) {
bool all = true;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if(i && a[i] != a[i - 1]) all = false;
}
if(all) {
puts("1");
for(int i = 0; i < n; i++) printf("1 ");
} else if(n % 2 == 0 || a[0] == a[n - 1]) {
puts("2");
for(int i = 0; i < n; i++) printf("%d ", i % 2 + 1);
} else {
int id = f();
if(id == -1) {
puts("3");
for(int i = 0; i < n - 1; i++) printf("%d ", i % 2 + 1);
printf("3");
} else {
puts("2");
for(int i = 0; i < n; i++) {
if(i < id) printf("%d ", i % 2 + 1);
else printf("%d ", (i + 1) % 2 + 1);
}
}
}
putchar(10);
}
return 0;
}E. Tree Queries
已知：$n(2 \leq n \leq 2 \cdot10^5)$个点的树，1为根节点
求：给定$k(1 \leq k \leq n)$个点，问是否存在点$u$，使$k$个点都在根节点到$u$的路径上或距离为1，共$t(1\leq t \leq 2 \cdot 10^4)$次询问。
赛中思路：把$k$个点按深度排序，从下往上合并，若不能合并则说明路径不存在。
TLE：判断$u$是否是$v$的祖先效率太慢。
赛后优化：dfs一遍，进入的时候标记左端点，离开的时候标记右端点。若$u$是$v$的祖先，则一定满足$l[u]<l[v]<r[v]<r[u]$，总体时间复杂度$O(n+m)$。
举个例子：如下图所示：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;
int n, m, k, t;
int deep[MAXN], root[MAXN];
int l[MAXN], r[MAXN];
int point[MAXN];
struct Edge {
int to, ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
t = tot = 0;
memset(head, -1, sizeof(head));
memset(deep, 0, sizeof(deep));
memset(root, 0, sizeof(root));
}
void addedge(int u, int v) {
edge[tot].to = v;
edge[tot].ne = head[u];
head[u] = tot++;
}
void dfs(int id, int num) {
l[id] = t++;
deep[id] = num;
for(int i = head[id]; i != -1; i = edge[i].ne) {
if(deep[edge[i].to]) continue;
root[edge[i].to] = id;
dfs(edge[i].to, num + 1);
}
r[id] = t++;
}
bool check(int u, int v) {
if(l[u] <= l[v] && r[v] <= r[u]) return true;
return false;
}
int main() {
init();
scanf("%d%d", &n, &m);
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, 1);
while(m--) {
scanf("%d", &k);
int maxid = 0;
for(int i = 0; i < k; i++) {
scanf("%d", &point[i]);
if(deep[point[i]] > deep[point[maxid]]) maxid = i;
}
bool pr = true;
for(int i = 0; i < k; i++) {
if(!pr) break;
if(i != maxid && point[i] != 1) {
point[i] = root[point[i]];
if(!check(point[i], point[maxid])) pr = false;
}
}
if(pr) puts("YES");
else puts("NO");
}
return 0;
}F. Make k Equal
把$n$个数排序后，设$f(i)$为得到$k$个$a[i]$所需要的操作次数，$l(i)$为$a[i]$最左边的位置，$r(i)$为$a[i]$最右边的位置，$pre(i)$表示前$i$项的和，$suf(i)$表示后$i$项的和，$dx(i)=r(i)-l(i)+1-k$，则可分为以下四种情况：
- 若$dx(i) \leq 0$，则$f(i)=0$。
- 若只由左边的数通过+1操作得到，设$lcost(i)=(l(i)-1)*(a[i]-1)-pre(l(i)-1)$表示左边的数全部变成$a[i]-1$所需要的操作数，则$f(i)=lcost(i)+dx(i)$。
- 若只由右边的数通过-1操作得到，设$rcost(i)=suf(r(i)+1)-(n-r(i))*(a[i]+1)$表示右边的数全部变成$a[i]+1$所需要的操作数，则$f(i)=rcost(i)+dx(i)$。
- 由左边的数和右边的数共同得到，则$f(i)=lcost(i)+rcost(i)+dx(i)$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;
int n, k;
LL a[MAXN];
LL pre[MAXN], suf[MAXN];
map<int, int>l, r;
void build() {
for(int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
if(l[a[i]] == 0) l[a[i]] = i;
}
for(int i = n; i > 0; i--) {
suf[i] = suf[i + 1] + a[i];
if(r[a[i]] == 0) r[a[i]] = i;
}
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1);
build();
LL ans = 1e15;
for(int i = 1; i <= n; i++) {
int dx = k - (r[a[i]] - l[a[i]] + 1);//还需要dx个数
if(dx <= 0) {
ans = 0;
break;
}
LL lcost = (l[a[i]] - 1) * (a[i] - 1) - pre[l[a[i]] - 1];//左边的数全部变成a[i]-1所需要的操作次数
LL rcost = suf[r[a[i]] + 1] - (n - r[a[i]]) * (a[i] + 1);//右边的数全部变成a[i]+1所需要的操作次数
if(i >= k) ans = min(ans, lcost + dx);
if(n - i + 1 >= k) ans = min(ans, rcost + dx);
ans = min(ans, lcost + rcost + dx);
}
printf("%lld\n", ans);
return 0;
}尾
一次愉快的cf体验，赛中有点紧张，思路不够清晰，码代码也不够快，从来没有四题的弱鸡快哭了。赛后把不好看的代码全部重构提交了一遍，希望能早日上到1600+愉快的玩耍。
版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/120/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。
