# CF341E Candies Game(CF341E Candies Game)-其他

## CF341E Candies Game(CF341E Candies Game)

### 二、解法

模操作
• 如果 $$y$$ 的当前位为 $$1$$，那么操作 $$(x,y)$$，这样 $$x$$ 也会扩倍，顺利进入下一个数位。
• 如果 $$y$$ 的当前位为 $$0$$，操作 $$(x,y)$$ 会破坏 $$k$$ 的结构，但是我们又要处理下一个数位啊。所以此时操作 $$(x,z)$$，因为 $$z\geq y$$，所以 $$z$$ 一定是支持这次操作的，顺利进入下一个数位。

模操作

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 1005;
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,p1,p2,p3,cnt,p[M*M][2];
struct node{int x,y;} a[M],tmp1,tmp2;
void chk(node &a,node &b) {if(a.x>b.x) swap(a,b);}
void move(node &a,node &b)
{
b.x-=a.x;a.x+=a.x;
m++;p[m][0]=a.y;p[m][1]=b.y;
}
void merge(node a,node b,node c)
{
chk(a,b);chk(a,c);chk(b,c);
if(a.x==0)
{
tmp1=b;tmp2=c;
return ;
}
int k=b.x/a.x;
while(k)
{
if(k&1) move(a,b);
else move(a,c);
k>>=1;
}
merge(a,b,c);
}
signed main()
{
for(int i=1;i<=n;i++)
{
cnt+=(a[i].x==0);
}
if(n-cnt<2) {puts("-1");return 0;}
for(p1=1;p1<=n && !a[p1].x;p1++);
for(p2=p1+1;p2<=n && !a[p2].x;p2++);
for(p3=p2+1;p3<=n && !a[p3].x;p3++);
while(p3<=n)
{
merge(a[p1],a[p2],a[p3]);
a[p2]=tmp1;a[p3]=tmp2;
p1=p2;p2=p3;
for(p3++;p3<=n && !a[p3].x;p3++);
}
printf("%d\n",m);
for(int i=1;i<=m;i++)
printf("%d %d\n",p[i][0],p[i][1]);
}

————————

### 2、 Solution

It was very difficult to start directly until I suddenly thought of the guiding principle of \ (\ TT EI \) problem solving and put forward the simplified problem first!

I found that I can only play \ (n = 3 \) easily, but I can’t feel any rules. Then I called a pop search to find a solution for me and found that all the situations I encounter have solutions. Therefore, we can try to find the construction scheme of \ (n = 3 \), and then multiple numbers can be done in groups of \ (3 \).

It is still very difficult to construct directly. We consider < strong > reducing the minimum value in each small step, and then it will be reduced to \ (0 \) < / strong >, and then my thinking will stop here. It seems that my analysis ability is still poor. I must draft paper next time I think of the place behind!

Reducing the minimum value can be realized by the current minimum value of the module, so we want to construct. Set \ (x \ Leq y \ Leq Z \), \ (y = k \ cdot{x} + T \), because each operation with \ (x \) will cause it to “double”, so we < strong > analyze the binary bits of \ (Y \) < / strong >:

模操作
• If the current bit of \ (Y \) is \ (1 \), operate \ ((x, y) \), so that \ (x \) will also be multiplied and enter the next digit smoothly.
• If the current bit of \ (Y \) is \ (0 \), the operation \ ((x, y) \) will destroy the structure of \ (K \), but we have to deal with the next digit. Therefore, at this time, the operation \ ((x, z) \), because \ (Z \ GEQ y \), so \ (Z \) must support this operation and enter the next digit smoothly.

After completing the above process \ (Y \) becomes \ (t \), so we are finished. The complexity of the operation is also easy to analyze, which is \ (O (\ log ^ 2 a) \)

模操作

The final construction method of this topic is extremely simple, but I write so long to clarify the process. I hope to maintain such thinking quality in the future!

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 1005;
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,p1,p2,p3,cnt,p[M*M][2];
struct node{int x,y;} a[M],tmp1,tmp2;
void chk(node &a,node &b) {if(a.x>b.x) swap(a,b);}
void move(node &a,node &b)
{
b.x-=a.x;a.x+=a.x;
m++;p[m][0]=a.y;p[m][1]=b.y;
}
void merge(node a,node b,node c)
{
chk(a,b);chk(a,c);chk(b,c);
if(a.x==0)
{
tmp1=b;tmp2=c;
return ;
}
int k=b.x/a.x;
while(k)
{
if(k&1) move(a,b);
else move(a,c);
k>>=1;
}
merge(a,b,c);
}
signed main()
{
for(int i=1;i<=n;i++)
{
cnt+=(a[i].x==0);
}
if(n-cnt<2) {puts("-1");return 0;}
for(p1=1;p1<=n && !a[p1].x;p1++);
for(p2=p1+1;p2<=n && !a[p2].x;p2++);
for(p3=p2+1;p3<=n && !a[p3].x;p3++);
while(p3<=n)
{
merge(a[p1],a[p2],a[p3]);
a[p2]=tmp1;a[p3]=tmp2;
p1=p2;p2=p3;
for(p3++;p3<=n && !a[p3].x;p3++);
}
printf("%d\n",m);
for(int i=1;i<=m;i++)
printf("%d %d\n",p[i][0],p[i][1]);
}