CF341E Candies Game(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 <cstdio>
#include <iostream>
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]);
}
————————

1、 Title

Click here to see the question

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 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]);
}