2022牛客OI赛前集训营-提高组（第四场）赛后总结

博弈

https://ac.nowcoder.com/acm/contest/40648/A

时间	名称	赛制	组别	得分	排名
2022.10.11	2022牛客OI赛前集训营（第四场）	OI	提高组	200/400	15

A.博弈

之前没用过 hash-xor 所以考试没做出来，采用 set 暴力维护每个节点到根节点的路径上的数然而卡时出问题了 $40 - > 0$ 。

其实不难发现一个结论：如果两节点之间的路径上出现的边权均为偶数次那么先手必败，其余情况先手必胜。

那么很容易想到从反面去做，只要找到必败态的情况即可。

于是先对给定的边权离散化，重新赋值 $B A S E^{w}$ （ $B A S E$ 这里取 $13331$ , $w$ 是离散后的边权）。

然后维护每个节点到根节点的异或和，这样如果两个节点到根节点的异或和相等，那么它们路径上边权出现的次数一定均为偶数。

统计答案用个 unordered_map，时间复杂度 $O (n l o g n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,unsigned long long> pa;
const int MAXN=5e5+5;
const int BASE=13331;
vector<pa>G[MAXN];
unordered_map<unsigned long long,int>vis;
unsigned long long number[MAXN],sum[MAXN];
int num[MAXN],len;
void dfs(int x,int father)
{
    for(auto i:G[x])
    {
        int y=i.first,z=i.second;
        if(y==father) continue;
        sum[y]=sum[x]^number[lower_bound(num+1,num+len+1,z)-num-1];
        dfs(y,x);
    }
}
int main()
{
    int T;
    cin>>T;
    int n;
    while(T--)
    {
        scanf("%d",&n);
        number[0]=1,vis.clear();
        for(int i=1;i<=n;++i) G[i].clear(),number[i]=number[i-1]*BASE;
        int u,v,w;
        for(int i=1;i<n;++i) scanf("%d %d %d",&u,&v,&w),G[u].push_back({v,w}),G[v].push_back({u,w}),num[i]=w;
        sort(num+1,num+n);
        len=unique(num+1,num+n)-num-1;
        dfs(1,0);
        long long ans=(long long)n*(n-1)/2;
        for(int i=1;i<=n;++i)
        {
            ans-=vis[sum[i]];
            ++vis[sum[i]];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

B.跳跃

思路来源于赛后各AC代码，题解思路过于清奇。

首先维护前缀和 $s u m_{i}$ ，点 $i$ 向前跳最多得分 $m a x l_{i}$ ，向后跳最多得分 $m a x r_{i}$ 。

然后根据维护的值进行 dp，初始设 $dp_{i,j}$ 表示从 $1$ 花 $j$ 步跳到 $i$ 的最大得分。

那么可以列出原始转移方程：

$dp_{i,j}=\begin{cases}\max_{k=1}^{n}\{dp_{k,j-1}+sum_i-sum_{k-1}\}&j \mod 2=0\\\max_{k=n}^{1}\{dp_{k,j-1}+sum_k-sum_{i-1}\}&j \mod 2=1\end{cases}$

发现可以压掉一维，以及用前缀/后缀最大值优化，时间复杂度 $O (n k)$ ，然而由于最多 $5000$ 步内即可更新所有 dp 值，所以时间复杂度 $O (5000 n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e3+5;
const long long INF=1e18;
int sum[MAXN],maxl[MAXN],maxr[MAXN];
long long dp[MAXN];
int main()
{
	int T;
	cin>>T;
	int n,k;
	while(T--)
	{
		scanf("%d %d",&n,&k);
		for(int i=1;i<=n;++i) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
		int tmp=0;
		for(int i=1;i<=n;++i)
		{
			maxl[i]=sum[i]-tmp;
			tmp=min(tmp,sum[i]);
		}
		tmp=sum[n];
		for(int i=n;i>=1;--i)
		{
			maxr[i]=tmp-sum[i-1];
			tmp=max(tmp,sum[i]);
		}
		memset(dp,-0x3f,sizeof(dp));
		dp[1]=0;
		long long ans=0;
		for(int j=1;j<=min(k,5000);++j)
		{
			if(j&1)
			{
				long long maxn=-INF;
				for(int i=1;i<=n;++i)
				{
					maxn=max(maxn,dp[i]-sum[i-1]);
					dp[i]=maxn+sum[i]>=0?maxn+sum[i]:-INF;
					ans=max(ans,dp[i]+max(0ll,1ll*(k-j)*maxl[i]));
				}
			}
			else
			{
				long long maxn=-INF;
				for(int i=n;i>=1;--i)
				{
					maxn=max(maxn,dp[i]+sum[i]);
					dp[i]=maxn-sum[i-1]>=0?maxn-sum[i-1]:-INF;
					ans=max(ans,dp[i]+max(0ll,1ll*(k-j)*maxr[i]));
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C.大陆

原题，参见「SCOI2005」王室联邦，连样例都一模一样……

做法是构造，对于每个点，优先满足子树形成一个省，即若当前子树的节点和（包括子树剩余的）大于 $B$ ，省会为当前节点，这个省一定不会大于 $B\times2$ 。

如果有剩余向上递归，这样可以保证每个省及其省会是连续的。

递归结束后，可能还有一些城市没有找到省会，把这些城市并入根节点所在成市，该省大小不超过 $B\times3$ 。

时间复杂度 $O (n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e4+5;
vector<int>G[MAXN];
int stk[MAXN],ans[MAXN],leader[MAXN];
int n,B,top=0,siz=0;
void dfs(int x,int father)
{
	int tmp=top;
	for(auto y:G[x])
	{
		if(y==father) continue;
		dfs(y,x);
		if(top-tmp>=B)
		{
			leader[++siz]=x;
			while(top>tmp) ans[stk[top--]]=siz;
		}
	}
	stk[++top]=x;
}
int main()
{

	cin>>n>>B;
	int u,v;
	for(int i=1;i<n;++i) scanf("%d %d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	dfs(1,0);
	if(!siz) leader[++siz]=1;
	while(top) ans[stk[top--]]=siz;
	cout<<siz<<endl;
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
	putchar('\n');
	for(int i=1;i<=siz;++i) printf("%d ",leader[i]); 
	return 0;
}