P8128 [ICPC2020 WF] Cardiology 题解

· · 题解

NOIP 前写一写题解。

题目大意差不多是有一个矩阵，其中有一个数，每次取这个数所在的一列，从固定位置（固定位置与 p 有关）开始将这一列依次排列到后面去，如此往复，直到猜到这个数的位置，并找到符合条件的里中心最近的位置与 p 的大小。

容易发现此时数的位置可能会发生改变，而且数的位置始终是在一个区间内的，其次每取一次这个区间就会缩小一次，直到只有一个数为止，可以考虑枚举 p 的大小，进行模拟即可。

可以考虑极端情况，假设这个数在这个区间的开头或结尾，然后依据此计算出下一次的区间会会缩小的哪里，但这并不是对的，以为有某些区间并不会缩小了，这个时候就要跳过这个情况，尝试枚举下一种情况。

核心代码。


        be = 1; ed = r*c;
        LL fi = r * (p - 1ll) + 1ll,maxis=0;
        FOR(i, 1, 500){
            LL nowbe=be,nowed=ed;
            LL L = (be+c-1ll)/c;
            LL R = (ed+c-1ll)/c;
            be = fi + L - 1ll;
            ed = fi + R - 1ll;
            if(nowbe==be&&nowed==ed)break;
            if(be==ed){maxis=ibreak;}
        }
        if(be!=ed)continue;
        LL x=be%c,y=(be+c-1ll)/c;
        if(dis(x,y)<ans){
            ans=dis(x,y);
            id=be;  
            sp=p;
            maxi=maxis;
        }