P11312 题解

发表于 阅读次数：

其他大神的正解写的很好，我特此来发一篇乱搞做法。

本题解只作参考，主要指出骗分的方法和为什么乱搞做法通过率高（并给出一个乱搞做法），并不是实际意义上的正确做法。（但还是求管理员大大给过 QAQ）

赛时一个一个 subtask 骗分，骗着骗着就 AC 了，感觉好激动。本篇乱搞做法就围绕各 subtask 展开。

subtask 1

$k=1$ 时，由于任意两数的最大公约数至少为 $l$，所以肯定有解并随意输出区间中的数即可。

subtask 2

观察到 $n$ 和锁圈的拨动范围极小，直接暴力 dfs 即可。

subtask 3

直接枚举最大公约数，$\mathcal{O}(n)$ 判断是否可行，由于最大公约数肯定不超过 $\min_{i=1}^n r_i$，所以时间复杂度是可接受的。

subtask 4

由于 $l,r$ 随机生成，所以其间包含的数期望会比较多，又因为 $k$ 比较小，大概率有解，直接计算任意一个不小于 $l_i$ 且不大于 $r_i$ 的数输出即可。

subtask 5

由于存在 $l_i=r_i$，所以这个锁圈只能选择 $l_i$，所以最大公约数肯定为 $l_i$ 的因数。可以 $\mathcal{O}(\sqrt{l})$ 枚举因数并 $\mathcal{O}(n)$ 判断即可。这里有个小技巧，如果有多个 $l_i=r_i$ 时，我们可以直接记录这些 $l_i$ 的最大公约数并只枚举其因数即可。

subtask 6

玄学。赛时由于数据交水，直接暴力从 $k$ 开始枚举到 $\min_{i=1}^n r_i$ 并 $\mathcal{O}(n)$ 判断可过。加强了数据后就挂了，会 T 一个点。

不妨想一想为什么会超时。我们发现有两个可能：

  1. 最终合法的最大公约数过大。

  2. 由于判断的顺序导致每一次判断都会 $\mathcal{O}(n)$ 跑满减慢程序运行。

争对第一点，由于公约数大，所以要么各个区间会产生重叠（每个区间包含这个数），要么导致 $n$ 减小、区间变小（每个区间包含这个数的两倍、三倍……可以发现因为最大公约数很大，所以区间数也相应会减少，虽然这么说并不严谨）。可以判断是否所有区间有重叠部分和精妙的玄学方法来解决问题。

对于第二点，我们略作思考，可以随机变换原序列的顺序，来尽量防止特意构造的数据把每一次 $n$ 次判断跑满。注意，这只能减少程序效率降低的概率，并不能真正地提高程序的效率。

综上所述，可得代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;
int T,n,k,chose[N];
struct node {
    int l,r,id;
} a[N];

bool dfs(int x) {
    if(x>n) {
        int gcd=chose[1];
        for(int i=2;i<=n;i++) gcd=__gcd(gcd,chose[i]);
        if(gcd>=k) {
            printf("Yes\n");
            for(int i=1;i<=n;i++) printf("%d ",chose[i]);
            printf("\n"); return true;
        }
        return false;
    }
    for(int i=a[x].l;i<=a[x].r;i++) {
        chose[a[x].id]=i;
        if(dfs(x+1)) return true;
    }
    return false;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        int mxl=0,mnl=1e9,mxr=0,mnr=1e9;
        bool subtask=true;
        int sbtask=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a[i].l,&a[i].r);
            a[i].id=i;
            if(a[i].r-a[i].l>4) subtask=false;
            if(a[i].l==a[i].r) sbtask=__gcd(sbtask,a[i].l);
            mxr=max(mxr,a[i].r),mnr=min(mnr,a[i].r);
            mxl=max(mxl,a[i].l),mnl=min(mnl,a[i].l);
        }
        random_shuffle(a+1,a+1+n);

        if(k==1) {
            printf("Yes\n");
            for(int i=1;i<=n;i++) chose[a[i].id]=a[i].l;
            for(int i=1;i<=n;i++) printf("%d ",chose[i]);
            printf("\n"); continue ;
        }
        if(mxr<=1000) {
            bool ans=false;
            for(int i=k;i<=mxr;i++) {
                bool flag=true;
                for(int j=1;j<=n;j++)
                    if(((a[j].l-1)/i+1)*i>a[j].r) {
                        flag=false; break ;
                    }
                if(flag) {
                    printf("Yes\n");
                    for(int j=1;j<=n;j++) chose[a[j].id]=((a[j].l-1)/i+1)*i;
                    for(int j=1;j<=n;j++) printf("%d ",chose[j]);
                    printf("\n"),ans=true; break ;
                }
            }
            if(!ans) printf("No\n");
            continue ;
        }
        if(subtask) {
            if(!dfs(1)) printf("No\n");
            continue ;
        }
        if(sbtask) {
            bool ans=false;
            for(int i=k;i*i<=sbtask;i++)
                if(sbtask) {
                    bool flag=true;
                    for(int j=1;j<=n;j++)
                        if(((a[j].l-1)/i+1)*i>a[j].r) {
                            flag=false; break ;
                        }
                    if(flag) {
                        printf("Yes\n");
                        for(int j=1;j<=n;j++) chose[a[j].id]=((a[j].l-1)/i+1)*i;
                        for(int j=1;j<=n;j++) printf("%d ",chose[j]);
                        printf("\n"),ans=true; break ;
                    }
                }
            if(!ans) printf("No\n");
            continue ;
        }
        if(k<=5) {
            printf("Yes\n");
            for(int i=1;i<=n;i++) chose[a[i].id]=a[i].l/5*5+5;
            for(int i=1;i<=n;i++) printf("%d ",chose[i]);
            printf("\n"); continue ;
        }
        bool ans=false;
        for(int i=k;i<=mnr;i++) {
            bool flag=true;
            for(int j=1;j<=n;j++)
                if(!((a[j].l-1)/i<a[j].r/i)) {
                    flag=false; break ;
                }
            if(flag) {
                printf("Yes\n");
                for(int j=1;j<=n;j++) chose[a[j].id]=((a[j].l-1)/i+1)*i;
                for(int j=1;j<=n;j++) printf("%d ",chose[j]);
                printf("\n"),ans=true; break ;
            }
        }
        if(!ans) printf("No\n");
    }
    return 0;
}