xgc的模拟赛

SHAO · 2019-11-11 17:18:04 · 个人记录

T1

Description

正方形有 4 个点， 4 条边；正方体有 8 个点， 12 条边，6 个面。

定义点为零维基础图形，线段为一维基础图形，正方形为二维基础图形，正方体为三维基础图形...，问一个 n 维基础图形包含多少个 m 维基础图形。

多次询问，答案对 998244353 取模。

Input

第一行一个正整数 T 表示数据组数。

下接 T 行，每行两个自然数 n,m，描述一组数据。

Output

输出 T 行，每行一个数字表示答案。

Sample Input

Sample Output

Hint

对于全部数据，T\leq 10^5,0\leq m\leq n\leq 10^5。

存在 10\% 的数据满足 m=1

存在 10\% 的数据满足 m=n-1

存在 10\% 的数据满足 m=2

存在 10\% 的数据满足 m=n-2

题解

原题链接

解法一

由于都是基础图形，那么直接将边的长度看作 1 ，n维的基础图形看作由 2^{n} 个 n 维的点组成，这些n维的点的坐标为 (0/1,0/1,0/1 ...0/1) ，求 n 维图形中有多少个 m 维图形，即每个点选择相同的 m 维，这 m 维中的数字不同，除这 m 维之外的 n-m 维数字全部相同。举例：

在3维基础图形中求2维基础图形的个数，先将所有构成3维基础图形的点写出来：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 共8个点。要求含有的2维图形个数，需要选择两维来变换。假设选择第一维和第二维，固定第三维，那么可以写出这样四个点：(0,1,0/1),(1,1,0/1),(1,0,0/1),(0,0,0/1)，可以发现，这8个点在第三维选择0/1时可以分别组成2个平面，而类似的选择另外两维，则又可以得到C_3^2 \times 2个。拓展到 n 维选择 m 维的话，m 维共有 C_n^m 中选法，每一种选法的固定维数都是n-m维，这n-m维可以的每一维都可以选择为1或是为0，综合可得 n 维图形共有C_n^m \times 2^{n-m}个 m 维图形。

解法二

由点动成线，线动成面，面动成体这种规律中可以得知，如果要将 i-1 维的图形拓展成 i 维图形，可以将 i-1 维图形复制一遍，再将对应点连线，则可以得到 i 维图形。

以2维构造3维为例。由于2维时共有4条边，转成3维就是先加上复制生成的4 \times 2条边，再加上4个对应点连起来的4条边，共12条边。算面的话，2维共有1个面，所以3维有1\times 2个面，再加上4条对应边生成的4个面，所以共6个面。由此推出一个递推式，设f[i][j]代表的意义为i 维图形中含有f[i][j]个j维图形，则f[i][j]=2 \times f[i-1][j] +f[i-1][j-1]，将f数组抽象成一张网格图，则第 i 行第 j 列的值为第 i-1 行第 j 列的值\times 2+第 i-1 行第 j-1 列的值组成，再以此类推表示出第 i-1 行第 j 列的值和第 i-1 行第 j-1 列的值。因为最左上角为f[1][1]=1，所以如果求出f[i][j]是由多少个f[1][1]组成即可得到答案。设第 j 列上的值表示1的系数，j-1列表示 x 的系数，j-2列表示x^{2}的系数，以此类推，第1列表示x^{m}的系数。发现若f[i][j]位置设为1，则f[i-1][j]为2，f[i-1][j-1]为1，f[i-2][j-2]的值为1，f[i-2][j-1]的值为4，f[i-2][j]的值为4，发现这些值的变化规律可以写成(x+2)^{t} \ t\in [0,i]的系数变化规律, 即 i 行为0次方，i-1 行为1次方，i-2行为2次方...第1行为n次方。所以题目就变为了求(x+2)^{n}展开后x^m的系数，由二项式定理可得。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5,mod=998244353;
typedef long long ll;
ll fac[N],inv[N];
inline ll power(ll a,ll b)
{
    ll sum=1;
    while(b)
    {
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;b>>=1;
    }
    return sum;
}
inline ll C(ll n,ll m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    fac[0]=inv[0]=1;
    for(int i=1;i<=N-5;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-5]=power(fac[N-5],mod-2);
    for(int i=N-6;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
    int T;scanf("%d",&T);
    while(T--)
    {
        ll n,m;
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",C(n,m)*power(2,n-m)%mod);
    }
    return 0;
}

T2

Description

从1号节点出发，每一次可以从一个点沿着树上的一条边走到另一个点，沿着一条权值为 x 的边走需要花 x 秒，定义到达某个点的最小距离是第一次到达这个点所花的时间。

现在希望求所有点的最小距离和，并输出这个值除以 n-1 。

Input

第一行一个数 n。

接下来 n-1 行每行三个数 u, v, w，表示 u 到 v 之间一条权值为 w 的边。

Output

一行一个实数表示答案，保留10位小数。

Sample Input

Sample Output

3.0000000000

Hint

对于所有测试点，边权 ≤ 1000,n\le100000。

对于测试点 1 ∼ 5:n ≤ 8。

对于测试点 6 ∼ 7: 所有点的父亲都是 1 号点。

对于测试点 8 ∼ 11: 每个点最多两个儿子。

对于测试点 12 ∼ 20: 无特殊限制。

题解

考虑对于一个节点求出它的儿子的遍历的优先顺序。

考虑对于一个拥有两个儿子的节点，遍历节点的优先顺序，假设把 i 的子树走完且不用回来的时间是t_i，走完 i 的子树并且回头的时间是s_i，设i的子树有tot_i个节点，则先走 i 再走 j 的花费和先走 j 再走 i 的花费比较得：

t_i+t_j+tot_j*s_i< t_i+t_j+tot_i*s_j

\frac {tot_j}{s_j}<\frac {tot_i}{s_i}

因此按照 \frac {tot_i}{s_i} 从大到小排序即可，其中s_i是 i 的子树的边的总和\times 2。

代码

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5;
vector<int>vec[N];
int arrive[N],last[N],sum[N],tot[N],w[N],len,n;
struct edge{int x,y,d,next;}a[N<<1];
inline void ins(int x,int y,int d)
{
    len++;a[len].x=x;a[len].y=y;a[len].d=d;
    a[len].next=last[x];last[x]=len;
}
inline bool cmp(int x,int y){return ((double)tot[x]/(double)sum[x]>(double)tot[y]/(double)sum[y]);}
inline void dfs(int x,int fa)
{
    tot[x]=1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa)continue;
        w[y]=a[k].d;
        sum[y]=w[y]*2;
        vec[x].push_back(y);
        dfs(y,x);
        tot[x]+=tot[y];
        sum[x]+=sum[y];
    }
    sort(vec[x].begin(),vec[x].end(),cmp);
}
inline int work(int x)
{
    int ns=0;
    for(int k=0;k<vec[x].size();k++)
    {
        int y=vec[x][k];
        arrive[y]=arrive[x]+ns+w[y];
        ns+=work(y)+w[y]*2;
    }
    return ns;
}
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    n=read();
    for(int i=1;i<=n-1;i++)
    {
        int x,y,d;
        x=read();y=read();d=read();
        ins(x,y,d);ins(y,x,d);
    }
    dfs(1,0);
    work(1);
    double ans=0;
    for(int i=1;i<=n;i++)ans+=(double)arrive[i];
    printf("%.10lf\n",ans/(n-1));
    return 0;
}

