洛谷一些经典好题整理

毕竟要退役了,对自己昔日最喜欢的oj还是友善点吧

洛谷乐色?抱歉,绝大多数人都不这样认为

T158782 Galgame/P7118

一个n个点的二叉树的方案数是卡特兰数

因为显然我们 $f_i$ 表示i个点的二叉树方案数,转移的时候枚举左子树大小进行卷积,就是卡特兰数的形式

于是我们想复习一下卡特兰数的知识

$h_n=C_{n,2n}-C_{n+1,2n}$

这个式子实际含义是

对于一个n个元素的出栈问题,我们有n次入栈(1),n次出栈(0)

那么我们就要写成一个0/1序列,表示出进栈序列,不难发现他的方案数就是 $h_n$

于是我们可以得出 $C_{n,2n}$ 表示这些出栈序列总的方案数

但是还要减去不合法的,你会发现相当于从左向右扫第一次0的个数比1多了

此时有m个1,m+1个0

那么我们不妨钦点从那个位置多了的位置开始向后的1/0交换个数,有n-m个0,n-m-1个1

那么就相当于选出n+1个0的方案数 $C_{n+1,2n}$

这个也可以用坐标轴理解...相当于n对括号有多少种匹配方式？

的+-1问题

于是回到这个题

我们发现,可以按照如下顺序不重不漏的计数

一开始的时候求出所有小于他的树方案数

设当前根为u,已知siz[u]=n

钦点左子树小于右子树进行计数,枚举左子树大小进行卷积即可
递归左子树,大小正好等于原来左子树大小(下一步比较出来),得到方案数乘上右子树随便的方案数
递归右子树,没有系数,因为左子树一定要一样....
递归到叶子,返回0,因为不可能比较出来啦

第一步优化:如果左子树小于右子树,直接枚举,否则我们总方案数-左子树超出的部分(选大于原来左子树的方案数)

于是卷积?这个复杂度是允许的,因为我们是枚举小的一边进行卷积,根据启发式合并原理,一个点要想被算到,它祖先的兄弟节点一定比祖先大,所以每次一定会翻倍,所以最多算 $O(log)$ 次

最后复杂度 $O(nlogn)$


//其实就是卷卷积
//但是这个复杂度分析是真没想到啊
//2i!/i!*(i+1)!
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
const int P = 998244353;
int n, ls[MAXN], rs[MAXN], h[MAXN], siz[MAXN];
int fac[MAXN], ifac[MAXN], ans;

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

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;
	h[0] = 1;
	for(int i = 1; i <= n << 1; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n << 1] = ksm(fac[n << 1], P - 2);
	for(int i = (n << 1) - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	for(int i = 1; i <= n; ++i)h[i] = 1ll * fac[i << 1] * ifac[i] % P * ifac[i + 1] % P;
	for(int i = 1; i < n; ++i) {
		add(ans, h[i]);
	}
	return;
}

inline int solve(int u) {
	if(!u)return 0;//不存在
	siz[u] = 1;
	int ret1 = solve(ls[u]), ret2 = solve(rs[u]);
	siz[u] += siz[ls[u]];
	siz[u] += siz[rs[u]];
	int ret = (1ll * ret1 * h[siz[rs[u]]] % P + ret2) % P;
	if(siz[ls[u]] <= siz[rs[u]]) {
		for(int i = 0; i < siz[ls[u]]; ++i) {
			add(ret, 1ll * h[i] * h[siz[u] - i - 1] % P);
		}//直接卷起来
	} else {
		add(ret, h[siz[u]]);
		for(int i = siz[ls[u]]; i < siz[u]; ++i) {
			sub(ret, 1ll * h[i]*h[siz[u] - i - 1] % P);
		}//角去根一点
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &ls[i], &rs[i]);
	}
	init();
	add(ans, solve(1));
	printf("%d\n", ans);
	return 0;
}
/*
3
2 3
0 0
0 0

*/

T157514 Mivik 的游戏

手玩一下?

