NOIP2018 全国模拟赛 (完结!)

http://noi.ac/contest/10

挺毒瘤的,但是看完题解感觉还可以

不难发现好像糖果数量确定的代表花费确定

那么我们就是要满足一个愉悦度情况下选择最少的糖果

考虑枚举一下第一家糖果用了多少

然后我们相应的,要第二家糖果买的sum愉悦度比第一家多,所以说可以二分或者双指针

实现的时候最后两边同时尺取,就是说如果两个指针都大于1就交替?--

最小生成树计数??

其实挺惊艳的

每条边都有一个可能,然后会发现当最小生成树是 $1~n-1$ 的时候就是直接把所有1~n-1形成一颗生成树后的结果

也就是说我们可以 $n^{n-2}$ 得知形态,然后分配权值 $*(n-1)!*(n*(n-1)/2-n+1)!$

如果没有呢?

会发现我们要记录所有可能的连通块信息?

不需要,因为我们连边转移其实只和连通块的大小有关....因为转移系数如果是自连边要在任意连通块内部连接,否则是合并连通块,而任意连通块内部连边在已知多少连通块的情况下这个系数可以直接计算的

而又不难发现,连通块大小相当于一个整数划分....所以说我们要记录所有整数划分的状态

$P_{40}$ ?也是很可的37338

有个优化转移的好方法,就是观察到大小不同的连通块最多根号个,也就是说我们可以把"有多少个大小为i"的这个信息写入转移里,然后就能 $O((\sqrt n)^2 + nlogn)$ 完成一个转移啦


//离散化这个整数划分方案
//具体的,我们可以搜索,用map映射
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 50;
const int MAXP = 5e4 + 7;
const int P = 1e9 + 7;
int n, a[MAXN], tot;
int rcx[MAXP], vis[MAXP], rcs[MAXP][MAXN];
map<vi, int> mp1;
map<int, vi> mp2;
vi b;
bool cmp(int x, int y) {
	return x > y;
}
inline void dfs(int x, int rs, int lst) {
	if(rs == 0) {
		if(mp1.find(b) == mp1.end()) {
			sort(b.begin(), b.end(), cmp);
			mp1[b] = ++tot;
			mp2[tot] = b;
			for(int j = 0; j < x; ++j) {
				rcx[tot] += b[j] * (b[j] - 1) / 2;//每个连通块内部完全图
			}
			for(int j = 0; j < x; ++j) {
				rcs[tot][b[j]]++;//统计有多少个
			}
		}
		return;
	}
	for(int i = lst; i >= 1; --i) {
		b[x] = i;
		if(rs - i < 0)continue;
		dfs(x + 1, rs - i, i);
		b[x] = 0;
	}
	return ;
}

int f[MAXP], g[MAXP];

inline void init() {
	b.resize(n);
	for(int i = 0; i < n; ++i)b[i] = 0;
	//注意每个v的大小都是n+1
	dfs(0, n, n);
	return;
}

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}
//转移我们同样大小连通块枚举一个即可
int tmp[MAXN][MAXN], q1[MAXN], q2[MAXN];
inline void solve() {
	int m = n * (n - 1) / 2;
	f[tot] = 1;//所有都没有
	for(int i = 1; i <= m; ++i) {
		if(vis[i]) {
			for(int S = 1; S <= tot; ++S) {
				vi v = mp2[S];
				if(f[S]) {
					int t = 0;
					for(int k = 0; k < n; ++k) {
						if(!v[k])break;
						for(int j = k + 1; j < n; ++j) {
							if(!v[j])break;
							if(!tmp[v[k]][v[j]]) {
								tmp[v[k]][v[j]] = 1;
								q1[++t] = v[k];
								q2[t] = v[j];
								vi q = v;
								q.pb(v[k] + v[j]);
								int qwq = v[k] * v[j];
								if(v[k] == v[j])qwq = qwq * rcs[S][v[k]] * (rcs[S][v[k]] - 1) / 2;
								else qwq = qwq * rcs[S][v[k]] * rcs[S][v[j]];
								q[k] = 0;
								q[j] = 0;
								sort(q.begin(), q.end(), cmp);
								q.resize(n);
								int T = mp1[q];
								add(g[T], 1ll * f[S] * qwq % P);
							}
						}
					}
					for(int k = 1; k <= t; ++k) {
						tmp[q1[k]][q2[k]] = 0;
					}
				}
			}
		} else {
			for(int S = 1; S <= tot; ++S) {
				add(g[S], 1ll * f[S] * (rcx[S] - i + 1) % P);
			}
		}
		for(int S = 1; S <= tot; ++S) {
			f[S] = g[S], g[S] = 0;
		}
	}
	printf("%d\n", f[1]);
	return;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d", &a[i]);
		vis[a[i]] = 1;
	}
	init();//预处理
	solve();//dp
	return 0;
}