T3

原题链接

代码

//代码参考lzy
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+10;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int n,m,t,tot,len,in[N],out[N],dep[N],last[N],fa[N][20];
struct edge{int y,next;}a[N<<1];
void ins(int x,int y)
{
    len++;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
void dfs(int x)
{
    in[x]=++tot;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa[x][0])continue;
        fa[y][0]=x;dep[y]=dep[x]+1;
        for(int i=1;i<=t;i++) 
            fa[y][i]=fa[fa[y][i-1]][i-1];
        dfs(y);
    }
    out[x]=tot;
}
struct seg{int l,r;}Line[N<<1];
inline bool cmp(seg n1,seg n2){return n1.l<n2.l;}
inline void jump(int &x,int k)
{
    for(int i=0;k;i++)
        if((k>>i)&1)x=fa[x][i],k^=1<<i;
}
inline int dis(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    int k=dep[x]-dep[y],s=k;
    jump(x,k);
    if(x==y)return s-1;
    for(int i=t;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            s+=1<<(i+1),x=fa[x][i],y=fa[y][i];
    return s+1;
}
void cover(int x,int y)
{
    int z=dis(x,y);
    if(dep[x]>dep[y])
    {
        jump(x,(z+1)>>1);
        if(in[x]>1)Line[++len]=(seg){1,in[x]-1};
        if(out[x]<n)Line[++len]=(seg){out[x]+1,n};
    }
    else
    {
        jump(y,z>>1);
        Line[++len]=(seg){in[y],out[y]};
    }
}
int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read();m=read();t=log2(n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        x=read(),y=read();
        ins(x,y),ins(y,x);
    }
    memset(fa[0],0,sizeof(fa[0]));
    dep[1]=1;fa[1][0]=0;
    dfs(1);
    while(m--)
    {
        int x,y,k,sum=0,pos=0;
        k=read();x=read();len=0;
        while(--k)
        {
            y=read();
            cover(x,y);
        }
        sort(Line+1,Line+len+1,cmp);
        for(int i=1;i<=len;i++)
        {
            if(pos<Line[i].l)
            {
                sum+=Line[i].r-Line[i].l+1;
                pos=Line[i].r;
            }
            else if(pos<Line[i].r)
            {
                sum+=Line[i].r-pos;
                pos=Line[i].r;
            }
        }
        printf("%d\n",n-sum);
    }
    return 0;
}