HNOI2018简要题解

2019/04/04 19:59
阅读数 7

#HNOI2018简要题解

D1T1 寻宝游戏

题意

某大学每年都会有一次 Mystery Hunt 的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会。

作为新生的你对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条走廊是如此的长,以至于它被人戏称为 infinite corridor。一次,你经过这条走廊的时,注意到在走廊的墙壁上隐藏着 $n$ 个等长的二进制的数字,长度均为 $m$。你从西向东将这些数字记录了下来,形成一个含有 $n$ 个数的二进制数组 $a_1, a_2, ..., a_n$。很快,在最新的一期 Voo Doo 杂志上,你发现了 $q$ 个长度也为 $m$ 的二进制串 $r_1, r_2, ..., r_q$。聪明的你很快发现了这些数字的含义。保持数组 $a_1, a_2, ..., a_n$ 的元素顺序不变,你可以在它们之间插入 $\wedge$(按位与运算)或者 $\vee$(按位或运算)两种二进制运算符。例如:$11011 \wedge 00111=00011,11011 \vee 00111=11111$。

你需要插入恰好 $n$ 个运算符,相邻两个数之间恰好一个,在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个 $0$,这就形成了一个运算式,我们可以计算它的值。与往常一样,运算顺序是从左往右。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo 杂志里的那一些二进制数 $r_1, r_2, ..., r_q$,而解谜的方法,就是对 $r_1, r_2, ..., r_q$ 中的每一个值 $r_i$,分别计算出有多少种方法填入这 $n$ 个运算符,使得这个运算式的值是 $r_i$ 。然而,infinite corridor 真的很长,这意味着数据范围可能非常大。因此,答案也可能非常大,但是你发现由于谜题的特殊性,你只需要求答案模 $1000000007$($10^9 + 7$,一个质数)的值。

对于 $10%$ 的数据,$n \le 20, m \le 30$,$q = 1$

对于另外 $20%$ 的数据,$n \le 1000$,$m \le 16$

对于另外 $40%$ 的数据,$n \le 500$,$m \le 1000$

对于 $100%$ 的数据,$1 \le n \le 1000$,$1 \le m \le 5000$,$1 \le q \le 1000$

题解

orz myy. 神题。

发现$|1$和$& 0$后的结果是一定的,所以某一位最后为1,则要求最后一个&0的位置要在|1之前。 据说这样从后往前爆搜,及时break可以得到70分?!

然后考虑把操作序列量化成01串,&=1,|=0,则对于某一位来说,从后往前,当操作串的字典序小于运算元素的串,则最后运算结果为1。

这样就很好处理了,把这m个串抠出来,操作串要小于其中一些字串的字典序,大于等于另一些的。也就是$x\le op<y$,把$x,y$转成二进制数后算差就是op的数量了。对这些串排序后算相邻两数差,最后要么没有答案要么是某相邻两数之差。

注意考场没有开O2所以最好用Trie树排序或者鸡排。

