NOMURA Programming Contest 2021

D.1 or 2

题目描述

点此看题

有 \(n\) 个物品，每次拿一个或者拿两个，记录下拿走物品的权值和 \(x\)，最小化 \(\max(x)-\min(x)\)

\(1\leq n\leq 5000\)

解法

不难猜到一个贪心就是我们把最大的和最小的配对，但这是可以证明的：

考虑 \(A\leq B\leq C\leq D\) 两种配对方式满足：

\(\max(A+C,B+D)\geq \max(A+D,B+C),\min(A+C,B+D)\leq\min(A+D,B+C)\)

显然第二种配对方法最优，所以贪心成立。

然后我来了发贪心交上去 \(\tt Wa\) 穿了，哎，就是我的思维不严谨，我是傻逼。

注意这种贪心的适用范围是只存在两两配对的情况，如果存在单个配对就不行了。但是我们可以加入 \(0\)，让单个配对的东西和 \(0\) 配对即可，所以我们要枚举加入 \(0\) 的个数，时间复杂度 \(O(n^2)\)

#include 
#include 
#include 
using namespace std;
const int inf = 2e9;
const int M = 10005;
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,ans,a[M];
signed main()
{
	n=m=read();ans=inf;
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int l=0;l<=n;l++)
	{
		sort(a+1,a+1+m);
		if(m%2==0)
		{
			int mx=-inf,mi=inf;
			for(int i=1;i<=m/2;i++)
			{
				mx=max(mx,a[i]+a[m-i+1]);
				mi=min(mi,a[i]+a[m-i+1]);
			}
			ans=min(ans,mx-mi);
		}
		a[++m]=0;
	}
	printf("%d\n",ans);
}

E.Directed Tree

题目描述

给定 \(n\) 个点的树，求排列 \(a\) 满足 \(a_i\) 不是 \(i\) 的祖先（如果 \(i=a_i\) 仍然认为合法）

\(1\leq n\leq 2000\)

解法

这道题一看就很容斥了，我们枚举 \(a_x\) 是 \(x\) 祖先的位置数量 \(i\)，那么有：

其中 \(f[i]\) 表示钦定 \(i\) 个位置不合法的方案数，可以用树形 \(dp\) 算一下，设 \(dp[i][j]\) 表示以 \(i\) 为根的子树中钦定了 \(j\) 个位置不合法的方案数，每次我们考虑让 \(u\) 的某个儿子 \(v\) 的 \(a_v=u\) 而不是让 \(a_u\) 成为 \(u\) 的某个祖先，这样只管子树内转移才不会有冲突，然后弄个树上背包合并一下子树不合法位置个数即可。

时间复杂度 \(O(n^2)\)

#include 
const int M = 2005;
const int MOD = 998244353;
#define int long long
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,tot,ans,f[M],siz[M],tmp[M],fac[M],dp[M][M];
struct edge
{
	int v,next;
}e[2*M];
void dfs(int u,int fa)
{
	dp[u][0]=1;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		for(int i=siz[u];i>=0;i--)
			for(int j=siz[v];j>=0;j--)
				tmp[i+j]=(tmp[i+j]+dp[u][i]*dp[v][j])%MOD;
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];i++)
			dp[u][i]=tmp[i],tmp[i]=0;
	}
	for(int i=siz[u];i>=0;i--)
		dp[u][i+1]=(dp[u][i+1]+dp[u][i]*(siz[u]-i))%MOD;
	siz[u]++;
}
signed main()
{
	n=read();
	for(int i=2;i<=n;i++)
	{
		int j=read();
		e[++tot]=edge{j,f[i]},f[i]=tot;
		e[++tot]=edge{i,f[j]},f[j]=tot;
	}
	dfs(1,0);fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	for(int i=0;i<=n;i++)
	{
		if(i&1) ans=(ans-dp[1][i]*fac[n-i])%MOD;
		else ans=(ans+dp[1][i]*fac[n-i])%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
}

F.Logical Operations on Tree

题目描述

点此看题

给定一棵 \(n\) 个节点的树，每个节点会被标记 \(0/1\)，每条边会被标记为 AND/OR

进行任意 \(n-1\) 次操作，每次操作选择有边相连的两个点合并成一个新的点，新点的标记为原来点标记经过边对应位运算的结果。

求最后整棵树能只剩下标记 \(1\) 为的点的树的数量。

\(n\leq 10^5\)

解法

思维方式真的很重要，这道题是树上删除问题，从叶子角度考虑最简单，我们讨论叶子和对应边的情况：

• 叶子标记为 \(1\)，边为 or，那么叶子以外的部分任意操作，最后都能合法。
• 叶子标记为 \(1\)，边为 and，那么这个点一定无影响。
• 叶子标记为 \(0\)，边为 or，那么这个点一定无影响。
• 叶子标记为 \(0\)，边为 and，那么操作这个点会让父亲为 \(0\)，优先操作一定最优。

综上，除了第一种情况，我们其它都可以无脑操作叶子。明确上面的结论之后我们可以暴力讨论 \(dp\)，但是官方给出更方便的做法。设 \(f[i]\) 表示子树内不存在 1 or 的情况，\(g[i]\) 表示 \(f[i]\) 的这些情况中合法情况个数，转移：

• 考虑边是 and/or，除掉 1 or 的情况：\(f[u]\leftarrow(2f[v]-g[i])\cdot f[u]\)
• 考虑是 1 and 或者 0 or：\(g[u]\leftarrow g[u]\cdot f[u]\)

最后的答案是 \(2^{2n-1}-f[1]+g[1]\)，这是一个简单的容斥。

#include 
const int M = 100005;
const int MOD = 998244353;
#define int long long
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,tot,f[M],F[M],G[M];
struct edge
{
	int v,next;
}e[2*M];
int qkpow(int a,int b)
{
	int r=1;
	while(b>0)
	{
		if(b&1) r=r*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return r;
}
void dfs(int u,int fa)
{
	F[u]=2;G[u]=1;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		F[u]=(F[v]*2-G[v])*F[u]%MOD;
		G[u]=G[u]*F[v]%MOD; 
	}
}
signed main()
{
	n=read();
	for(int i=1;i