10101->10001->11001->11101->11111

首先不可能有never,因为像这样的游戏,一定是在两个位置反复横跳才行,而他玩几组发现不可能在两个位置横跳

然后观察发现,我们一定有个分界点,满足前面的都在k前后面都大于等于k

那么这个一定就会导致:
k
00000001......

00000011......

00000010......

00000000......

00000100......

00000110......

发现我们每个位置要 $p_i-j$ 次操作才能改变

每个位置对于答案的贡献形如 $2p_i-2j+1$ 次,其中j表示目前k的大小

所以答案就是 $2 *\sum p_i -2 *\sum k + k$

做完了啦,我们用线段树维护 $p_i$ 和k之和即可

P7108 移花接木

分类讨论吧

$a<b$

我们既要移花也要接木

不难发现我们前h层要

$(b-a) * (b^0+b^1+b^2+...+b^{h-1})$

次移花

后面那个根据等比数列求和是 $b^h-1$

发现我们h+1层此时也补齐了,所以说我们要移花干掉一些

然后我们要把第h+1层都干掉,为 $b^h * a$ ,但是我们有可以从中移花(额外干掉),所以说要减去之前移花的代价

相加正好就是 $b^{h} * a$

$a>b$

此时可以移花....

所以说我们可以(a-b)调整好一个节点,而我们要保留 $b^{h}-1$ 个节点

所以是 $(a-b)*{b^{h}-1}$

但是还不太够,我们最后一层的都要干掉

为 $b^h*a$

最后a=b

答案是 $a^{h+1}$

那个公式还要特判公比为1的情况.....因为此时求和公式分母为0....


#include<bits/stdc++.h>
#define ll long long
const int P = 1e9 + 7;
int T, a, b, h;

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;
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%d%d%d", &a, &b, &h);
		if(a == b)printf("%lld\n", ksm(a, h + 1) % P);
		else if(a < b)printf("%lld\n", ksm(b, h) * a % P);
		else if(b != 1)printf("%lld\n", ((ksm(b, h)*a % P + (ksm(b, h) - 1) * (a - b) % P * ksm(b - 1, P - 2) % P) + P) % P);
		else printf("%lld\n", ((ksm(b, h)*a % P + 1ll * h * (a - b) % P) + P) % P);
	}
	return 0;
}

P7105 「C.E.L.U-01」门禁

期望DP,find it in C.E.L.U-01

P6858 深海少女与胖头鱼

一个胖头鱼被攻击,分两类情况
攻击到带圣盾的
转换到一个简单局面:除了一只外所有鱼都有圣盾
这样下无论如何要连续对一个造成两次伤害才行....
我们看两个的情况
1
1/2 -> 1
1 ??
1/2 -> 2
不变...
f_i表示i个鱼都有圣盾,然后现在要期望攻击几次
$f_i=1+1+f_{i-1}*1/i+(f_i-1)*{i-1/i}$
$1/i*f_i=1+f_{i-1}*1/i+1/i$
$f_i=i+1+f_{i-1}$
2 3 4 5 6....
的一个前缀和
然后我们还可能有不带圣盾的
会发现,攻击一次我们的数量减少1
然后概率可能会变变变
$g_i$ 表示有i只没有带圣盾的到最终结束时的期望次数
$g_i=1+i/n+i*g_{i-1}+n/n+i*f_{i+n}$
$g_0=f_n$
做完了,复杂度 $O(m)$

P6859 蝴蝶与花/P3514 [POI2011]LIZ-Lollipop

学到了学到了有毒啊有毒啊

这个我记得是正瑞之前出过的,就是1,2序列问有没有区间和为x.....

这种思想应该是对于小值域情况下移动端点的讨论吧

先不算这个删除

那么就会发现,我们有个很牛逼很牛逼的结论

对于k(k>2),如果他能拼出,k-2一定能拼出

因为我们可以通过左右两边有2,就缩小2,反之左右同时缩小,减少2*1

所以TAK/NIE只需要找到最大的奇数和最大的偶数即可