复杂度$\mathcal O(nm)$。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define pb push_back
using namespace std;
const int N=1100,M=5100,Tr=5e6+10,mod=1e9+7;
int n,m,q,nod=1,ch[Tr][2],rk[M],tt,bit[N],d[M];
char s[N][M];
vector<int> tag[Tr];
struct Num
{
	int s[N],rk;
	int operator - (Num A) const
		{
			int res=0;
			for(int i=n;i>=1;i--)
				if(s[i]!=A.s[i])
					(res+=1ll*(s[i]-A.s[i]+mod)*bit[n-i+1]%mod)%=mod;
			return res;
		}
}A[M];
void Insert(Num A,int id)
{
	int x=1;
	for(int i=1;i<=n;i++)
	{
		int &v=ch[x][A.s[i]];
		if(!v) v=++nod;x=v;
	}
	tag[x].pb(id);
}
void dfs(int x)
{
	for(int l=tag[x].size(),i=0;i<l;i++)
		rk[++tt]=tag[x][i];
	if(ch[x][0]) dfs(ch[x][0]);
	if(ch[x][1]) dfs(ch[x][1]);
}
int main()
{
	cin>>n>>m>>q;bit[1]=1;
	for(int i=2;i<=n;i++) bit[i]=2ll*bit[i-1]%mod;
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=m;i++)
		for(int j=n,p=0;j>=1;j--)
			A[i].s[++p]=s[j][i]-'0';
	for(int i=1;i<=m;i++) Insert(A[i],i);
	dfs(1);
	for(int i=1;i<=m;i++) A[rk[i]].rk=i;
	for(int i=1;i<m;i++) d[i]=A[rk[i+1]]-A[rk[i]];
	for(int i=1;i<=n;i++) A[m+1].s[i]=0,A[m+2].s[i]=1;
	d[0]=A[rk[1]]-A[m+1],d[m]=(A[m+2]-A[rk[m]]+1)%mod;
	for(int w=1;w<=q;w++)
	{
		scanf("%s",s[0]+1);
		int ans=0,mxl=0,mnr=m+1;
		for(int i=1;i<=m;i++)
			if(s[0][i]=='1') mnr=min(mnr,A[i].rk);
			else mxl=max(mxl,A[i].rk);
		if(mxl<mnr) ans=d[mxl];
		printf("%d\n",ans);
	}
	return 0;
}

D1T2 转盘

题意

一次小 G 和小 H 原本准备去聚餐,但由于太麻烦了于是题面简化如下:

一个转盘上有摆成一圈的 $n$ 个物品(编号 $1$ 至 $n$)其中第 $i$ 个物品会在 $T_i$ 时刻出现。

在 $0$ 时刻时,小 G 可以任选 $n$ 个物品中的一个,我们将其编号记为 $s_0$。并且如果 $i$ 时刻选择了物品 $s_i$,那么 $i + 1$ 时刻可以继续选择当前物品或者选择下一个物品。当 $s_i$ 为 $n$ 时,下一个物品为物品 $1$,否则下一个物品为 $s_{i} + 1$。在每一时刻(包括 $0$ 时刻),如果小 G 所选择的物品已经出现了,那么小 G 将会标记它。小 H 想知道,在物品选择的最优策略下,小 G 什么时候能标记所有物品?

但麻烦的是,物品的出现时间会不时修改。我们将其描述为 $m$ 次修改,每次修改将改变其中一个物品的出现时间。每次修改之后,你也需要求出当前局面的答案。对于其中部分测试点,小 H 还追加了强制在线的要求。

测试点编号 $n$ $m$ $T_i/T_x$ $p$
1 $\le 10$ $\le 10$ $\le 10$ $=0$
2 $\le 1000$ $=0$ $\le 1000$ $=0$
3 $\le 10^5$ $=0$ $\le 10^5$ $=0$
4 $\le 5000$ $\le 5000$ $\le 10^5$ $=0$
5 $\le 8\times 10^4$ $\le 8\times 10^4$ $\le 10^5$ $=0$
6 $\le 8\times 10^4$ $\le 8\times 10^4$ $\le 10^5$ $=1$
7 $\le 9\times 10^4$ $\le 9\times 10^4$ $\le 10^5$ $=0$
8 $\le 9\times 10^4$ $\le 9\times 10^4$ $\le 10^5$ $=1$
9 $\le 10^5$ $\le 10^5$ $\le 10^5$ $=0$
10 $\le 10^5$ $\le 10^5$ $\le 10^5$ $=1$

题解

我真佩服去年的自己、竟然有40分,而今天看了好久才看懂去年的做法。

首先可以证明的是一定是只走一圈。

去年的40分做法:

序列倍长后,$a[i]=T[i]-i$,对于a维护单调递减队列,答案为n个滑动窗口的队头+i。可以把a看成是等待时间,最后加上n-1就是真正的答案了。

AC做法:

其实答案求的就是$$min_{i=1}^{n}[max_{j=i}^{i+n}A_j+i]$$。

