「GDKOI2021普及组Day2」简要题解

Thunder_S · 2021-01-29 20:14:18 · 个人记录

T1：初中生数学题

题目大意：给出a_1,a_2,a_3,\dots,a_{10}，求1^{a_1}\times2^{a_2}\times3^{a_3}\times\dots\times10^{a_{10}}的结果的从低到高位的第一个非0数。

题解：

首先知道1是无用的，然后我们可以将2~10分解到2、3、5、7这4个质数，然后根据小学知识知道，0是由2和5产生的，那么2和5的指数减去两者中最小值就不会产生0了。然后题目转换为求几个数相乘后的最后一位，显然可以乘起来模10，龟速乘和快速幂都可以

当然也可以用周期，O(1)解决，快人一等……

当然你用高精度+快速幂说不定也可以……

Code

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll ans,ten,a[15];
bool flag;
int main()
{
    for (int i=1;i<=10;++i)
        scanf("%d",&a[i]);
    a[2]+=a[6];
    a[3]+=a[6];
    a[6]=0;
    a[2]+=a[4]*2;
    a[2]+=a[8]*3;
    a[4]=a[8]=0;
    a[3]+=a[9]*2;
    a[9]=0;
    a[2]+=a[10];
    a[5]+=a[10];
    a[10]=0;
    ten=min(a[2],a[5]);
    a[2]-=ten;
    a[5]-=ten;
    ans=1;
    flag=false;
    for (int i=1;i<=10;++i)
    {
        for (int j=1;j<=a[i];++j)
        {
            flag=true;
            ans=ans*i%10;
        }
    }
    printf("%d\n",ans); 
    return 0;
} 

T2：二叉树

题目大意：给出一颗二叉搜索树的\text{BFS}序，判断这棵树是否是正则二叉树

题解：

我们可以预处理这棵二叉搜索数的大小关系，然后用两个指针i,j，分别指向序列和树，然后把序列上的数放到树上来，记录一下每个节点的儿子节点的个数。最后看能不能找到一个点的儿子节点的数量不为2或0即可

Code

