一道三进制分组的好题，完全看不出来。
不得不说，这道题很神仙。
事实上，这道题可以乱搞过去。
题目链接。
题意
现在给你两个数字 ，满足 。
你需要构造一个长度为 的序列
使得：
- 序列内数字两两不同
- 序列中不存在三个数字 且
题解
为了方便，我们首先对上述要求做一个小转化。
我们构造的序列不能存在 ，这个式子可以写作 。
接下来就是本题最神仙的部分：三进制分组。
三进制分组
我们定义一个数是“好的”当且仅当这个数字在写成 进制后，只存在 和 。
举个例子，数字 ，所以
就是不好的；
数字 ，所以 是好的。
那么就有一个结论：如果一个序列的数字全是好的，那么这个序列就不存在
的情况。
想要证明这个结论，我们只需要证明对于任意 个好的数字 ，不存在 就可以。
首先
这个数字是好的，那么就说明 在
进制表示下，只存在数字 和数字 。
都是好的，那么 进制表示下， 就不会存在进位的情况。
同时， 和
这两个数字在三进制下每一位都相等。
那就是说，对于每一位 都有
或 ，这里 表示 在 进制下的第 位。
所以就会有 ，显然这个结论成立。
这个时候我们就构造了一个序列，这个序列只剩下第 个条件没有满足。
第
个条件
首先会有这么一个结论：如果一个序列满足第三个要求，现在我们把这个序列整体加上一个值，那么这个序列肯定还满足要求。
这个很好证明，因为所有数字都加上了一个值，这个时候 和 的值都不会变化。
所以这个时候，我们就可以通过 给整个序列 来实现让这个序列的和 。
剩下就是最关键的一个问题，如果这个时候我们要调整的值小于 怎么办？
我们能不能在整个序列中选若干个数字，将他们 ，使得之后这个序列的所有数字还是”好的“呢？
直接这样做显然不可行，因为能选的数字大概只占整个序列的一半。
怎样能使这个方法正确呢？
我们只需要让一开始构造的序列，里面的数字全是 的倍数就可以了。
这个时候，所有数字在
进制下，最后一位全是 ，这就意味着所有数字 之后，还是”好的“。
其他部分按照我们刚刚步骤就可以啦。
代码也很短。
代码
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
35
36
| #include<cstdio>
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[10001];
int p[18];
int n;
ll m;
int main()
{
n=read(),m=lread();ll sum=0;
p[0]=1;for(int i=1;i<18;i++) p[i]=p[i-1]*3;
for(int i=1;i<=n;i++)
{
for(int j=1;j<18;j++) if((2*i)&(1<<j)) a[i]+=p[j];
sum+=a[i];
}
sum=m-sum;
int y=(sum%n+n)%n,x=(sum-y)/n;
for(int i=1;i<=y;i++) a[i]++;
for(int i=1;i<=n;i++) printf("%d ",a[i]+x);
return 0;
}
|
感谢观看！