发现$A_j>A_{j+n}$后,式子里的max就可以换成后缀max了。考虑用线段树维护这个东西。

每个节点$(l,r)$维护$mx[x]$表示最大的A,$ans[x]$表示$i$取到$[l,mid]$时候的最小答案。

合并信息就重新递归一下,和男神那题超级像。

复杂度$\mathcal O(nlog^2n)$。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=2e5+10;
int n,m,op,T[N],a[N],ans[N<<2],mx[N<<2],Ans;
int calc(int x,int l,int r,int b)
{
	if(l==r) return l+max(mx[x],b);
	int mid=(l+r)>>1;
	if(mx[x<<1|1]>=b) return min(ans[x],calc(x<<1|1,mid+1,r,b));
	else return min(calc(x<<1,l,mid,b),mid+1+b);
}
void pushup(int x,int l,int r)
{
	mx[x]=max(mx[x<<1],mx[x<<1|1]);
	ans[x]=calc(x<<1,l,(l+r)>>1,mx[x<<1|1]);
}
void build(int x,int l,int r)
{
	if(l==r) {mx[x]=a[l],ans[x]=T[l];return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x,l,r);
}
void update(int x,int l,int r,int p)
{
	if(l==r) {mx[x]=a[l],ans[x]=T[l];return;}
	int mid=(l+r)>>1;
	if(p<=mid) update(x<<1,l,mid,p);
	else update(x<<1|1,mid+1,r,p);
	pushup(x,l,r);
}
int main()
{
	cin>>n>>m>>op;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&T[i]);a[i]=T[i]-i;
		T[i+n]=T[i],a[i+n]=T[i]-(i+n);
	}
	build(1,1,n*2);printf("%d\n",Ans=ans[1]+n-1);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(op) x^=Ans,y^=Ans;
		T[x]=T[x+n]=y,a[x]=y-x,a[x+n]=y-x-n;
		update(1,1,n*2,x),update(1,1,n*2,x+n);
		printf("%d\n",Ans=ans[1]+n-1);
	}
	return 0;
}

D1T3 毒瘤

题意

从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题:给出一个数组,要求支持若干种奇奇怪怪的修改操作(例如给一个区间内的数同时加上 $c$,或者将一个区间内的数同时开平方根),并且支持询问区间的和。毒瘤考虑了 $n$ 个这样的修改操作,并将它们编号为 $1 \ldots n$。当毒瘤要出数据结构题的时候,他就将这些修改操作中选若干个出来,然后出成一道题。

当然了,这样出的题有可能不可做。通过精妙的数学推理,毒瘤揭露了这些修改操作之间的关系:有 $m$ 对「互相排斥」的修改操作,第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题中同时含有 $u_i$ 和 $v_i$ 这两个操作时,这道题就会变得不可做。另一方面,当一道题中不包含任何「互相排斥」的操作时,这个题就是可做的。此外,毒瘤还发现了一个规律:$m − n$ 是一个很小的数字(参见「数据范围」中的说明),且任意两个修改操作都是连通的。两个修改操作 $a, b$ 是连通的,当且仅当存在若干操作 $t_0, t_1, ... , t_l$,使得 $t_0 = a,t_l = b$,且对任意 $1 \le i \le l$,$t_{i−1}$ 和 $t_i$ 都是「互相排斥」的修改操作。

一对「互相排斥」的修改操作称为互斥对。现在毒瘤想知道,给定值 $n$ 和 $m$ 个互斥对,他一共能出出多少道可做的不同的数据结构题。两个数据结构题是不同的,当且仅当其中某个操作出现在了其中一个题中,但是没有出现在另一个题中。

测试点 # 1~4 5~6 7~8 9 10~11 12~14 15~16 17~20
$n \le$ $20$ $10^5$ $10^5$ $3000$ $10^5$ $3000$ $10^5$ $10^5$
$m \le$ $n + 10$ $n - 1$ $n$ $n + 1$ $n + 1$ $n + 10$ $n + 7$ $n + 10$

