NOIP提高组模拟赛Day1

NOIP提高组模拟赛题解

比赛链接
Markdown&PDF&大样例
[数据以及全部压缩包]明天发


Agent1

对于20\%的数据 N \leq 10

这样的话我们可以使用DFS搜索进行枚举,枚举每一个Agent是进A队还是进B队还是不参加大战,复杂度为O(3^{10})

对于40\%的数据 N \leq 10^3

然而我们也可以加入一些剪枝,例如中间判断一下有没有元素是不符合的就剪掉,例如B里加入了个比A里最大元素小的人,那么就剪掉,估计可以再卡过几个点。

对于100\% 的数据 N \leq 10^9

到了10^7甚至10^9规模的数据,这样就不可以使用暴力了。那么我们考率一下推一下式子。

我们可以把Agent的能力值考虑成是有序,然后枚举一个分界线i,把Agent分成两个部分1~ii+1~n,我们要从前面一个部分和后一个部分都组出一只队伍。那么我们确定在i是一定要加入队伍的情况下,看看1~i-1i+1~n分别可以组出多少只队伍,方案数就是他们两个相乘。

\sum_{i=1}^{n} 2^{i-1}*(2^{n-i}-1)

然后我们拆一下式子得出

\sum_{i=1}^{n} 2^{n-1}-2^{i-1}

最后我们再把2^{n-1}拉出来

n*2^{n-1}-\sum_{i=1}^{n} 2^{i-1}

然后我们用公式再把2^{i-1}次方化简一下

n*2^{n-1}-2^n+1

然后我们就可以开个long long然后快速幂后减一下啦。


Portal1

对于20\%的数据 N\leq 5,T[i],C[i] \leq 5,D[i] \leq 10​

这个只要爆搜一下估计可以过啦,5​的全排列再乘2^5​的复杂度。

对于100\%的数据 N\leq 100,T[i],C[i] \leq 20,D[i] \leq 2000

这题我们可以用贪心的方法来解答,我们首先把所有的PortalD[i]为关键字从小到大排序,然后背包判断一下可不可以取,算出个可以取的最大库存,然后倒叙取物品,这样就可以保证时间不会超过消失值,而取到价格库存最大的资源。

还有来自P党dalao炜哥的大虐标程做法,但好像差不多

还有事后告诉我爆搜可以水过的HNYLMS_EndSaH


War1

对于20\%的数据 N \leq 10

对于这个数据而言,直接DFS可以拿到10分,然后加点策略贪心一下估计可以拿到20分。

对于100\%的数据 N\leq 100,M \leq 2*N

这样的话,我们可以考虑用网络流做,在题目中,每点个最多可以向其他边传输A[i]点能量值,那么我们可以把每个Portal拆成两个点,拆成i,i+N。然后再建立st,ed点,对于每个Portalst都向i连一条流量为A[i]的边,i+N都向ed连一条流量为B[i]的边,这样用来限制每个Portal传输给别的Portal的最大能量值,和限制该Portal最大可以接收的能量值。对于每条LINK连接X,Y两个Protal,为了让其只能流向直接相连的点,应该从XY+N连一条边,流量为无限大。最后跑一下网络流,看看可不可以跑满流即可。跑完之后若有可行方案,可以沿边目录枚举每条边,看一下它流过去多少流量,那样用数组记录一下输出即可。

另10月6日博客有NOIP提高组分析报告,有兴趣的关注一下。

“NOIP提高组模拟赛Day1”的6个回复

  1. T3一眼网络流,两眼网络流,三眼网络流……我还以为我看错了,,,
    NOIP模拟赛啊

发表评论

电子邮件地址不会被公开。 必填项已用*标注