郑州Day6

今天考了毕姥爷的一套题，差点保龄

题目

挺良心的一套题，至少我不用再搬一遍题面了

T1.B君的第一题

我为什么当时去写了一个树形\(dp\)还妄图\(A\)掉啊

这题保龄感觉舒爽

首先如果我们要求的是点联通块的期望个数的话，那就非常好求了，一个点周围的边就算全删掉，这个点也是一个联通块，又因为这是一个树，所以每删一条边就会新增加一个联通块

所以答案就是

\[\frac{\sum_{i=0}^{n-1}\binom{n-1}{i}\times (i+1)}{2^{n-1}}
\]

但是这道题求的是边联通块，删掉\(i\)条边之后可能并不会剩下\(i+1\)个联通块

于是考虑把那些多算的贡献减掉，发现一个点周围的所有边都被删除之后这个点就不会成为联通块了

于是对于每个点单独算一些贡献

\[\sum_{i=1}^n\frac{1}{2^{d_i}}
\]

\(d_i\)表示\(i\)的度，即和\(i\)相连的边数

代码

#include<cstdio>

typedef long long LL;

const LL MOD=1000000007;

LL inv[100005];

int x,y,d[100005];

LL pw[100005];

int n;

int main()

{

    LL now=1,ans=1;

    scanf("%d",&n);

    for( int i=1;i<n;i++) scanf("%d%d",&x,&y),d[x]++,d[y]++;

    inv[1]=1;

    for (int i=2;i<=n+1;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;

    for (int i=1;i<n;i++) {

        now=((now*(n-i))%MOD*inv[i])%MOD;

        ans=(ans+now*(i+1)%MOD)%MOD;

    }

    ans=ans*2ll;ans%=MOD;

	pw[0]=1;

	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2ll%MOD;

	for(int i=1;i<=n;i++)

		ans=(ans+MOD-pw[n-d[i]])%MOD;

	printf("%lld\n",ans);

    return 0;

}

T2.B君的第二题

还是不怎么会

但是当时并没有看出来这是一个查第\(k\)大的数据结构可以维护的东西，甚至想用树状数组加二分，想一想好像挺难写就弃疗了

正解是求出每一个元素是第几轮出去的，之后上一个基排

并没有看懂\(f[i]=f[i-i/k-1]+1\)这样的操作，先放上毕姥爷代码

#include <bits/stdc++.h>

using namespace std;

int t, n, k, p, mod = 1000000007;

int f[1000020];

int c[1000020];

int a[1000020];

bool isPrime(int x) {

	if (x < 2) {

		return false;

	}

	for (int i = 2; i * i <= x; i++) {

		if (x % i == 0) {

			return false;

		}

	}

	return true;

}

int main() {

	freopen("harbin.in", "r", stdin);

	freopen("harbin.out", "w", stdout);

	scanf("%d", &t);

	for (int tt = 0; tt < t; tt++) {

		scanf("%d%d", &n, &k);

		p = n;

		while (!isPrime(p)) {

			p++;

		}

		for (int i = 0; i < n; i++) {

			c[i] = 0;

		}

		for (int i = 0; i < n; i++) {

			if (i % k == 0) {

				f[i] = 0;

			} else {

				f[i] = f[i - i / k - 1] + 1;

			}

			c[f[i] + 1]++;

		}

		for (int i = 1; i <= n; i++) {

			c[i] += c[i - 1];

		}

		for (int i = 0; i < n; i++) {

			a[c[f[i]]++] = i;

		}

		int z = 0;

		for (int i = n - 1; i >= 0; i--) {

			z = ((long long)z * p + a[i]) % mod;

		}

		printf("%d\n", z);

	}

	return 0;

}

T2.B君的第三题

可能是最简单的题了，也是我唯一能\(A\)的题了

看到都互质这个要求，我们就想到分解质因数之后没有相同的质因数

发现\(a_i<=30\)，于是我们只需要考虑\(2\)到\(53\)这些质数，因为把\(30\)变成\(60\)多的数显然不如直接改成\(1\)更划算

发现这也就是\(16\)个质数，于是我们可以考虑状压

\(dp[i][s]\)表示前\(i\)个数选择的质因数状态为\(s\)的最小花费，每次我们枚举这个数改成什么，预处理出这个数分解之后的状态和\(s\)不能有交集就可以转移

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define maxn 105

#define inf 15000

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int p[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};

short dp[2][1024*128+1];

int a[maxn],val[maxn];

int n,o,M;

int main()

{

	n=read();

	for(re int i=1;i<=n;i++) a[i]=read();

	std::sort(a+1,a+n+1);

	o=0;

	for(re int i=1;i<=16;i++) if(a[n]+n<=p[i]) {M=i;break;}

	if(!M) M=16;

	for(re int i=1;i<(1<<M);i++) dp[o][i]=inf;

	for(re int i=1;i<=p[M];i++)

	{

		int now=0,t=i;

		for(re int k=1;k<=M;k++)

		{

			while(t%p[k]==0) t/=p[k],now|=(1<<(k-1));

			if(t==1) break;

		}

		val[i]=now;

	}

	for(re int i=1;i<=n;i++,o^=1)

	{

		for(re int k=0;k<(1<<M);k++) dp[o^1][k]=inf;

		for(re int j=1;j<=p[M];j++)

		{

			int now=((1<<M)-1)^val[j],t=(a[i]>j?a[i]-j:j-a[i]);

			for(re int k=now;k;k=(k-1)&now)

				dp[o^1][k|val[j]]=min(dp[o^1][k|val[j]],dp[o][k]+t);

			dp[o^1][val[j]]=min(dp[o^1][val[j]],dp[o][0]+t);

		}

	}

	int ans=inf;

	for(re int k=0;k<(1<<M);k++)

		ans=min(dp[o][k],ans);

	printf("%d\n",ans);

	return 0;

}

巴特西

郑州Day6

T1.B君的第一题

T2.B君的第二题

T2.B君的第三题

最新文章

热门文章