2023 CCPC哈尔滨 报告

比赛链接：Dashboard - 10.6组队训练赛-2023CCPC哈尔滨站 - Codeforceshttps://codeforces.com/group/w6iGs8kreW/contest/552949

做题数：3 题

三题都是队友写的。所以来补一下 B L J。

B题：

B. Memory

Little G used to be a participant in programming contests and he had attended nn contests in total, and for the ii-th contest, Little G got aiai happiness. However, Little G would also be influenced by past contests since memory also plays an important role to influence one's mood. So we can use following formula to value Little G's mood after the ii-th contest:

Mood(i)=∑j=1i2j−i×ajMood(i)=∑j=1i2j−i×aj

Now Little G is recalling the past and is curious about the moods after every contest, so he wants to tag the moods for every contest. Specifically, Little G will tag a positive sign ("+") for the ii-th contest if Mood(i)>0Mood(i)>0, or tag a negative sign ("-") if Mood(i)<0Mood(i)<0, or tag a zero ("0") if Mood(i)=0Mood(i)=0. But Little G is busy working and working, so he is now asking you, the best programming contestant, to help him tag the moods.

Input

The first line contains one integers nn (1≤n≤1051≤n≤105), denoting the number of contests Little G had attended.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109), denoting the happiness values after every contest.

Output

Output one line containing a string which is of length nn and only contains "+", "-" or "0", denoting the mood tags after every contest.

WA：一开始觉得这题就是签到题（最后看似乎也差不多。。。是我菜）。可以从题目给的解释找到很简单的规律。假设上一次（i-1）的答案为k，那么第i次的答案就是 k/2+a[i]。一开始就这么用double暴力写的。但是！double会爆精度。所以wa了很多次。然后又想着用分子分母来表示，但是！这样会爆long long。所以就要考虑别的策略了。

AC：我们需要考虑小数对答案的影响。我们发现，本来有小数部分的数不管怎么/2 ，都有小数部分（也就是不可能为0）。那么我们就可以把一个数分为两部分来表示：a.b 。a表示整数部分，b是小数部分。然后模拟。

这题赛后补题的时候我思路特别乱，然后队友帮我掰正了捋了一遍。要感谢模拟大王队友^-^。事实就是，模拟的时候，一步一步来，不要上来就想着该怎么分怎么分，先把这一步的运算结束了，再考虑分类讨论。分类也要有条理。比如这题，一般情况，小数部分是不会对整数部分产生影响的，但当a/2+k[i]后a变号的时候，就要看有没有小数了。比如a=5，k=-4，5/2-4=-1.5。如果a/2还用a表示，运算完之后a就要再+1（-2+1=-1）。

看一下代码：

#include<iostream>
#include<cmath>
using namespace std;
#define int long long
 
int n;
int k[1000010];
int a,b;
 
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	a=k[1],b=0;
	if(a>0){
		cout<<'+';
	}else if(a==0){
		cout<<'0';
	}else{
		cout<<'-';
	}
	for(int i=2;i<=n;i++){
		if(a%2!=0){
			if(a>0)b=1;
			else if(a<0)b=-1;
		}
		a/=2;
		int g=a;
		a+=k[i];
		if(g*a<0){
			if(g>0&&b!=0){
				a++;
				b=-b;
			}else if(g<0&&b!=0){
				a--;
				b=-b;
			}
		}
		if(a==0&&b==0){
			cout<<'0';
		}else if(a>0||(a==0&&b>0)){
			cout<<'+';
		}else{
			cout<<'-';
		}
//		cout<<a<<" "<<b<<endl;
	}
	return 0;
}

L题：

L. Palm Island

Toph is playing a card game. She has nn cards and each card has a unique number of 1,2⋯n1,2⋯n. In this game, Toph can operate the deck of the cards. We may wish to assume that the cards from the top to the bottom of the deck are p1,p2,⋯pnp1,p2,⋯pn (a permutation), then each operation must be one of the following two cases:

1. Place the top card at the bottom of the deck, that is, change the order of the deck into p2,p3⋯pn,p1p2,p3⋯pn,p1.
2. Place the second card from the top at the bottom of the deck, that is, change the order of the deck into p1,p3⋯pn,p2p1,p3⋯pn,p2

Now, you know that the initial order(from top to bottom) of Toph's deck is a1,a2,⋯ana1,a2,⋯an, and Toph wants to change the order of the deck into b1,b2,⋯bnb1,b2,⋯bn after some operations. Please construct the operation sequence to help Toph implement the change.

Toph has no patience. So the number of operations should not exceed n2n2.

Input

The first line contains an integer TT , indicating the number of test cases.

For each test case:

• The first line contains an integer, n(3≤n≤1000)n(3≤n≤1000), indicating the number of Toph's cards.
• The second line contains nn integers a1,a2,⋯ana1,a2,⋯an, a permutation indicating the order of the deck initially.
• The third line contains nn integers b1,b2,⋯bnb1,b2,⋯bn, a permutation indicating the order of the deck want to make.

It is guaranteed that the sum of nn in TT test cases is not exceed 10001000.

Output

For each test case:

• Output a line, which contains a string s1s2…sk(si∈{1,2}, 1≤i≤k)s1s2…sk(si∈{1,2}, 1≤i≤k) as your operation sequence. The length of the string should not exceed n2n2, or you will get "Wrong Answer".
• If there are multiple solutions, output any of them.

