Colors and Intervals

Colors and Intervals

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

• 1 ≤ a i < b i ≤ n × k 1 \le a_i < b_i \le n \times k 1≤ai​<bi​≤n×k
• 第 a i a_i ai​ 个和第 b i b_i bi​ 个格子的颜色都是 i i i。
• 每个格子被包含不超过 ⌈ n k − 1 ⌉ \lceil \frac{n}{k-1} \rceil ⌈k−1n​⌉ 次。

样例 #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

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

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

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

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

考虑每次如何取区间，取到 [ l 1 , r 1 ] [l_1,r_1] [l1​,r1​] 后，清空记录的前驱信息，从 r 1 + 1 r_1+1 r1​+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;
}