其实题解做法是对应了三种不同的排序方式呢

插入排序

选择最小的旋转到最前

归并排序

对于0/1序列可以这样做,因为我们合并的时候直接reverse左半边的1和右半边的0即可

前面都是0后面都是1就排好序了,实现的时候要一次,就是类似于000[1111 0 0000]11

变为000[0000 0 1111]11

qwq就是使得多的一边有一个回文中心,并且左边都是1即可

快速排序

实现原理就是选取一个 $pivot$ 然后小于这个值的分到左边,大于的分到右边,紧接着递归左右区间

小于的记为0,大于的记为1

排序一个0/1序列?调用归并排序

这样你就有一个最优才 $O(nlog^2n)$ 的乐色排序算法了!

bst...我顺序开题!

考虑操作一本质上顺序不会影响

就是说我们对于一个节点,先交换他和他兄弟还是他父亲和他父亲的兄弟是一样的

而第一个区间操作,会发现其实就是对应了几层全部修改和两层区间修改(前后缀)

而因为n很小,那我们也可以把修改压入一个int内,第i位为0/1表示有没有进行这一位的翻转

那就变成了一个很多次全局加和几个区间加了!

所以说我们直接树状数组维护即可

然后全局加在外层打标记

查询的时候,先查查这个点的标记,然后再跳跳跳即可

显然是贪心匹配最优....

也就是说我们维护一个L1,R1,L2,R2表示前面的一段L1_{R1和后面的一段L2}R2能否匹配

然后每次用哈希判断,子串哈希值即可,如果能匹配就直接 $L1=R1$ , $L2=R2$ , $tot+=2$

然后 $R1>L2$ 就结束了

注意因为 $R1-L1=R2-L2$ 所以说本质不同的其实只有O(n)个

直接枚举

显然的是我们有第一类操作使得每个字符串顺序无意义

$f_{i,j,k}$ 表示i个A,j个B,k个C的点

而魔法也相当于有x个A....能转换成y个A....

于是我们就可以...建图啦!注意这里我们只需要一个字符串使用一个魔法即可!

因为我们没有DP的必要,每个节点都代表了n!种本质不同的字符串,所以说直接做即可

所以说求出最长这个拓扑图上路径即可

随便统计一下都是 $O(n^2)$ 的....就可以知道所以人在行列的排名,就可以用类似map的东西计数

艹...一开始傻逼了

就是直接dp, $f_{i,j}$ 表示前i个数,然后最后有j个数本质不同的方案数

钦点我们不转移到 $f_{i,k}$ 即可......

额鹅鹅鹅这个比ARC原题弱100倍我还是sb了



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int n, m, P;
int f[MAXN][MAXN], sum[MAXN][MAXN];

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}

int main() {
	scanf("%d%d%d", &n, &m, &P);
	f[0][0] = 1;//没意思
	sum[0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < m; ++j) {
			if(j)
				add(f[i][j], 1ll * f[i - 1][j - 1] * (m - j + 1) % P); //接
			add(f[i][j], sum[i - 1][j]); //长度大于j的直接做
		}
		for(int j = m - 1; j >= 1; --j) {
			sum[i][j] = sum[i][j + 1];
			add(sum[i][j], f[i][j]);
		}
	}
	printf("%d\n", sum[n][1]);
	return 0;
}

这什么超级弱化版啊

线段树

对于操作1,我们记录区间距离 $a_{i+1}$ 最近的值(+-)

然后我们修改如果能够改掉就向下递归即可

操作2显然只能影响一个数,带来的额外代价也就 $O(mlogn)$

没有什么....TLE的可能呢

咕咕咕

真的....很傻啊

一个子图只能是几个森林

但凡存在非森林(环)部分,我们把那个环提出来,然后那个又不合法了

所以说我们只需要求出一个最大生成树,然后之外的全部删掉即可

猜到了结论,没有做法

显然我们一定最多只会选择两个....

因为但凡选择第三个,游戏结束后,我们可以删除掉不包括第一次重复元素的集合,就变成两个了

然后我们就能发现可以直接计数了

因为我们第一个集合选择了元素i之后

我们一定会在某个另一个集合选择qwq,直到那个数出现,这个次数是 $c_i-1$ (包含i的集合中本质不同的数字种类数)

那么这个就直接预处理,排序!

