Reincarnation

正因为梦易碎，才格外美好。

绍兴一中NOIP模拟赛 & 组题

发表于 更新于 分类于 ，
本文字数： 4k 阅读时长 ≈ 4 分钟

最打摆的一集，第二弹！

A. 郁闷的小G（depression）

题目简介

给定 个 ，存在 种坑， 填 ， 填 ， 填 ，求一种填坑方式，最大化 。

数据范围：

考虑最大化最小值，所以考虑二分，我们设 ，那么可以通过 的个数推断出 不填入 的个数，从而得到当前 的大小，直接判即可，时间复杂度 。

听说有 做法，大概是分讨吧。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
ll a,b,c,d,e,ans;
inline bool check(ll x)
{
	ll tb=b,td=d;
	tb-=std::max(0ll,x-a),td-=std::max(0ll,x-e);
	if(tb<0||td<0) return 0;
	return c+tb+td>=x;
}
int main()
{
	freopen("depression.in","r",stdin);
	freopen("depression.out","w",stdout);
	read(a,b,c,d,e);
	ans=std::min(std::min(a,c),e);
	a-=ans,c-=ans,e-=ans;
	ll l=0,r=a+c+e+(b+d)/3,res=0;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid)) res=mid,l=mid+1;
		else r=mid-1;
	}
	write(ans+res);
	return 0;
}
/*

*/

B. 小G的树（gtree）

题目简介

给定一棵树，每一条边都有 的概率长 或 ，求出直径期望。

数据范围：

一个很朴素的 做法，这里不细讲。

然后考虑一个更朴素的 做法。考虑求树的直径的朴素做法，记 表示 子树内最长直径， 表示延申到 的最长链。然后合并 即可。

所以我们考虑记录 表示 子树内当前 时的概率，然后记和。然后记 表示前 个儿子中最长链为 ，次长链为 ，子树直径为 的概率，滚动数组 维后做到 。

然后我们考虑取一个前缀，将状态设计为小于等于 的情况，这样可以减少一次枚举，然后再按照树上背包的形式进行优化就可以做到 。

C. 数的距离（number）

题目简介

定义一次操作为乘上一个质数或者除以一个质因子，定义 表示用最少的操作将 变为 。

给定 次操作，维护一个初始为空的不可重集 ：

  • 将 插入 ；
  • 删除 中的 ；
  • 给定 ，求出 。

数据范围：

设 表示 能够除尽的质数的个数，那么 可以进行转化：，或者用一个更加简洁的形式：

然后我们考虑枚举 的因数 作为 ，然后统计答案，这个过程是 的。

然后你发现实际上 的质因子个数不会超过 个，所以这个过程可以开个 std::bitset 优化一下，做到 。

D. PE（pe）

题目简介

给定一个长度为 的序列 ，定义一个长度为 的序列 的权值为：

对 求出 长度为 的权值最大的子序列。

数据范围：

有一个大家都不证，我也不会，但是非常重要的结论——定义 表示长度为 时的答案，那么 一定从 转移而来。

所以暴力求取 ，之后贪心选择 个使得答案最大的数即可。若加入了 ，那么 ，中间所有加入过的数会取反，可以采用线段树维护这一操作。维护权值与后缀相反数的最大值。

还有一种比较厉害的 做法。网上好像找得到。

E. Square（square）

题目简介

原题链接：https://www.luogu.com.cn/problem/P3394

初始存在于 ，现在有一个长度为 的指令串，会使机器人向东西南北中任意一个方向移动一个单位，将该指令串重复 次，求出有多少个格子满足四个角都被走过。具体来讲，求出所有满足 都被走过的二元组 。

数据范围：

首先考虑 的情况，这个时候可以暴力枚举，但显然没有办法扩展。

我们记录第一次循环后到达的点 ，那么对于第一次循环中经过的点 ，一定有 个 。

所以我们按照分别模 分组，也就是可以通过加 得到的分为一类，得到 个同余系。

那么对于点 ，其贡献一定在

之内。

那么每次求交只会涉及 个集合。观察性质，发现每个点集都是相差 的点的并，所以我们视作连续线段后在衰减 倍即可。

所以实际解法就是先线段求并，然后集合求交。

相关文章