其中一个甚至不需要找,统计一遍和即可

另外一个,我们找到开头向后/结尾向前最近一个1即可

那么P3514 就做完了

然后P6859带修版本,我们要上线段树

但是整体思想和这个还是一样的,考虑端点扰动

先找到 $[l,r]$ 满足和为 $s+1$ 且 $a[r]$ 等于2

然后从l向前找第一个1,r向后找第一个1,二者最小位置平移过去即可

因为两边存在一个1都可以缩端点成立

否则,我们只能整体右移保持和不变

线段树二分/树状数组二分维护这个前缀和即可

而找1其实可以另一个树状数组上二分实现,其中2=0,1=1

P7100 [w3R1] 团

哇偶

这样建图可以很懒的不用输入很多边,相应代价就是求最短路跟玩似的

使用dijkstra的思路,每个点按照到一号点最短路存下

取出堆顶,访问所有包括这个点的集合,如果有个集合还没有被标记
访问所有集合内的点进行松弛,把这个集合标记
弹出,回到步骤1

为什么是对的呢?因为你会发现最关键的边权只由两个数决定,而且其中一个是我们无法篡改的

那么我们从1号点出发只需要松弛一次就能得到其所在集合所有最小的

而又因为正是因为自己的 $w_i$ 是所有的当前最小的,才会在第二歩被取出,然后去松弛其他集合

也就不存在反复松弛一个点的情况

等等,这是读错题的版本吧....好像每个点在不同集合中的点权不同?????????

那还是优化建图吧,所有一个集合内的点向一个点连边,然后边权为 $w_i$ 即可

P6862 [RC-03] 随机树生成器

有毒啊呸

我喜欢算期望/划掉

考虑k成为一个大于k的j概率是什么

$\frac 1 j $

所以所有度数求和呢?

$(\sum \frac 1 j + 1) * fac[n]$

注意1没有父亲


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e7 + 7;
const int P = 1e9 + 9;
int T;
int fac[MAXN], ifac[MAXN], inv[MAXN], sum[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() {
	int n = 1e7;
	fac[0] = 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;
	for(int i = 1; i <= n; ++i)inv[i] = 1ll * ifac[i] * fac[i - 1] % P;
	for(int i = 1; i <= n; ++i)sum[i] = (sum[i - 1] + inv[i]) % P;
}

int main() {
	scanf("%d", &T);
	init();
	for(int i = 1, n, k; i <= T; ++i) {
		scanf("%d%d", &n, &k);
		if(k != 1)
			printf("%lld\n", 1ll * fac[n - 1] * (sum[n - 1] - sum[k - 1] + 1 + P) % P);
		else 	printf("%lld\n", 1ll * fac[n - 1] * (sum[n - 1] - sum[k - 1] + P) % P);
	}
	return 0;
}

P6860 象棋与马

数学推导还是很好玩的

显然,我们只要能走到(0,1),就能走到所有地方

为什么?你能走到(1,0)吧,也能走到(x,y)吧

$gcd(a,b)$ 不为1显然无解

那么我们考虑发觉一个(a,b)满足条件的要求

能发现,我们能走到的无非是 $(2ax,2by),(2ax+x,2by+y)$ , $(2cy,2dx),(2cy+y,2dx+x)$

然后神仙推导:

仿照(0,0)->(1,1)过程

我们有
1.
$2ax=2cx$

$2by=2dx+1$
2.
$2ax=2cy+y$

$2by=2dx+x....$

等共四组个式子

然后设k为任意整数

那你会发现 $ax-by,cy-dx$ 就是任意整数

然后我们有什么 $2k-x/y=0/1$ ,从而推的x+y为奇数时有解

很神仙....

然后发现,这个条件相当于(a,b)=1且a+b为奇数

对于一个偶数x,显然所有偶数都和他不互质,答案为 $\phi x$

对于一个奇数x,显然存在奇数和他互质, $gcd(x,y)=1$ ,就有 $gcd(x,x-y)=1$

$x-y$ 是一个偶数/jk

那么也玩完了,答案为 $\frac {\phi x} {2}$

最后我们做1e10

杜教筛 $phi$

补充一个求原根的方法

就是先根号求出phi,用公式 $n*\prod_i{1-1/pi}$

然后我们除掉每个质因子,和枚举的原根mod m意义下求次方,如果有一个等于1,当前g一定不是原根

即 $g^{\phi m / p_i} \equiv 1 (\mod m)$

然后最后求答案我们可以写成这个式子

ans_n=ans_{\lfloor \frac{n}{2} \rfloor}+\sum_i \phi i

相当于算上一遍奇数的,然后去算偶数的,又因为偶数 $\phi 2x$ 的等于 $2\phi x$

qwq就能做完啦

P6863 [RC-03] 上下求索

观察下面方程发现,我们乘积项一定可以干掉右边一个次方项

然后留下次方项-乘积项的系数,加给 $x_1$ 的系数

然后最后统计一下开头项系数,右边除掉后开根即可...注意一定是正负两个解

艹.不对

点开题解,我直接吓死

左边配方

$a_ix_i^2+b_ix_ix_{i-1}+a_{i+1}x_{i+1}^2$

然后

$(a_i-\frac{b_i^2}{4a_{i+1}})x_i^2+(\frac{b_i}{2\sqrt{a_{i+1}}}x_i+\sqrt{a_{i+1}}x_{i+1})^2$

右边哪项显然可以干掉,把左边哪项向前推即可

时间复杂度On,其实思想就是一样的


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e5 + 7;
int n, m;
ll a[MAXN], b[MAXN];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)scanf("%lld", &a[i]);
	for(int j = 1; j < n; ++j)scanf("%lld", &b[j]);
	for(int i = n - 1; i >= 1; --i) {
		a[i] -= (b[i] * b[i] / 4 / a[i + 1]);
	}
	printf("%lld %lld\n", (ll) - sqrt(1ll * m / a[1]), (ll)sqrt(1ll * m / a[1]));
	return 0;
}