题解

就是求有11条返祖边的树的独立集个数。

很良心地给了75左右的暴力容斥部分分。

正解:

把11*2个点抠出来建虚树,一共不到50个点。预处理出没有返祖边的树的dp值。

现在考虑仍然暴力容斥,但是计算过程可以只用在虚树上计算,也就是说优化掉一个$n$。

发现虚树上每条边的转移系数是一定的,把未知数代进去转移、就可以预处理出转移系数了。

具体来说我的$g[x][0/1]=(a,b)$,$x$的虚树父亲为$f$,则 $$ dp[f][0]=(g[x][0].adp[x][0]+g[x][1].a*dp[x][1]); $$

$$ dp[f][1]=(g[x][0].bdp[x][0]+g[x][1].b*dp[x][1]); $$

所以显然初值$g[x][0]=(1,1),g[x][1]=(1,0)$ 。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define pa pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
const int N=2e5+10,mod=998244353;
struct edge{int next,to;}a[N];
int head[N],cnt,n,m,sf[N],fa[N],f[N][2],ST[N][18];
int dfn[N],S[N],c,tot,dep[N],sta[N],top,out[N];
void link(int x,int y) {a[++cnt]=(edge){head[x],y};head[x]=cnt;}
int find(int x) {return sf[x]==x?x:sf[x]=find(sf[x]);}
int ksm(int x,int k)
{
	int s=1;for(;k;k>>=1,x=1ll*x*x%mod)
				if(k&1) s=1ll*s*x%mod;return s; 
}
void dfs(int x,int fr)
{
	fa[x]=fr;ST[x][0]=fr;
	dep[x]=dep[fr]+1;dfn[x]=++tot;
	for(int p=1;p<=16;p++)
		ST[x][p]=ST[ST[x][p-1]][p-1];
	f[x][0]=f[x][1]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int R=a[i].to;if(R==fr) continue;
		dfs(R,x);
		f[x][0]=1ll*f[x][0]*(f[R][0]+f[R][1])%mod;
		f[x][1]=1ll*f[x][1]*f[R][0]%mod;
	}
	out[x]=tot;
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int p=16;p>=0;p--)
		if(dep[ST[x][p]]>=dep[y]) x=ST[x][p];
	for(int p=16;p>=0;p--)
		if(ST[x][p]!=ST[y][p])
			x=ST[x][p],y=ST[y][p];
	return x==y?x:ST[x][0];
}
void Jump(int &R,int x)
{
	for(int p=16;p>=0;p--)
		if(dep[ST[R][p]]>dep[x]) R=ST[R][p];
}
int cmp(int a,int b) {return dfn[a]<dfn[b];}

