首页 > 代码库 > bzoj1293题解

bzoj1293题解

2024-09-01 01:31:42   217人阅读

【题意分析】

给你一条有n个点的数轴，每个点属于一个种类，总共有k个种类。求一段最短的线段，使对于每个种类，这段线段上有至少一个点属于它。

【算法分析】

1.对于50%的数据，N≤10000

对于每一个从左到右枚举的l，从左到右枚举r>=l并不断加入r号彩珠，直到满足条件为止，更新答案。

时间复杂度O(n2)。

2.对于80%的数据，N≤800000

预处理k个种类的前缀和。对于每一个从左到右枚举的l，进行O(klog2n)的二分询问。

时间复杂度O(nklog2n)

3.对于100%的数据，1≤N≤1000000，1≤K≤60，0≤Ti<231

动态维护一个大小为k的离散数组，s[i]表示当前状态下第i个种类的彩珠数。深入考虑算法一，我们发现对于每一个从左到右枚举的l，r是单调不减的。于是固定l时，不断将r号彩珠加入s并右移指针r，直到满足条件为止，更新答案；当l自增时，在s中弹出原l号彩珠，不重置r。这样扫描的时间就是线性的了。

时间复杂度O(nk)

【参考代码】

 1 #pragma GCC optimize(2)
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <functional>
 5 #define REP(i,low,high) for(register int i=(low);i<=(high);i++)
 6 using namespace std;
 7 
 8 //ex_cmp {
 9 template<typename T,class Compare> inline bool getcmp(T &target,const T &pattern,Compare comp)
10 {
11     return comp(pattern,target)?target=pattern,1:0;
12 }
13 //} ex_cmp
14 
15 struct beat
16 {
17     int kind,pos; void input(const int &K) {kind=K,scanf("%d",&pos);}
18     bool operator<(const beat &another)const{return pos<another.pos;}
19 }beats[1000010];
20 int s[70]={0}; static int n,k;
21 inline bool cannot() {REP(i,1,k) if(!s[i]) return 1; return 0;}
22 int main()
23 {
24     scanf("%d%d",&n,&k); int tot=0; REP(i,1,k)
25     {
26         int cnt; for(scanf("%d",&cnt);cnt--;) tot++,beats[tot].input(i);
27     }
28     sort(beats+1,beats+n+1),s[beats[1].kind]=1; int j=1;
29     for(;j<=n&&cannot();s[beats[j].kind]++) j++; int ans=beats[j].pos-beats[1].pos;
30     REP(i,2,n)
31     {
32         s[beats[i-1].kind]--; for(;j<=n&&cannot();s[beats[j].kind]++) j++;
33         if(j>n) break; getcmp(ans,beats[j].pos-beats[i].pos,less<int>());
34     }
35     return printf("%d\n",ans),0;
36 }

 

bzoj1293题解


联系
我们