但是要小心二者是一个集合的情况

只在一个集合选择,答案就是 $c_i+1$ ,前提是有多个元素

差不许多

会发现我们可以树链剖分维护一下树上路径区间线性基?

怎么实现复杂度都很自闭,三个log?

完蛋完蛋

我们可以考虑分治?

就是处理所有经过mid的询问

预处理一个从mid开始前缀的线性基,一个mid开始后缀线性基

然后两个线性基可以 $O(log^2)$ 加(合并)

那么把两边加起来即可

好像复杂度是 $O(nloglogMax)$ 因为我们 $O(mlog^2n)$ 根本算不上号!

rqy的实现方法

本质不同的线性基只有logMax个,我们记录左边的,左边全部处理出来,挂到log个地方

然后我们扫描线一个r,从 $mid$ 到 $R$ ,插入一个元素就暴力插入之前所有线性基位置,插不动就停下

因为这些线性基本质相同(相互包含),所以l从大到小考虑每次都能用上一次结果->?

$O(logMax)$ 就能完成答案了!

? : 类似于之前区间线性基,就是维护[l,mid]每个基最靠右的位置,这样我们插入的时候就能很开心的只更新log个位置(因为看上去只有一个基)

长度为 $n+1$ 的序列A，其中的每个数都是不大于n的正整数，且n以内每个正整数至少出现一次。

对于每一个正整数 $k=1,..,n+1$ ，求出的本质不同的长度为k的子序列(不一定要连续)的数量。对 $10^9+7$ 取模。

直接计数.....

首先选出子序列方案数为 $\binom{i}{n}$

然后发现算重了一个,就是前面某个位置k和后面某个相同位置j,在k前和j后选择从而凑齐了k的方案数

减去即可,时间复杂度O(n)

code:


#include<bits/stdc++.h>
#define ll long long
const int P = 1e9 + 7;
using namespace std;
const int MAXN = 3e5 + 7;
int n, rc1, rc2;
int a[MAXN], vis[MAXN];
int fac[MAXN], ifac[MAXN];

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init() {
	fac[0] = 1;
	ifac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	return ;
}

inline ll C(int n, int m) {
	if(n < m)return 0;
	return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int main() {
	scanf("%d", &n);
	++n;
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		if(vis[a[i]]) {
			rc1 = vis[a[i]];
			rc2 = i;
		}
		vis[a[i]] = i;
	}
	init();
	for(int i = 1; i <= n; ++i) {
		ll ans = C(n, i);
		ans = ans - C(rc1 - 1 + n - rc2, i - 1) + P; //这个会算重
		ans = ans % P;
		printf("%lld\n", ans);
	}
	return 0;
}

首先转化每一个数为下标和权值的差,这个小于0就别想了

那么一个数能放的位置是固定的....

而且我们有这个数前面要删掉多少数才能凑齐的一个要求

感觉上就是一个上升子序列了的...

这个看上去就是吧?

$f_{i}$ 表示前i个数,而且满足 $A_i==i$ 最长子序列

转移?我们可以发现,一个数i能转移到j当且仅当

$i<j$ 且 $a_i-a_j<i-j$ 就是说这个满足条件..相当于我们有足够多的空位删掉

那么这个转移优化很显然了 $a_i-i<a_j-j$

那么我们就可以二维数点啦!!

一开始假假假了

就是想枚举一些编号,然后看这些点能否形成连通块这样子

显然我们可以花费额外的代价选点使他们连通

那我们换个思路,改为枚举一下区间后,包括这些点的最小连通块大小

有一个 $O(n^3)$ 做法,就是每次 $O(n)$ 判断

判断方法也很简单,我们从每一个点开始dfs,找到一个点就把这个点到那个点路径全染上色继续dfs

直到染色的为一个连通块

$O(n^2)$

发现我们有单调性

就是说随着左端点向右移,右端点也只能单调向右移动

因为我们一定是上次连通块变大才可能行啊,我们删掉点了嘛...

那么我们直接双指针即可

而优化这个,就是在判断上下功夫

结论:一个点集连通所需必要点数为,按照dfs序排序后每个点 $\sum_i{dis(i,i+1)}+dis(1,n)/2+1$

这个包括点集内部已经选上的点啊

所以说我们如果能在 $twopointer$ 时快速维护这个式子就做完了

发现是前驱/后继信息查询,还真能set,做完了

发现可以做

就是说我们暴力枚举的复杂度是允许的,因为均摊是O(m)的

枚举每一行的点
枚举每一列的点
枚举每一个左上-右下对角线的点
枚举每一个左下-右上对角线的点

