Colors and Intervals

Colors and Intervals

$n\times k$ 个格子，编号从 $1$ 到 $n\times k$，染成 $n$ 种颜色，每种颜色恰好 $k$ 个。
构造 $n$ 个区间，第 $i$ 个区间 $[a_i,b_i]$ 满足

• $1\le a_i<b_i\le n\times k$
• 第 $a_i$ 个和第 $b_i$ 个格子的颜色都是 $i$。
• 每个格子被包含不超过 $\lceil \frac{n}{k-1}\rceil$ 次。

样例 #1

样例输入 #1

4 3
2 4 3 1 1 4 2 3 2 1 3 4

样例输出 #1

4 5
1 7
8 11
6 12

样例 #2

样例输入 #2

1 2
1 1

样例输出 #2

1 2

样例 #3

样例输入 #3

3 3
3 1 2 3 2 1 2 1 3

样例输出 #3

6 8
3 7
1 4

样例 #4

样例输入 #4

2 3
2 1 1 1 2 2

样例输出 #4

2 3
5 6

题目要求每个格子被包含不超过 $\lceil \frac{n}{k-1}\rceil$ ，那我们可以考虑每次求出 $k-1$ 个不连续的区间，总共求出 $n$ 个后，即可确保每段被包含的次数满足条件。

先来证明每次都能求出 $k-1$ 个区间：

可以用数学归纳法来证明。证明的命题为：对于 $k-1$ 种颜色(由于此时要取 $k-1$ 个区间，只与 $k-1$ 个颜色有关，其他颜色在其他轮的取区间中再考虑)，每种 $k$ 个，可以去到 $k-1$ 个区间。

• 当 $k=2$ 时，一种颜色，且有两个，显然成立。
• 假设 $k=k_1-1$ 时成立，对于 $k_1-2$ 种颜色，每种 $k_1-1$ 个，可以取到 $k_1-2$ 个区间。
• 当 $k=k_1$ 时，令第一个取到的区间为 $[l_1,r_1]$ ，可以证明 $[1,r_1-1]$ 中没有一种颜色出现两次（若有，则 $r_1$ 可以更小），此时一种颜色被取过后，不需要考虑这种颜色，所以此时颜色还剩 $k_1-2$ 种，每种 $k_1-1$ 或 $k_1$ 个，显然，每种颜色越多，越容易取到区间，所以可令每种还有 $k_1-1$ 个，要取 $k_1-2$ 个区间，所以命题成立。

考虑每次如何取区间，取到 $[l_1,r_1]$ 后，清空记录的前驱信息，从 $r_1+1$ 开始遍历，然后取区间。

注意题目要求每个区间要按颜色输出。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,k,cnt,pre[N],a[N*N];
bitset<N> vis;
pair<int,int> ans[N];
//ans记录答案，vis记录颜色是否取过
//cnt记录还能取几个区间
//pre记录每个颜色最后出现的位置
int main(){
    scanf("%d%d",&n,&k);cnt=n;
    for(int i=1;i<=n*k;i++) scanf("%d",&a[i]);
    while(cnt){
        for(int i=1;i<=n*k;i++){
            if(vis[a[i]]) continue;
            if(pre[a[i]]){
                ans[a[i]]={pre[a[i]],i};
                cnt--;
                vis[a[i]]=1;
                memset(pre,0,sizeof(pre));
            }
            else pre[a[i]]=i;
        }
        memset(pre,0,sizeof(pre));
    }
    for(int i=1;i<=n;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}