A - Star
题目大意
下一个大于\(X\)的\(100\)的倍数与\(X\)的差是多少？
\(1\le X\le 10^5\)
输入格式
\(X\)
输出格式
输出答案。
样例
| \(X\) | 输出 |
|---|---|
| \(140\) | \(60\) |
| \(1000\) | \(100\) |
分析
下一个大于\(X\)的\(100\)的倍数是\((\lfloor X/100\rfloor+1)\times 100\)。所以，这题我们直接输出\((\lfloor X/100\rfloor+1)\times 100-X\)。
代码
#include <cstdio>
using namespace std;
int main()
{
int x;
scanf("%d", &x);
printf("%d\n", (x / 100 + 1) * 100 - x);
return 0;
}
B - uNrEaDaBlE sTrInG
题目大意
当一个字符串的奇数位置上（第\(1\)位、第\(3\)位、第\(5\)位……，下标从\(1\)开始）都是小写英文字母且偶数位置上（第\(2\)位、第\(4\)位、第\(6\)位……）都是大写英文字母时，它是一个难以阅读的字符串。
字符串\(S\)难以阅读吗？
\(1\le |S|\le 1000\)
\(S\)由大写字母和小写字母组成。
输入格式
\(S\)
输出格式
如果\(S\)难以阅读，输出Yes；否则，输出No。
样例
| \(S\) | 输出 |
|---|---|
| \(\text{dIfFiCuLt}\) | Yes |
| \(\text{eASY}\) | No |
| \(\text{a}\) | Yes |
分析
这题只要照题目说的做即可。
代码
#include <cstdio>
using namespace std;
int main()
{
char c;
int n = 0;
while((c = getchar()) != '\n')
{
if(n++ % 2 == 0)
{
if(c < 'a' || c > 'z')
{
puts("No");
return 0;
}
continue;
}
if(c < 'A' || c > 'Z')
{
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
C - Kaprekar Number
题目大意
对于一个自然数\(x\)，我们对\(g1(x),g2(x),f(x)\)的定义如下：
- \(g1(x)=x\)按十进制位降序排序的结果
- \(g2(x)=x\)按十进制位升序排序的结果
- \(f(x)=g1(x)-g2(x)\)
举几个例子：\(g1(314)=431,g2(3021)=123,f(271)=721-127=594\)。请注意，前导\(0\)会被忽略！
给你两个数\(N,K\)，请进行\(K\)次\(N:=f(N)\)这个操作，并输出最终的\(N\)。
\(0\le N\le 10^9\)
\(1\le K\le 10^5\)
输入格式
\(N~K\)
输出格式
输出一行，即最终的\(N\)。
样例
| \(N\) | \(K\) | 输出 |
|---|---|---|
| \(314\) | \(2\) | \(693\) |
| \(1000000000\) | \(100\) | \(0\) |
| \(6174\) | \(100000\) | \(6174\) |
分析
这题在计算\(f(n)\)时可以使用一个桶来排序\(n\)，从而得到\(\mathcal O(K)\)的总复杂度。
代码
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int cnt[10];
int f(int x)
{
for(int i=0; i<10; i++) cnt[i] = 0;
while(x > 0)
{
cnt[x % 10] ++;
x /= 10;
}
int g1 = 0, g2 = 0, t = 1;
for(int i=0; i<10; i++)
while(cnt[i]--)
{
g1 += i * t, g2 = g2 * 10 + i;
t *= 10;
}
return g1 - g2;
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
while(k--) n = f(n);
printf("%d\n", n);
return 0;
}
D - Base n
题目大意
给你一个大整数\(X\)（别想得太美，）和整数\(M\)。我们设\(d\)为\(X\)中最大的位上的十进制数。long long存不下
有多少个符合“将\(X\)看成（不是转换成）\(n\)进制的数的十进制表示不超过\(M\)”这个条件的\(n\)？
\(X\)是一个没有前导\(0\)的正整数。
\(X\)在十进制表示下至少有\(1\)位、至多有\(60\)位。
\(1\le M\le 10^{18}\)
输入格式
\(X\)
\(M\)
输出格式
输出一行，即符合条件的\(n\)的个数。
样例
略，请自行前往AtCoder查看
分析
很明显，这题\(n\)的范围是\(d<n\le M\)。我们可以用二分找到最大可能的\(N\)，再用这个数减去\(d\)即可。
代码
写这份代码，需要注意如下三个点：
- 二分的边界
- 二分的判断
- 大整数的处理
废话不多说，我们直接上代码！\(\downarrow~~~~~~\downarrow~~~~~~\downarrow\)
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
char x[65];
ULL m;
inline void setmax(int& x, int y)
{
if(y > x) x = y;
}
inline bool check(const ULL& base)
{
// Returns: (x -> base) <= m?
ULL t = 0ULL;
for(int i=0; x[i]; i++)
{
if(t > m / base)
return false;
t *= base;
if((t += x[i] - '0') > m)
return false;
}
return true;
}
int main()
{
scanf("%s%llu", x, &m);
int d = 0;
for(int i=0; x[i]; i++)
setmax(d, x[i] - '0');
if(x[1] == '\0')
{
puts(d > m? "0": "1");
return 0;
}
ULL l = d, r = m;
while(l < r)
{
ULL mid = l + r + 1ULL >> 1ULL;
if(check(mid)) l = mid;
else r = mid - 1ULL;
}
printf("%llu\n", l - d);
return 0;
}