然后就做完啦

时间复杂度 $O(m)$

直接dp不太行吗?嗯,会计重

就是说我们第一个梯子成为目标的同时第二个梯子也可能成为了目标

$f_{i,j,k}$ 表示考虑了前i层,然后距离最近的为了满足条件的梯子为j,以及现在选择的是哪个去满足

不行,就是这样计重啦

$f_{i,j,k,l,m}$ 表示考虑前i个层,j,k,l,m为最近的横木距离多少

然后转移放在哪里即可

但是最后答案呢?

发现我们可以用额外的0/1?不不不,如果这一维为h就不变(h->h),否则我们才想(x->x+1)

最后答案就是 $f_{n,x,h,h,h}+f_{n,h,x,h,h}+f_{n,h,h,x,h}.....$

正解?

我们再压掉一维就好了....

$f_{i,j,k,l,m}$ 表示前i层,然后在这一层放横木的梯子能否爬到这一行,k,l,m还是和之前相同

转移靠....

考虑我们怎么转移??

如果放在相同位置,直接变为 ${i+1,j+1,k+1,l}$

如果放在不同位置,如果为0(可以爬到这一行),相当于我们已经要计算下一个能否爬过来,也就是说只有当这个第一个状态为h的时候才不行

变为 ${h,i2+1,i3+1,i1==h}$ (为1是爬不到了)

其他三个也同理

然后如果为0,相当于我们这一层爬的他如果要放给其他的,距离只能是距离1,同时其他的也一样,要么平移要么直接给第三维

虽然我们已知dynamic状态,还是不会计重

最后统计所有可行状态方案数之和即可

写的时候注意有一个亡命状态叫做 ${h,h,h,1}$ ,就是说我四个梯子都挂了....千万不能算上他.....

代码中钦点第一维大于=第二维大于=第三维,,而且第四维为1代表不能....qwq

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 32;
const int P = 1e9 + 9;
int n, f[MAXN][MAXN][MAXN][2], g[MAXN][MAXN][MAXN][2], h;

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}

int main() {
	scanf("%d%d", &n, &h);
	f[0][0][0][0] = 1;
	for(int i = 0; i < n; ++i) {
		for(int j = h; j >= 0; --j) {
			for(int k = j; k >= 0; --k) {
				for(int l = k; l >= 0; --l) {
					for(int m = 0; m < 2; ++m) {
						if(m == 1 && j == h && k == h && l == h)continue;
						add(g[min(j + 1, h)][min(k + 1, h)][min(l + 1, h)][m], f[j][k][l][m]);
						if(m) {//如果没有
							add(g[h][min(k + 1, h)][min(l + 1, h)][j == h], f[j][k][l][m]);
							add(g[h][min(j + 1, h)][min(l + 1, h)][k == h], f[j][k][l][m]);
							add(g[h][min(j + 1, h)][min(k + 1, h)][l == h], f[j][k][l][m]);
						} else {
							add(g[min(k + 1, h)][min(l + 1, h)][1][j == h], f[j][k][l][m]);
							add(g[min(j + 1, h)][min(l + 1, h)][1][k == h], f[j][k][l][m]);
							add(g[min(j + 1, h)][min(k + 1, h)][1][l == h], f[j][k][l][m]);
						}
					}
				}
			}
		}
		for(int j = h; j >= 0; --j) {
			for(int k = j; k >= 0; --k) {
				for(int l = k; l >= 0; --l) {
					for(int m = 0; m < 2; ++m) {
						f[j][k][l][m] = g[j][k][l][m];
						g[j][k][l][m] = 0;
					}
				}
			}
		}
	}
	int ans = 0;
	for(int j = h; j >= 0; --j) {
		for(int k = j; k >= 0; --k) {
			for(int l = k; l >= 0; --l) {
				for(int m = 0; m < 2; ++m) {
					if(m == 1 && j == h && k == h && l == h)continue;
					add(ans, f[j][k][l][m]);
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

显然可以扫描线,先预处理每个颜色向前跳一步是哪个位置

然后我们动态维护一个向前跳T步跳到的位置,....静态维护也行

回答所有右端点在j的答案,显然线段树维护所有左端点在某个区间的询问的答案

然后我们有对于一个颜色相当于向前跳T步位置+1,向前跳T+1步的位置-1

查询答案就是一个区间和查询, $[L,R]$ 的 $sum$

六场完结,有机会会更新六场热身赛的题解

夏晓光(loveJY)的博客

qbxt D10 && NOIP提高组考前刷题冲刺班（第十场）