• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7034]Array

admin

11月 28, 2021

令$f(a)_{i}=min_{i<jle n,a_{i}=a_{j}}j$​​(特别的,若不存在$j$​​则令$f(a)_{i}=n+1$​​),则有以下性质:

1.对于$b_{i}$​​​​​​​,存在$a_{i}$​​​​​​​使得$f(a)=b$​​​​,当且仅当$i<b_{i}$​​​​且不为$n+1$的$b_{i}$互不相同(以下称这样的$b_{i}$​​​​​​​合法)

2.合法的$b_{i}$​可以唯一确定$a_{i}$​​(仅关心权值是否相同,即$a_{i}
e a’_{i}$当且仅当$exists i
e j,[a_{i}=a_{j}]
e [a’_{i}=a’_{j}]$)

通过这两个性质,问题即判定是否存在合法的$b_{i}$,使得其(唯一)对应的$a_{i}$满足题中的条件

而题中的条件从$b_{i}$​​​的角度来看,实际上是这样的:令$forall 1le i<n,B_{i+1}=max(B_{i},b_{i})$且$B_{1}$为最后一个之前没有出现过的数位置,也即$max_{1le ile n且forall 1le jle n,b_{j}
e i}i$

考虑从后往前贪心确定$b_{i}$​​(其中$1le i<n$​​),并维护以下两个集合:

1.$A_{0}$​​表示强制存在的元素(初始为$(B_{1},n]$​​​,若$b_{i}in A_{0}$则将其从$A_{0}$​中删除)

2.$A_{1}$表示允许存在的元素(初始为$[1,B_{1})cup{n+1}$,若$b_{i}in A_{1}$且$b_{i}le n$则将其从$A_{1}$中删除)

下面,再分类讨论:

1.若$B_{i}<B_{i+1}$​,则$b_{i}=B_{i+1}$​(注意判定$b_{i}>i$)

2.若$B_{i}=B_{i+1}$​,则要求$i<b_{i}le B_{i}$​,注意到该区间的左端点单调递增,因此用set维护$A_{0}$​和$A_{1}$​,分别不断删除最小值(若删除$A_{0}$​的最小值则无解)直至最小值$>i$​​

进一步的,再分类讨论:

(1)若两者的最小值都不能选择,则无解(还有$le B_{i}$​的限制)

(2)若只有一个最小值可以选择,显然选择该最小值即可

(3)若两个最小值都可以选择,设分别为$x$和$y$,将两者的都删除并将$max(x,y)$加入$A_{1}$​

关于(3)的解释:注意到右端点单调不下降,因此最终$min(x,y)$​能选择那么$max(x,y)$​一定能选择

若$x<y$​​显然可以这样贪心,若$x>y$​​即要求$x=max(x,y)$​​一定被选择,如果最终$x$​​被选择显然没有影响,若未被选择那么不妨将$b_{i}$​​修改为$x$​​​即可

(注意特判$B_{1}>n$的情况)

由此维护即可,时间复杂度为$o(nlog n)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 set<int>A0,A1;
 5 int t,n,B[N];
 6 void del(int x){
 7     if (x>n)return;
 8     if (A0.find(x)!=A0.end())A0.erase(x);
 9     else A1.erase(x);
10 }
11 int main(){
12     scanf("%d",&t);
13     while (t--){
14         scanf("%d",&n);
15         for(int i=1;i<=n;i++)scanf("%d",&B[i]);
16         bool flag=(B[1]>n);
17         for(int i=1;i<=n;i++)
18             if (B[i]<i){
19                 flag=1;
20                 break;
21             }
22         if (flag){
23             printf("NO
");
24             continue;
25         }
26         A0.clear(),A1.clear();
27         for(int i=B[1]+1;i<=n;i++)A0.insert(i);
28         for(int i=1;i<B[1];i++)A1.insert(i);
29         A1.insert(n+1);
30         for(int i=1;i<n;i++){
31             if (B[i]<B[i+1])del(B[i+1]);
32             else{
33                 if ((!A0.empty())&&((*A0.begin())<=i)){
34                     flag=1;
35                     break;
36                 }
37                 while ((*A1.begin())<=i)A1.erase(A1.begin());
38                 int x=0,y=(*A1.begin());
39                 if ((!A0.empty())&&((*A0.begin())<=B[i]))x=(*A0.begin());
40                 if (y>B[i])y=0;
41                 if ((!x)&&(!y)){
42                     flag=1;
43                     break;
44                 }
45                 if (x)del(x);
46                 if (y)del(y);
47                 if ((x)&&(y))A1.insert(max(x,y));
48             }
49         }
50         if (!A0.empty())flag=1;
51         if (flag)printf("NO
");
52         else printf("YES
");
53     }
54     return 0;
55 } 

View Code

《[hdu7034]Array》有一个想法
  1. Howdy! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my website to rank for some targeted keywords but I’m not seeing
    very good success. If you know of any please share.
    Thank you! I saw similar art here: Hitman.agency

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注