题解：CF2031C Penchick and BBQ Buns

致敬传奇构造题。

首先知道一个很简单的结论，1 也是完全平方数。所以我们完全可以构造出一个区间 l\sim r，其中区间长度为偶数，将其中的元素两两一组构造，这样对于这个区间一定是满足题意的。

举例：若 n=6，则构造 (1,1,2,2,3,3)。

所以说，若题目中给的 n 是偶数，可以直接通过上述方法构造。

如果是奇数，怎么办？

这里肯定至少要选一个数出现次数为奇数了。

这里考虑如果一个数出现次数为奇数还满足题目条件会有什么性质。

题目说的是，对于任意二元组 (i,j)，若颜色 c_i=c_j，则 \lvert i-j \rvert 为完全平方数。

这样的话，如果跟完全平方数沾边，自然会想到勾股定理。

有啥关系呢？我们知道勾股定理的内容是在一个直角三角形中，直角边的平方和等于斜边的平方。

考虑将这个结论转移到序列上。

不难发现，我们假设有 (i,j,k) 这三个元素颜色相等（这里假设 i<j<k）。那么就有 j-i 为完全平方数，k-j 为完全平方数，k-i 为完全平方数。从这里就看出来了，j-i 和 k-j 等价于直角边，k-i 等价于斜边。成功转化。

那么考虑最小的勾股数组合 (3,4,5)，那么我们就令 c_1=c_{10}=c_{26}，这样的话这三个数就满足了题意。

同时我们也可以发现，如果 n\leq 26 且为奇数，则无解。

• 对于区间 2\sim9，直接套结论构造，因为区间元素个数为偶数。
• 对于区间 11\sim25，不能直接构造，怎么办？而且区间元素个数为 15，与上述结论矛盾。

但是可以发现，如果我们可以采取一个办法，将区间元素个数变成偶数，是不是就可以解决了。

区间中间的元素肯定是不能乱动的，只能套结论。我们发现区间两头的元素是不是有可能和 26 以后的数拼一下，因为对于 27\sim n 之间的元素个数也是奇数，也不能上结论，所以可以对两段区间端点组合，将两段区间元素个数变成偶数再套结论。

然后你就可以发现，若 c_{11}=c_{27}，是满足题意的，也符合上述条件。如果这个结论你不能一眼看出，可以参考我的代码写法，因为我也不是一眼看出来的，是调试时偶然发现的。

所以结论如下。

偶数一定有解，对于 27 及以上的奇数一定有解，反之无解。

code

只放奇数端点写法。

int l1 = 11, l2 = 25,   
    r1 = 27, r2 = n;
int d1 = r1 - l1,
    d2 = r1 - l2;
int e1 = r2 - l1,
    e2 = r2 - l2;
if((int)sqrt(d1) * (int)sqrt(d1) == d1) {
    a[l1] = a[r1] = 1e6 - 1;
    int tot = 5;
    rep(i, 12, 25) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i;
    }
    rep(i, r1 + 1, r2) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i; 
    }
} 
else if((int)sqrt(d2) * (int)sqrt(d2) == d2) {
    a[l2] = a[r1] = 1e6 - 1;
    int tot = 5;
    rep(i, 11, 24) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i;
    }
    rep(i, r1 + 1, r2) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i; 
    }
}
else if((int)sqrt(e1) * (int)sqrt(e1) == e1) {
    a[l1] = a[r2] = 1e6 - 1;
    int tot = 5;
    rep(i, 12, 25) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i;
    }
    rep(i, r1, r2 - 1) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i; 
    }
}
else if((int)sqrt(e2) * (int)sqrt(e2) == e2) {
    a[l2] = a[r2] = 1e6 - 1;
    int tot = 5;
    rep(i, 12, 25) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i;
    }
    rep(i, r1, r2 - 1) {
        a[i] = a[i + 1] = tot;
        ++tot, ++i; 
    }
}

两个区间左右端点两两组合有 4 种情况。时间复杂度 O(N)。 完整代码可以私信要，因为我这代码是复杂的，知道结论后完全可以简化。