首页 > 代码库 > Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

题目链接:Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

题意:

给你n个数,现在让你选一些区间出来,对于每个区间中的每一种数,全部都要出现在这个区间。

每个区间的价值为该区间不同的数的异或值,现在问你这n个数最大的价值是多少。

题解:

比赛的时间直接就想到了做法,不过在选取合法区间的时候,细节上出了点小问题。

然后一直wa到怀疑人生。太菜了。

首先,先将合法的区间选取出来。

对于这些区间,按照左端点排序,

然后对于选出来的区间做一个dp,这个dp类似最长上升子序列。

技术分享
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 typedef long long ll;
 5 typedef pair<int,int>P;
 6 const int N=1e5+7;
 7 
 8 int n,a[N],ed,vis[N],dp[N];
 9 P LR[N];
10 set<int>S;
11 set<int>::iterator it;
12 struct Node
13 {
14     int l,r,val;
15     Node(int a=0,int b=0,int c=0):l(a),r(b),val(c){}
16     bool operator <(const Node &b)const{return l<b.l;}
17 }seg[N];
18 set<Node>tmp;
19 set<Node>::iterator iit;
20 
21 int main()
22 {
23     scanf("%d",&n);
24     F(i,1,n)scanf("%d",a+i);
25     F(i,1,n)//处理出每一种数的区间
26     {
27         if(vis[a[i]]==0)
28         {
29             vis[a[i]]=1;
30             int j;
31             for(j=n;j>0;j--)if(a[j]==a[i])break;
32             LR[a[i]]=P(i,j);
33         }
34     }
35     F(i,1,n)
36     {
37         if(vis[a[i]]<2)
38         {
39             vis[a[i]]=2;
40             int L=LR[a[i]].first,R=LR[a[i]].second;
41             while(1)//将该区间的每一种数全部包含
42             {
43                 int flag=1;
44                 F(ii,L,R)
45                 {
46                     if(LR[a[ii]].first<L)
47                     {
48                         L=LR[a[ii]].first;
49                         if(LR[a[ii]].second>R)R=LR[a[ii]].second;
50                         flag=0;
51                         break;
52                     }
53                     if(LR[a[ii]].second>R)
54                     {
55                         R=LR[a[ii]].second;
56                         flag=0;
57                         break;
58                     }
59                 }
60                 if(flag)break;
61             }
62             S.clear();
63             F(ii,L,R)S.insert(a[ii]);
64             int val=0;
65             for(it=S.begin();it!=S.end();it++)val^=*it;
66             tmp.insert(Node(L,R,val));
67         }
68     }
69     for(iit=tmp.begin();iit!=tmp.end();iit++)seg[++ed]=*iit;
70     F(i,1,ed)
71     {
72         dp[i]=seg[i].val;
73         F(j,1,i-1)
74             if(seg[j].r<seg[i].l)
75                 dp[i]=max(dp[i],dp[j]+seg[i].val);
76     }
77     int mx=0;
78     F(i,1,ed)mx=max(mx,dp[i]);
79     printf("%d\n",mx);
80     return 0;
81 }
View Code

 

Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip