Codeforces 1004D

转载自：https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/80951796

题目链接：

http://codeforces.com/contest/1004/problem/D

 

为了方便叙述我在(0,0)(0,0)建立直角坐标系，那么xx轴和yy轴都是对称轴，(0,0)(0,0)是对称中心，相同的数字呈现闭合的菱形分布。 
在每一个象限内，直线x=kx=k或y=ky=k(k是任意非零整数)上的数字都呈现公差为11的等差数列，所有斜率为±1±1的直线上的点都呈现公差为22的等差数列 
到任何一个点曼哈顿距离的最大或最小值都在四个角之一，边界上离某个点曼哈顿距离最小的点都是从该点向边界做垂线交得的点

出题人的意思

由于这个东西具有对称性，每一种解都可以通过翻转将它变化出最多四种解。 
我们仅考虑(x,y)(x,y)在靠近左边界或者上边界的解。 
举个例子，题目中给出了这种情形：  
 
那么我们可以等价为： 

设a,ba,b分别为到0,00,0最近、最远的点，那么(1,1)(1,1)到(x,y)(x,y)的距离设为aa，(n,m)(n,m)到(x,y)(x,y)的距离设为bb 
显然a,ba,b分别是给出的数字中的最大和最小值 
列式 

{a=x−1+y−1b=n−x+m−y(1)(2){a=x−1+y−1(1)b=n−x+m−y(2)

xx就是给出的数字中最小的出现次数不为本身值的44倍的数字，这个很好理解，因为我们求的是(x,y)(x,y)在左上的解，当曼哈顿距离相同数字构成的菱形在向外一层一层扩展时，首先触碰到的是左边界或者上边界，在这之前每个数字都比前一个数字的出现次数多44，出现次构成了通项为4n4n的等差数列。在刚好触碰边界的数字的下一个数字，就不满足这个通项了，而观察表格就发现这个数字的值恰好等于00到边界的最小距离。 
那么你求出这个数字之后，它应该作为xx的值或者作为yy的值，但是我为什么说它就是xx的值？因为我可以通过一次90∘90∘旋转对这两种情况做出等价变形。 
现在x,a,bx,a,b已知，由上述方程组可以得到y=n+m−b−xy=n+m−b−x 
现在就差n,mn,m不知道了， 
显然nm=tnm=t 
所以n,mn,m都是tt的约数，这个肯定可以Θ(t√)Θ(t)枚举 
最后的复杂度取决于tt的约数个数 
复杂度为O(σ0(t)t)O(σ0(t)t)

 

改进算法的稳定性

其实很多解都是不合法的，当找到一组(n,m)(n,m)时，代回(1),(2)(1),(2)两式检验，理论上二元二次方程有四组根，所以复杂度是Θ(t)的 
这样就不会被那些约数超多的数字卡掉了

#include <bits/stdc++.h>

using namespace std;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int t, b = 0;
    cin >> t;
    vector<int> a (t * 10);
    for(int i = 0; i < t; i ++) {
        int c;
        cin >> c;
        a[c] ++;
        b = max(b, c);
    }
    if(a[0] > 1) {
        cout << -1 << '\n';
        return 0;
    }
    int x = 1;
    for(int i = 1; i <= b; i ++) {
        if(a[i] / i != 4) {
            x = i;
            break;
        }
    }
    for(int n = 1; n <= t; n ++) {
        if(t % n != 0) continue;
        int m = t / n;
        int y = n + m - b - x;
        if(abs(n - x) + abs(m - y) != b) continue;
        vector<int> should (n + m + n + m, 0);
//        cout << "n = " << n << " m = " << m << " x = " << x << " y = " <<y << '\n';
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                should[abs(i - x) + abs(j - y)] ++;
            }
        }
        bool fg = 1;
        for(int i = 0; i < n + m; i ++) {
            if(a[i] != should[i]) {
                fg = 0;
                break;
            }
        }
        if(fg) {
            cout << n << ' ' << m << '\n';
            cout << x << ' ' << y << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}