自动搬运

查看原文

来自洛谷，原作者为

	Austin0116 ？？？

搬运于2025-08-24 23:06:20，当前版本为作者最后更新于2024-11-23 23:22:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

首先我们发扬人类智慧

感觉最大公因数不会太大，所以直接从 $k$ 枚举到 $10^6$ ，判断每个区间是否符合，在未加强数据时，这个代码可以得到 $100$ 分的好成绩。

贴一下主要部分的代码。

for(int i=k;i<=1000000;i++){
  fl=0;
  for(int j=2;j<=n;j++) if(a[j].x>a[j].y||(a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
    fl=1;//有区间不符合条件
    break;
  }
  if(!fl){//所有区间符合条件直接统计答案
    c.clear();
    puts("Yes");
    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
    for(int x:c) printf("%d ",x);
    putchar('\n');
    break;
  } 	
}

但是加强数据后只能获得 $65$ 分，我们考虑如何继续发扬人类智慧。

我们可以猜测由于答案比较大，所以每个区间都比较分散，所以可以从选择一个最小的右端点,枚举 $k$ 到这个右段点的每一个数，然后判断每个区间是否符合，最后可以获得 $85$ 分的好成绩。

贴一下重点代码。

struct ha{
	int x,y,id;
};
ha a[10005];
inline bool cmp1(ha &a,ha &b){
	return a.y<b.y;
}
inline bool cmp2(ha &a,ha &b){
	return a.id<b.id;
}
sort(a+1,a+1+n,cmp1);
if(a[n].x>a[n].y){//特判
  puts("No");
  continue;
}
fl=1;
for(int i=k;i<=a[1].y;i++){
  fl=0;
  for(int j=1;j<=n;j++) if((a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
    fl=1;//不符合条件
    break;
  }
  if(!fl){//符合条件
    c.clear();
    puts("Yes");
    sort(a+1,a+1+n,cmp2);
    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
    for(int x:c) printf("%d ",x);
    putchar('\n');
    break;
  } 
}
if(fl) puts("No");

我们继续发扬人类智慧。

由于只有一个点错了，而且这个点是 Subtask 2 的原来能过的点，所以我们只需要进行数据分治： $n \le 10$ 用第一种方法，剩下情况用第二种方法。

AC 代码

#include <bits/stdc++.h>
using namespace std;
struct ha{
	int x,y,id;
};
ha a[10005];
inline bool cmp1(ha &a,ha &b){
	return a.y<b.y;
}
inline bool cmp2(ha &a,ha &b){
	return a.id<b.id;
}
int t,n,k;
bool fl;
vector<int> c;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].x,&a[i].y);
			a[i].id=i;
			a[i].x=max(a[i].x,k); 
		} 
		if(n<=10){
			for(int i=k;i<=1000000;i++){
				fl=0;
				for(int j=2;j<=n;j++) if(a[j].x>a[j].y||(a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
					fl=1;
					break;
				}
				if(!fl){
					c.clear();
					puts("Yes");
					for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
					for(int x:c) printf("%d ",x);
					putchar('\n');
					break;
				} 	
			}
			if(fl) puts("No");
		}
		else{
			sort(a+1,a+1+n,cmp1);
			if(a[n].x>a[n].y){
				puts("No");
				continue;
			}
            fl=1;
			for(int i=k;i<=a[1].y;i++){
				fl=0;
				for(int j=1;j<=n;j++) if((a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
					fl=1;
					break;
				}
				if(!fl){
					c.clear();
					puts("Yes");
					sort(a+1,a+1+n,cmp2);
					for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
					for(int x:c) printf("%d ",x);
					putchar('\n');
					break;
				} 
			}
			if(fl) puts("No");	
		}
	}
	return 0;
}