2021.07.10【NOIP提高B组】模拟 总结

第一题：设 f i f_i fi​表示前 i i i此操作每个位置不在原来位置的概率（因为每一个位置的概率是相同的）。转移考虑上一个位置是否相同并转移。

公式：

f i = f i − 1 ( 1 − 1 C n 2 ) + ( 1 − f i − 1 ) n − 1 C n 2 f_i=f_{i-1}(1-\frac{1}{C_n^2})+(1-f_{i-1})\frac{n-1}{C_n^2} fi​=fi−1​(1−Cn2​1​)+(1−fi−1​)Cn2​n−1​

答案：

a n s = ∑ ( 1 − f k ) a i × i ( n − i + 1 ) C n + 1 2 + f k s u m − a i n − 1 × i ( n − i + 1 ) C n + 1 2 ans=\sum(1-f_k)a_i\times\frac{i(n-i+1)}{C_{n+1}^2}+f_k\frac{sum-a_i}{n-1}\times\frac{i(n-i+1)}{C_{n+1}^2} ans=∑(1−fk​)ai​×Cn+12​i(n−i+1)​+fk​n−1sum−ai​​×Cn+12​i(n−i+1)​

第二题：如果一个点在基环树的树上（不包括环上的点），那么它的方案一定时 k − 1 k-1 k−1，因为它只有一个父亲约束它。如果在环上，有一个动态规划：设 f i , 0 / 1 f_{i,0/1} fi,0/1​表示第 i i i个点与第 1 1 1个点相同或不相同的方案数。

转移：

f i , 0 = f i − 1 , 1 f i , 1 = f i − 1 , 0 × ( k − 1 ) + f i − 1 , 1 × ( k − 2 ) f_{i,0}=f_{i-1,1}\\ f_{i,1}=f_{i-1,0}\times (k-1)+f_{i-1,1}\times (k-2) fi,0​=fi−1,1​fi,1​=fi−1,0​×(k−1)+fi−1,1​×(k−2)

接着看一下每一个基环树的答案乘起来即可。

第三题：一眼看时分数规划，发现不会做。

二分 x x x，答案要求 ∑ n 1 q 1 i + ∑ n 2 q 2 i ∑ n 1 c 1 i + ∑ n 2 c 2 i \frac{\sum^{n1}{q1_i}+\sum^{n2}{q2i}}{\sum^{n1}{c1_i}+\sum^{n2}{c2i}} ∑n1c1i​+∑n2c2i∑n1q1i​+∑n2q2i​最大。

∑ n 1 q 1 i + ∑ n 2 q 2 i ∑ n 1 c 1 i + ∑ n 2 c 2 i ≥ x ∑ n 1 q 1 i − x c 1 i + ∑ n 2 q 2 i − x c 2 i ≥ 0 \frac{\sum^{n1}{q1_i}+\sum^{n2}{q2i}}{\sum^{n1}{c1_i}+\sum^{n2}{c2i}}\ge x\\ \sum^{n1}{q1_i-xc1_i}+\sum^{n2}{q2_i-xc2_i}\ge 0 ∑n1c1i​+∑n2c2i∑n1q1i​+∑n2q2i​≥x∑n1​q1i​−xc1i​+∑n2​q2i​−xc2i​≥0

发现按 q 1 i − x c 1 i − ( q 2 i − x c 2 i ) q1_i-xc1_i-(q2_i-xc2_i) q1i​−xc1i​−(q2i​−xc2i​)从大到小排序，中间一定会有一个分界线：前面的时 1 1 1队的，后面的时 2 2 2队的。

设 f i , j f_{i,j} fi,j​表示前 i i i队选了 j j j个 1 1 1队的答案， g g g同理（选 2 2 2）。枚举分界线就行了。

第四题：首先看一下小于 k k k的答案怎么求，发现 C n k C_n^k Cnk​很小，所以直接暴力求，设为 y y y。那么我们可以用一种方法把所有的答案算出来，设为 x x x。首先把序列分成两部分分别算出 ∑ a i − b i \sum a_i-b_i ∑ai​−bi​和 ∑ a i − c i \sum a_i-c_i ∑ai​−ci​。前后的答案分别设为 f , g f,g f,g。则我们要保证 f ( ∑ a i − b i ) + g ( ∑ a i − b i ) > 0 , f ( ∑ a i − c i ) + g ( ∑ a i − c i ) > 0 f(\sum a_i-b_i)+g(\sum a_i-b_i)>0,f(\sum a_i-c_i)+g(\sum a_i-c_i)>0 f(∑ai​−bi​)+g(∑ai​−bi​)>0,f(∑ai​−ci​)+g(∑ai​−ci​)>0。

