Atcoder Beginner Contest 161 DEF

$D.$D.
题意： 求第 $k$k个所有相邻数绝对值差小于2的数
题解： 看题意以为是数位 $dp$dp，后来反应过来数据范围可以直接搜出来。
具体就是每次搜的都是还未搜到的最小的数，那么只要搜 $1e5$1e5个就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100000;

typedef long long ll;
int k;

vector<ll> ans;
queue<ll> q;
void bfs() {
	for(ll i = 1; i < 10; i++) q.push(i);
	while(q.size()) {
		ll t = q.front(); q.pop();
		ans.push_back(t);
		if((int)ans.size() >= N) break;
		
		ll now = t % 10;
		if(now - 1 >= 0) {
			ll t1 = t * 10 + now - 1;
			q.push(t1);
		}
		q.push(t * 10 + now);
		
		if(now + 1 < 10) {
			ll t1 = t * 10 + now + 1;
			q.push(t1);
		} 
	}
}

int main()
{
	scanf("%d", &k);
	bfs();
	sort(ans.begin(), ans.end());
	printf("%lld\n", ans[k - 1]);
	return 0; 
}

$E.$E.
题意： 给定一个字符串表示某人的工作日和休息日。只有在工作日才能工作，每次工作一天后的 $c$c天不能再工作。他一共要工作 $k$k天，问哪些天是必须工作的。
题解：
这个人无论如何一定是存在两个极端：
$1.$1.从第 $1$1天开始直到工作了 $k$k天，记为 $a$a
$2.$2.从最后一天开始往前直到满了 $k$k天，记为 $b$b
那么必须工作的天就是 $a\left[i\right]==b\left[i\right]$a[i]==b[i]的时候。
因为只要 $a\left[i\right]\ne b\left[i\right]$a[i]​=b[i]，那么必须工作的第 $i$i天就至少有两个选择，故必须保证第 $i$i天的选择是唯一的。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
char s[N];
vector<int> a, b;
int main()
{
	int n, k, c;
	scanf("%d%d%d", &n, &k, &c);
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	
	
	for(int i = 1; i <= len; i++) {
		if(s[i] == 'o') {
			a.push_back(i);
			i += c;
		}
		if(a.size() == k) break;
	}
	for(int i = n; i >= 1; i--) {
		if(s[i] == 'o') {
			b.push_back(i);
			i -= c;
		}
		if(b.size() == k) break;
	}
	reverse(b.begin(), b.end());
	
	int la = a.size(), lb = b.size();
	if(la == lb) {
		for(int i = 0; i < la; i++) 
			if(a[i] == b[i]) printf("%d\n", a[i]);
	}
} 

$F.$F.
题意： 求 $2\sim n$2∼n中的数 $k$k使得 $n\%k==1$n%k==1的 $k$k的个数
题解：
$1.$1. $k$k为 $n$n的因子，那么枚举 $n$n的因子k， $n$n中去掉 $k$k后得到 $x$x，再判断 $n\%x==1$n%x==1即可
$2.$2. $k$k非 $n$n的因子，那么对于 $n\%k==1$n%k==1，有 $(n-1)\%k==0$(n−1)%k==0，故求 $n-1$n−1的因子。注意 $k$k为1的时候，由于 $n\%1==0$n%1==0，所以无论如何 $k==1$k==1的时候都不符合。
由于 $1$1不符合，故从 $2$2开始枚举，因此先加上 $n$n和 $n-1$n−1，又因为 $n\%(n-1)$n%(n−1) $\ne 0$​=0，当 $n==2$n==2的时候不成立，故特判下 $2$2即可。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n;

bool check(ll x) {
	ll t = n;
	while(t % x == 0) t /= x;
	t %= x;
	if(t == 1) return 1;
	return 0;
}

int main()
{
	scanf("%lld", &n);
	if(n == 2) puts("1");
	else {
		ll res = 2, t = n - 1; 
		for(ll i = 2; i * i <= t; i++) {
			if(t % i == 0) {
				res++;
				if(i * i != t) res++;
			} 
		}
		
		for(ll i = 2; i * i <= n; i++) {
			if(n % i == 0) {
				res += check(i);
				if(i * i != n) res += check(n / i);
			}
		}
		
		printf("%lld\n", res);
	}
	return 0;
}