Codeforces Round 864 (Div. 2) C和D

比赛地址

C. Li Hua and Chess

题意：给出一个棋盘长宽n,m，有一颗棋子在棋盘上，向八个方向走一步的路程代价都为1，现在进行最多3次询问，问能否确认棋子的位置

Solution

第一次做交互题，想很好想，先询问(1,1)，得到x，再询问(1+x,1+x)，得到y，最后询问(1+x,1+x-y)，如果得到的是0，则输出这个点，反之输出(1+x-y,1+x)

不过有个坑，看到了但是我只看到了一半，1+x可能比n或m小，所以第二次询问时要分别跟n和m判断一下，与1+x横坐标和纵坐标都取小，询问的时候也是

好像关闭了输入流就不能用fflush(stdout)?

void solve()
{
	int n,m;cin>>n>>m;
	cout<<"? 1 1"<<"\n";
	cout.flush();
	int x;cin>>x;
	int y;
	cout<<"? "<<n<<" "<<m<<"\n";
	cout.flush();
	cin>>y;
	int ansx=0,ansy=0;
	if(x+y==n)
	{
		cout<<"?"<<" "<<x<<" "<<x<<"\n";
		cout.flush();
		int z;cin>>z;
		cout<<"!"<<" "<<x<<" "<<x-z<<"\n";
		cout.flush();
	}
	else if(x+y==m)
	{
		cout<<"?"<<" "<<x<<" "<<x<<"\n";
		cout.flush();
		int z;cin>>z;
		cout<<"!"<<" "<<x-z<<" "<<x<<"\n";
		cout.flush();
	}
}

D. Li Hua and Tree

题意：给出一颗树，每个节点上都有一个权值a[i]，定义重儿子为非叶子节点的子结点中子树大小最大的子结点

进行q次操作：

1:1 x，输出以x的子树和x上所有点的权值和

2:2 x，让x的重儿子的父节点变为x的父节点，让x的重儿子变成x的父节点，将如果x是叶子，不继续操作

Solution

操作很简单，树形dp记录最初的状态后，维护一下每个节点的重儿子即可，这里用set+结构体重载运算符维护

struct node
{
	int x,y;
	bool operator < (const node& b) const{
		if(x!=b.x)return x > b.x;
		return y < b.y;
	}
};
int a[N];
vector<int>e[N];
int dp[N];
int t[N];
set<node>st[N];
int p[N];
void dfs(int x,int pre)
{
	dp[x]=a[x];
	t[x]=1;
	for(auto it:e[x])
	{
		if(it==pre)continue;
		dfs(it,x);
		p[it]=x;
		dp[x]+=dp[it];
		t[x]+=t[it];
		node xx;
		xx.x=t[it],xx.y=it;
		st[x].insert(xx);
	}

}


void solve()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	//for(int i=1;i<=n;i++)cout<<dp[i]<<"\n";
	while(q--)
	{
		int op,x;cin>>op>>x;
		if(op==1)cout<<dp[x]<<"\n";
		else
		{
			if(st[x].size()==0)continue;
			int ts=st[x].begin()->x;
			int ti=st[x].begin()->y;
			int xx=dp[x]-dp[ti];
			int yy=t[x]-ts;
			st[p[x]].erase({t[x],x});
			st[p[x]].insert({t[x],ti});
			st[ti].insert({yy,x});
			st[x].erase(st[x].begin());
			dp[ti]=dp[x];
			dp[x]=xx;
			t[ti]=t[x];
			t[x]=yy;
			p[ti]=p[x];
			p[x]=ti;
		}
	}
}