五一欢乐赛方程的解染色光无向图问题

本文主要是介绍五一欢乐赛方程的解染色光无向图问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接

考场上顺序开题。

\(\mathrm{A.}\mathbb{方程的解}\)：\(\mathrm{exgcd}\) 板子

\(\mathrm{B.}\mathbb{染色}\)：树形 \(\mathrm{dp}\)

\(\mathrm{C.}\mathbb{光}\)：优化 \(\mathrm{dfs}\)

\(\mathrm{D.}\mathbb{无向图问题}\)：这道题说了个啥？

打开发现又是原题大赛，除了 \(\mathrm{D}\) 都是见过的原题，于是果断的先打了 \(\mathrm{A}\) 和 \(\mathrm{C}\)。

打 \(\mathrm{A}\) 时没有一遍过，细节太多太杂，调了大概一个小时才过，打 \(C\) 时有一个小细节写挂了，快结束才改过来，幸好过了。

结果比较水的 \(\mathrm{B}\) 后来没时间打了，所以尽管过了 \(\mathrm{C}\) 分还是在第二档的水平。

~~以后一眼题先写，别拖到最后。~~

估分：\(100+0+100+0=200\)

实际：\(100+0+100+0=200\)

还是说正解吧（

A.方程的解

正解

很明显先用 \(\mathrm{exgcd}\) 算出来判断是否有解，并算出一组可行解。然后用这组解推出当 \(x\) 为最小正整数解时的 \(y\) 的值，接下来判断有几组正整数解就行了。

可以在求出最小正整数解之前先根据 \(a,b,c\) 的符号来判断是否会有 \(x,y\) 同时为正整数的情况，这样可以在后面判断负数时较为容易一些。

时间复杂度：\(O(Tn\log n)\)

code

#include<bits/stdc++.h>
using namespace std;
int t;
long long a,b,c,x,y;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    long long d=exgcd(b,a%b,x,y);
    long long z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a==0&&b==0)
        {
            if(c==0) printf("ZenMeZheMeDuo\n");
            else printf("0\n");
            continue;
        }
        if(b==0)
        {
            if(c%a==0&&c*a>0) printf("ZenMeZheMeDuo\n");
            else printf("0\n");
            continue;
        }
        if(a==0)
        {
            if(c%b==0&&c*b>0) printf("ZenMeZheMeDuo\n");
            else printf("0\n");
            continue;
        }
        if((a>0&&b>0&&c<0)||(a<0&&b<0&&c>0))
        {
            printf("0\n");
            continue;
        }
        if(a<0&&b<0) a=-a,b=-b,c=-c;
        long long d=exgcd(a,b,x,y),k;
        if(c%d!=0)
        {
            printf("0\n");
            continue;
        }
        if((a>0&&b<0)||(a<0&&b>0))
        {
            printf("ZenMeZheMeDuo\n");
            continue;
        }
        x*=c/d,y*=c/=d;
        a/=d,b/=d;
        if(x<=0) k=ceil((1.0-x)/b),x+=b*k,y-=a*k;
        else k=(x-1)/b,x-=b*k,y+=a*k;
        if(y>0)
        {
            if((y-1)/a+1>65535) printf("ZenMeZheMeDuo\n");
            else printf("%lld\n",(y-1)/a+1);
        }
        else printf("0\n");
    }
    return 0;
}

B.染色

正解

首先可以不算任何两个点之间的距离之和，只需算每条边被经过的次数。再根据乘法原理，每一条边的经过次数就等于它两侧的黑色个数之积加上白色个数之积，这样只需在树形 \(\mathrm{dp}\) 时枚举以 \(u\) 为根的子树内恰好有 \(j\) 个点为黑色的边权的最大值，再枚举其中一个儿子 \(v\) 内有 \(k\) 个点为黑色。就能得到转移方程：

\[f_{u,j}=\max\{f_{u,j-k}+f_{v,k}+dis\times [k(m-k)+(siz_v-k)(n-siz_v-m+k)]\} \]

注意枚举 \(j\) 时要从大到小枚举，其原理类似于背包。

时间复杂度：\(O(n^2)\)

code

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m;
int head[N],cnt;
int siz[N];
long long f[N][N];
struct Node
{
    int to,nxt,dis;
}e[N*2];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa)
{
    siz[u]=1;
    f[u][0]=f[u][1]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        for(int j=min(siz[u],m);j>=0;j--)
        {
            for(int k=0;k<=min(siz[v],j);k++)
            {
                if(f[u][j-k]==-1) continue;
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+1ll*e[i].dis*(k*(m-k)+(siz[v]-k)*(n-siz[v]-m+k)));
            }
        }
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    cout<<f[1][m]<<endl;
    return 0;
}

C.光

