一名蒟蒻的曲折解题过程

原题：P15061 琥峪枫

题目大意

本蒟蒻比较懒不想解释太详细了QwQ

翻译过来其实就是利用 $ask$ 函数求满二叉树中所有节点的权值的和

第一步

在题目的交互示例中，不难看出示例中的 $u$ 将每个点都遍历了一遍，因此考虑 $ask(1 \sim n,1)$ ，并画图进一步理解

图画的不太好，大家见谅

总之，很容易发现，所有叶子节点的权值都被统计了一次，根节点的权值被统计了两次，其余节点被统计了三次

第二步

考虑找到所有叶子节点权值的总和及根节点权值，进行补全

可以发现，叶子节点权值总和有两种获取方式，第一是对根节点的两个子节点 $ask(i,h)$ 并将结果相加，另一种是对根节点 $ask(i,h-1)$ ，但对根节点询问可能使得 $g(x)$ 中的 $x>4$ ，因此舍去

通过判断 $ask(1\dots n,h+1)==0$ 可以找出根节点及其子节点，通过 $ask(i,h)==0$ 可以进一步找出根节点，且 $ask(child,1)-ask(root,2)$ 可以得出根节点权值的两倍

由此，我们可以利用叶子节点权值与根节点权值进行补全至答案的三倍，通过变量储存交互结果，复杂度可为 $2n+4$

以此思路完成的代码如下：

#include <bits/stdc++.h>
using namespace std;
long long ask(int u,int d);
long long solve(int subtask,int h)
{
	int n=(1<<h)-1;
	long long ans=0,ans2=0;//ans2为根节点权值的两倍
	for(int i=1;i<=n;++i)
	{
		long long res1=ask(i,1);
		ans+=res1;
		if(ask(i,h+1)==0)
		{
			long long res2=ask(i,h);
			if(res2!=0)
			{
				ans+=res2*2;
				ans2+=res1;
			}
			else
			{
				if(h==2) ans2-=res2;
				else ans2-=ask(i,2);
			}
		}
	}
	return (ans+ans2/2)/3;
}

第三步

提交这份代码还不够，因为复杂度是 $2n+4$ ，无法达到满分要求 $2n+3$

此时想到当 $i=1$ 时，必定触发 $ask(i,h+1)==0$ 的判断条件，而此条件为寻找根节点及其子节点的条件，符合条件的只有三个节点

考虑使用 $cnt$ 记录找到的根节点及其子节点的数量，当 $cnt<3$ 时，说明还有符合条件的点没有被找到

因此，我们只需要将 i=1 这一项放在最后处理，使用 $cnt<3$ 代替 $ask(i,h+1)==0$ ，即可避免此次询问，使复杂度达到 $2n+3$

最终代码

#include <bits/stdc++.h>
using namespace std;
long long ask(int u,int d);
long long solve(int subtask,int h)
{
	int n=(1<<h)-1;
	long long ans=0,ans2=0,cnt=0;//ans2为根节点权值的两倍
	for(int i=2;i<=n;++i)
	{
		long long res1=ask(i,1);
		ans+=res1;
		if(cnt<3&&ask(i,h+1)==0)
		{
			++cnt;
			long long res2=ask(i,h);
			if(res2!=0)
			{
				ans+=res2*2;
				ans2+=res1;
			}
			else
			{
				if(h==2) ans2-=res2;
				else ans2-=ask(i,2);
			}
		}
	}
	long long res1=ask(1,1);
	ans+=res1;
	if(cnt<3)
	{
		long long res2=ask(1,h);
		if(res2!=0)
		{
			ans+=res2*2;
			ans2+=res1;
		}
		else
		{
			if(h==2) ans2-=res2;
			else ans2-=ask(1,2);
		}
	}
	return (ans+ans2/2)/3;
}

后记

该题为本蒟蒻因中考停止写代码一个月后写的，且是第一次写交互题，耗费了我将近两个多小时QwQ

该题解为本蒟蒻第一个题解，如有不好的地方，欢迎各位大佬指出ovo

对了，一定要注意long long！！！我在这里卡了半个小时QAQ