A Divisibility Problem

题目描述

给定两个正整数 $a$ 和 $b$，你可以在一步操作中将 $a$ 加上 $1$。你需要找到最少需要多少步操作可以使得 $a \mid b $。存在最开始就满足 $a \mid b$ 的可能从而只需要 $0$ 步操作。

输入格式

第一行一个正整数 $t( 1 \le t \le 10^4)$。

之后 $t$ 行每行两个正整数 $a,b(1\le a,b \le 10^9)$。

输出格式

输出共 $t$ 行，每行一个整数，表示能达到 $a\mid b$ 的最小操作步数。

解法

题面上描述的是 $a \mid b$ 也就是 $a$ 能够整除 $b$ ，对于 $a \nmid b$ 一定是形如 $a \div b=c\cdots d$ ，那么相当于去枚举一个 $c$ 。我们可以知道 $b\times( c+1)$ 就是第一个能整除 $b$ 的整数，一开始是 $c\times b$ 现在是 $(c+1)\times b$ ，所以多了一个 $b$ ，之前比 $c\times b$ 多了 $d$ 最终所需要的答案也就是 $b-d$。

#include <bits/stdc++.h>
using namespace std;
int n, a, b;
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d", &a, &b);
		if(a % b == 0) printf("0\n");
		else printf("%d\n", b - a % b);
	}
	return 0;
}

B K-th Beautiful String

题目描述

给定两个正整数 $n,k$，生成 $\frac{n \cdot (n-1)}{2}$ 组长度为 $n$ 其中 $n-2$ 个 a ，$2$ 个 b 的字符串，求按字典序排序后第 $k$ 个字符串。

对于两个长度相等的字符串 $s,t$ 如果存在 $i(1\le i \le n)$ 使得 $s_i<t_i$ 且存在 $j( 1 \le j < i )$ 使得 $s_j = t_j$，$s$ 的字典序小于 $t$。

这是 $n=5$ 时的一个例子：

aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa

输入格式

第一行一个正整数 $t( 1 \le t \le 10^4)$。

之后 $t$ 行每行两个正整数 $n,k(3\le n \le 10^5,1 \le k \le \min(2 \cdot 10^9,\frac{n \cdot (n-1)}{2}))$。

输出格式

输出共 $t$ 行，每行一个字符串，表示按字典序排序后第 $k$ 个字符串。

解法

我们用 $x$ 来表示第一个 b 出现的位置，用 $y$ 来表示第二个 b 出现的位置，一开始 $x=n-1,y=n$，我们发现有如下规则

1. $x=y-1$，$x\gets x-1,y=n$
2. $x \ne y-1$，$y\gets y-1$

如果只考虑 $x$ ，当 $y = n$ 的时候，要移动到 $x$，需要 $n-x+1$ 步。

而 $x$ 的分布规律和 $k_i$ 的分布也是有关系的，拿题目中的样例解释

1. aaabb $x=4,y=5,k=1$
2. aabab $x=3,y=5,k=2$
3. aabba $x=3,y=4,k=3$
4. abaab $x=2,y=5,k=4$
5. ababa $x=2,y=4,k=5$
6. abbaa $x=2,y=3,k=6$
7. baaab $x=1,y=5,k=7$
8. baaba $x=1,y=4,k=8$
9. babaa $x=1,y=3,k=9$
10. bbaaa $x=1,y=2,k=10$

我们提取出每次使得 $x$ 的值同上一个 $x$ 的值不同的 $k$ 也就是 ${1,2,4,7,\cdots}$

这些数有什么规律呢？很容易发现这个数列的规律是 $+1,+2,+3,+\cdots$

我们可以处理出这样的一个数列 $ka={1,2,4,7,\cdots}$，那么对于 $[ka_i,ka_{i+1})$ 这么一个区间中的每一个 $x$ 都满足 $x=n-i,y=n-k+ka_i$ ，这一题的代码如下