正解

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k;
int sx,sy,sdir,cnt,cnt2,flag;
char s[5];
struct Point
{
    int x,y;
}a[N*4];
long long ans;
bool cmp(Point a,Point b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
vector<Point> d1[N*2],d2[N*2];
map<pair<int,int>,int> t1,t2;
void dfs(int x,int y,int dir)
{
    if(x==sx&&y==sy&&dir==sdir&&flag==1)
    {
        flag=2;
        return;
    }
    flag=1;
    if(dir==0)
    {
        if(t1[make_pair(x-1,y)]!=0&&t1[make_pair(x,y+1)]!=0) return;
        if(t1[make_pair(x-1,y)]==0&&t1[make_pair(x,y+1)]==0) return;
        if(t1[make_pair(x-1,y)]!=0) y++,dir=1;
        else x--,dir=2;
    }
    else if(dir==1)
    {
        if(t1[make_pair(x-1,y)]!=0&&t1[make_pair(x,y-1)]!=0) return;
        if(t1[make_pair(x-1,y)]==0&&t1[make_pair(x,y-1)]==0) return;
        if(t1[make_pair(x-1,y)]!=0) y--,dir=0;
        else x--,dir=3;
    }
    else if(dir==2)
    {
        if(t1[make_pair(x+1,y)]!=0&&t1[make_pair(x,y+1)]!=0) return;
        if(t1[make_pair(x+1,y)]==0&&t1[make_pair(x,y+1)]==0) return;
        if(t1[make_pair(x+1,y)]!=0) y++,dir=3;
        else x++,dir=0;
    }
    else
    {
        if(t1[make_pair(x+1,y)]!=0&&t1[make_pair(x,y-1)]!=0) return;
        if(t1[make_pair(x+1,y)]==0&&t1[make_pair(x,y-1)]==0) return;
        if(t1[make_pair(x+1,y)]!=0) y--,dir=2;
        else x++,dir=1;
    }
    if(dir==0) ans+=(long long)d2[x+y][t2[make_pair(x-1,y+1)]].x-x,dfs(d2[x+y][t2[make_pair(x-1,y+1)]].x,d2[x+y][t2[make_pair(x-1,y+1)]].y,dir);
    else if(dir==1) ans+=(long long)d1[x-y+m+1][t1[make_pair(x-1,y-1)]].x-x,dfs(d1[x-y+m+1][t1[make_pair(x-1,y-1)]].x,d1[x-y+m+1][t1[make_pair(x-1,y-1)]].y,dir);
    else if(dir==2) ans+=(long long)x-d1[x-y+m+1][t1[make_pair(x+1,y+1)]-2].x,dfs(d1[x-y+m+1][t1[make_pair(x+1,y+1)]-2].x,d1[x-y+m+1][t1[make_pair(x+1,y+1)]-2].y,dir);
    else ans+=(long long)x-d2[x+y][t2[make_pair(x+1,y-1)]-2].x,dfs(d2[x+y][t2[make_pair(x+1,y-1)]-2].x,d2[x+y][t2[make_pair(x+1,y-1)]-2].y,dir);
    return;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) cin>>a[i].x>>a[i].y;
    int dir=0;
    cin>>sx>>sy>>(s+1);
    if(s[1]=='N') dir+=2;
    if(s[2]=='E') dir+=1;
    for(int i=0;i<=n+1;i++)
    {
        a[++k].x=i,a[k].y=0;
        a[++k].x=i,a[k].y=m+1;
    }
    for(int i=1;i<=m;i++)
    {
        a[++k].x=0,a[k].y=i;
        a[++k].x=n+1,a[k].y=i;
    }
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++)
    {
        d1[a[i].x-a[i].y+m+1].push_back(a[i]);
        d2[a[i].x+a[i].y].push_back(a[i]);
        t1[make_pair(a[i].x,a[i].y)]=d1[a[i].x-a[i].y+m+1].size();
        t2[make_pair(a[i].x,a[i].y)]=d2[a[i].x+a[i].y].size();
        //cout<<a[i].x<<" "<<a[i].y<<endl;
        if(cnt) continue;
        if(dir==1&&sx-sy==a[i].x-a[i].y&&a[i].x>=sx) cnt=t1[make_pair(a[i].x,a[i].y)];
        if(dir==2&&sx-sy==a[i].x-a[i].y&&a[i].x>=sx) cnt=t1[make_pair(a[i].x,a[i].y)]-1;
        if(dir==3&&sx+sy==a[i].x+a[i].y&&a[i].x>=sx) cnt=t2[make_pair(a[i].x,a[i].y)]-1;
        if(dir==0&&sx+sy==a[i].x+a[i].y&&a[i].x>=sx) cnt=t2[make_pair(a[i].x,a[i].y)];
        if(cnt2) continue;
        if(dir==2&&sx-sy==a[i].x-a[i].y&&a[i].x>=sx) cnt2=t1[make_pair(a[i].x,a[i].y)];
        if(dir==1&&sx-sy==a[i].x-a[i].y&&a[i].x>=sx) cnt2=t1[make_pair(a[i].x,a[i].y)]-1;
        if(dir==0&&sx+sy==a[i].x+a[i].y&&a[i].x>=sx) cnt2=t2[make_pair(a[i].x,a[i].y)]-1;
        if(dir==3&&sx+sy==a[i].x+a[i].y&&a[i].x>=sx) cnt2=t2[make_pair(a[i].x,a[i].y)];
    }
    cnt--,cnt2--;
    int tx,ty;
    if(dir==1||dir==2) tx=d1[sx-sy+m+1][cnt].x,ty=d1[sx-sy+m+1][cnt].y;
    else tx=d2[sx+sy][cnt].x,ty=d2[sx+sy][cnt].y;
    sx=tx,sy=ty,sdir=dir;
    dfs(sx,sy,dir);
    //cout<<endl;
    if(flag==1)
    {
        if(dir==1||dir==2) tx=d1[sx-sy+m+1][cnt2].x,ty=d1[sx-sy+m+1][cnt2].y;
        else tx=d2[sx+sy][cnt2].x,ty=d2[sx+sy][cnt2].y;
        ans+=(long long)abs(tx-sx)-1;
        sx=tx,sy=ty,sdir=3-dir;
        flag=0,dfs(sx,sy,3-dir);
    }
    cout<<ans<<endl;
    return 0;
}

D.无向图问题

正解

这篇关于五一欢乐赛方程的解染色光无向图问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程