JXOI2018简要题解

2019/04/04 19:58
阅读数 20

JXOI2018简要题解

T1 排序问题

题意

九条可怜是一个热爱思考的女孩子。

九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法: Gobo sort !

Gobo sort 的算法描述大致如下:

  1. 假设我们要对一个大小为 $n$ 的数列 $a$ 排序。
  2. 等概率随机生成一个大小为 $n$ 的排列 $p$ 。
  3. 构造一个大小为 $n$ 的数列 $b$ 满足 $b_i=a_{p_i}$ ,检查 $b$ 是否有序,如果 $b$ 已经有序了就结束算法,并返回 $b$ ,不然返回步骤 $2$ 。

显然这个算法的期望时间复杂度是 $O(n\times n!)$ 的,但是九条可怜惊奇的发现,利用量子的神奇性质,在量子系统中,可以把这个算法的时间复杂度优化到线性。

九条可怜对这个排序算法进行了进一步研究,她发现如果一个序列满足一些性质,那么 Gobo sort 会很快计算出正确的结果。为了量化这个速度,她定义 Gobo sort 的执行轮数是步骤 $2$ 的执行次数。

于是她就想到了这么一个问题:

现在有一个长度为 $n$ 的序列 $x$ ,九条可怜会在这个序列后面加入 $m$ 个元素,每个元素是 $[l,r]$ 内的正整数。 她希望新的长度为 $n+m$ 的序列执行 Gobo sort 的期望执行轮数尽量的多。她希望得到这个最多的期望轮数。

九条可怜很聪明,她很快就算出了答案,她希望和你核对一下,由于这个期望轮数实在是太大了,于是她只要求你输出对 $998244353$ 取模的结果。

对于 $30%$ 的数据, $T\leq 10$ , $n,m,l,r\leq 8$。
对于 $50%$ 的数据, $T\leq 300,n,m,l,r,a_i\leq 300$ 。
对于 $60%$ 的数据, $\sum{r-l+1}\leq 10^7$ 。
对于 $70%$ 的数据, $\sum{n} \leq 2\times 10^5$ 。
对于 $90%$ 的数据,$m\leq 2\times 10^5$。
对于 $100%$ 的数据, $T\leq 10^5,n\leq 2\times 10^5,m\leq 10^7,1\leq l\leq r\leq 10^9$ 。
对于 $100%$ 的数据, $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。

题解

一道不错的签到题。

首先如果每个数都不同,画一画可以知道,有且只有唯一的一种排列是满足条件的,此时需要$n!$次。

但是有数相同,那么我们可以强制他们有大小关系、每一种大小关系对应一种排列。如果相同的数个数分别是$a_1,a_2...a_k$,则答案为$\frac{n!}{a_1!a_2!a_3!...a_k!}$

考虑怎么样加数会使得答案最大:肯定越平均越大(优先加个数少的数字,因为乘的分母小)。于是就维护一个类似阶梯的东西贪心地加就好了。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int mod=998244353,N=2e5+10;
int n,m,l,r,jc[11000000],a[N],b[N],c[N],t[N];
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 Work()
{
	scanf("%d%d%d%d",&n,&m,&l,&r);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int ans=jc[n+m],t1=0,t2=0,top=0;
	for(int i=1;i<=n;i++)
		if(a[i]>=l&&a[i]<=r) b[++t1]=a[i];
		else c[++t2]=a[i];
	b[t1+1]=c[t2+1]=0;
	for(int i=2,res=1;i<=t2+1;i++)
		if(c[i]!=c[i-1]) ans=1ll*ans*ksm(jc[res],mod-2)%mod,res=1;
		else res++;
	for(int i=2,res=1;i<=t1+1;i++)
		if(b[i]!=b[i-1]) t[++top]=res,res=1;
		else res++;
	sort(t+1,t+top+1);
	int s=r-l+1-top,nw=0,i=1;
	for(;i<=top;i++)
		if(1ll*s*(t[i]-nw)<=m)
			m-=1ll*s*(t[i]-nw),nw=t[i],s++;
		else break;
	nw+=m/s;m%=s;
	ans=1ll*ans*ksm(ksm(jc[nw+1],mod-2),m)%mod;
	ans=1ll*ans*ksm(ksm(jc[nw],mod-2),s-m)%mod;
	for(;i<=top;i++) ans=1ll*ans*ksm(jc[t[i]],mod-2)%mod;
	printf("%d\n",ans);
}
int main()
{
	int T;cin>>T;jc[0]=1;
	for(int i=1;i<=1e7+1e6;i++) jc[i]=1ll*jc[i-1]*i%mod;
	while(T--) Work();
}