vector<int> E[N];
int ban[N],g[N][2],s,Ans;
pa f0[N],f1[N],M[N];
void Calc(int x,int y)
{
	int p=x;
	f0[x]=mp(1,1);f1[x]=mp(1,0);
	while(fa[p]!=y)
	{
		int bs0=1,bs1=1;
		for(int i=head[fa[p]];i;i=a[i].next)
		{
			int R=a[i].to;
			if(R==fa[fa[p]]||R==p) continue;
			bs0=1ll*bs0*(f[R][0]+f[R][1])%mod;
			bs1=1ll*bs1*f[R][0]%mod;
		}
		pa ff0=mp(1ll*f0[x].fi*bs0%mod,1ll*f0[x].se*bs0%mod);
		pa ff1=mp(1ll*f1[x].fi*bs1%mod,1ll*f1[x].se*bs1%mod);
		f0[x]=mp((ff0.fi+ff1.fi)%mod,(ff0.se+ff1.se)%mod);
		f1[x]=mp(ff0.fi,ff0.se);
		p=fa[p];
	}
}
int DP()
{
	for(int i=1;i<=c;i++) g[S[i]][1]=1,g[S[i]][0]=ban[S[i]]?0:1;
	for(int i=c;i>=1;i--)
	{
		int x=S[i];
		g[x][0]*=f[x][0],g[x][1]*=f[x][1];
		for(int j=0,l=E[x].size();j<l;j++)
		{
			int R=E[x][j];Jump(R,x);
			g[x][0]=1ll*g[x][0]*ksm((f[R][0]+f[R][1])%mod,mod-2)%mod;
			g[x][1]=1ll*g[x][1]*ksm(f[R][0],mod-2)%mod;
		}
		for(int j=0,l=E[x].size();j<l;j++)
		{
			int R=E[x][j];
			g[x][0]=1ll*g[x][0]*(1ll*f0[R].fi*g[R][0]%mod+1ll*f0[R].se*g[R][1]%mod)%mod;
			g[x][1]=1ll*g[x][1]*(1ll*f1[R].fi*g[R][0]%mod+1ll*f1[R].se*g[R][1]%mod)%mod;
		}
	}
	return (g[1][0]+g[1][1])%mod;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) sf[i]=i;
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(find(x)!=find(y)) sf[find(x)]=find(y),link(x,y),link(y,x);
		else M[++s]=mp(x,y),S[++c]=x,S[++c]=y;
	}
	dfs(1,0);
	sort(S+1,S+c+1,cmp);
	for(int i=2,t=c;i<=t;i++) S[++c]=LCA(S[i-1],S[i]);
	S[++c]=1;sort(S+1,S+c+1,cmp);
	c=unique(S+1,S+c+1)-S-1;
	for(int i=1;i<=c;sta[++top]=S[i],i++)
	{
		while(top&&dfn[S[i]]>out[sta[top]]) top--;
		if(top) E[sta[top]].pb(S[i]),Calc(S[i],sta[top]);
	}

	for(int zt=0,d=1;zt<1<<s;zt++)
	{
		for(int i=1;i<=s;i++)
			if(zt&(1<<(i-1)))
				d=mod-d,ban[M[i].fi]=ban[M[i].se]=1;
		int res=DP();
		(Ans+=1ll*res*d%mod)%=mod;
		d=1;for(int i=1;i<=s;i++)
				ban[M[i].fi]=ban[M[i].se]=0;
	}
	cout<<Ans<<endl;
}

D2T1 游戏

题意

一次小 G 和小 H 在玩寻宝游戏,有 $n$ 个房间排成一列,编号为 $1,2,…,n$,相邻房间之间都有 $1$ 道门。其中一部分门上有锁(因此需要对应的钥匙才能开门),其余的门都能直接打开。

现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里(每把锁有且只有一把钥匙),并作出 $p$ 次指示:第 $i$ 次让小 H 从第 $S_i$ 个房间出发,去第 $T_i$ 个房间寻宝。但是小 G 有时会故意在指令里放入死路,而小 H 也不想浪费多余的体力去尝试,于是想事先调查清楚每次的指令是否存在一条通路。

你是否能为小 H 作出解答呢?

测试点编号 n m 其他特性
1 $ \le 1000 $ $ \le 1000 $
2 $ \le 1000 $ $ \le 1000 $
3 $ \le 10^5 $ $ \le 10^5 $ $y \le x$ 恒成立
4 $ \le 10^5 $ $ \le 10^5 $ $y \le x$ 恒成立
5 $ \le 10^5 $ $ \le 10^5 $
6 $ \le 10^5 $ $ \le 10^5 $
7 $ \le 10^6 $ $ \le 10^6 $ $y \le x$ 恒成立
8 $ \le 10^6 $ $ \le 10^6 $ $y \le x$ 恒成立
9 $ \le 10^6 $ $ \le 10^6 $
10 $ \le 10^6 $ $ \le 10^6 $

对于所有数据,保证 $1 \le n,p \le 10^6$,$0 \le m < n$,$1 \le x, y, S_i,T_i < n$,保证 $x$ 不重复。

由于本题输入文件较大,建议在程序中使用读入优化。

