频道栏目
首页 > 考试 > 其他 > 正文
HDU5943-Kingdom of Obsession
2017-07-03 09:29:12         来源:wang_128的博客  
收藏   我要投稿

Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1162Accepted Submission(s): 356

Problem Description There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there arenpeople with their id continuous(s+1,s+2,?,s+n)standing in a line in arbitrary order, be more obsessively, people with idxwants to stand atythposition which satisfy
xmody=0
Is there any way to satisfy everyone's requirement?
Input First line contains an integerT, which indicates the number of test cases.
Every test case contains one line with two integersn,s.
Limits
1≤T≤100.
1≤n≤109.
0≤s≤109.
Output For every test case, you should output'Case #x: y', wherexindicates the case number and counts from1andyis the result string.
If there is any way to satisfy everyone's requirement,yequals'Yes', otherwiseyequals'No'.
Sample Input

2 5 14 4 11

题意:有n个人,每个人的标号以此是s+1到s+n,要求将所有人重新排序之后满足每个人的位置y能够保证被他的标号整除,就是数组重排之后满足每一位的a[i]%i==0

解题思路:一定区间之内最多只有一个质数,所以多于一个质数的直接NO(差不多任意两个相邻之间的素数的差不会超过500),其他情况可以直接二分图匹配去跑,把这段区间和1~n作为2*n个节点直接n^2建图跑匈牙利就行(这段区间和1~n可能有重叠的部分,这段是要删去的,重叠部分一定满足所以不需要匹配,所以最后图中的节点就是一边时1到min(n,s)一边是max(n,s)到n+s)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 

using namespace std;

#define LL long long
const int INF=0x3f3f3f3f;

int n,ss;
int x[559],y[559];
int s[559],nt[260009],e[260009];
int visit[559];

bool path(int k)
{
    for(int i=s[k]; ~i; i=nt[i])
    {
        int ee=e[i];
        if(!visit[ee])
        {
            visit[ee]=1;
            if(y[ee]==-1||path(y[ee]))
            {
                y[ee]=k;
                x[k]=ee;
                return 1;
            }
        }
    }
    return 0;
}

void MaxMatch()
{
    int ans=0;
    memset(x,-1,sizeof x);
    memset(y,-1,sizeof y);
    for(int i=1; i<=n; i++)
    {
        if(x[i]==-1)
        {
            memset(visit,0,sizeof visit);
            if(path(i)) ans++;
        }
    }
    if(ans==n) printf("Yes\n");
    else printf("No\n");
}

int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case #%d: ",++cas);
        scanf("%d%d",&n,&ss);
        if(ss<=1)
        {
            printf("Yes\n");
            continue;
        }
        if(ss550)
        {
            printf("No\n");
            continue;
        }
        int cnt=1;
        memset(s,-1,sizeof s);
        for(int i=ss+1; i<=ss+n; i++)
            for(int j=1; j<=n; j++)
                if(i%j==0) nt[cnt]=s[i-ss],s[i-ss]=cnt,e[cnt++]=j;
        MaxMatch();
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:HDU5938-Four Operations
下一篇:HDU5935-Car
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站