CF341E Candies Game

一、题目

点此看题

二、解法

直接入手十分困难，直到我突然想到 \(\tt EI\) 的，先提出简化的问题！

我发现我只玩得动 \(n=3\) 的情况，可以轻易地玩出来却感受不出什么规律，然后我打个爆搜给我找解，发现所有我遇到情况都是有解的。所以我们可以尝试寻找 \(n=3\) 的构造方案，那么多个数就按 \(3\) 个一组来做即可。

直接构造还是很困难，我们考虑每一小步减少最小值，那么最后一定能减少到 \(0\)，然后我的思路到这里就为止了，看来我的分析能力还欠佳啊，下次想到后面的地方一定要上草稿纸了！

减小最小值可以尝试通过模当前的最小值来实现，那么我们就想构造出模操作。设 \(x\leq y\leq z\)，\(y=k\cdot{x}+t\)，由于每次和 \(x\) 的操作都会导致其"翻倍"，所以我们分析 \(y\) 的二进制位：

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

做完上述过程之后 \(y\) 就变成了 \(t\)，所以我们就完成了模操作。操作的复杂度也是便于分析的，是 \(O(\log^2 a)\)

本题最后构造的方法是极其简单的，但是我写这么长就是为了说清楚过程，希望以后也保持这样的思考质量！

#include 
#include 
using namespace std;
const int M = 1005;
int read()
{
	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()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i].x=read(),a[i].y=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]);
}