题解

被暴力艹过90分真的无语。省选如果出现这种情况退役那也没有什么办法了。

方法是对于每个点维护向左以及向右最多能到的区间。

先用单调栈维护最大可能区间,之后由$[l,r]$扩展,找到$[LS,l-1]$中从右往左第一个$key[i]>r$的地方,并把$l$设置为$i+1$。之后便可以拓展右区间。

由于右区间的扩展类似于单调栈,所以不难发现拓展次数最多为$\mathcal O(n)$。因此总复杂度为$\mathcal O(nlogn)$ 。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=1e6+10;
int n,m,q,key[N],l[N],r[N],t[N<<2];
int sta[N],top,LS[N],RS[N];
void build(int x,int l,int r)
{
	if(l==r) {t[x]=key[l];return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x]=max(t[x<<1],t[x<<1|1]);
}
int query(int x,int l,int r,int gl,int gr,int bs)
{
	int mid=(l+r)>>1,res=0;
	if(l>=gl&&r<=gr)
	{
		if(t[x]<=bs) return 0;
		if(l==r) return l;
		if(t[x<<1|1]>bs) return query(x<<1|1,mid+1,r,gl,gr,bs);
		else return query(x<<1,l,mid,gl,gr,bs);
	}
	if(gr>mid) res=query(x<<1|1,mid+1,r,gl,gr,bs);
	if(gl<=mid&&!res) res=query(x<<1,l,mid,gl,gr,bs);
	return res;
}
int Find(int l,int r,int x)
{
	if(l>r) return l;
	int p=query(1,1,n,l,r,x);
	return p?p+1:l;
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),key[x]=y;
	build(1,1,n);LS[1]=1,RS[n]=n;
	for(int i=2;i<=n;i++) LS[i]=(key[i-1]&&key[i-1]<=i-1)?i:LS[i-1];
	for(int i=n-1;i>=1;i--) RS[i]=(key[i]&&key[i]>i)?i:RS[i+1];
	for(int i=n;i>=1;i--)
	{
		r[i]=i;l[i]=Find(LS[i],i-1,i);
		while(r[i]<n&&(!key[r[i]]||(key[r[i]]>=l[i]&&key[r[i]]<=r[i])))
			r[i]=r[r[i]+1],l[i]=Find(LS[i],l[i]-1,r[i]);
	}
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y),puts((l[x]<=y&&r[x]>=y)?"YES":"NO");
}

D2T2 排列

题意

给定 $n$ 个整数 $a_1, a_2, \ldots , a_n(0 \le a_i \le n)$,以及 $n$ 个整数 $w_1, w_2, …, w_n$。称 $a_1, a_2, \ldots , a_n$ 的一个排列 $a_{p[1]}, a_{p[2]}, \ldots , a_{p[n]}$ 为 $a_1, a_2, \ldots , a_n$ 的一个合法排列,当且仅当该排列满足:对于任意的 $k$ 和任意的 $j$,如果 $j \le k$,那么 $a_{p[j]}$ 不等于 $p[k]$。(换句话说就是:对于任意的 $k$ 和任意的 $j$,如果 $p[k]$ 等于 $a_{p[j]}$,那么 $k<j$。)

定义这个合法排列的权值为 $w_{p[1]} + 2w_{p[2]} + \ldots + nw_{p[n]}$。你需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出 $-1$。

样例解释中给出了合法排列和非法排列的实例。

对于前 $20%$ 的数据,$1 \le n \le 10$;

对于前 $40%$ 的数据,$1 \le n \le 15$;

对于前 $60%$ 的数据,$1 \le n \le 1000$;

对于前 $80%$ 的数据,$1 \le n \le 100000$;

对于 $100%$ 的数据,$1 \le n \le 500000$,$0 \le a_i \le n (1 \le i \le n)$,$1 \le w_i \le 10^9$ ,所有 $w_i$ 的和不超过 $1.5 \times 10^{13}$。

题解