T2 游戏

题意

九条可怜是一个富有的女孩子。她长大以后创业了,开了一个公司。 但是管理公司是一个很累人的活,员工们经常背着可怜偷懒,可怜需要时不时对办公室进行检查。

可怜公司有 $n$ 个办公室,办公室编号是 $l\sim l+n-1$ ,可怜会事先制定一个顺序,按照这个顺序依次检查办公室。一开始的时候,所有办公室的员工都在偷懒,当她检查完编号是 $i$ 的办公室时候,这个办公室的员工会认真工作,并且这个办公室的员工通知所有办公室编号是 $i$ 的倍数的办公室,通知他们老板来了,让他们认真工作。因此,可怜检查完第 $i$ 个办公室的时候,所有编号是 $i$ 的倍数(包括 $i$ )的办公室的员工会认真工作。

可怜发现了员工们通风报信的行为,她发现,对于每种不同的顺序 $p$ ,都存在一个最小的 $t(p)$ ,使得可怜按照这个顺序检查完前 $t(p)$ 个办公室之后,所有的办公室都会开始认真工作。她把这个 $t(p)$ 定义为 $p$ 的检查时间。

可怜想知道所有 $t(p)$ 的和。

但是这个结果可能很大,她想知道和对 $10^9+7$ 取模后的结果。

对于 $20%$ 的数据,$r-l+1\leq 8$。
对于另 $10%$ 的数据,$l=1$。
对于另 $10%$ 的数据,$l=2$。
对于另 $30%$ 的数据,$l\leq 200$。
对于 $100%$ 的数据,$1\leq l\leq r\leq 10^7$。

题解

一道简单的组合计数问题。

如果把倍数关系画成一张拓扑图的话,那么当且仅当入度为0的点都被选了,检查结束。

设一共有k个入度为0的点,考虑选多少次能够选全,答案就是

$$\sum_{i=k-1}^{n-1}(i+1)C_{i}^{k-1}k!(n-k)!$$

含义是在前$i$次中选了$k-1$个,在第$i+1$次中选了剩下的那一个。贡献是$i+1$,在前$i$次中选出$k-1$次决策用来选必选点,把每一种决策是否选必选点分配好后、只需要把必选点和非必选点排列上去就是方案了,为$k!(n-k)!$。

在找入度为0的点是用线性筛,找到自己在$[l,r]$且为质数或最大因数不在$[l,r]$的数。

代码

