题解：CF1948E Clique Partition

· · 题解

首先，观察到题目中两点连边的条件为 \lvert i-j \rvert + \lvert a_i-a_j \rvert \le k，与曼哈顿距离的定义式 d = \lvert x_a-x_b \rvert + \lvert y_a-y_b \rvert 很像，所以可以考虑将题目条件转换成坐标系中的曼哈顿距离（其实双绝对值转曼哈顿距离是数学里的常用技巧吧）。

那么，建立平面直角坐标系，对于每一个点，以下标 i 作为横坐标，以 a_i 作为纵坐标，就可以将这 n 个点转化成坐标系中的 n 个坐标。

接着，根据曼哈顿距离的性质，与坐标 (x,y) 距离小于等于 k 的点构成一个菱形（斜 45\degree 的正方形），如下（与坐标 (7,6) 距离小于等于 5 的点）：

其次，要使一块区域每一个点都可以这样覆盖其它所有点，这些点就必须保证都在以下黑色区域内：

黑色区域就是能互相形成团的坐标范围，在这个区域内所有的点都可以构成同一个团，所以我们只需在这个区域内填入尽量多的点使所有点的横纵坐标均不同。

这个区域的对角线长度是 k 且对角线是水平或竖直的，且在满足上述条件时最多放 k 个点，这是其中一种放置方式（图形位置略有移动，紫色“×”代表放置点）：

（放置方式多种多样，只要保证区域内点的横纵坐标均不相同即可。）

这样，将点每连续 k 个分为一组，像这样依次填入就可以了。

时间复杂度 O(N)。

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=45;
int ans[N],bel[N];

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,k; scanf("%d%d",&n,&k);
        int idx=0,part=0;
        for(int l=1;l<=n;l+=k)
        {
            part++;
            int r=min(n,l+k-1);
            int mid=l+r>>1;
            for(int i=mid+1;i<=r;i++)
                ans[i]=++idx,bel[i]=part;
            for(int i=l;i<=mid;i++)
                ans[i]=++idx,bel[i]=part;
        }
        for(int i=1;i<=n;i++)
            printf("%d ",ans[i]);
        putchar('\n');
        printf("%d\n",part);
        for(int i=1;i<=n;i++)
            printf("%d ",bel[i]);
        putchar('\n');
    }
    return 0;
}