Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

答案wa,但是评论区的数据都过了,拿AC代码写对拍也没查出来问题

Posted by BUAAllx at 2024-03-23 09:05:04 on Problem 1417
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int M=601,N=2001;

int n,p1,p2,m;
int f[M*2],s[M*2],dp[M][N],from[M][N],ts[M],ans[M*2];

int find(int x)
{
    if(x==f[x])
    {
        return f[x];
    }
    f[x]=find(f[x]);
    return f[x];
}

void bind(int x,int y)
{
    if(x==y)
    {
        return;
    }
    if(s[x]>s[y])
    {
        f[y]=x;
        s[x]+=s[y];
    }
    else
    {
        f[x]=y;
        s[y]+=s[x];
    }
    return;
}

int main()
{
    while(scanf("%d%d%d",&n,&p1,&p2))
    {
        int tot=0;
        if(!n && !p1 && !p2)
        {
            break;
        }
        m=p1+p2;
        for(int i=1;i<=m*2;i++)
        {
            f[i]=i;
            s[i]=1;
        }
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        memset(ts,0,sizeof(ts));
        for(int i=1;i<=n;i++)
        {
            int a,b;
            char s[10];
            scanf(" %d%d %s",&a,&b,s);
            int a1=find(a),a2=find(a+m);
            int b1=find(b),b2=find(b+m);
            if(s[0]=='y')
            {
                bind(a1,b1);
                bind(a2,b2);
            }
            else
            {   
                bind(a1,b2);
                bind(a2,b1);
            }
        }
        
        //判断过程
        if(p1==p2)
        {
            printf("no\n");
            continue;
        }
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            int k=find(i);
            if(k>m)
            {
                continue;
            }
            ts[k]++;
        }
        for(int i=1;i<=m;i++)
        {
            if(f[i]!=i)
            {
                continue;
            }
            tot++;
            for(int j=0;j<=p1;j++)
            {
                if(dp[tot-1][j])
                {
                    if(j+ts[i]<=p1)
                    {
                        dp[tot][j+ts[i]]+=dp[tot-1][j];
                        from[tot][j+ts[i]]=i;
                    }
                    if(j+s[i]-ts[i]<=p1)
                    {
                        dp[tot][j+s[i]-ts[i]]+=dp[tot-1][j];
                        from[tot][j+s[i]-ts[i]]=m+i;
                    }
                }
            }
        }
        if(!dp[tot][p1] || dp[tot][p1]>1)
        {
            printf("no\n");
        }
        else
        {
            int r=p1;
            while(r)
            {
                ans[from[tot][r]]=1;
                if(from[tot][r]<=m)
                {
                    r-=ts[from[tot][r]];
                }
                else
                {
                    r-=s[from[tot][r]-m]-ts[from[tot][r]-m];
                }
                tot--;
            }
            for(int i=1;i<=m;i++)
            {
                if(ans[f[i]])
                {
                    printf("%d\n",i);
                }
            }
            printf("end\n");
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator