「题解」「CF1325B」CopyCopyCopyCopyCopy

Codeforces Round #628 (Div. 2) 一道比较简单的思考+动态规划+贪心+构造题。

题目链接:Codeforces 1325B


系列题解:
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem

题目

原题

题意简述

给出一个长度为 $n$ 的数列 $a_n$,求将数列复制 $n$ 遍后的 LIS(最长上升子序列)的长度。

输入有多组数据,数据组数用 $t$ 表示。

数据范围

$$1\leq \sum n\leq 10^5$$

$$1\leq a_i\leq 10^9$$

时空限制

见原题 pdf 文件。

题解

思路

考虑新数列 $b$($a$ 复制得到的)的值域与 $a$ 相同,而原题求 LIS 的长度,所以答案必定不超过 $n$。

再利用贪心的思想,如果 $a_i$ 在多个地方反复出现,那么肯定最先出现的 $a_i$ 转移得到的 LIS 最长。所以我们可以简单得到一个性质:有利用价值的 $a_i$ 必然各不相同。

于是我们得到了一个结论:答案必定不超过 $n-\text{cnt}$,其中 $\text{cnt}$ 为重复元素个数。

下面根据题意构造一种取法。

考虑每次选择去重后数列的第 $k$ 小,则

例如 $a_3<a_2<a_5<a_4<a_1$

$$a_1,a_2,{\color{red}a_3},a_4,a_5\\
a_1,{\color{red}a_2},a_3,a_4,a_5\\
a_1,a_2,a_3,a_4,{\color{red}a_5}\\
a_1,a_2,a_3,{\color{red}a_4},a_5\\
{\color{red}a_1},a_2,a_3,a_4,a_5
$$

发现答案就是去重后 $a$ 的元素个数。

代码

set 可以快速得出去重后 $a$ 的元素个数。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

int n;

int main(void){
    reg int T=read();
    while(T--){
        n=read();
        set<int> S;
        while(n--){
            static int x;
            x=read();
            S.insert(x);
        }
        printf("%d\n",(int)S.size()); //输出结果
    }
    return 0;
}