【HDOJ5943】Kingdom of Obsession（数论）

题意：给定n个人，n个座位，人的编号是【1，n】，座位的编号是【s+1，s+n】，编号为i的人能坐在编号为j的座位上的条件是j%i=0

问是否存在一组方案使得座位和人一一对应

n,s<=1e9

思路：首先考虑如果区间【1，n】和【s+1，s+n】有重叠则重叠部分必然座位和人两两编号相同对应，因为这样能使解的空间更加宽松

现在考虑两端无重叠且等长的区间，显然如果靠后那段区间中出现了大于1个质数则他们都必须要用1，必然无解

根据质数密度分布可以近似算出阈值（据tls说是60？），如果区间长度大于阈值则必然无解，否则跑二分图最大匹配

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef long double ld;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,ll>P;

 #define N  2000000+10

 #define M  200000+10

 #define INF 1e9

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 #define fors(i) for(auto i:e[x]) if(i!=p)

 const int MOD=,inv2=(MOD+)/;

       //int p=1e4+7;

       //double eps=1e-6;

       int dx[]={-,,,};

       int dy[]={,,-,};

 int head[N],vet[N],nxt[N],match[N],flag[N],a[N],b[N],tot;

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 ll readll()

 {

    ll v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void add(int a,int b)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     head[a]=tot;

 }

 int dfs(int u)

 {

     flag[u]=;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(!match[v]||!flag[match[v]]&&dfs(match[v]))

         {

             match[v]=u;

             return ;

         }

         e=nxt[e];

     }

     return ;

 }

 int main()

 {

     //freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

     int cas=read();

     rep(v,,cas)

     {

         int n=read(),s=read();

         int x1,y1,x2,y2;

         if(n<s+) x1=,y1=n,x2=s+,y2=s+n;

          else x1=,y1=s,x2=n+,y2=s+n;

         if(y1-x1>) printf("Case #%d: No\n",v);

          else

          {

              int n=;

              rep(i,x1,y1)

              {

                  n++; a[n]=i;

              }

              n=;

              rep(i,x2,y2)

              {

                  n++; b[n]=i;

              }

              rep(i,,n) head[i]=match[i]=;

              tot=;

              rep(i,,n)

               rep(j,,n)

                if(b[j]%a[i]==) add(i,j);

              int ans=;

              rep(i,,n)

              {

                  rep(j,,n) flag[j]=;

                  if(dfs(i)) ans++;

              }

              if(ans==n) printf("Case #%d: Yes\n",v);

               else printf("Case #%d: No\n",v);

          }

     }

     return ;

 }

巴特西

【HDOJ5943】Kingdom of Obsession（数论）

最新文章

热门文章