2020杭电多校训练（第五、六场）

• 生活家

目录

    • 第五场
      • 1001.Tetrahedron
      • 1009.Paperfolding
      • 1003.Boring-Game
      • 1012.Set1
      • 1007.Tree
    • 第六场
      • 1006.A-Very-Easy-Graph-Problem
      • 1010.Expectation
      • 1005.Fragrant-numbers
      • 1007.A-Very-Easy-Math-Problem

第五场

1001.Tetrahedron

标签：数学、结论

结论题。设直角四面体一点到底面3个顶点距离分别为a、b、c，顶点到底面高为h，则有 1 h 2 = 1 a 2 + 1 b 2 + 1 c 2 \frac{1}{h^2}=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2} h21​=a21​+b21​+c21​

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=6e6+5,MOD=998244353;

int T,n,m;

int A[N],sum[N],inv[N];

int qpower(int x,ll p)
{
    int res=1;
    for (int base=x;p;p>>=1,base=(1ll*base*base)%MOD)
        if (p&1==1) res=(1ll*res*base)%MOD;
    return res;
}

ll ans;
int main()
{
    for (int i=1;i<=N-5;i++)
    {
        inv[i]=qpower(i,MOD-2);
        A[i]=qpower((1ll*i*i)%MOD,MOD-2);
        sum[i]=(sum[i-1]+A[i])%MOD;
    }
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",((1ll*sum[n]*3)%MOD*inv[n])%MOD);
    }
    return 0;
}

1009.Paperfolding

标签：数学
上下折k下，左右折n-k下的方案数为 C n k C_n^k Cnk​，剪下来的片数为 ( 2 k + 1 ) ( 2 n − k + 1 ) (2^k+1)(2^{n-k}+1) (2k+1)(2n−k+1)

所以 s u m = ∑ k = 0 n C n k ( 2 k + 1 ) ( 2 n − k + 1 ) = ∑ k = 0 n C n k ( 2 n + 2 k + 2 n − k + 1 ) = 2 n 2 n + 2 n + 2 ∑ k = 0 n C n k 2 k sum=\sum_{k=0}^{n}C_n^k(2^k+1)(2^{n-k}+1)=\sum_{k=0}^{n} C_n^k(2^n+2^k+2^{n-k}+1)=2^n2^n+2^n+2\sum_{k=0}^{n}C_n^k2^k sum=∑k=0n​Cnk​(2k+1)(2n−k+1)=∑k=0n​Cnk​(2n+2k+2n−k+1)=2n2n+2n+2∑k=0n​Cnk​2k

(最后一项 ∑ k = 0 n C n k 2 k = 3 n \sum_{k=0}^{n}C_n^k2^k=3^n ∑k=0n​Cnk​2k=3n)

除去总方案数 2 n 2^n 2n得到期望 e x p = 2 n + 1 + 3 n 2 n − 1 exp=2^n+1+\frac{3^n}{2^{n-1}} exp=2n+1+2n−13n​

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,MOD=998244353;

int T,m;

ll n;
int inv2;

int qpower(int x,ll p)
{
    int res=1;
    for (int base=x;p;p>>=1,base=(1ll*base*base)%MOD)
        if (p&1==1) res=(1ll*res*base)%MOD;
    return res;
}

