ABC161 Summary

ABC161 Summary(2020-4-4 20:00~21:40)

xiaoh 2020-4-5

D-Lunlun number

题意

将一个数称为$Lunlun\;number$,当且仅当这个数十进制表达下任意两个数位的差的绝对值不大于$2$.求第$k$个$Lunlun\;number$($1\leq k\leq 10^5$).

题解

出题人用的似乎是找规律做的?(雾)反正我用的是我们引以为傲的搜索.在此我们要利用到$IDDFS$的思想,限制数位的深度,然后从小到大进行搜索,一旦找到了输出即可.时间复杂度$O(10k)$.

Code

#include<bits/stdc++.h>
using namespace std;
int k;
int tot=0;
void dfs(int step,int depth,string ans)
{
	if(step>=depth)
	{
		tot++;
		if(tot==k)
		{
			cout<<ans<<endl;
			exit(0);
		}
		return;
	}
	if(step==0)
	{
		for(int i=1;i<=9;i++) dfs(step+1,depth,ans+(char)(i+'0'));
		return;
	}
	int l=ans.length()-1;
	if(ans[l]>'0') dfs(step+1,depth,ans+(char)(ans[l]-1));
	dfs(step+1,depth,ans+(char)(ans[l]));
	if(ans[l]<'9') dfs(step+1,depth,ans+(char)(ans[l]+1));
}
int main()
{
	cin>>k;
	for(int i=1;i<=10;i++) dfs(0,i,"");
	return 0;
}

E-Yutori(unsolved)

题意

有$n$天时间,其中要选择$k$天时间进行工作($1\leq k\leq n\leq 2\times 10^5$).给定一个字符串$s$,则选择的时间要有如下的规定:

$1.$当$s_i=x$时，不能工作;

$2.$工作一天后,接下来$c$天不能工作.($1\leq c\leq n$)

保证有满足条件的方案.求哪些时间是不得不工作的.

题解

这道题的题解居然出奇的简单我还没想出来……$QAQ$

考虑使用贪心,正序遍历整个$s$,一旦能工作就立即工作,则记录第$i$次工作的日期的数组$l_i$即为第$i$次工作的最早时间.

再倒序遍历$s$,能工作就立即工作,同样的,可以得到一个数组$r_i$,为第$i$次工作的最晚时间.

显然,$l_i=r_i$时，这个日期不得不工作.遍历两个数组,输出即可.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n,k,c;
char ch[MAXN];
int l[MAXN],r[MAXN];
int main()
{
	read(n),read(k),read(c);
	scanf("%s",ch+1);
	int pre=-3*n,cnt=0;
	for(int i=1;i<=n;i++)
	if(ch[i]!='x'&&i-pre>c&&cnt<=k)
	{
		l[++cnt]=i;
		pre=i;
	}
	pre=3*n,cnt=k;
	for(int i=n;i>=1;i--)
	if(ch[i]!='x'&&pre-i>c&&cnt)
	{
		r[cnt--]=i;
		pre=i;
	}
	for(int i=1;i<=k;i++)
	if(l[i]==r[i]) write(l[i]),putchar('\n');
	return 0;
}

F-Division or Substraction

题意

给定一个正整数$n$($1\leq n\leq 10^{12}$),记$k$为$[2,n]$内的整数,且对$n$进行如下操作:

若$k|n$,则将$n$变为$n\div k$.否则将$n$变为$n-k$.

求使最终的$n$能变为$1$的$k$的个数.

题解

注意到若一旦进行第二个操作,则说明$k$无法整除$n$,于是以后将一直进行操作$2$直至小于$0$.

所以答案可以有如下两种形式:$p^q$,或$(ap+1)p^q$.

考虑第一种形式,当$q=1$时,$p=n$满足条件.

当$q\geq 2$时,则$p\leq\sqrt n$,因此枚举即可.

考虑第二种形式,则当$q=0$时,原式可化为:$ap+1$.所以$p$为$n-1$的所有约数.直接暴力枚举素因数然后按照公式计算总的约数个数即可.

当$q\geq1$时,则显然$ap^q+1\leq n$,因此$p\leq \sqrt n$,暴力枚举即可.

接下来考虑上述的几种情况是否有重叠.不难得到只要在枚举时控制第二种形式的$a\neq0$,就能保证没有重复的答案.因此按照上述的算法计算即可.时间复杂度$O(\sqrt n)$

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n;
bool check(long long x)
{
	long long tmp=x;
	while(tmp*x<=n)
	{
		if((n-tmp)%(tmp*x)==0) return 1;
		tmp*=x;
	}
	tmp=x*x;
	while(tmp<=n)
	{
		if(tmp==n) return 1;
		tmp*=x;
	}
	return 0;
}
int ans=0;
long long calc(long long x)
{
	x--;
	int tot=1;
	for(long long i=2;i*i<=n;i++)
	if(x%i==0)
	{
		int cnt=1;
		while(x%i==0) cnt++,x/=i;
		tot*=cnt;
	}
	if(x>1) tot*=2;
	return tot;
}
signed main()
{
	cin>>n;
	if(n==2)
	{
		cout<<1<<endl;
		return 0;
	}
	for(long long i=2;i*i<=n;i++)
	if(check(i)) ans++;
	ans+=calc(n);
	cout<<ans<<endl;
	return 0;
}