HDU5943 Kingdom of Obsession（思路题+二分匹配）-白红宇

HDU5943 Kingdom of Obsession（思路题+二分匹配）

阅读量：6485 次

发布时间：2019-06-23

本文共 1440 字，大约阅读时间需要 4 分钟。

题意：

给你两个数n,s(1e9)，问你能否使得s+1--s+n和1--n全部匹配

每个数只能匹配他的因子

思路：

要匹配的这一段数中非重合部分最多有1个素数，也就是说n和s不能同时很大

我打了1e9的素数间隔表，发现最大间距才280多。。

然后索性直接当n和s都大于500的时候就输出no就可以了

符合条件的数非重合部分最多500个，二分匹配一下

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate
                  
                   inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=5e4+10;LL n,s;vector
                   
                    eg[N];int linker[N];bool vis[N];bool dfs(int u){ for(int i=0; i
                    
                     500&&s>500) { printf("No\n"); continue; } if(n>s) swap(n,s); for(int i=1; i<=n; i++) eg[i].clear(); for(int i=1; i<=n; i++) add(i); int ans=0; memset(linker,-1,sizeof(linker)); for(int i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } if(ans==n) printf("Yes\n"); else printf("No\n"); } return 0;}