题意:
给你n个数,你需要平均分成两份,分别有\frac{n}{2}个,如果两个数满足下面等式,则会发生冲突,那么就需要在同一类才不会发生冲突:
{\rm concat}(A_i,A_j)\times {\rm concat}(A_j,A_i)+A_iA_j \equiv Z \quad {\rm mod} \ 3
思路:
举个例子{\rm concat}(123,456)=123456,那么其实就是123\times 10^3+456,那么这个跟幂有关系,但是有一个很重要的10\equiv 1\quad ({\rm mod}\ 3),所以有:
10^p\equiv 1\quad ({\rm mod}\ 3)
那么有
{\rm concat}(A_i,A_j)=\overline{A_iA_j}=A_i+A_j\equiv Z\quad {\rm mod}\ 3
所以最后化简可以为:

然后来看看A_i在模3意义下的关系:

那么现在可以分成两种情况:
-
1)val=0的个数
res
大于等于\frac{n}{2}
这个时候只需要令Z=2,res
中输出\frac{n}{2}个0,其他输出1即可不发生碰撞 -
2)val=0的个数
res
小于\frac{n}{2}
这些res
个肯定需要输出0,其他的找\frac{n}{2}-\rm res出来即可。
代码:
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]%3==0) cnt++;
}
if (cnt>=n/2)
{
cout<<2<<endl;
int res = n/2;
for (int i=1;i<=n;i++)
if (a[i]%3==0&&res) cout<<0,res--;
else cout<<1;
}
else
{
cout<<0<<endl;
int res = n/2-cnt;
for (int i=1;i<=n;i++)
if (a[i]%3==0) cout<<0;
else if (res) cout<<0,res--;
else cout<<1;
}
}
文章评论