codeforces 462div.2

A	A Compatible Pair standard input/output 1 s, 256 MB	x1916
B	A Prosperous Lot standard input/output 1 s, 256 MB	x3290
C	A Twisty Movement standard input/output 1 s, 256 MB	x527
D	A Determined Cleanup standard input/output 1 s, 256 MB	x191
E	A Colourful Prospect standard input/output 1 s, 256 MB	x10

-----------

A 934A

两个人T,B有n和m个灯笼,

要从每个人选出一个灯笼,放在一起,其权值为两者之积,注意权值可以为负数

B来选择两个灯笼组合,目的是组合结果最大

T要提前删去一个灯笼,目的是让组合结果最小,注意T是知道两人的灯笼情况的

求最后B的最大值

分析:

模拟,算出所有组合,找到最大组合中T的灯笼编号A,然后删掉所有包含A的灯笼组合

注意:需要开ll,删除的时候可以用vis数组,可以用-INF,可以用最小的灯笼组合-INF

推荐vis数组和最小组合-INF,如果用-INF必须足够小,建议-2e18或者-0x3f3f3f3f3f3f3f3f

----------

B 934B

题意:

给一个n,要求输出一个数字,阿拉伯数字中封闭区域的数量等于n,不存在输出-1;,要求答案小于等于18位

分析

题目说的很不清楚,任何组合都是存在的,只是很多无法在19位之前达到而已,具体应该是"能在18位之内达到就输出,否则输出-1"

首先8是2个,6,4,9,0,是一个,

然后注意0不能做前导数字,所以不用0,在4,6,9里任选就行

一开始如果大于36(18个8)就输出-1

然后贪心就行...

---------

C 934C

题意:

给一个1,2组成的数列,可以将一个区间翻转,求最大的不下降子序列

分析:

比赛时候最后几分钟有了思路,那一瞬间脑内进行了大概1e5次博弈,然后决定放弃...

复杂度n²,qls说其实是线性的算法,orz..

首先答案的子序列一定是111111....11222....2这样,注意有可能没有1或者没有2

递推过程,为了进行决策,先分析一波:

　　1.如果当前是以2结尾的未翻转子序列最长,后面的区间根本不需要翻转.对结果没有影响

　　2.如果当前是以1结尾的未翻转子序列最长,对于后面的所有翻转选择,

　　以1开头的子区间一定不是最优的,简单来说要反转肯定是从2开始,

　　而如果要反转,最终的子序列一定是以2结尾,而且第一个2是在反转的区间之内,不然反转毫无意义

所以最终的决策就是:

　1.不反转,这部分的最大值可以提前On预处理得到,用递推或者前缀和都可以得到

　　可以dp[x][maxn] 分别保存1结尾,2结尾+反转,也可以用一个值保存1结尾/2结尾不反转的最大值

　2,反转我们考虑子序列的3个部分,反转区间之前,反转区间,反转区间之后

　　　　反转区间之前,肯定是1结尾,所以直接由预处理的前缀和得到

　　　　反转区间之后,肯定是2开头2结尾,所以也是预处理前缀和得到

　　　　反转区间中,一定是1.....12....2这样,没有别的情况了

　　那具体怎么实现?

　　具体过程就是直接枚举反转区间里面,第一个2的位置

　　然后分别向前和向后枚举反转区间的起点p1和终点p2

　　转移的时候,利用前缀和计算,转移时间是O(1)

　　记第一个2的位置为P0,显然翻转之后,P0左边的2全部到P0右边了,右边的1到了左边

　　所以,P0左边的最长子序列是S1[1,p1-1]+S2[p1,p0],p0右边是S2[p2+1,n]+S1[p0,p2]

　　然后比较 1结尾不反转的最大值,以2结尾且反转的最大值(区间长度为1的时候就是不反转)

　　简单来说还是...On²的算法...

 1 /**********************
 2 *@Name:
 3 *
 4 *@Author: Nervending
 5 *@Describtion:
 6 *@DateTime:
 7 ***********************/
 8 #include <bits/stdc++.h>
 9 #define show(x) cout<<#x<<"="<<x<<endl
10 using namespace std;
11 const int maxn=1e5+10;
12 const int maxm=1e6+10;
13 const int INF=0x3f3f3f3f;
14 typedef long long ll;
15 typedef unsigned long long ull;
16 int casn,n,m,k;
17 int num[maxn];
18 int s1[maxn],s2[maxn];
19 int dp[4][maxn];
20 int ans;
21 int main() {
22 //#define test
23 #ifdef test
24     freopen("in.txt","r",stdin);
25     freopen("out.txt","w",stdout);
26 #endif
27 
28     cin>>n;
29     for(int i=1; i<=n; i++) {
30         cin>>num[i];
31         s1[i]=s1[i-1]+(num[i]==1);
32         s2[i]=s2[i-1]+(num[i]==2);
33     }
34     for(int i=1; i<=n; i++) {
35         if(num[i]==2) dp[1][i]=max(dp[1][i-1],dp[0][i-1])+1;
36         else {
37             dp[0][i]=dp[0][i-1]+1;
38             dp[1][i]=dp[1][i-1];
39         }
40     }
41     for(int i=1; i<=n; i++) {
42         ans=max(dp[0][i],max(ans,dp[1][i]));
43         if(num[i]!=2) continue;
44         for(int j=1; j<=i; j++) {
45             dp[2][i]=max(dp[2][i],s1[j-1]+(s2[i]-s2[j-1]));
46         }
47         for(int j=i; j<=n; j++) {
48             dp[3][i]=max(dp[3][i],s1[j]-s1[i]+(s2[n]-s2[j]));
49         }
50         ans=max(ans,dp[3][i]+dp[2][i]);
51     }
52     cout<<ans<<endl;
53 
54 #ifdef test
55     fclose(stdin);
56     fclose(stdout);
57     system("out.txt");
58 #endif
59     return 0;
60 }

View Code