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) |