NOMURA Programming Contest 2021(AtCoder Regular Contest 121)

C.Odd Even Sort

题目描述

点此看题

有一个长度为 \(n\) 的排列,要求通过 \(n^2\) 次操作把他变成 \(1,2...n\) 的排列:

  • 奇数次操作可以操作奇数位置 \(x\),即交换 \(p[x],p[x+1]\)
  • 偶数次操作可以操作偶数位置 \(x\),即交换 \(p[x],p[x+1]\)

\(n\leq 500\)

解法

\(n^2\) 次操作这么宽松,可以考虑一下一次把 \(1,2,3...\) 换到第一个位置,第二个位置,第三个位置 \(...\)

看上去交换是很容易的,如果目标数字在奇数位置,现在操作也在奇数位置怎么办?这就涉及了浪费步数的问题,递归到 \(n=3\) 的情况是可以特判的,那么我们考虑 \(n>3\) 的情况。

可以直接操作目标数字,再操作初始目标数字位置的前一位浪费步数,那么现在奇偶性就对得上了,直接往前一直操作就行。注意如果目标数字在 \(n\) 这个位置,就操作 \(n-2\) 浪费步数即可。

对于 \(n=3\) 一直无脑乱换,可以证明有限步内达到答案状态。

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int M = 505;
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 T,n,nw,f,ji,ou,p[M];vector<int> ans;
void work(int &nw)
{
    if(nw) swap(p[ji],p[ji+1]),ans.push_back(ji);
    else swap(p[ou],p[ou+1]),ans.push_back(ou);
    nw^=1;
}
void solve(int x)
{
    if(x==n-2)
    {
        while(!(p[n-2]<p[n-1] && p[n-1]<p[n]))
        {
            if(nw) swap(p[ji],p[ji+1]),ans.push_back(ji);
            else swap(p[ou],p[ou+1]),ans.push_back(ou);
            nw^=1;
        }
        return ;
    }
    for(int i=x;i<=n;i++)
        if(p[i]==x)
        {
        	if(i==x) {solve(x+1);return ;}
            if(i%2==nw)
            {
            	if(i==n)
            	{
            		swap(p[n-2],p[n-1]),ans.push_back(n-2);
            		nw^=1;
				}
				else
				{
					swap(p[i],p[i+1]),ans.push_back(i);
	            	swap(p[i-1],p[i]),ans.push_back(i-1);
	            	i++;
				}
            }
            for(int j=i-1;j>=x;j--)
            {
                swap(p[j],p[j+1]);
                ans.push_back(j);nw^=1;
            }
            solve(x+1);
            return ;
        }
}
signed main()
{
    T=read();
    while(T--)
    {
        n=read();ans.clear();nw=1;
        if(n%2==0) ji=n-1,ou=n-2;
        else ji=n-2,ou=n-1;
        for(int i=1;i<=n;i++)
            p[i]=read();
        if(n==2)
        {
            if(p[1]==1) puts("0\n");
            else printf("1\n1\n");
            continue;
        }
        solve(1);
        printf("%d\n",ans.size());
        for(int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
        puts("");
    }
}

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 <cstdio>
#include <iostream>
#include <algorithm>
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\),那么有:

\[ans=\sum_{i=0}^n(-1)^i\cdot f[i]\cdot (n-i)! \]

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

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

#include <cstdio>
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 <cstdio>
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<n;i++)
	{
		int u=read(),v=read();
		e[++tot]=edge{v,f[u]},f[u]=tot;
		e[++tot]=edge{u,f[v]},f[v]=tot;
	}
	dfs(1,0);
	printf("%lld\n",(qkpow(2,2*n-1)-F[1]+G[1]+MOD)%MOD);
}
上一篇:[答疑]我设计的任务状态转换,不需要任务暂停这个状态


下一篇:vuebase-10_Axios配置