ll ans;
int main()
{
    cin>>T;
    inv2=qpower(2,MOD-2);
    while(T--)
    {
        scanf("%lld",&n);
        if (n==0){
            printf("4\n");
            continue;
        }
        ans=0;
        ans+=qpower(2,n);
        ans+=1;
        ll temp=(1ll*qpower(3,n)*qpower(inv2,n-1))%MOD;
        ans=(ans+temp)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

1003.Boring-Game

标签：模拟

模拟，一层一层把它翻下来。

起始状态可以视作一堆，每翻一层可以拆分成两个过程。

  1. 把当前状态每一堆一分为二，在上面的一段继承原来的编号，下面的一段编号乘2
  2. 把上面那段内部的值整体翻转，然后按照编号倒着放在左边

随便画一下就是

然后实现的话用A记录内部的翻转，B记录整体的编号情况（因为不能push_front所以先push_back然后再reverse，写的有点绕）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e5+5,MOD=998244353;

int T,n,m,k;

int jc[20];

int A[N],ans[N];

vector<int>B;

void solve()
{
    cin>>n>>k;
    int tot=2*n*jc[k];
    for (int i=1;i<=tot;i++) A[i]=i;
    int len=tot/2;
    B.clear();
    B.push_back(1);
    for (int i=1;i<=k;i++)
    {
        for (int j=1;j<=tot;j+=len*2)
        {
            reverse(A+j,A+len+j);
        }
        len/=2;
    }
    for (int i=1;i<=k;i++)
    {
        for (int i=0;i<B.size();i++) B[i]*=2;
        for (int i=B.size()-1;i>=0;i--) B.push_back(B[i]-1);
    }
    reverse(B.begin(),B.end());
    for (int i=1;i<=tot;i++)
    {
        int x;
        scanf("%d",&x);
        ans[i]=x;
    }
    len*=2;
    for (int i=1;i<=n*2;i++)
        for (int j=1;j<=jc[k];j++)
        {

            printf("%d",ans[A[i+len*(B[j-1]-1)]]);
            if (i!=n*2 || j!=jc[k]) printf(" ");
        }
    printf("\n");
}
int main()
{
    cin>>T;
    jc[0]=1;
    for (int i=1;i<=15;i++) jc[i]=jc[i-1]*2;
    while(T--) solve();
    return 0;
}

1012.Set1

标签：找规律， 组合数，概率

这题我感觉题解可能稍微讲复杂了一点。。

对于当前的i，我们的目标是对于前i-1个数，每个数都能找到另一个对应的数，并且最终除了i之外每个数都能匹配上。这样一来每自动消去一个数，就选择删掉它对应的那个数，最终一定对应了一种合法方案。

首先当i<=n/2时，前i-1个数不能使后n-i个数都匹配，答案为0。

当i>n/2时，先固定住后n-i个数，用前i-1个数去匹配，一共有 P i − 1 n − i P_{i-1}^{n-i} Pi−1n−i​种方案，对于剩下的 2 i − 1 − n 2i-1-n 2i−1−n个数再两两匹配并消除先后顺序，也就是 ( 2 i − 1 − n 2 , 2 , 2 , . . . ) × 1 ( 2 i − 1 − n 2 ) ! \binom{2i-1-n}{2,2,2,…}\times \frac{1}{(\frac{2i-1-n}{2})!} (2,2,2,...2i−1−n​)×(22i−1−n​)!1​

乘起来计算一下就是 ( i − 1 ) ! 2 ( 2 i − 1 − n ) / 2 × ( 2 i − 1 − n 2 ) ! \frac{(i-1)!}{2^{(2i-1-n)/2}}\times (\frac{2i-1-n}{2})! 2(2i−1−n)/2(i−1)!​×(22i−1−n​)!

最后再除以总方案数 ( n − 1 ) ! ! (n-1)!! (n−1)!!

可以 O ( n ) O(n) O(n)线性计算

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=5e6+5,MOD=998244353;

int T,n,sjc[N],jc[N],inv[N];

int bin(int base,int p) {
	int res=1;
	for (;p;p>>=1,base=(1ll*base*base)%MOD) {
		if (p&1) res=(1ll*res*base)%MOD;
	}
	return res;
}

void init() {
	jc[0]=jc[1]=sjc[0]=sjc[1]=inv[1]=1;
	for (int i=2;i<=N-5;i++) {
		sjc[i]=(1ll*sjc[i-2]*i)%MOD;
		jc[i]=(1ll*jc[i-1]*i)%MOD;
		inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
}
void solve() {
	cin>>n;
	int ans;
	for (int i=1;i<=n;i++) {
		if (i<=n/2) {
			printf("0%c",i==n?'\n':' ');
			continue;
		}
		if (i==n/2+1) ans=1ll*jc[i-1]*bin(bin(2,(2*i-1-n)/2),MOD-2)%MOD*bin(sjc[n-1],MOD-2)%MOD;
		else ans=1ll*ans*(i-1)%MOD*inv[2]%MOD*inv[(2*i-1-n)/2]%MOD;
		printf("%d%c",ans,i==n?'\n':' ');
	}
}
int main() {
	init();
	cin>>T;
	while(T--) solve();
	return 0;
}

1007.Tree

标签：树形dp

用dp[n][0]表示对于当前子树根n，任何子结点度数都小于等于k的最大权值(n当前度数最多为k-1)。
用dp[n][1]表示对于当前子树根n，存在结点度数大于k时的最大权值。

定义好之后转移起来就不是很麻烦了。
dp[n][0]为子树中最大的k-1个dp[x][0] （x为子树根）
dp[n][1]要么为所有子树的dp[x][0]，要么为k-2个dp[x][0]+1个dp[x][1]权值最大的方案。

然后还需要特判一种情况，就是当前的n向下连了k棵子树并不再向上连边。判断方法和dp[n][1]的求法类似。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+5;
struct Edge{
int to;
ll v;
};
vector<Edge>G[N];
vector<pii>ve[N];
ll ans;
int T,n,m,k;
ll dp[N][2];
void dfs(int x,int f) {
if (G[x].size()==1 && f!=-1) return;
for (auto now:G[x]){
int to=now.to,v=now.v;
if (to==f) continue;
dfs(to,x);
ve[x].push_back({dp[to][0]+v,dp[to][1]+v});
}
sort(ve[x].begin(),ve[x].end(),[&](pii a,pii b){return a.first>b.first;});
ll sum1=0,sum2=0,sum3=0,mx1=0,mx2=0;
for (int i=0;i<ve[x].size();i++){
if (i<k-1) sum1+=ve[x][i].first;
sum2+=ve[x][i].first;
if (i<k-1) mx1=max(mx1,ve[x][i].second-ve[x][i].first);
if (i>=k-1 && k>=2) mx1=max(mx1,ve[x][i].second-ve[x][k-2].first);
}
if (ve[x].size()>=k) {
for (int i=0;i<ve[x].size();i++){
if (i<k) mx2=max(mx2,ve[x][i].second-ve[x][i].first);
if (i>=k) mx2=max(mx2,ve[x][i].second-ve[x][k-1].first);
}
sum3=sum1+ve[x][k-1].first;
ans=max(ans,sum3+mx2);
}
dp[x][0]=max(dp[x][0],sum1);
dp[x][1]=max(dp[x][1],sum2);
dp[x][1]=max(dp[x][1],sum1+mx1);
ans=max(ans,dp[x][0]);
ans=max(ans,dp[x][1]);
}
void solve() {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) {
G[i].clear();
ve[i].clear();
}
for (int i=1;i<=n-1;i++) {
int u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
G[u].push_back({v,w});
G[v].push_back({u,w});
}
if (k==0) {
printf("0\n");
return;
}
ans=0;
for (int i=1;i<=n;i++) dp[i][0]=dp[i][1]=0;
dfs(1,-1);
printf("%lld\n",ans);
}
int main() {
cin>>T;
while(T--) solve();
return 0;
}

第六场

1006.A-Very-Easy-Graph-Problem

标签：并查集，树形dp

思考关键点是按照边给出的顺序，如果当前的两个点本来就是连通的，那么这条边肯定不起作用，直接忽略。如果这两个点不连通，就连一条边。判断联通可以用并查集实现。

最后肯定连成一棵树，然后树形dp，记录每颗子树0和1的个数，以及所有0和1到达子树根节点的路径长就可以dp转移了。

还有一种做法就是枚举边，记录每条边两侧0和1的数量，得到这条边被经过的次数，次数×权值计算贡献。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
const int N=2e5+5,MOD=1e9+7;
int T,n,m,tmp;
int fa[N],a[N];
long long cnt[N][2],sum[N][2],ans;
struct Edge{
int to,v;
};
vector<Edge>G[N];
int getfa(int x) {
if (fa[x]==x) return x;
else return fa[x]=getfa(fa[x]);
}
void init() {
ans=0;
for (int i=1;i<=n;i++) {
G[i].clear();
fa[i]=i;
cnt[i][0]=cnt[i][1]=0;
sum[i][0]=sum[i][1]=0;
}
}
void dfs(int x,int f) {
if (G[x].size()==1 && ~f) {
cnt[x][a[x]]++;
return;
}
for (auto t:G[x]){
int to=t.to,v=t.v;
if (to==f) continue;
dfs(to,x);
cnt[x][0]+=cnt[to][0];cnt[x][1]+=cnt[to][1];
cnt[x][0]%=MOD;cnt[x][1]%=MOD;
sum[x][0]=(sum[x][0]+sum[to][0]+1ll*v*cnt[to][0])%MOD;
sum[x][1]=(sum[x][1]+sum[to][1]+1ll*v*cnt[to][1])%MOD;
}
for (auto t:G[x]){
int to=t.to,v=t.v;
if (to==f) continue;
ans=(ans+(cnt[x][0]-cnt[to][0]+MOD)%MOD*cnt[to][1]*v)%MOD;
ans=(ans+(cnt[x][1]-cnt[to][1]+MOD)%MOD*cnt[to][0]*v)%MOD;
ans=(ans+(sum[to][0]*(cnt[x][1]-cnt[to][1]+MOD)%MOD))%MOD;
ans=(ans+(sum[to][1]*(cnt[x][0]-cnt[to][0]+MOD)%MOD))%MOD;
ans=(ans+1ll*cnt[to][1-a[x]]*v+sum[to][1-a[x]])%MOD;
}
cnt[x][a[x]]=(cnt[x][a[x]]+1)%MOD;
}
int main() {
cin>>T;
while(T--) {
scanf("%d%d",&n,&m);
init();
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
tmp=2;
for (int i=1;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
if (getfa(u)!=getfa(v)){
G[u].push_back({v,tmp});
G[v].push_back({u,tmp});
fa[getfa(v)]=getfa(u);
}
tmp=(1ll*tmp*2)%MOD;
}
dfs(1,-1);
printf("%lld\n",ans);
}
return 0;
}

1010.Expectation

标签：位运算、生成树计数、计算行列式

把每一位拆开来分别计算贡献。

先把所有边都连上计算出生成树的总和tot，然后把当前位为1的边再建个图计算新图生成树的个数cnt，那么第i位对答案的贡献就为 1 < < ( i − 1 ) × c n t t o t 1<<(i-1)\times\frac{cnt}{tot} 1<<(i−1)×totcnt​

关键在于怎么计算生成树的个数。其实我也不会，临时去搜了个板子。

其实就是根据图构造一个行列式，满足
a i j = { d e g [ i ] i = = j − 1 i 、 j 之 间 存 在 一 条 边 0 i 、 j 之 间 没 有 边 a_{ij}=\begin{cases}deg[i] &i==j\\ -1&i、j之间存在一条边\\ 0&i、j之间没有边\end{cases} aij​=⎩⎪⎨⎪⎧​deg[i]−10​i==ji、j之间存在一条边i、j之间没有边​
然后去掉一个点的信息（比如这里去掉的是第n行第n列）之后算一下行列式的值就是生成树的个数了。

这题应该还需要考虑重边的情况，方法就是i、j之间每有一条边， a i j a_{ij} aij​就减1。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
#define LL long long
using namespace std;
const int MOD=998244353,MAXN=1e2+5;
LL a[MAXN][MAXN],ans;
int T,n,m,sign;
int M[MAXN][MAXN],M2[MAXN][MAXN];
int bin(int base,int p) {
int res=1;
for (;p;p>>=1,base=(1ll*base*base)%MOD)
if (p&1) res=(1ll*res*base)%MOD;
return res;
}
struct Edge{
int u,v,w;
}e[10005];
LL solve(int N){
sign = 0; LL ans = 1;
for(int i=1; i<N; i++){
for(int j=i+1; j<N; j++){//当前之后的每一行第一个数要转化成0
int x=i, y=j;
while( a[y][i] ){//利用gcd的方法，不停地进行辗转相除
LL t = a[x][i] / a[y][i];
for(int k=i; k<N; k++)
a[x][k] = (a[x][k] - a[y][k] * t) % MOD;
swap(x, y);
}
if(x != i){//奇数次交换，则D=-D'整行交换
for(int k=1; k<N; k++)
swap(a[i][k], a[x][k]);
sign ^= 1;//行列式*-1
}
}
if( !a[i][i] ){//斜对角中有一个0，则结果为0
return 0;
}
else ans = ans * a[i][i] % MOD;
}
if(sign != 0) ans *= -1;
if(ans < 0) ans += MOD;//
return ans;
}
int main(){
cin>>T;
while(T--) {
scanf("%d%d",&n,&m);
memset(M,0,sizeof(M));
for (int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i].u=u;e[i].v=v;e[i].w=w;
}
memset(a,0,sizeof(a));
for (int k=1;k<=m;k++) {
int i=e[k].u,j=e[k].v;
a[i][i]++;a[j][j]++;
a[i][j]--;a[j][i]--;
}
LL tot=solve(n);
tot=bin(tot,MOD-2);
ans=0;
for (int i=0;i<=30;i++)
{
memset(M2,0,sizeof(M2));
/*for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) M2[j][k]=M[j][k]&(1<<i);*/
memset(a,0,sizeof(a));
for (int p=1;p<=m;p++) {
if (e[p].w&(1<<i)) {
int j=e[p].u,k=e[p].v;
a[j][j]++;a[k][k]++;
a[j][k]--;a[k][j]--;
}
}
LL cur=solve(n);
ans=(ans+(1ll*cur*tot)%MOD*(1<<i))%MOD;
}
printf("%lld\n",ans);
}
return 0;
}

1005.Fragrant-numbers

标签：思维、dp

关键点：先打个表，然后就会发现只有3和7不能构造，其他5000内的所有数答案都在13位以内。然后就用集合dp[l][r]表示从l到r能组成的所有数（只记录5000以内的），那么dp[l][r]就为dp[l][mid]和dp[mid+1][r]中每个数任意组合之后的和或积了。

#include<bits/stdc++.h>
using namespace std;
const int N=20,M=5e3+5;
const string s=".11451419191145141919";
int T,n;
set<int>dp[N][N];
int ans[M];
int getNum(int l,int r) {
int res=0;
for (int i=l;i<=r;i++) {
res=res*10+s[i]-'0';
}
return res;
}
void dfs(int l,int r) {
if (l>r) return;
if (dp[l][r].size()) return;
if (r-l<4) {
int x=getNum(l,r);
if (x<=5000) dp[l][r].insert(x);
}
for (int i=l;i<r;i++) {
dfs(l,i);dfs(i+1,r);
for (int u:dp[l][i]) for (int v:dp[i+1][r]) {
if (u+v<=5000) dp[l][r].insert(u+v);
if (u*v<=5000) dp[l][r].insert(u*v);
}
}
}
int main() {
memset(ans,-1,sizeof(ans));
dfs(1,13);
for (int i=1;i<=13;i++) for (int x:dp[1][i])
if (ans[x]==-1) ans[x]=i;
cin>>T;
while(T--) {
int x;
scanf("%d",&x);
printf("%d\n",ans[x]);
}
return 0;
}

1007.A-Very-Easy-Math-Problem

标签：莫比乌斯反演

我其实很想把这题一起补了，但是实在是没有接触过莫比乌斯反演之类的题目（确切说，突然发现自己对所有数论的知识都完全没什么接触 只会GCD）看了一天还是没搞出个所以然，只能暂时搁置先把其他题补了。尽快学一下数论的内容吧。。任务单+1

本文地址：https://blog.csdn.net/MorphLing_/article/details/107868808

赞 (0)
上一篇 2022年3月22日
下一篇 2022年3月22日

相关推荐