HDU 5943.Kingdom of Obsession(2016 CCPC 杭州 K)

227

题目


点击显/隐题目

There is a kindom of obsession, so people in this kingdom do things very strictly.

They name themselves in integer, and there are n people with their id continuous (s+1,s+2, ,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at yth position which satisfy

x mod y=0

Is there any way to satisfy everyone's requirement

First line contains an integer T, which indicates the number of test cases.

Every test case contains one line with two integers n, s.

Limits
1≤T≤100.
1≤n≤109.
0≤s≤109.


For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.

If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

2
5 14
4 11

Case #1: No
Case #2: Yes



题解


题意比较容易理解,对于 [s+1,s+n]n 个人,将他们放置在 [1,n] 这些位置上
其中 编号为 x 的人 只能放在位置 y 上,有 x mod y = 0

按照样例自己在纸上花出来,可以发现就是 二分图匹配
对于一组数据判断是否能够做到 最佳完美匹配

看数据量可以发现数据高达 109
然而,根据经验可知,随着数的增大,两个素数之间的距离会变大,但对于 109 的数据量,间距仍然是一个确定的值
当需要运算的区间 有多个素数时,显然可以直接输出 "No"
(都要放在 1 的位置上)

因此,一个比较可行的思路是先判断下是否有多个素数,如果有可能有解的情况下,使用 匈牙利算法 进行计算

关于判断是否有多个思路,有两种思路:
  1. 对于一组数据的每一个数据都进行判断是否为素数,当找到 2 个以上时,直接跳出循环
  2. 找到 109 素数间隔的最大值,只在小于时计算

首先假设最大的间隔为 Max
对于第一种思路,采用 费马小定理 每次判断的时间复杂度为 log(n)^2
一组数据最坏要查询 Max 次
而直接判断显然可以忽略这个时间

而由于匈牙利算法的时间复杂度为 O(nm)

显然,只有 Max 较大的情况下,方案 1 更好
(已经可以预知,不管怎么样,如果方案 2 都超时,方案 1 必定超时)

根据查表, 109 的素数最大间隔还不到 300

因此大于 300 直接输出 "No" 即可
对于小于 300 的情况直接使用是匈牙利算法即可

有一点需要特别注意: [s+1,s+n] 和 [1,n] 有可能存在重合区间
对于重合部分,无论有多少素数,都没关系(自己对自己取余为 0 )

因此,二分图处理的部分应该是不重合的部分(找因子的时候,直接使用本身比使用它的一个因子更“划算”)
假设有重合区域,则重合区域应该为 [s+1,n]
因此应该对 [1,s+1)(n,s+n] 区域求二分图匹配
也即对 [1,s][n+1,n+s] 区域求二分图匹配,恰好就是交换 sn
也就是说,当 n>=s+1 (s<n) 时交换两者,就可以避过重合问题
(当然,通过其他的判断也可以解决)


代码


点击显/隐代码
`cpp Kingdom of Obsession https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*
#define debug
#include
//*/

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

/*
  • 匈牙利算法邻接表形式
  • 使用前用init()进行初始化,给uN赋值
  • 加边使用函数addedge(u,v)
  • */
    const int MAXN = 2005;//点数的最大值
    const int MAXM = MAXN*MAXN;//边数的最大值
    struct Edge {
    }edge[MAXM];

int head[MAXN],tot,uN;
void init(int un) {
uN = un;
tot = 0;
memset(head,-1,sizeof(head));
}

void addedge(int u,int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}

int linker[MAXN];
bool used[MAXN];
bool dfs(int u) {
for(int i = head[u]; i != -1;i = edge[i].next){
int v = edge[i].to;
if(!used[v]){
used[v] = true;
if(linker[v] == -1 || dfs(linker[v])){
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary(){
int res = 0;
memset(linker,-1,sizeof(linker));
for(int u = 0; u < uN;u++){//点的编号0~uN-1
memset(used,false,sizeof(used));
if(dfs(u))
res++;
}
return res;
}

bool Solve(int n,int s){
if(sif(n>1000) return false;

//匈牙利算法 求解二分图
init(n);
for(int i=1;i<=n;i++){
LL t = (LL)i+(LL)s;
for(int j=1;j<=n;j++){
if(t%j==0)
addedge(j-1,i-1);
}
}
//cout<return hungary()==n;
}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif

int T;
cin>>T;
for(int kase=1;kase<=T;kase++){
int n,s;
cin>>n>>s;
cout<<"Case #"<}

#ifdef debug
printf("Time:%.3lfsn", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论