#include<iostream>
using namespace std;
const int N=1e7+10,mod=1e9+7;
int l,r,n,Ans,cnt,ispri[N],pri[N],jc[N],inv[N],tot;
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 Pre()
{
	ispri[1]=pri[1]=1;
	if(l==1) {cnt=1;return;}
	for(int i=2;i<=r;i++)
	{
		if(!ispri[i]) pri[++tot]=i,cnt+=(i>=l);
		for(int j=1;j<=tot&&i*pri[j]<=r;j++)
		{
			ispri[i*pri[j]]=1;
			if(i<l&&i*pri[j]>=l) cnt++;
			if(i%pri[j]==0) break;
		}
	}
}
int main()
{
	cin>>l>>r;n=r-l+1;Pre();jc[0]=inv[0]=1;
	for(int i=1;i<=r;i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[r]=ksm(jc[r],mod-2);
	for(int i=r-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	for(int i=cnt-1;i<=n-1;i++)
		(Ans+=1ll*jc[i]*inv[i-cnt+1]%mod*(i+1)%mod)%=mod;
	Ans=1ll*Ans*cnt%mod*jc[n-cnt]%mod;
	cout<<Ans<<endl;
}

T3 守卫

题意

九条可怜是一个热爱运动的女孩子。

这一天她去爬山,她的父亲为了她的安全,雇了一些保镖,让他们固定地呆在在山的某些位置,来实时监视九条可怜,从而保护她。

具体来说,一座山可以描述为一条折线,折线的下方是岩石。这条折线有 $n$ 个折点,每个折点上有一个亭子,第 $i$ 个折点的坐标是 $(i,h_i)$ 。九条可怜只可能会在亭子处玩耍,那些保镖也只会在亭子处监视可怜。

由于技术方面的原因,一个保镖只能监视所有他能看得到的,横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子 $p$ ,当且仅当他所在的亭子 $q$ 和 $p$ 的连线不经过任何一块岩石。特别地,如果这条连线恰好经过了除了 $p,q$ 以外的亭子,那么我们认为保镖看不到可怜。

雇佣保镖是一件很费钱的事情,可怜的父亲希望保镖越少越好。

可怜的父亲还希望得到详尽的雇佣保镖的方案,他知道有些亭子可能正在维修,他想对所有的 $1\leq l\leq r\leq n$ 计算:如果事先已知了只有区间 $[l,r]$ 的亭子可以用来玩耍(和监视),那么最少需要多少个保镖,才能让 $[l,r]$ 中的每一个亭子都被监视到。

可怜的父亲已经得到了一个结果,他希望和你核实他的结果是否正确。

对于 $30%$ 的数据, $n\leq 20$ 。
对于 $70%$ 的数据, $n\leq 500$ 。
对于 $100%$ 的数据, $n\leq 5000$ 。
对于 $100%$ 的数据, $1\leq h_i\leq 10^9$ 。

题解

略有难度的DP。

首先可以维护斜率最值来得到两点间的可见关系。(一开始以为可见区域一定是一段区间,搞了好久的贪心结果错了,Hack:5 1 4 5)

然后设$f[l][r]$表示这个区间的最少关键点数,那么一定要在$r$处放置一个,再依次找$r$看不到的极大区间$[l1,r1]$,考虑在$r1,r1+1$中选一个点作为关键点就好了。

一个需要解释的地方就是为什么$[r1+2,r]$都看不到$[l1,r1]$:因为$r$看得到$r1+1$和$r1+2$,所以$r$和$r1+2$连线的夹角要大一些、在$r$和$r1+1$连线下方;如果$r1+2$看得到$r1$的话,则$r1+2$和$r1+1$的连线的夹角比$r1+2$和$r1$的大。夹角均为x正半轴出发的有向角,如此一画发现矛盾,$r1+2$看不到$r1$。

代码很简单,固定一个$r$,从后往前扫$l$。

代码

#include<iostream>
using namespace std;
const int N=5100;
int n,h[N],f[N][N],see[N][N],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1,l=0;i<=n;i++,l=i-1)
		for(double mn=1e9;l>=1;l--)
			if(1.0*(h[i]-h[l])/(i-l)<mn) mn=1.0*(h[i]-h[l])/(i-l),see[l][i]=1;
	for(int r=1;r<=n;r++)
		for(int l=r,s=1,lst=l;l>=1;l--)
		{
			if(see[l][r])
			{
				if(!see[l+1][r]) s+=min(f[l+1][lst],f[l+1][lst+1]);
				f[l][r]=s;
			}
			else
			{
				if(see[l+1][r]) lst=l;
				f[l][r]=s+min(f[l][lst],f[l][lst+1]);
			}
			ans^=f[l][r];
		}
	cout<<ans<<endl;
}

后记

听说JXOI 80分就能进队什么鬼啊。。

这放在HN那不晓得有多少AK的。。

我做起来还是比较轻松吧,100+100+30。当然T2推式子的时候有一项推错了,瞟一眼题解发现这题确实是推式子才继续把它推对;T3xjb贪心过了前三个点。这些都是考场上三个半小时不一定能写出来的,所以说虽然80分可以进队,但真正如果是考试,自己又能不能不失误呢?还需要斟酌、修炼。

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