Codeforces Round #267 (Div. 2) E Alex and Complicated Task_html/css_WEB-ITnose
程序员文章站
2022-05-04 08:17:16
...
很不错的思维题,贪心
题目大意:给你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关系分以下情况:
推荐阅读
-
Codeforces Round #FF (Div. 2)E(线段树成段更新)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #280 (Div. 2) 解题报告 A.B.C.D.E._html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E题:Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #281 (Div. 2)E(数学)_html/css_WEB-ITnose
-
Codeforces Round #267 (Div. 2) E Alex and Complicated Task_html/css_WEB-ITnose
-
Codeforces Round #280 (Div. 2 A,B,C,D,E)_html/css_WEB-ITnose
-
Codeforces Round #267 (Div. 2) E Alex and Complicated Task_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E题:Riding in a Lift(DP)_html/css_WEB-ITnose