欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  互联网

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

程序员文章站 2022-06-23 08:39:07
目录第五场1001.Tetrahedron1009.Paperfolding1003.Boring-Game1012.Set11007.Tree第六场1006.A-Very-Easy-Graph-Problem1010.Expectation1005.Fragrant-numbers1007.A-Very-Easy-Math-Problem第五场1001.Tetrahedron标签：数学、结论结论题。设直角四面体一点到底面3个顶点距离分别为a、b、c，顶点到底面高为h，则有1h2=1a2+1b2+1...

目录

第五场

1001.Tetrahedron

标签：数学、结论

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

#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下的方案数为CnkC_n^k，剪下来的片数为(2k+1)(2n−k+1)(2^k+1)(2^{n-k}+1)

所以sum=∑k=0nCnk(2k+1)(2n−k+1)=∑k=0nCnk(2n+2k+2n−k+1)=2n2n+2n+2∑k=0nCnk2ksum=\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

(最后一项∑k=0nCnk2k=3n\sum_{k=0}^{n}C_n^k2^k=3^n)

除去总方案数2n2^n得到期望exp=2n+1+3n2n−1exp=2^n+1+\frac{3^n}{2^{n-1}}

#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. 把上面那段内部的值整体翻转，然后按照编号倒着放在左边

随便画一下就是
2020杭电多校训练（第五、六场）
然后实现的话用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个数去匹配，一共有Pi−1n−iP_{i-1}^{n-i}种方案，对于剩下的2i−1−n2i-1-n个数再两两匹配并消除先后顺序，也就是(2i−1−n2,2,2,...)×1(2i−1−n2)!\binom{2i-1-n}{2,2,2,...}\times \frac{1}{(\frac{2i-1-n}{2})!}

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

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

可以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)×cnttot1<<(i-1)\times\frac{cnt}{tot}

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

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

这题应该还需要考虑重边的情况，方法就是i、j之间每有一条边，aija_{ij}就减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

上一篇： React-router

下一篇： 蜀汉大将军费祎遇刺，幕后主使真的是姜维？

推荐阅读