题解 P2436 【钦定】

· · 题解

前：本文对萌新很友好，因为题目难度较低。我感觉题目难度应该会更高。蒟蒻交了17次，除掉对着现有的唯一的题解打了一遍AC掉，剩下的都是自己写的。思路和目前唯一一篇题解一样。但是，我只有60分。不过我相信，这篇题解一定能帮助别人，自然也会具有一定的学习意义。

分割线-------------------------------------------------

正文从这里开始。

看到这种区间问题，可以想到与 % （模运算） 有关。

这是一个突破口。

我们需要枚举周期。题目有写，选手编号小于等于 (n+m)*10，所以，枚举要从2到这个数+1。

    cnt=(n+m)*10+1;
    for(int i=2;i<=cnt;i++)

定义数组 a 为神犇数列，b 为蒟蒻（我）数列。我们还可以观察到，这两个数列中的数不连续，分散地分布在数轴上。

所以，我们用这里面的每一个数去模枚举的周期，模完后的值肯定有大有小。我们在 a 数组中取最大值，在 b 数组中取最小值。

    answer1=0;answer2=INF;
    for(int j=1;j<=n;j++){
        c[j]=a[j]%i;
        if(c[j]==0)answer1=max(answer1,i);
        else answer1=max(answer1,c[j]);
    }
    for(int j=1;j<=m;j++){
        d[j]=b[j]%i;
        if(d[j]==0)answer2=min(answer2,i);
        else answer2=min(answer2,d[j]);
    }

用两个 answer 记录好。

可以发现（比方说找规律，打表）：最大值与最小值之和一定等于周期。

蒟蒻有一个不严谨的证明，这边不贴了。还是我太差了。

根据这一个结论，就可以写出最后的代码部分了。

我的代码和题解基本一样，因为我是在那篇题解的启发下，才有了思路，理解了题目。

    if(!t){
        puts("NO");printf("\n");
        continue;
    }
        sort(q+1,q+t+1,cmp);
        cout<<q[1].x<<" "<<q[1].y<<endl;

60分的完整代码：CODE by lmrttx。

后：蒟蒻最近刚开始写题解，做贡献，涨咕值，自然会有许多不足。我也会虚心改进。我看到记录里许多人直接复制题解，我不认可这种行为，题目必须要有思考。希望这篇题解可以给你们做题的想法，谢谢阅读。