这题的映射关系非常复杂好嘛!希望不要出现这种题目特别难懂的题目了!

把这题映射关系搞清楚后,发现就是$a[i]->i$,然后在这棵树(有环无解)上按照拓扑序依次选完所有的点,贡献为选某点的时间×该点权值。

这样大概有40分的状压DP,但是考虑正解:

显然权值小的点要先选,那么权值最小的点在选完其父亲(如果有的话)后,一定马上被选。 考虑每个点向父亲缩,代价为父亲的siz×该点的val。于是各个联通块的权值如何确定呢?

考虑两个联通块AB,当前时刻为i,可以很轻松地列出$W_{AB},W_{BA}$的式子,相减发现$\frac{\sum val}{siz}$小的被先选会更优。

所以用一个set维护每个点,每次选取最小点向父亲合并,最后合成一个点就好了。

这题听说是YALI考过的题,HNOI考完走出考场听到许多“YALI人AK了”之类的言语,不是很爽快——HNOI有YALI学长出的题。当然不可否认的是YALI确实很强,应该也没有泄题的情况。但是我总觉得在这种大赛搬原题是一种极其不负责任的表现。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=1e6+10;
int n,m,q,key[N],l[N],r[N],t[N<<2];
int sta[N],top,LS[N],RS[N];
void build(int x,int l,int r)
{
	if(l==r) {t[x]=key[l];return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x]=max(t[x<<1],t[x<<1|1]);
}
int query(int x,int l,int r,int gl,int gr,int bs)
{
	int mid=(l+r)>>1,res=0;
	if(l>=gl&&r<=gr)
	{
		if(t[x]<=bs) return 0;
		if(l==r) return l;
		if(t[x<<1|1]>bs) return query(x<<1|1,mid+1,r,gl,gr,bs);
		else return query(x<<1,l,mid,gl,gr,bs);
	}
	if(gr>mid) res=query(x<<1|1,mid+1,r,gl,gr,bs);
	if(gl<=mid&&!res) res=query(x<<1,l,mid,gl,gr,bs);
	return res;
}
int Find(int l,int r,int x)
{
	if(l>r) return l;
	int p=query(1,1,n,l,r,x);
	return p?p+1:l;
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),key[x]=y;
	build(1,1,n);LS[1]=1,RS[n]=n;
	for(int i=2;i<=n;i++) LS[i]=(key[i-1]&&key[i-1]<=i-1)?i:LS[i-1];
	for(int i=n-1;i>=1;i--) RS[i]=(key[i]&&key[i]>i)?i:RS[i+1];
	for(int i=n;i>=1;i--)
	{
		r[i]=i;l[i]=Find(LS[i],i-1,i);
		while(r[i]<n&&(!key[r[i]]||(key[r[i]]>=l[i]&&key[r[i]]<=r[i])))
			r[i]=r[r[i]+1],l[i]=Find(LS[i],l[i]-1,r[i]);
	}
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y),puts((l[x]<=y&&r[x]>=y)?"YES":"NO");
}

D2T3 道路

题意

W 国的交通呈一棵树的形状。W 国一共有 $n − 1$ 个城市和 $n$ 个乡村,其中城市从 $1$ 到 $n − 1$ 编号,乡村从 $1$ 到 $n$ 编号,且 $1$ 号城市是首都。道路都是单向的,本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市,恰有一条公路和一条铁路通向这座城市。对于城市 $i$,通向该城市的道路(公路或铁路)的起点,要么是一个乡村,要么是一个编号比 $i$ 大的城市。没有道路通向任何乡村。除了首都以外,从任何城市或乡村出发只有一条道路;首都没有往外的道路。从任何乡村出发,沿着唯一往外的道路走,总可以到达首都。