#include<cstdio>
#include<cstring>
#include<cmath>
#define N 100005
#define inf 1e9
using namespace std;
struct node
{
    int mn,mx;
}tree[200005];
int t,n,a[N],v[N];
bool flag,bj[N],bz[N];
int read()
{
    int res=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res;
}
void build(int now,int l,int r)
{
    if (now>N) return;
    tree[now].mn=l;
    tree[now].mx=r;
    build(now<<1,l,now);
    build(now<<1|1,now,r);
}
int main()
{
    build(1,0,N);
    t=read();
    while (t--)
    {
        memset(bj,true,sizeof(bj));
        memset(bz,false,sizeof(bz));
        memset(v,0,sizeof(v));
        n=read();
        for (int i=1;i<=n;++i)
            a[i]=read();
        v[N]=inf;
        v[0]=-1;
        int i=1,j=1;
        flag=true;
        while (j<=n&&i<=N)
        {
            while (!v[i>>1]) ++i;
            if (a[j]>v[tree[i].mn]&&a[j]<=v[tree[i].mx]) 
            {
                v[i]=a[j];
                bz[i>>1]=true;
                ++j;
            }
            else bj[i>>1]=false;
            ++i;
        }
        for (i=1;i<=n;++i)
            if (bz[i]&&!bj[i])
            {
                flag=false;
                break;
            }       
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

为什么讲的不清楚是因为我也没搞清楚我在打什么

T3：我的世界

题目大意：有两个世界：主世界和异界，其中若一条边在异界的权值为e，那么在主世界也会有对应的边，权值为8e。任意一个点i都可以花费a_i进入异界或主世界。求从主世界的x走到y的经过最少点的最短路径。

题解：

容易得出只会下去上来一次的结论

那么就可以分类讨论（dis[x]表示从x到根的在异界的最短路，u为路径上最优去异界的点，v为路径上最优回主世界的点）

1. 不去异界：ans=(dis[x]-dis[lca]+dis[y]-dis[lca])\times8
2. 在x到lca的路径上去异界，在lca到y的路径上回主世界：ans=(dis[x]-dis[u])\times8+(dis[u]-dis[lca])+(dis[v]-dis[lca])+(dis[y]-dis[v])\times8
3. 在x到lca的路径上去异界，在x到lca的路径上回主世界：注意到这种情况需要满足u在v下面，那么就可以先求u再求u到lca上的v，也可以先求v，再求x到v上的u，两种情况比较就可以了。ans=(dis[x]-dis[u])\times8+(dis[u]-dis[v])+(dis[v]-dis[lca])\times8+(dis[y]-dis[lca])\times8
4. 在lca到y的路径上去异界，在lca到y的路径上回主世界：这种情况要满足u在v上面，求法跟第3中情况类似。ans=(dis[x]-dis[lca])\times8+(dis[u]-dis[lca])\times8+(dis[v]-dis[u])+(dis[y]-dis[v])\times8

那么现在问题就难在求u和v

可以考虑倍增，设g1[i][j]表示从i往上2^j-1的区间内某个最优点，g2[i][j]表示从i往上2^j-1的区间另一个最优的点（好像说了没说，其实这两个的不同只有比较的方式）

直接放出如何比较：

反之则是v比u优

反之则是v比u优

然后在查询的时候，我们从x或y不断向上跳2^j，然后比较一下就好

这个比较也需要分类讨论……

1. 在x到lca的路上找去异界的点：比较g1
2. 在x到lca的路上找回主世界的点：比较g2
3. 在y到lca的路上找去异界的点：比较g2
4. 在y到lca的路上找回主世界的点：比较g1

自己画画图理解就好了

Code

我的代码有点奇怪是因为学校的出题人卡栈而且卡常……

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
#define N2 500005
#define ll long long
using namespace std;
struct node
{
    ll val;
    int to,next,head;
}a[N<<1];
int n,q,x,y,tot,lca,deep[N],f[N2][20],g1[N2][20],g2[N2][20],d[N][3];
ll z,ans1,ans2,ans3,ans4,c[N],dis[N];;
void add(int x,int y,ll z)
{
    a[++tot].to=y;
    a[tot].val=z;
    a[tot].next=a[x].head;
    a[x].head=tot;
}
void bfs()
{
    int h=0,t=1;
    d[1][1]=1;
    d[1][2]=0;
    d[1][3]=0;
    while (h<t)
    {
        int now=d[++h][1];
        f[now][0]=d[h][2];
        g1[now][0]=g2[now][0]=now;
        deep[now]=deep[f[now][0]]+1;
        dis[now]=dis[f[now][0]]+d[h][3];
        for (int i=1;i<=18;++i)
        {
            f[now][i]=f[f[now][i-1]][i-1];
            int u=g1[now][i-1],v=g1[f[now][i-1]][i-1];
            if (c[u]<c[v]+7*(dis[u]-dis[v])) g1[now][i]=u;
            else g1[now][i]=v;
            u=g2[now][i-1],v=g2[f[now][i-1]][i-1];
            if (c[u]<c[v]-7*(dis[u]-dis[v])) g2[now][i]=u;
            else g2[now][i]=v;
        }
        for (int i=a[now].head;i;i=a[i].next)
        {
            int v=a[i].to;
            if (v==f[now][0]) continue;
            d[++t][1]=v;d[t][2]=now;d[t][3]=a[i].val;
        }
    }
}
int LCA(int x,int y)
{
    if (deep[x]!=deep[y])
    {
        if (deep[x]<deep[y]) swap(x,y);
        for (int i=18;i>=0;--i)
            if (deep[f[x][i]]>deep[y]) x=f[x][i];
        x=f[x][0];
    }
    if (x==y) return x;
    for (int i=18;i>=0;--i)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int get_up_down(int x,int y)
{
    if (x==y) return x;
    int u=0;
    for (int i=18;i>=0;--i)
    {
        if(deep[f[x][i]]>deep[y])
        {
            int v=g1[x][i];
            if (!u) u=v;
            else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
            x=f[x][i];
        }
    }
    int v=g1[f[x][0]][0];
    if (!u) u=v;
    else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
    v=g1[x][0];
    if (!u) u=v;
    else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
    return u;
}
int get_up_up(int x,int y)
{
    if (x==y) return x;
    int u=0;
    for (int i=18;i>=0;--i)
    {
        if(deep[f[x][i]]>deep[y])
        {
            int v=g2[x][i];
            if (!u) u=v;
            else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
            x=f[x][i];
        }
    }
    int v=g2[f[x][0]][0];
    if (!u) u=v;
    else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
    v=g2[x][0];
    if (!u) u=v;
    else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
    return u;
} 
int get_down_up(int x,int y)
{
    if (x==y) return x;
    int u=0;
    for (int i=18;i>=0;--i)
    {
        if(deep[f[x][i]]>deep[y])
        {
            int v=g1[x][i];
            if (!u) u=v;
            else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
            x=f[x][i];
        }
    }
    int v=g1[f[x][0]][0];
    if (!u) u=v;
    else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
    v=g1[x][0];
    if (!u) u=v;
    else if (c[u]>c[v]+7*(dis[u]-dis[v])) u=v;
    return u;
}
int get_down_down(int x,int y)
{
    if (x==y) return x;
    int u=0;
    for (int i=18;i>=0;--i)
    {
        if(deep[f[x][i]]>deep[y])
        {
            int v=g2[x][i];
            if (!u) u=v;
            else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
            x=f[x][i];
        }
    }
    int v=g2[f[x][0]][0];
    if (!u) u=v;
    else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
    v=g2[x][0];
    if (!u) u=v;
    else if (c[u]>c[v]-7*(dis[u]-dis[v])) u=v;
    return u;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%lld",&c[i]);
    for (int i=1;i<n;++i)
    {
        scanf("%d%d%lld",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    bfs();
    scanf("%d",&q);
    while (q--)
    {
        int up,down;
        scanf("%d%d",&x,&y);
        lca=LCA(x,y);
        ans1=(dis[x]-dis[lca]+dis[y]-dis[lca])*8;
        down=get_up_down(x,lca);up=get_down_up(y,lca);
        ans2=(dis[x]-dis[down])*8+(dis[down]-dis[lca])+(dis[up]-dis[lca])+(dis[y]-dis[up])*8+c[down]+c[up]; 
        down=get_up_down(x,lca);up=get_up_up(down,lca);
        ans3=(dis[x]-dis[down])*8+(dis[down]-dis[up])+(dis[up]-dis[lca])*8+(dis[y]-dis[lca])*8+c[down]+c[up];
        up=get_up_up(x,lca);down=get_up_down(x,up);
        ans3=min(ans3,(dis[x]-dis[down])*8+(dis[down]-dis[up])+(dis[up]-dis[lca])*8+(dis[y]-dis[lca])*8+c[down]+c[up]);
        down=get_down_down(y,lca);up=get_down_up(y,down);
        ans4=(dis[x]-dis[lca])*8+(dis[down]-dis[lca])*8+(dis[up]-dis[down])+(dis[y]-dis[up])*8+c[down]+c[up];
        up=get_down_up(y,lca);down=get_down_down(up,lca);
        ans4=min(ans4,(dis[x]-dis[lca])*8+(dis[down]-dis[lca])*8+(dis[up]-dis[down])+(dis[y]-dis[up])*8+c[down]+c[up]);
        printf("%lld\n",min(min(ans1,ans2),min(ans3,ans4)));
    }
    return 0;   
} 

T4：矩阵

题目大意：给出一个n\times n的矩阵A，设r_i是A里第i行的元素和，c_j是A里第j列的元素和，所有的r_i和c_j都是偶数。现在要矩阵A拆成两个矩阵B,C，满足B+C=A，且对于任意1\le i\le n，都有\sum\limits_{j=1}^nB_{i,j}=\sum\limits_{j=1}^nC_{i,j},\sum\limits_{j=1}^nB_{j,i}=\sum\limits_{j=1}^nC_{j,i} 求任意一种方案

题解：

首先对于A里的所有偶数都可以两两分开，奇数留下1后也可以两两分开，那么A就变成了一个01矩阵，每行每列选取1的个数的一半给B，剩下的给C。

那么就可以玩二分图了！！！

以下的A都是拆分后的01矩阵

我们把行和列分开来

如果A_{i,j}=1，那么就从i往j+n连一条流量为1的边（i表示第i行，j+n表示第j列）

然后设一个源点S，汇点T，然后S连向所有的i，流量为那一行的1的个数的一半。所有的j+n连向T，流量为那一列的1的个数的一半，然后跑一下最大流

最后看一下哪条边流完了，就说明对应的那个点在B（或者C）中是1。如果没有流完，那么就是另一个矩阵里是1

Code

#include<cstdio>
#include<cstring> 
#include<algorithm>
#define N 3005
#define ll long long
#define inf 2147483647
using namespace std;
struct node
{
    int val,to,next;
}net[N*N];
int n,tot,s,t,a[N][N],b[N][N],c[N][N],hang[N],lie[N],deep[N],q[N],head[N<<2],cur[N<<2];
int read()
{
    int res=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res;
}
void add(int x,int y,int z)
{
    net[tot].to=y;
    net[tot].val=z;
    net[tot].next=head[x];
    head[x]=tot++;  
} 
bool bfs(int st,int en)
{
    int hd=0,tl=1;
    for (int i=1;i<=2*n+2;++i)
        cur[i]=head[i];
    memset(deep,0,sizeof(deep));
    q[1]=st;
    deep[st]=1;
    while (hd<tl)
    {
        for (int i=head[q[++hd]];i!=-1;i=net[i].next)
        {
            int x=net[i].to;
            if (!deep[x]&&net[i].val>0)
            {
                q[++tl]=x;
                deep[x]=deep[q[hd]]+1;
            }
        }
    }
    if (deep[en]==0) return false;
    else return true;
}
int dfs(int now,int t,int sum)
{
    if (now==t||sum==0) return sum;
    int delat=0,del;
    for (int i=cur[now];i!=-1;i=net[i].next)
    {
        cur[now]=i;
        if (deep[net[i].to]==deep[now]+1&&net[i].val>0)
        {
            int x=net[i].to,del=dfs(x,t,min(sum,net[i].val));
            if (del<=0) deep[x]=0;
            sum-=del;
            delat+=del;
            net[i].val-=del;
            net[i^1].val+=del;
            if (sum==0) break;
        }
    }
    return delat;
}
void dinic(int s,int t)
{
    while (bfs(s,t)==true) 
        dfs(s,t,inf);
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        {
            a[i][j]=read();
            b[i][j]=c[i][j]=a[i][j]/2;
            a[i][j]%=2;
            hang[i]+=a[i][j];
            lie[j]+=a[i][j];
        }
    s=2*n+1;t=2*n+2;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (a[i][j])
            {
                add(i,j+n,1);
                add(j+n,i,0);
            }
    for (int i=1;i<=n;++i)
    {
        if (hang[i]) add(s,i,hang[i]/2),add(i,s,0);
        if (lie[i]) add(i+n,t,lie[i]/2),add(t,i+n,0);
    }
    dinic(s,t);
    for (int i=1;i<=n;++i)
    {
        for (int j=head[i];j!=-1;j=net[j].next)
        {
            if (net[j].to==s) continue;
            if (net[j].val==0) ++b[i][net[j].to-n];
            else ++c[i][net[j].to-n];
        }
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
            printf("%d ",b[i][j]);
        printf("\n");
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
            printf("%d ",c[i][j]);
        printf("\n");
    }
    return 0;
}