#include<bits/stdc++.h>
using namespace std;
char ch[100005];
long long k[100005];
int t,a,b,p;
inline char getcha() {
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    char ch=getcha();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getcha();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getcha();}
    return ret*f;
}
int main() {
	k[1]=1,k[2]=2;
	for(int i=3;i<=100005;++i) k[i]=k[i-1]+i-1;
	t=read();
	while(t--) {
		a=read(),b=read();
		for(int i=1;i<=a;++i) ch[i]='a';
		for(int i=1;i<=a;++i) if(k[i+1]>b) {p=i;break;}
		//也可以用p=lower_bound(k+1,k+1+a,b+1)-k-1;
		ch[a-p]=ch[a-b+k[p]]='b';
		for(int i=1;i<=a;i++) printf("%c",ch[i]);
        printf("\n");
	}
	return 0;
}

C Ternary XOR

题目描述

一个三进制数各位必定由 $0,1,2$ 组成，例如 $1022,11,21,2022$。

给定一个三进制数 $x$,$x$ 的首位必定为 $2$，其余位数有可能是 $0$ 或 $1$ 或 $2$ 。

我们定义三进制的异或操作符 $⊙$，对于两个长度均为 $n$ 的三进制数 $a,b$ ，$a⊙b$ 的结果为 $c$，$c_i=(a_i+b_i) \bmod 3 $。这也就是说，将 $a,b$ 相应的数字相加并除以 $3$。例如，$10222⊙11021=21210$。

你需要找到两个长度为 $n$ 且没有前导零的三进制数 $a,b$ 使得 $a⊙b=x$ 且 $\max {a,b }$ 最小。

输入格式

第一行一个正整数 $t( 1 \le t \le 10^4)$。

之后 $t$ 组数据每组数据第一行一个正整数 $n(1 \le n \le 5 \cdot 10^4)$ 表示 $x$ 的长度为 $n$，第二行一个长度为 $n$ 的三进制数 $x$ （$x$ 由 $n$ 个 $0$ 或 $1$ 或 $2$ 组成且没有前导零）。

保证所有组数据 $n$ 的总和不超过 $5 \cdot 10^4(\sum n \le 5 \cdot 10^4)$。

输出格式

输出共 $t$ 组，每组两行，两个使得 $a⊙b=x$ 且 $\max {a,b }$ 最小的长度为 $n$ 的三进制数 $a,b$。

如果有多组 $a,b$ 满足条件，输出任意一种。

解法

如果要使 $\max {a,b }$ 最小，那么一定不存在进位。

对于 $a=b$

1. $x_i=0$ $a_i=b_i=0$
2. $x_i=1$ $a_i=1,b_i=0$
3. $x_i=2$ $a_i=b_i=1$

对于 $a>b$

1. $x_i=0$ $a_i=b_i=0$
2. $x_i=1$ $a_i=0,b_i=1$
3. $x_i=2$ $a_i=0,b_i=2$

（因为 $a=b$ 时的第二条规则保证存在至少一个 $i$ 使得 $a_i>b_i$ 从而保证了 $a>b$ 所以可以在 $a>b$ 时把所有位上的数给 $b$，避免将 $a$ 的值增大）

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    char ch=getchar();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
    return ret*f;
}
int t,len,flag;
char c[50015],c1[50015],c2[50015];
int main()
{
	t=read();
	while(t--)
    {
        len=read();
		scanf("%s",c+1);
		flag=0;
		for(int i=1;i<=len;i++)
        {
			if(c[i]=='2')
            {
				if(!flag) c1[i]=c2[i]='1';
				else c1[i]='0',c2[i]='2';
			}
			else if(c[i]=='1')
            {
				if(!flag) c1[i]='1',c2[i]='0',flag=1;
				else c1[i]='0',c2[i]='1';
			}
			else if(c[i]=='0') c1[i]=c2[i]='0';
		}
		for(int i=1;i<=len;i++) printf("%c",c1[i]);
		printf("\n");
		for(int i=1;i<=len;i++) printf("%c",c2[i]);
		printf("\n");
	}
	return 0;
}