W 国的国王小 W 获得了一笔资金,他决定用这笔资金来改善交通。由于资金有限,小 W 只能翻修 $n − 1$ 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路,即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利,于是根据人口调查的数据,小 W 对每个乡村制定了三个参数,编号为 $i$ 的乡村的三个参数是 $a_i$,$b_i$ 和 $c_i$。假设从编号为 $i$ 的乡村走到首都一共需要经过 $x$ 条未翻修的公路与 $y$ 条未翻修的铁路,那么该乡村的不便利值为 $$ c_i \cdot (ai + x) \cdot (bi + y) $$ 在给定的翻修方案下,每个乡村的不便利值相加的和为该翻修方案的不便利值。

翻修 $n − 1$ 条道路有很多方案,其中不便利值最小的方案称为最优翻修方案,小 W 自然希望找到最优翻修方案,请你帮助他求出这个最优翻修方案的不便利值。

共 $20$ 组数据,编号为 $1 ∼ 20$。

对于编号 $\le 4$ 的数据,$n \le 20$;

对于编号为 $5 \sim 8$ 的数据,$a_i, b_i, c_i \le 5,n \le 50$;

对于编号为 $9 \sim 12$ 的数据,$n \le 2000$;

对于所有的数据,$n \le 20000$,$1 \le a_i, b_i \le 60$,$1 \le c_i \le 10^9$,$s_i, t_i$ 是 $[−n, −1] \cap (i, n − 1]$ 内的整数,任意乡村可以通过不超过 $40$ 条道路到达首都。

题解

据说这题出题人想复杂了于是成为了普及题。。。验题人干嘛去了啊。。

然而我刚才苦苦思索十分钟还是忘记怎么做了(去年做的)。。就怕被降智啊!!!

设$dp[x][a][b]$表示$x$的子树内,到根还有a条没有修好的公路、b条没有修好的铁路的最小总代价。

没了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
	char ch=getchar();int h=0,t=1;
	while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch=='-')t=-1,ch=getchar();
	while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
	return h*t;	
}
const int MAXN=40010;
int N,head[MAXN],cnt,L[MAXN],R[MAXN];
int A[MAXN],B[MAXN],C[MAXN];
ll dp[MAXN>>1][41][41];
struct edge{int next,to,w;}a[MAXN<<2];
void link(int x,int y,int w){a[++cnt]=(edge){head[x],y,w};head[x]=cnt;}
void Pre(int x,int fa)
{
	for(int i=head[x];~i;i=a[i].next)
	{
		int S=a[i].to;
		if(S==fa)continue;
		L[S]=L[x],R[S]=R[x];
		(a[i].w==1)?L[S]++:R[S]++;
		Pre(S,x);
	}
}
ll DP(int x,int i,int j)
{
	if(x<=N) return dp[x][i][j];
	return 1LL*C[x]*(A[x]+i)*(B[x]+j);
}
void DFS(int x,int fa)
{
	int lc=0,rc=0;
	for(int i=head[x];~i;i=a[i].next)
		if(a[i].to!=fa){DFS(a[i].to,x);rc?lc=a[i].to:rc=a[i].to;}
	if(!lc) return;
	for(int i=0;i<=L[x];i++)
		for(int j=0;j<=R[x];j++)
			dp[x][i][j]=min(DP(lc,i+1,j)+DP(rc,i,j),DP(lc,i,j)+DP(rc,i,j+1));
}
int main()
{
	N=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<N;i++)
	{
		int x=read(),y=read();
		if(x<0)x=-x+N;
		if(y<0)y=-y+N;
		link(i,x,1);link(x,i,1);
		link(i,y,2);link(y,i,2);
	}
	for(int i=1;i<=N;i++)
	{
		int pos=i+N;
		A[pos]=read();
		B[pos]=read();
		C[pos]=read();
	}
	Pre(1,0);
	DFS(1,0);
	printf("%lld\n",dp[1][0][0]);
	return 0;
}

后记

这套题目可以说是非常好、质量非常高的啦。

如果今年让我考这套题目的话,最好的成绩是30+40+75+60+40+100,然而算上联赛也只能踩队线。 可以说非常刺激了。

后天加油啊!

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部