NOIP 8/12 题解

T1：

题意概述：

有

n

次操作，有两种形式：

1.获得

x

元或

0

元。

2.获得

y

元或

[0,\frac{y}{2}下取整]

元的随机数。

问能不能通过

n

次操作获得

m

元。

T

组数据。

30pts：

枚举。

100pts：

数学题。

m

的上界是

ny

，

m>ny

一定无解。考虑变化量，需要构造一种变化量，正好是

ny-m

。第二种操作的变化量是

[\frac{y}{2}上取整,ny]

。

发现并出来的是一个连续区间

[\dfrac{y}{2}上取整,y]

。

考虑第一种操作，每次变化量为

y-x

，所以

y-x|ny-m

，且

n(y-x) \ge ny-m

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--){
		ll n,x,y,m;
		cin>>n>>x>>y>>m;
		if(m>n*y){
			cout<<"No"<<'\n';
			continue;
		}
		if(n*y-m>=ceil(y/2)&&n*y-m<=n*y){
			cout<<"Yes"<<'\n';
			continue;
		}
		if((n*y-m)%(y-x)==0&&(n*(y-x)>n*y-m||n*(y-x)==n*y-m)){
			cout<<"Yes"<<'\n';
			continue;
		}
		cout<<"No"<<'\n';
	}
	return 0;
}

T2:

题意概述：

有一个

n

点

m

边的图，原图每个点点权

a_i

，重新分配权值是

b_i

。

（1）

∀w(u,v),\dfrac{b_u}{b_v}<x

。

（2）

\sum a_i=\sum b_i

。

（3）

∀1 \le i \le n,\dfrac{b_i}{a_i} \ge \dfrac{p}{q}

求

x_{\min}

。

10pts：

送分。

30pts：

注意到，平均分配是最优的。

根节点要给自己留下

\dfrac{p}{q}

的权值，剩下每个节点分配出

\dfrac{1-\dfrac{p}{q}}{n-1}

。为什么要平均分配？如果不平均分配，那么就有一个节点大，一个节点小，则如果

nq \ge p

，那么

x

会更大。所以答案就是

(n-1) \dfrac{p}{q-p}

。

60pts:

最坏情况：有一节点无穷大，其他节点权值为

0

。从

1

到

n

枚举一个点有权值，其他点没权值，建出一颗树。二分

x

，以每个点为根，做出每个点的深度，求

\dfrac{1}{x^d}

求和，如果小于

1-\dfrac{p}{q}

就可以。

时间复杂度

O(n^2 \log n)

。

100pts：

以

i

号点为根做出一颗 bfs 树，非树边最多出现在同层或相邻一层，求出最短路径即可。

优化：先跑 bfs 再二分。每个点在 bfs 树的深度时是一样的，所以我们只需要在二分之外再进行 bfs，时间复杂度

O(nm+n^2 \log \dfrac{ans}{eps})

。

代码：回去补。

T3：

两个

n

个字符的字串

s

，

t

，只能交换

s

的两个相邻字符，求最少次数使得

s<t

。

5pts:

CPP

cout<<-1;

15pts:

CPP

cout<<0;

20pts：

找到最小的

i

s.t.

s_i<t_1

，

i

不存在就输出

-1

。

60pts：

如何比较

s

和

t

，一位一位比较。

设

s

和

t

的 LCP 是

i

，则

s_1=t_1,...,s_i=t_i

，

s_{i+1}<t_{i+1}

，第一步，枚举 LCP，LCP 中的字符怎么对应？一一对应，选最前面的。如果交换两个相邻字符是不优的。你可以飞快地一一对应完。每次扩展 LCP 时，就把

t

中的对应位置移到

i

，问题就又转换为

B

性质，我们可以从

i+1

往后枚举就行了，时间复杂度为

O(n^2)

。

100pts：

对每种字符开一个队列，每次扩展一格的时候，把

t_i

的队列的队头取出，就可以建立一个关系，但是不能暴力计算，需要快速计算。

注意到 LCP 是

s

中最前面的位置，只需要数出星号后有多少个位置往前移动？用树状数组维护，就相当于把

0

改成

1

，求后缀和问题，就可以快速计算贡献。

时间复杂度

O(26n \log n)

。

注意到每次都要查一遍，对于 26 个队头，只需要确定最优的查一次就可以了，时间复杂度

O(26n+n \log n)

。

T4：

形式化题意：

n

个点

rt

为根的图，求树的拓扑序的逆序对的个数和。

15pts：

暴力搜索。

25pts：

状压 DP。

dp_{i,S}

表示当前是

S

状态，能到第

i

个数的逆序对数量。

时间复杂度

O(2^nn^2)

。

100pts：

如果

u

是

v

的祖先，则

u

在拓扑序上一定先于

v

，如果

u<v

则贡献为

0

，否则贡献为

1

。

一棵树的拓扑序数量就是

\dfrac{n!}{siz_1 \times siz_2 \times ... siz_n}

。以概率考虑的时候，随机排律满足

i

号点在它的子树的最前面概率是

\dfrac{1}{siz_i}

，最后概率乘积再乘上排列数

n!

就得到了数量。

问题转化为期望乘上拓扑序数量。

u,v

为祖孙关系已经解决，那如果是非祖先关系呢？

不妨设

u<v

，设

cnt_{u,v}

表示

u,v

贡献的逆序对个数，

a

为

u

到

lca

之间的（不包括

lca

）点数，

b

为

lca

到

v

之间的（不包括

lca

）点数。考虑只把

u-lca(u,v)-v

这条链拉出来，最后加的点只可能是

u

或者

v

，如果最后拉出来的是

u

，则求的就是

cnt_{fa_u,v}

，那么

u

成为最后一个点的概率是什么？

设

f_{u,v}

代表只考虑

u

子树和

v

子树相互之间产生逆序对的概率之和。我们只需要算出

v

子树中有多少个节点编号小于

u

的。我们只需要预处理出

sum_{u,i}

，表示

u

中有多少个点编号小于

i

的，只需要将

u

的子树染黑，

v

的子树染白，

u

就是黑色中最前面的，

v

就是白色中最前面的，只需要计算出黑色在最前面的概率。

同理，所以贡献就是

sum_{v,u} \times \dfrac{siz_u}{siz_u+siz_v}+sum_{u,v} \times \dfrac{siz_v}{siz_u+siz_v}

，所以转移方程就是

f_{u,v}=(sum_{v,u}+\sum{f_{son(u),v}}) \times \dfrac{siz_u}{siz_u+siz_v}+(sum_{u,v}+\sum{f_{son(v),u}}) \times \dfrac{siz_v}{siz_u+siz_v}

。

答案就是枚举

lca

，如果

u,v

都是儿子的话，那么答案就是

f_{u,v}

之和，再加上祖孙关系的和。

为什么不能直接算概率？若

u

的子树大，

v

的子树很小，那么概率就不是

\dfrac{1}{2}

了。

时间复杂度

O(n^2)

。

文章操作

相关推荐

评论

NOIP 8/12 题解