CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

来源：懂视网责编：小采时间：2020-11-27 15:55:50

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css_WEB-ITnose:很不错的思维题，贪心题目大意：给你n个数，你需要找到一个最长的子序列，使得这个子序列的第4k-4k+3项为a,b,a,b的形式(从0标号)。牛逼的贪心啊，思维能力还是不行...... 思路倒是能想一点，但是代码写下来不行... 参考了 http://www.cnblo

推荐度：

点击下载本文 文档为doc格式

导读CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css_WEB-ITnose:很不错的思维题，贪心题目大意：给你n个数，你需要找到一个最长的子序列，使得这个子序列的第4k-4k+3项为a,b,a,b的形式(从0标号)。牛逼的贪心啊，思维能力还是不行...... 思路倒是能想一点，但是代码写下来不行... 参考了 http://www.cnblo

很不错的思维题，贪心

题目大意：给你n个数，你需要找到一个最长的子序列，使得这个子序列的第4k-4k+3项为a,b,a,b的形式(从0标号)。

牛逼的贪心啊，思维能力还是不行......

思路倒是能想一点，但是代码写下来不行...

参考了 http://www.cnblogs.com/shiina-mashiro/p/3981944.html

思路：

1、处理四个数相等的情况，直接输出四个数就行----其中记录数出现的次数用map，这样就不用离散化了（网上查的说map的查询时logn，离散化需要排序，nlogn，需要把大数映射成小数的时候岂不是不需要离散化了。。）

2、ABAB的情况

首先要想明白一点：两对数要满足形成ABAB那么必然是相邻的，最初没考虑到这点，以为要O(n^2)算法，不敢写了。

然后举出相邻两对数分析思路（a,b） (c,d)。

d>b显然，因为d是当前读到的数，a,b,c,是之前读到的数

然后根据c与a,b关系分以下情况：

(1)c

(2)b>c>=a 形成ABAB，记录之

(3)c>=b 不知道(a,b) (c,d) 该取哪个那么都存下先，等着下一个数读入作处理

//#pragma comment(linker, "/STACK:102400000,102400000")#include #include #include #include #include #include #include using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i>1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 500000+100;struct Node{ int l,r; int x;}nodes[MAXN];mappos,cnt;vectorb;int num[MAXN],n,top;void read(){ b.clear(); top=0; for(int i=1;i<=n;i++) scanf("%d",&num[i]);}void push(int x, int y){ b.push_back(x); b.push_back(y); b.push_back(x); b.push_back(y); cnt.clear(); pos.clear(); top=0;}int main(){ //IN("E.txt"); while(~scanf("%d",&n)) { read(); for(int i=1;i<=n;i++) {  int x=num[i];  if(cnt[x] != 0) cnt[x]++;  else cnt[x] = 1;  if(cnt[x] == 4){push(x,x);continue;}  if(pos[x] == 0){pos[x] = i; continue;}  //system("pause");  /*下面两行牛逼代码*/  int l=pos[x],r=i;  pos[x]=i;  while(top>0)  {  int bl=nodes[top-1].l, br=nodes[top-1].r, bx=nodes[top-1].x;  if(l>bl && l < br){push(bx,x);break;}  else if(l<=bl)top--;  else  {   nodes[top].l=l;   nodes[top].r=r;   nodes[top].x=x;   top++;   break;///  }  }  if(top == 0){nodes[0].l=l;nodes[0].r=r;nodes[0].x=x;top++;} } printf("%d\n",b.size()); if(b.size())printf("%d",b[0]); for(int i=1;i

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

推荐度：

点击下载本文 文档为doc格式

标签： and (2) codeforcesround#

热门焦点

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

CodeforcesRound#267(Div.2)EAlexandComplicatedTask_html/css

最新推荐

猜你喜欢

热门推荐