• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

解决五一快乐游戏方程的色光无向图问题


Recommended Posts

竞争环节

在考场上按顺序出题。

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

\(\mathrm{B.}\mathbb{染色} \): tree \(\mathrm{dp}\)

\(\ mathrm { c . } \ mathbb { light } \):optimization \(\ 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)\)

密码

#includebits/stdc。h

使用命名空间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)

{

如果(b==0)

{

x=1,y=0;

返回a;

}

long long d=exgcd(b,a%b,x,y);

long long z=x;

x=y;

y=z-y *(a/b);

返回d;

}

int main()

{

scanf('%d ',t);

while(t -)

{

scanf('%lld%lld%lld ',a,b,c);

如果(a==0b==0)

{

if(c==0)printf(' ZenMeZheMeDuo \ n ');

else printf(' 0 \ n ');

继续;

}

如果(b==0)

{

if(c % a==0c * A0)printf(' ZenMeZheMeDuo \ n ');

else printf(' 0 \ n ');

继续;

}

如果(a==0)

{

if(c % b==0c * B0)printf(' ZenMeZheMeDuo \ n ');

else printf(' 0 \ n ');

继续;

}

if((a0b0c0)||(a0b0c0))

{

printf(' 0 \ n ');

继续;

}

if(a0b0) a=-a,b=-b,c=-c;

long long d=exgcd(a,b,x,y),k;

if(c%d!=0)

{

printf(' 0 \ n ');

继续;

}

if((a0b0)||(a0b0))

{

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.无向图问题

正解

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now