AC：这题还是要感谢队友，提供了两个很重要的方向。一个是，这其实就是一个排序问题。例如，一开始数列是 2 4 5 3 1，要变成 4 1 2 5 3。那么等价操作就是，先把 4 1 2 5 3 编号 1 2 3 4 5，那么 问题就是把 3 1 4 5 2 变成 1 2 3 4 5。这不就是一个排序问题吗？排序问题是第一个点。还有一个点就是 把两个操作等效为 冒泡排序。冒泡排序怎么排呢，就是不断比较相邻两点大小，把大的往后移（swap），那么其实 2 1 操作就相当于一次swap。这是第二个点。

看一下代码：

#include<bits/stdc++.h>
 
using namespace std;
 
int t;
int n;
int a[1010],b[1010],id[1010];
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			id[b[i]]=i;
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n-1;j++)
			{
				if(id[a[j]]>id[a[j+1]])
				{
					cout<<'2';
					swap(a[j],a[j+1]);
				}
				else
					cout<<'1';
			}
			cout<<'1';
		}
		cout<<'\n';
	
	}
	return 0;
}

J题：

j题比赛可谓半点不会，而且之前从来没有做过树上博弈论问题。（准确地说 都不知道sg函数。。。）补题的时候研究两天sg函数的原理（包括树上sg如何和nim游戏联系起来）。终于ac了。现在先贴一下从各大佬文章里看到的有关sg重要的公式。

算法学习笔记（博弈论中的SG函数）-CSDN博客

用sg判断胜负状态的关键大概是：把原游戏看成k个子游戏（例如 本题就是每个数是一个“子状态”，又或者nim游戏中每堆石子的个数是一个“子状态”）。那么，把这k个“子状态”的sg函数值求异或，若异或和为0，那么 必败。否则，存在必胜态。

那么，每个状态的sg函数值怎么求呢？用这个子状态的子状态的sg函数值求mex。

(mex函数的值表示不属于集合的最小非负整数)

可以自己推算，很容易证明出nim游戏必胜态的规律（每堆石子数异或和为0则必败）。

但我们一直被困在 如何将nim游戏和博弈论联系起来。我们一直以为 nim游戏的异或和公式是由sg函数导出的。但其实，我们是将sg的性质nim游戏相联系。我们要注意sg函数的定义：一个状态sg函数值为k，那么 它的子状态的sg函数 一定包含0~k-1的所有数。！！！这点和nim游戏的性质一样啊。nim游戏的性质是：数量为k的石子堆可以在下个状态中变为从0~k-1中的任意一个状态。那么，我们就可以用nim游戏的结论来引入sg函数赢的结论：所有状态的sg函数异或和为0，则为必败态。

所以以后博弈论问题，我们就如何判断一个状态的胜负态呢？把所有分立状态的sg函数值异或和，为0则是必败态。

例如这题，我们手推发现，数点数为奇数是树的sg函数为1，偶数是为2，点数为0时sg函数为0。那么就暴力走dfs，把每个状态都走一遍，看看子状态sg函数异或和，若为0，则ans++（子状态必输，则现在必赢）。

看代码吧~：

#include<iostream>
using namespace std;

int n,m,ans;
struct EDGE{
	int u,v;
	EDGE* ne;
}edge[1000010];
struct NODE{
	EDGE* fir;
}node[1000010];
int fa[10000010];
int SG;

int sg(int i){
	if(i==0)return 0;
	else return (2-i%2);
}

void init(int n){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
}
int find(int i){
	if(fa[i]==i){
		return fa[i];
	}
	fa[i]=find(fa[i]);
	return fa[i];
}
void unionn(int i,int j){
	int fa_i=find(i);
	int fa_j=find(j);
	fa[fa_i]=fa_j;
}

int tot;
void my_build(int u,int v){
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].ne=node[u].fir;
	node[u].fir=&edge[tot];
	tot++;
}

int siz[1000010];
void dfs1(int u,int fa){
	siz[u]=1;
	EDGE* i=node[u].fir;
	while(i!=NULL){
		if(i->v==fa){
			i=i->ne;
			continue;
		}
		dfs1(i->v,u);
		siz[u]+=siz[i->v];
		i=i->ne;
	}
}

void dfs2(int u,int fa,int k){
	int nowsg=0;
	EDGE* i=node[u].fir;
	while(i!=NULL){
		if(i->v==fa){
			i=i->ne;
			continue;
		}
		nowsg^=sg(siz[i->v]);
		dfs2(i->v,u,k);
		i=i->ne;
	}
	//delete node
	if((SG^sg(siz[k]-siz[u])^nowsg)==0){
		ans++;
	}
	//delete edge
	if(fa!=0&&(SG^sg(siz[u])^sg(siz[k]-siz[u]))==0){
		ans++;
	}
}

int main()
{
	cin>>n>>m;
	int u,v;
	init(n);
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		my_build(u,v);
		my_build(v,u);
		unionn(u,v);
	}
	for(int i=1;i<=n;i++){
		if(find(i)==i){
			dfs1(i,0);
			SG^=sg(siz[i]);
		}
	}
	for(int i=1;i<=n;i++){
		if(find(i)==i){
			SG^=sg(siz[i]);
			dfs2(i,0,i);
			SG^=sg(siz[i]);
		}
	}
	cout<<ans;
	return 0;
}

呼...整了三天，才整完银牌题。路漫漫其修远兮...