把 g g g取个相反数，就变成了二维偏序。考虑树状数组维护：首先离散化一个，然后把另一个排序，双指针维护，用星星点灯的做法搞一下即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[50],b[50],c[50],n,k,m1,m2;
struct node{ll s1,s2;}f[150000],g[150000];
struct node2{ll val,rk,id;}a1[150000],a2[150000];
const ll inf=1000000000000000000;
void dfs1(ll x,ll en,ll st,ll sum1,ll sum2){
	m1=max(m1,st);
	if (x>en){
		f[st].s1=sum1;
		f[st].s2=sum2;
		return;
	}
	dfs1(x+1,en,st<<1,sum1,sum2);
	dfs1(x+1,en,st<<1|1,sum1+a[x]-b[x],sum2+a[x]-c[x]);
}
void dfs2(ll x,ll en,ll st,ll sum1,ll sum2){
	m2=max(m2,st);
	if (x>en){
		g[st].s1=sum1;
		g[st].s2=sum2;
		return;
	}
	dfs2(x+1,en,st<<1,sum1,sum2);
	dfs2(x+1,en,st<<1|1,sum1+a[x]-b[x],sum2+a[x]-c[x]);
}
ll bz[50];
ll ans2=0; 
void dfs3(ll x,ll las,ll en,ll sum1,ll sum2){
	if (x>en){
		if (sum1>0&&sum2>0)ans2++;
		return;
	}
	for (ll i=las+1;i<=n;i++)
		if (!bz[i]){
			bz[i]=1;
			dfs3(x+1,i,en,sum1+a[i]-b[i],sum2+a[i]-c[i]);
			bz[i]=0; 
		}
} 
bool cmp(node2 x,node2 y){return x.val<y.val;}
bool cmp2(node x,node y){return x.s2<y.s2;}
ll tr[300000],m;
ll lowbit(ll x){return x&(-x);}
void add(ll x,ll v){for (ll i=x;i<=m;i+=lowbit(i))tr[i]+=v;}
ll query(ll x){ll sum=0;for (ll i=x;i;i-=lowbit(i))sum+=tr[i];return sum;}
int main(){
	freopen("show.in","r",stdin);
	freopen("show.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for (ll i=1;i<=n;i++)scanf("%lld",&a[i]); 
	for (ll i=1;i<=n;i++)scanf("%lld",&b[i]); 
	for (ll i=1;i<=n;i++)scanf("%lld",&c[i]); 
	dfs1(1,n/2,0,0,0);
	dfs2(n/2+1,n,0,0,0);
	ll ans=0;
	for (ll i=0;i<=m2;i++)g[i].s1=-g[i].s1,g[i].s2=-g[i].s2;
	for (ll i=m1+1;i;i--)f[i].s1=f[i-1].s1,f[i].s2=f[i-1].s2;m1++;
	for (ll i=m2+1;i;i--)g[i].s1=g[i-1].s1,g[i].s2=g[i-1].s2;m2++;
	for (ll i=1;i<=m1;i++)a1[i].val=f[i].s1,a1[i].id=i;
	for (ll i=1;i<=m2;i++)a1[i+m1].val=g[i].s1,a1[i+m1].id=i+m1;
	sort(a1+1,a1+m1+m2+1,cmp);
	a1[0].val=-inf;
	for (ll i=1;i<=m1+m2;i++)a1[i].rk=a1[i-1].rk+(a1[i].val==a1[i-1].val?0:1);m=a1[m1+m2].rk;
	for (ll i=1;i<=m1+m2;i++)
		if (a1[i].id>m1)g[a1[i].id-m1].s1=a1[i].rk;
		else f[a1[i].id].s1=a1[i].rk;
	sort(f+1,f+m1+1,cmp2),sort(g+1,g+m2+1,cmp2);
	for (ll i=1;i<=m1;i++)add(f[i].s1,1);
	ll j=1;
	for (ll i=1;i<=m2;i++){
		while (g[i].s2>=f[j].s2&&j<=m1)add(f[j].s1,-1),j++;
		if (j>m1)break;
		ans+=m1-j+1-query(g[i].s1);
	}
	for (ll i=1;i<k;i++)memset(bz,0,sizeof(bz)),dfs3(1,0,i,0,0);
	printf("%lld\n",ans-ans2);
}