Codeforces 1295A~D 题解
Codeforces 1295A Display The Number 题解
题意
你需要在一个电子数字屏幕上显示一个数，每个数码都会占若干个线段。如下图，$1$占$2$个线段，$7$占$3$个线段。
给定$n$ ($2\le n\le10^5$)，输出一个最大的数，使得它占用的线段数量小于等于$n$。
题解
既然要数最大，肯定是要数位最多，$1$占的线段最少，肯定要尽可能多地用$1$。
如果$n$是偶数，那么全都用$1$。
如果$n$是奇数，发现$7$只占$3$个线段，那么第一个数码用$7$，其它的都用$1$即可。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1295B Infinite Prefixes 题解
题意
给定$n,x$ ($1\le n\le10^5,-10^9\le x\le10^9$)和一个长度为$n$的01字符串$s$，有一个由无限个$s$组成的字符串$t=ssss\dots$。
求有多少个$t$的前缀字符串，使得它的平衡度等于$x$。一个字符串$q$的平衡度是指$cnt_{0,q}-cnt_{1,q}$，$cnt_{0,q}$是指$q$中有多少个字符0，$cnt_{1,q}$是指$q$中有多少个字符1。如果有无限个，输出$-1$。
注意：前缀字符串包括空串。
题解
数组$d_i (0\le i\le n)$维护字符串$s$长度为$i$的前缀字符串的$cnt_0-cnt_1$。
首先考虑答案为$-1$的情况：$d_n=0$且$d_i=x$，这样才能保证$s$无论重复多少次，在后面加上长度为$i$的前缀，此时的字符串的平衡度等于$x$。
再来考虑答案不是$-1$的情况：记$t$的一个前缀
枚举$b$，然后看$x-d_b$是否与$d_n$同号且能整除$d_n$，如果可以，那么就是一个可行的答案。
注意：不要$\%0$。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1295C Obtain The String 题解
题意
给定两个长度在$10^5$之内的字符串$s,t$。你有一个空串$z$，你希望把它变成$t$。
每一步中，你可以在$s$中选出一个子序列$w$，然后令$z=z+w$。
求把$z$变成$t$的最小步数。如果不可能变成$t$，输出$-1$。
题解
答案是$-1$的情况很容易：如果$t$中的某个字符$s$中没有，那么就不可能得到$t$。
考虑贪心。
如果当前考虑的字符为$t_i$，在$s$中找到一个下标最小的字符$s_j=t_i$且$j$大于$t_{i-1}$在$s$中选择的位置。
- 如果有这样的$s_j$，选择$s_j$，继续。
- 如果没有这样的$s_j$，只能重新找一个子序列，选择$s$中第一个等于$t_i$的字符即可。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1295D Same GCDs 题解
题意
给定两个整数$a,m$ ($1\le a<m\le10^{10}$)，求整数$x$的个数，满足$0\le x<m$且$\gcd(a,m)=\gcd(a+x,m)$。
题解
设$\gcd(a,m)=\gcd(a+x,m)=d$，再设$a=d\cdot p,m=d\cdot q,x=d\cdot r$，
则$\gcd(p,q)=1$，相当于求$r\in[0,q)$中使得$\gcd(p+r,q)=1$的个数。
其实就是求$[p,p+q)$中与$q$互质的数的个数
$\Longrightarrow$ $[p,q]$和$[q+1,p+q)$中与$q$互质的数的个数
$\Longrightarrow$ $[p,q]$和$[1,p)$中与$q$互质的数的个数
$\Longrightarrow$ $[1,q]$中与$q$互质的数的个数
$\Longrightarrow$ $\phi(q)$
$\Longrightarrow$ $\phi\left(\frac{m}{\gcd(a,m)}\right)$。
注：$\phi$为欧拉函数。
程序
1 | // #pragma GCC optimize(2) |