https://atcoder.jp/contests/abc161/tasks
C - Replacing Integer
题意：给定x，k，每次操作把x变为 ∣x−k∣，问x最小值。
考虑x<k的情况，则此时只会在x,k-x这两个数里变化，找到小的那个即可，而如果x大于k，则一定可以变为x<k。
1
2
3
4
5
6
7
8
9
10
11
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll n, k;
int main() {
cin >> n >> k;
cout << min(n%k, k - n % k) << endl;
return 0;
}
|
D - Lunlun Number
题意：要求的数相邻十进制位的差值必须小于等于1，问第x个这样的数是几。
x最大只有1e5，而这样的数的个数是随着位数以幂次增长的，所以最终位数一定不大，直接dfs预处理出所有的，再直接输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
vector<ll>vc;
void dfs(int dep, ll pre) {
if (dep == 0) {
vc.push_back(pre);
return;
}
int p = pre % 10;
for (int i = max(0, p - 1); i <= min(9, p + 1); i++) {
dfs(dep - 1, pre * 10 + i);
}
}
int main() {
int num = 1;
while (1) {
for (int i = 1; i <= 9 && (int)vc.size() < 100000; i++) {
dfs(num - 1, i);
}
if ((int)vc.size() >= 100000)break;
num++;
}
sort(vc.begin(), vc.end());
int n;
cin >> n;
printf("%lld\n", vc[n - 1]);
return 0;
}
|
E - Yutori
题意：共有n天，需要工作k天，且当天工作后，后面c天必须休息，且给定字符串为‘x’的那天不能工作，问哪几天必须工作。
贪心
首先要发现，贪心的能工作就工作，一定可以工作最多天，因为今天工作了，冷却地更早，比明天工作有更多选择余地。
然后就是要判断当天如果不工作，完不成任务，那么当天就必须工作。
先从左到右贪心处理出前i天最多工作几天，再从右到左类似处理出以最后一天为第一天，后i天最多工作几天。
然后第i天不工作，则最多工作天数=前i-1天最多的工作天数+第i+1天起第一个能工作的日子后最多工作的天数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k, c;
char s[N];
int f[N], g[N], fr[N], bk[N];
int main() {
scanf("%d%d%d", &n, &k, &c);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
bk[i] = bk[i - 1];
f[i] = f[i - 1];
if (i >= bk[i] && s[i] == 'o') {
f[i]++;
bk[i] = i + c + 1;
}
}
fr[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
fr[i] = fr[i + 1];
g[i] = g[i + 1];
if (i <= fr[i] && s[i] == 'o') {
g[i]++;
fr[i] = i - c - 1;
}
}
for (int i = 1; i <= n; i++) {
if (s[i] == 'x')continue;
if (f[i - 1] + g[max(i + 1, bk[i - 1])] < k)printf("%d\n", i);
}
return 0;
}
|
F - Division or Substraction
题意：操作：如果k整除n，则n/=k，否则n-=k。重复操作直到n小于k。问有几个k，能使最终的n值为1.
n=kp⋅(ak+1)，则先枚举n的因子（p不为0），再枚举n-1的因子（p为0），注意去重和结果再算上n-1和n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll n;
int main() {
cin >> n;
ll ans = 0;
if (n == 2) { puts("1"); return 0; }
for (ll k = 2; k*k <= n; k++) {
if (n%k)continue;
ll tmp = n;
while (tmp%k == 0)tmp /= k;
if (tmp%k == 1)ans++;
tmp = n;
ll b = n / k;
while (tmp%b == 0)tmp /= b;
if (tmp%b == 1)ans++;
if (b == k)ans--;
}
for (ll k = 2; k*k <= (n - 1); k++) {
if ((n - 1) % k != 0 || (n%k) == 0)continue;
ans++;
ll b = (n - 1) / k;
if (b == k || (n - 1) % b != 0 || (n%b) == 0)continue;
ans++;
}
printf("%lld\n", ans + 2);
return 0;
}
|
