这道题的难度其实很大一部分取决于你的解法——你可以使用数位 dp 来解决此题，但是这就是大材小用了。一个更简单的方法是借用递归（也有点像 dfs），官方题解中的队列也可以解决本题。
递归解法：令 \(num[j]\) 表示第 \(j\) 位的数字，\(j\) 从小到大对应的是从低位到高位。
考虑第 \(j\) 位，当 \(num[j]=num[j+1]-1\) 时，下一个数字肯定就有 \(num[j]=num[j+1]\)。
当 \(num[j]=num[j+1]\) 时，如果 \(num[j+1] ≠ 9\)，下一个数字肯定有 \(num[j]=num[j+1]+1\)。如果 \(num[j+1]=9\)，说明这两位为 \(99\)，递归更高一位解决。
当 \(num[j]<num[j+1]\) 时，有两种情况。第一种情况是，\(j\) 非最高位，此时直接递归到更高位解决。第二种情况是，\(j\) 为最高位，按照题目规定，此时直接把 \(num[j]\) 加 \(1\) 即可。
此外还有一点细节，请移步代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
using namespace std;
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(‘0‘ <= c && c <= ‘9‘) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
return x * f;
}
int k, num[20], lim = 1;
bool vis[20];
void dfs(int j) {
lim = max(lim, j);
if(num[j] > num[j + 1]) {
if(lim == j && num[j] < 9) ++num[j];
else dfs(j + 1), num[j] = num[j + 1] ? num[j + 1] - 1 : 0;
}
else if(num[j] == num[j + 1] - 1) {num[j] = num[j + 1]; return;}
else {
if(num[j] < 9) {num[j] = num[j + 1] + 1; return;}
else dfs(j + 1), num[j] = num[j + 1] ? num[j + 1] - 1 : 0;
}
}
void output() {
bool lead = 1;
for(int j = 12; j; --j) {
if(lead && !num[j]) continue;
else {
lead = 0;
cout << num[j];
}
}
cout << endl;
}
int main() {
k = read();
for(int i = 1; i <= k; ++i) dfs(1);
output();
return 0;
}
一道有一点思维含量的题目。考试时因为时间不够（都用来划水了），没有做这道题（当时看 F 题 AC 人数更多就先做的 F）。
Tag：贪心。其实这道题不是很难，问题是需要保持头脑清醒并理性转化问题。
考虑令 \(L[i]\) 表示前 \(i\) 天最多可以安排多少工作日，\(R[i]\) 表示后 \(i\) 天最多可以安排多少工作日。
这个 \(L[i]\) 和 \(R[i]\) 可以显然地用贪心求出，细节可以康代码，这里便不再赘述。
对于第 \(i\) 天必须成为工作日的条件就是 \(L[i-1]+R[i+1]+1=K\)，这个不难理解。这么想：前 \(i-1\) 天最多工作 \(L[i-1]\) 天，后 \(i+1\) 天最多工作 \(R[i+1]\) 天。这两边做到极致，如果都无法完成 \(K\) 天的任务，那么就必须让第 \(i\) 天参与工作。反之我们总有方案使得第 \(i\) 天不用工作。
其实这个解法有一个小瑕疵——前 \(i-1\) 天工作的 \(L[i-1]\) 天中，可能有某一天与第 \(i\) 天的距离小于等于 \(C\)，按理说这样第 \(i\) 天便不能参与工作，此题无解。但显然这道题默认是有解的，恰好规避了这种情况，减少了我们的讨论。
细节移步代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#define Maxn 200010
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(‘0‘ <= c && c <= ‘9‘) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
return x * f;
}
int n, k, c, l[Maxn], r[Maxn];
char ch[Maxn];
int main() {
n = read(); k = read(); c = read();
scanf(" %s", ch + 1);
int j = 0;
for(int i = 1; i <= n; ++i) {
if(ch[i] == ‘o‘ && i > j) {
l[i] = l[i - 1] + 1;
j = i + c;
}
else l[i] = l[i - 1];
}
j = n + 1;
for(int i = n; i; --i) {
if(ch[i] == ‘o‘ && i < j) {
r[i] = r[i + 1] + 1;
j = i - c;
}
else r[i] = r[i + 1];
}
for(int i = 1; i <= n; ++i) {
if(ch[i] == ‘o‘ && l[i - 1] + r[i + 1] + 1 == k) printf("%d\n", i);
}
return 0;
}
一道比较基础的数论题目。
看到数据范围，首先显然想到约数枚举的 \(\sqrt{n}\)。
第一种情况，\(k\) 只能通过相减的方式使得 \(n\) 降至 \(1\) —— 只需判断 \(k\) 是否整除 \(n-1\) 即可。注意只用枚举 \(k \leq \sqrt{n}\) 的部分，另一部分对称可以得到。
第二种情况，\(k\) 可以通过相除或相减的方式使得 \(n\) 降至 \(1\)，这个时候就先让 \(k\) 尽量地整除 \(n\)，将整除后剩余的数字按照第一种方式判断即可。注意此时仍然只需要枚举 \(k \leq \sqrt{n}\) 的部分，因为对于 \(k > \sqrt{n}\) ，第一次整除后一定有 \(n‘<k\)，最后一定无法只剩下 \(1\)。
还有一点特判，细节参见代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define LL long long
#define rg register
using namespace std;
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(‘0‘ <= c && c <= ‘9‘) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
return x * f;
}
LL n, m, ans1, ans2;
int main() {
n = read(); m = sqrt(n);
if(n == 1) {cout << 1 << endl; return 0;}
if(n == 2) {cout << 1 << endl; return 0;}
for(rg LL i = 2; i <= m; ++i) {
LL now = n;
if(!(now % i)) {
while(!(now % i)) now /= i;
if(!((now - 1) % i)) ++ans1;
}
else if(!((now - 1) % i)) {
if(i * i == now - 1) ++ans2;
else ans2 += 2;
}
}
printf("%lld\n", ans1 + ans2 + 2);
return 0;
}
原文：https://www.cnblogs.com/sqrtyz/p/13418700.html