合并字符串的价值

https://ac.nowcoder.com/acm/problem/13248

就这啊

不难发现我们无论怎么合并,都是两个串左边一个前缀的和和右边后缀的和进行更新答案

而且是所有字符的min那种,这个min就很有单调性内味了

于是乎我们可以发现,随着我们左端点向右移动,另一个数组的分界点只能向左移动,而且不可能回弹,没有我多字符的情况下还要你多字符才能使对方取得min的情况

但是我们的移动可能会导致完蛋....就是说减少了一些不需要的字符使得答案变小了,然鹅继续向前移动可能增添一些字符使得答案变大了,不具有实际意义的单调性

然后呢?难道这个会很多吗?

不会,这样的case仅仅有4种

即我们枚举了一边后,另一边仅仅会有四条分界点,满足前面这个字符的贡献是一个东西,后面的贡献是一个东西

那么我们对于这4部分分别求最大值即可

具体的,我们在第一个上面推进,然后这几个分界点也只能单调移动,实现一个区间修改,直接维护每个分界点后移即可

线段树每个位置表示分界点在x的答案

P6855 「EZEC-4.5」走方格

我们只需要找到哪些是必经点即可

还记得我们之前做的那道题吗?满足从s到他和从他到t的方案数一样的点就是必经点,然后找到所有必经点中权值最大的内个删掉即可

不对,我们可以枚举哪个删掉,然后 $O(n^3)$ 了qaq

发现我们还是要计算删掉一个点(x,y)不经过他的最长路径

这样的路径要么经过 $(i,y)->(i,y+1)$ , $i<x$ ,要么经过 $(x,j)->(x+1,j)$ , $j<y$

哎?好像可以预处理了,每一行前缀最大值,每一列前缀最大值

做完了

退役了

夏晓光(loveJY)的博客

对于k(k>2),如果他能拼出,k-2一定能拼出

NOIP2018 全国热身赛(无法完结!)