【训练】算法竞赛进阶指南-1基本数据结构21题

本处难度分档以个人实力为参照系
难度1:半小时内想出,半小时内ac
难度2:半小时想不出,看题解,服气
难度3:半小时想不出,看题解,ac后依然觉得难度很大

0x10 基本数据结构

题目

1 hdu4699 Editor

7.3 难度1

请先思考后再展开

要特判非法情况,这个是题目没有说明清楚的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=1100000;
int mymax(int x,int y) {return x>y?x:y;}
int a[MAXN],sum[MAXN],mx[MAXN],top;
void push(int d)
{
a[++top]=d;
sum[top]=sum[top-1]+d;
mx[top]=mymax(mx[top-1],sum[top]);
}
void pop()
{
top--;
}
int ign[MAXN],igntp;//ignore元素栈
char s[10];
int main()
{
int Q;
while(scanf("%d",&Q)!=EOF)
{
top=0;sum[0]=0;
mx[0]=-0x3f3f3f3f;//debug
igntp=0;
while(Q--)
{
scanf("%s",s);
if(s[0]=='I')
{
int d;scanf("%d",&d);
push(d);
}
if(s[0]=='D') pop();
if(s[0]=='L') if(top>0) ign[++igntp]=a[top--];
if(s[0]=='R') if(igntp>0) push(ign[igntp--]);
if(s[0]=='Q')
{
int k;scanf("%d",&k);
printf("%d\n",mx[k]);
}
}
}
}

2 poj2559 Largest Rectangle in a Histogram

7.3 难度2

请先思考后再展开

看到提示用单调栈,大概是想通了
但发现我只会暴力地确定右端点后,枚举左端点来统计答案

看了发题解,发现大概思路差不多,主要就是统计答案的方法
如果从右端点开始考虑,其左端点是不定的
但如果稍微换个角度,利用一下单调性,可以发现:
对于一个左端点,其最优的右端点只有一个,那就是在其存在时期内最后那个

所谓存在时期,就是它从进入到弹出期间
我们可以考虑在它被弹出的时候再统计答案,而这时候,新矩形一定比它小
所以从它到【第一个被当前新矩形弹出的矩形】之间,就是当前高度下的最优宽度
所以边弹出,边累加宽度并统计答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=110000;
typedef long long ll;
ll mymax(ll a,ll b) {return a>b?a:b;}
struct Nod
{
int h,w;
}a[MAXN];//单调递增
int h[MAXN];
int main()
{
while(1)
{
int n;scanf("%d",&n);if(n==0) break;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
h[++n]=0;
int top=0;ll ans=0;
for(int i=1;i<=n;i++)
{
if(a[top].h<=h[i])
{
a[++top].h=h[i];a[top].w=1;
}
else
{
int wid=0;
while(top>0 and a[top].h>h[i])
{
wid+=a[top].w;
ans=mymax(ans,ll(a[top].h)*wid);
top--;
}
a[++top].h=h[i];a[top].w=wid+1;//debug 漏了
}
}
printf("%lld\n",ans);
}
}

3 poj2259 hdu1387 Team Queue

7.3 难度2

请先思考后再展开

偷懒,用了链表
然后看题,一是会有0,完全没注意就用了0表示空
二是多一个空行,读题时看到,写题时忘记
回想起不久前中考时也有这个毛病
或许应该写下这种注意点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=1100;
int ps[MAXN];//位置
struct Nod
{
int a;//所属小组
int nxt;
}p[MAXN*MAXN];
char s[20];
int main()
{
int cas=0;
while(1)
{
memset(ps,-1,sizeof ps);
//debug 没注意到正常编号中有0,所以空应该用-1表示
int n;scanf("%d",&n);if(n==0) break;
for(int i=1;i<=n;i++)
{
int c;scanf("%d",&c);
while(c--)
{
int t;scanf("%d",&t);
p[t].a=i;p[t].nxt=-1;
}
}
int qst=-1,qed=-1;//队尾
printf("Scenario #%d\n",++cas);
while(1)
{
scanf("%s",s);
if(s[0]=='E')
{
int t;scanf("%d",&t);
int k=ps[p[t].a];
if(k>-1)
{
p[t].nxt=p[k].nxt;
p[k].nxt=t;
if(qed==k) qed=t;
}
else
{
if(qst==-1) qst=t;
if(qed>-1) p[qed].nxt=t;
qed=t;
}
ps[p[t].a]=t;
}
if(s[0]=='D')
{
printf("%d\n",qst);
if(qst==qed) qed=-1;
if(qst==ps[p[qst].a]) ps[p[qst].a]=-1;
qst=p[qst].nxt;
}
if(s[0]=='S') break;
}
putchar('\n');//debug
}
}

4 bzoj2457 双端队列

7.3 难度3

请先思考后再展开

思考难度很大
因为 要按照顺序处理数字,而又涉及大小关系,直接线性处理是不可能的
考虑把数列排序一波(也可以从数据范围上观察得出)
然后记录下标
思考能够放在同一个双端队列里,需要满足的特性

结论:
在同一个双端队列,对于编号最前的,
比它大的要在它后面出现,比它小的也要在后面出现,
而且与它的差越大,与它的距离差就应该越大
如果用图像来表示,把排序后的数列,排名为x,原坐标为y,
则必须是一个单谷图像

所以,大致上的流程就是:排序, 按从小到大处理数列,记录递增或递减趋势,记录有多少个图像
但还有个细节:对于排名也就是大小一样的数,它们的原坐标顺序是可以任意排列的
为了尽量减少单谷数量,对于大小相同的一段,内部在单调时最优。
所以只要记录每一段的最大和最小值,任意变形来贪心地连接起来就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=210000;
struct Nod
{
int d,p;
}a[MAXN];
bool cmp(Nod a,Nod b) {return a.d<b.d or (a.d==b.d and a.p<b.p);}
int nx=0,mi[MAXN],mx[MAXN];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].d),a[i].p=i;
sort(a+1,a+n+1,cmp);
mi[1]=1;
for(int i=1;i<=n;i++)
if(i==1 or a[i-1].d!=a[i].d)
{
mx[nx]=a[i-1].p;
mi[++nx]=a[i].p;
}
mx[nx]=n;
bool up=1;
int ans=0,ed=0x3f3f3f3f;
for(int i=1;i<=nx;i++)
{
if(up)
{
if(ed<mi[i]) ed=mx[i];
else up=0,ans++,ed=mi[i];
}
else//down
{
if(ed>mx[i]) ed=mi[i];
else up=1,ed=mx[i];
}
}
printf("%d",ans);
}

5 1201 最大子序和

7.3 难度1

请先思考后再展开

这道题初看像是有限制条件的最大子段和,然鹅方法完全不一样
首先,因为有长度限制,在枚举右端点的过程中,需要把左端点向右移
那么因为和可以表示为sum[i]-sum[j-1],i-j+1<=m
因为我们的右端点是固定的,所以只要搞出一个符合条件中最小的sum[j-1]即可

稍微提醒一下,一定要明确是sum[j-1]而不是sum[j],逻辑差别很大
然后就wa了多次……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=310000;
const int INF=0x3f3f3f3f;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int sum[MAXN];
struct Nod
{
int d;
int p;
}a[MAXN];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
int ans=0;
int l=1,r=1;
a[1].d=0,a[1].p=0;
//debug,sum[i]-sum[j-1],重点是【j-1】而不是【j】
for(int i=1;i<=n;i++)
{
while(l<=r and i-a[l].p>m) l++;//debug,i-j+1<=m,i-(j-1)<=m
ans=mymax(ans,sum[i]-sum[a[l].p]);
while(l<=r and a[r].d>=sum[i]) r--;
a[++r].d=sum[i];a[r].p=i;
}
printf("%d",ans);
}

6 poj3349 Snowflake Snow Snowflakes

7.4 难度2

请先思考后再展开

这道题是真的毒瘤
本来用hash判重,然后丢到set里面
结果不是hash被卡wa就是stl被卡tle

总之,不得不用hash表,第一次写这玩意,以前只会理论
各种tle,抄了很多书上的代码,改了改类型、模数,才卡了过去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int now[6];
const int Mod=100003;
int gethash()
{
int has=1;
for(int i=0;i<=5;i++) if(now[i]!=0) has=( ll(has)*now[i] )%Mod;
//debug,爆int
for(int i=0;i<=5;i++) has=(has+now[i])%Mod;
return has;
}
struct HashTable
{
int a[6];
int nxt;
HashTable()
{
nxt=0;
}
}a[MAXN];
int head[Mod+10];
int id=0;
bool equal(int t,int op)
{
for(int i=0;i<=5;i++)
for(int j=0;j<=5;j++)
{
int s;
for(s=0;s<=5;s++) if(a[t].a[(i+s+6)%6]!=now[(j+s*op+6)%6]) break;
if(s==6) return 1;
}
return 0;
}
int main()
{
int n;scanf("%d",&n);
while(n--)
{
for(int i=0;i<=5;i++) scanf("%d",&now[i]);
int has=gethash();
for(int t=head[has];t>0;t=a[t].nxt)
if(equal(t,1) or equal(t,-1))
{
printf("Twin snowflakes found.");
return 0;
}
a[++id].nxt=head[has];
memcpy(a[id].a,now,sizeof now);
head[has]=id;
}
printf("No two snowflakes are alike.");
}

7 1401 兔子与兔子

7.4 难度1

请先思考后再展开

裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
ull has[MAXN];
const ull Base=13331;
ull bs[MAXN];
ull gethash(int l,int r)
{
return has[r]-has[l-1]*bs[r-l+1];
}
char s[MAXN];
int main()
{
scanf("%s",s+1);
int len=strlen(s+1);
bs[0]=1;
for(int i=1;i<=len;i++)
{
bs[i]=bs[i-1]*Base;
has[i]=has[i-1]*Base+s[i];
}
int m;scanf("%d",&m);
while(m--)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
if(gethash(a,b)==gethash(c,d)) printf("Yes\n");
else printf("No\n");
}
}

8 poj1961 Period

7.4 难度1

请先思考后再展开

经典题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
char s[MAXN];
int nxt[MAXN];
void prekmp(int len)
{
int j=0;nxt[1]=0;
for(int i=2;i<=len;i++)//debug,从2开始,否则不符合定义
{
while(j>0 and s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) j++;
nxt[i]=j;
}
}
int main()
{
int cas=0;
while(1)
{
int len;scanf("%d",&len);if(len==0) break;
scanf("%s",s+1);
prekmp(len);
printf("Test case #%d\n",++cas);
for(int i=1;i<=len;i++)
if(i-nxt[i]>0 and (i%(i-nxt[i]))==0 and nxt[i]>0)
printf("%d %d\n",i,i/(i-nxt[i]));
putchar('\n');//debug
}
}

9 1602 The XOR Largest Pair

7.4 难度1

请先思考后再展开

居然对了!
虽然不是1a,因为有个地方,得到的是int,就re了
思路:
把所有数转化成二进制,用类似字典树的结构存储
对于i,先统计答案,i是其中一个,贪心地找另一个
具体来说,贪心地从高位开始,尽量往反方向走,累计答案
当然是在不行还是要走正方向
统计完后,把这个串加入到字典树中供后人用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=4000000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int bin[40];
struct Trie
{
int son[2];
}p[MAXN];
int id=0;
void clear(int x)
{
p[x].son[0]=p[x].son[1]=-1;
}
int now[40];
void add()
{
int x=0;
for(int i=30;i>=0;i--)
{
if(p[x].son[now[i]]<0)
{
p[x].son[now[i]]=++id;
clear(id);
}
x=p[x].son[now[i]];
}
}
int solve()
{
int x=0,ans=0;
for(int i=30;i>=0;i--)
{
int nx=p[x].son[ 1-now[i] ];
if(nx>0)
{
ans+=bin[i];
x=nx;
}
else if(p[x].son[now[i]]>0) x=p[x].son[now[i]];
else break;
}
return ans;
}
int main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]*2;
int n;scanf("%d",&n);
clear(0);
int ans=0;
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
for(int j=0;j<=30;j++) now[j]=( t&bin[j] )>0;//debug 原本是int
if(i>1) ans=mymax(ans,solve());
add();
}
printf("%d",ans);
}

10 poj3764 The xor-longest Path

7.4 难度2

请先思考后再展开

想了一个小时,看到题解前半段的那一刻,难受的一匹
原来和上一题是一样的!

x到y路径上xor和=x到根xor和 xor y到根xor和
这基于同一个数xor自己,得到0,而0 xor 任何数=任何数

然鹅,自己在思考的时候,却想着还要xor lca(x,y)到根
因为感觉那部分只出现了一次,神tm自己想再补上一次……
感觉这给我的教训是要多动笔写下来,这样不容易错
我才不会说这是因为笔被我整天乱扔,摔断墨了……
自作自受吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int bin[40];
struct Trie
{
int son[2];
}tr[4000000];
int id=0;
void clear(int x)
{
tr[x].son[0]=tr[x].son[1]=-1;
}
int now[40];
void add()
{
int x=0;
for(int i=30;i>=0;i--)
{
if(tr[x].son[now[i]]<0)
{
tr[x].son[now[i]]=++id;
clear(id);
}
x=tr[x].son[now[i]];
}
}
int solve()
{
int x=0,ans=0;
for(int i=30;i>=0;i--)
{
int nx=tr[x].son[ 1-now[i] ];
if(nx>0) ans+=bin[i],x=nx;
else if(tr[x].son[now[i]]>0) x=tr[x].son[now[i]];
else break;
}
return ans;
}
struct Nod
{
int hou;
int dis;
}p[MAXN];
struct Edge
{
int y,c,g;
}e[MAXN*2];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
void dfs(int x,int fa)
{
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
p[y].dis=p[x].dis xor e[k].c;
dfs(y,x);
}
}
int main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]*2;
int n;
while(scanf("%d",&n)!=EOF)
{
p[1].dis=0;ln=0;
for(int i=1;i<=n;i++) p[i].hou=0;
for(int i=1;i<=n-1;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
x++;y++;
ins(x,y,c);ins(y,x,c);
}
dfs(1,0);
id=0;clear(0);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=30;j++) now[j]=( p[i].dis&bin[j] )>0;
if(i>1) ans=mymax(ans,solve());
add();
}
printf("%d\n",ans);
}
}

11 poj1456 Supermarket

7.4 难度3

请先思考后再展开

一开始写了个错误的贪心:
直接按照过期排序,第二关键字是价值
但这样就考虑不了【过期冲突,价值极大】的情况

先明确:如果现在是第t天,则应卖出能卖出的前t大
有一个套路,能够给限定数量的局部贪心后悔药:
维护一个大小为t的堆,堆顶是最不优秀的元素,尝试替换来修正原方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=11000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
int p,d;
friend bool operator > (Nod a,Nod b) {return a.p>b.p;}
}a[MAXN];
bool cmp(Nod a,Nod b) { return a.d<b.d; }
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].p,&a[i].d);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
int siz=q.size();
if(siz<a[i].d) q.push(a[i]);
else if(a[i].p>q.top().p) q.pop(),q.push(a[i]);
}
int ans=0;
while(!q.empty()) ans+=q.top().p,q.pop();
printf("%d\n",ans);
}
}

12 poj2442 Sequence

7.5 难度3

请先思考后再展开

1.
既然跟大小有关,先把每个序列排好序,确认了最小答案

2.
因为直接枚举方案会超时
这是因为产生了很多因为过大而无用的状态

这就用到了一个新套路(又被akc轻松想出)
把所有最小值组成一个方案,放进堆里面
通过堆进行决策的同时,基于堆的最优性进行拓展
因为我们已经排好了序,拓展只是某个指针的前移
此时复杂度是$O( n^2 \times log(nm) )$
濒临超时

3.
然鹅,上述方案有个致命的问题
两个不同的状态可能拓展出相同的状态
感觉强行hash判重也可以,不过没必要

4.
有一个不那么好想的方法(或许利用了答案要求的数量和序列长度相同这个特性)
先把两个序列合并,把得到的前n个作为一个新的序列
然后像同余方程组那样逐个合并。
而且,由于每次只处理两个数列,可以用bool判重解决上面的问题

复杂度$O( m \times n \times 2 \times log(n) )$,飞快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=2100;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int n;
int a0[MAXN],a1[MAXN];
struct Nod
{
int i,j;
Nod(int x=0,int y=0) {i=x,j=y;}
friend bool operator > (Nod x,Nod y)
{
return a0[x.i]+a1[x.j]>a0[y.i]+a1[y.j];
}
};
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
bool v[MAXN][MAXN];
void add(int i,int j)
{
if(!v[i][j])
{
v[i][j]=1;
q.push( Nod(i,j) );
}
}
int tmp[MAXN];
void merg()
{
memset(v,0,sizeof v);//debug 每次merg前,而不是每组数据
while(!q.empty()) q.pop();
add(1,1);
for(int i=1;i<=n;i++)
{
Nod tp=q.top();q.pop();
tmp[i]=a0[tp.i]+a1[tp.j];
if(tp.i+1<=n) add(tp.i+1,tp.j);
if(tp.j+1<=n) add(tp.i,tp.j+1);
}
memcpy(a0,tmp,sizeof tmp);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int m;scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) scanf("%d",&a0[i]);
sort(a0+1,a0+n+1);
for(int t=2;t<=m;t++)
{
for(int i=1;i<=n;i++) scanf("%d",&a1[i]);
sort(a1+1,a1+n+1);
merg();
}
for(int i=1;i<=n;i++) printf("%d ",a0[i]);
putchar('\n');
}
}

13 CTSC2007 数据备份 & bzoj2151 种树

7.5 难度2

请先思考后再展开

这道题一年多以前做过,当时并没有blog
然后我yy着就和远古时期的我产生了共鸣,回忆起了一个细节:在堆中进行可后悔决策
然鹅完全没有思路
虽然顺便又把一个关键性质想到了:不会有线路的重叠,故只会和旁边产生关系

如果想到这里,想必大佬们都能快速的想到怎么做
然后我还是蒙逼状态,尽管我又把一个关键的图画了出来:四个点之间的连线x-1、x、x+1

是不是觉得我灰常无可救药?都已经把所有前提想到了,还是不会……

事实上:
有一种贪心策略:每次找最短的一条边,然后把它两边的删除
但这样其实很容易举出反例,例如4,2,4,100000

怎么办?引入后悔机制,不要急着排除两边
相反,在堆种放入一个c[x-1]+c[x+1]-c[x]
也就是说,如果我再选择了一次,那么我就是花费两条边,把x-1和x+1建好了
当然如果没有再被拿出,意味着没必要

细细思考,不难发现这样能同时满足互斥的两种状态决策
总而言之,听起来灰常有道理,只不过不好想到【据说是一种模型,靠积累】

还有一些细节

  1. 如果我们放进去的被拿出来,意味着建两条边,
    那还是要找左右两侧的更远的边,在堆中去除
    因为要延长伸展,用链表比较方便
  2. 去除可以用可删堆,但还要确保编号相同;用set就灰常不方便了,毕竟是结构体;
    还有种方法是判断其是否和外界数据不同,表示其过时,直接弹出
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #include<vector>
    #include<map>
    #include<set>
    using namespace std;
    const int MAXN=110000;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    typedef unsigned long long ull;
    int mymax(int x,int y) {return x>y?x:y;}
    int mymin(int x,int y) {return x<y?x:y;}
    struct Nod
    {
    int d,x;
    Nod(int a=0,int b=0) { d=a,x=b; }
    friend bool operator > (Nod a,Nod b) { return a.d>b.d; }
    };
    priority_queue< Nod,vector<Nod>,greater<Nod> > q;
    int s[MAXN];
    int l[MAXN],r[MAXN];
    int main()
    {
    int n,k;scanf("%d%d",&n,&k);
    int lst=0;
    for(int i=1;i<=n;i++)
    {
    int t;scanf("%d",&t);
    s[i]=t-lst;lst=t;
    if(i>1) q.push( Nod(s[i],i) );
    l[i]=i-1;r[i]=i+1;
    }
    //边界哨兵节点
    l[2]=1;s[1]=INF;
    r[n]=n+1;s[n+1]=INF;
    int ans=0;
    while(k--)
    {
    while(q.top().d!=s[q.top().x]) q.pop();//old
    Nod now=q.top();q.pop();
    int x=now.x,left=l[x],right=r[x];
    //后悔药
    s[x]=s[left]+s[right]-s[x];//debug 忘记更新s[x],直接塞进去了
    q.push( Nod(s[x],x) );
    //删除左右
    l[x]=l[left];r[l[left]]=x;
    r[x]=r[right];l[r[right]]=x;
    s[left]=INF;s[right]=INF;
    //统计答案
    ans+=now.d;
    }
    printf("%d",ans);
    }

14 NOI2015 荷马史诗

bzoj4198 luogu2168 uoj130 loj2132
7.5 难度2

请先思考后再展开

入门好题,教程:【OI之路】09经典问题-3哈夫曼树

唯一不同的是第二问,要求最大深度最小
构造哈夫曼树的时候,我们只是保证了带权路径长度和最小
但当我们面对两个相同权值,但是一个下面的最大深度大的和小的
这个时候,如果先合并下面的最大深度大的,答案会更大
而先合并小的,就能把后面的机会留下了,从而减小了树的最大深度

具体做法很简单,重载堆的比较函数时,
把下面的最大深度作为第二关键字,优先小的就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
ll w;
int c;//最大深度
Nod(ll a=0,int b=0) {w=a,c=b;}
friend bool operator > (Nod a,Nod b)
{
return a.w>b.w or (a.w==b.w and a.c>b.c);
}
};
priority_queue< Nod,vector<Nod>,greater<Nod> > q;
int main()
{
int n,k;scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
ll t;scanf("%lld",&t);
q.push( Nod(t,0) );
}
while( (int(q.size())-1)%(k-1)!=0 ) q.push( Nod(0,0) );
ll ans=0;
while(1)
{
ll tot=0;
int mxdep=0;
for(int i=1;i<=k;i++)
{
Nod now=q.top();q.pop();
mxdep=mymax(mxdep,now.c);
tot+=now.w;
}
ans+=tot;
if(q.empty())
{
printf("%lld\n%d",ans,mxdep+1);
break;
}
q.push( Nod(tot,mxdep+1) );
}
}

0x18 基本数据结构练习

题目

15 1801 括号画家

7.6 难度1

请先思考后再展开

考细节……
应自己构造数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
char s[MAXN];
int sta[MAXN],top=0;
int main()
{
scanf("%s",s+1);int len=strlen(s+1);
int ans=0;
int lst=0;
for(int i=1;i<=len;i++)
{
int now;
if(s[i]=='{') now=0;
if(s[i]=='}') now=5;
if(s[i]=='[') now=1;
if(s[i]==']') now=4;
if(s[i]=='(') now=2;
if(s[i]==')') now=3;
if(now<=2) sta[++top]=now;
else
{
if(top>0 and sta[top]+now==5) lst+=2,top--;
else ans=mymax(ans,lst),lst=0,sta[++top]=now;
}
}
printf("%d",ans=mymax(ans,lst));
}

16 poj1964 City Game

7.6 难度2

请先思考后再展开

骚操作
预处理出每个点最大向上高度
然后看作是二维的Largest Rectangle in a Histogram……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
int h,w;
Nod(int a=0,int b=0) {h=a,w=b;}
}a[MAXN];
int up[MAXN][MAXN];
char c[10];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%s",c);
up[i][j]=(c[0]=='F')?1+up[i-1][j]:0;
}
up[i][m+1]=0;
int top=1;a[1]=Nod(up[i][1],1);
for(int j=2;j<=m+1;j++)
{
int wid=0;
while(top>0 and a[top].h>=up[i][j])//debug 判top>0
{
wid+=a[top].w;
ans=mymax(ans,a[top--].h*wid);
}
a[++top]=Nod(up[i][j],wid+1);
}
}
printf("%d\n",3*ans);
}
}

17 NOI1999 内存分配

7.6 难度2

请先思考后再展开

打了一大半
很多细节问题
先放着代码吧
复杂度估计$O(n \sqrt n)$(如果块状链表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=11000;
const int INF=0x3f3f3f3f;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
struct Lb
{
int st,ed;//内存
//应该改成ln形式
Lb(int a=0,int b=0) {st=a,ed=b;}
}a[MAXN*20];
int tou,ll[MAXN*20],rr[MAXN*20];
int id=0;
struct Task
{
int st,ln;//内存
int tst,ti;//时间
friend bool operator > (Task a,Task b) {return a.tst+a.ti>b.tst+b.ti;}
};
priority_queue< Task,vector<Task>,greater<Task> > q;
Task fail[MAXN];int fl=1,fr=0;
int ans=0;
void pop_update()
{
Task now=q.top();q.pop();
int nowed=now.st+now.ln-1;//内存
ans=now.tst+now.ti-1;
int x=tou;
while(x>0)
{
int rx=rr[x],rrx=rr[rx];
int ma=0;
if(x==tou)
{
if(nowed+1==a[x].st)//debug 特判新的tou
{
a[x].st=now.st;
ma=x;
}
else if(nowed<a[x].st)
{
tou=++id;//debug 原id++
rr[tou]=x;ll[x]=tou;
a[tou].st=now.st;a[tou].ed=now.st+now.ln-1;//debug 漏了
ma=tou;
}
}
else if(rx==0)
{
if(a[x].ed+1==now.st)
{
a[x].ed=nowed;
ma=x;
}
else
{
a[++id].st=now.st;a[id].ed=nowed;
rr[x]=id;ll[id]=x;
ma=id;
}
}
else
{
if(a[x].ed+1==now.st and nowed+1==a[rx].st)//二合一
{
a[x].ed=a[rx].ed;ll[x]=rrx;ll[rrx]=x;
ma=x;
}
else if(a[x].ed+1==now.st)
{
a[x].ed=nowed;
ma=x;
}
else if(nowed+1==a[rx].st)
{
a[rx].st=now.st;
ma=rx;
}
else if(a[x].ed<now.st and nowed<a[rx].st)
{
a[++id].st=now.st;a[id].ed=nowed;
rr[x]=id;ll[id]=x;ll[rx]=id;rr[id]=rx;
ma=id;
}
}
if(ma>0)
{
while(fl<=fr and a[ma].ed-a[ma].st+1>=fail[fl].ln)//debug 写成<=
{
fail[fl].st=a[ma].st;fail[fl].tst=now.tst+now.ti-1+1;//debug
q.push(fail[fl]);a[ma].st+=fail[fl++].ln;
}
if(a[ma].st>a[ma].ed)//空
{
if(ma==tou)
{
}
rr[ll[ma]]=rr[ma];ll[rr[ma]]=ll[ma];
if(ma==tou and rr[tou]>0) tou=rr[ma];//debug 特判tou,避免环
}
return;
}
x=rx;
}
}
void try_push(int tst,int ln,int ti)
{
int x=tou;
while( x>0 )
{
int lx=ll[x],rx=rr[x];
if( a[x].ed-a[x].st+1>=ln )//succeed
{
Task tmp;
tmp.st=a[x].st,tmp.ln=ln;
tmp.tst=tst,tmp.ti=ti;
q.push(tmp);
a[x].st += ln;
if(a[x].st>a[x].ed and x!=tou)//空
{
rr[lx]=rx;
ll[rx]=lx;
}
return;
}
x=rx;
}
fail[++fr].ln=ln;
fail[fr].ti=ti;
}
int main()
{
int n;scanf("%d",&n);
tou=++id;
a[tou]=Lb(0,n-1);
ll[tou]=0,rr[tou]=0;
while(1)
{
int tst,ln,ti;scanf("%d%d%d",&tst,&ln,&ti);
if(tst==0 and ln==0 and ti==0) break;
while(!q.empty() and q.top().tst+q.top().ti-1<tst) pop_update();
try_push(tst,ln,ti);
}
while(!q.empty()) pop_update();
printf("%d\n%d",ans+1,fr);//debug 要求所有彻底结束
//printf("fl=%d fr=%d",fl,fr);
}

18 1806 Matrix

7.7 难度2

请先思考后再展开

第一次二维hash,所以学了下
题目的特性在于a和b固定,所以可以直接预处理出每个矩阵的hash
然后排个序,后面的询问就灰常快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int n,m,a,b;
const ull Base1=131;
const ull Base2=13331;
int cnt=0;
ull sum[MAXN*MAXN];
char s[MAXN];
ull h[MAXN][MAXN];
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
ull b1a=1;for(int i=1;i<=a;i++) b1a*=Base1;//Base1^a
ull b2b=1;for(int i=1;i<=b;i++) b2b*=Base2;//Base2^b
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
{
h[i][j]=h[i-1][j]*Base1+h[i][j-1]*Base2-h[i-1][j-1]*Base1*Base2+s[j]-'0';
if(i>=a and j>=b) sum[++cnt]=(h[i][j]-h[i-a][j]*b1a)-(h[i][j-b]-h[i-a][j-b]*b1a)*b2b;
}
}
sort(sum+1,sum+cnt+1);
int q;scanf("%d",&q);
while(q--)
{
for(int i=1;i<=a;i++)
{
scanf("%s",s+1);
for(int j=1;j<=b;j++)
h[i][j]=h[i-1][j]*Base1+h[i][j-1]*Base2-h[i-1][j-1]*Base1*Base2+s[j]-'0';
}
int t=lower_bound(sum+1,sum+cnt+1,h[a][b])-sum;
printf("%d\n",sum[t]==h[a][b]);
}
}

19 1807 Necklace

7.7 难度1

请先思考后再展开

最小表示法裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int len;
char s[2][MAXN*2];
int getmin(int w)
{
int a=1,b=2;
while(1)
{
if(a==b) b++;
if(a>b) swap(a,b);
if(b>len) return a;
bool bk=1;//相同
for(int k=0;k<=len-1;k++)
{
if(s[w][a+k]<s[w][b+k]) {b=b+k+1;bk=0;break;}
else if(s[w][a+k]>s[w][b+k]) {a=a+k+1;bk=0;break;}
}
if(bk) return 1;
}
}
int main()
{
scanf("%s%s",s[0]+1,s[1]+1);len=strlen(s[0]+1);
for(int i=1;i<=len;i++) s[0][len+i]=s[0][i],s[1][len+i]=s[1][i];
int k0=getmin(0),k1=getmin(1);
for(int i=0;i<=len-1;i++)
if(s[0][k0+i]!=s[1][k1+i])
{
puts("No");
return 0;
}
puts("Yes");for(int i=0;i<=len-1;i++) printf("%c",s[0][k0+i]);
}

20 poj2185 Milking Grid

7.8 难度2

请先思考后再展开

有关kmp与最小覆盖的前置知识,请搜索kmp查看教程

然后一开始猜一手结论,行取max,列同样,居然ac了
其实后来我和mocha经过探讨发现,max是不正确的
(例如6和9,除非问题改成陶陶的名字),应该取lcm

UP 2018.7.11
其实lcm也是错误的
反例
8 2
AABBBBAA
AAABBAAA

正确的方法应该是强行比较的kmp(hash也行,快一点)
代码已更正

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int n,m;
char s[11000][110];
int nxt[11000];
bool cmp1(int col1,int col2)
{
for(int row=1;row<=n;row++)
if(s[row][col1]!=s[row][col2])
return 0;
return 1;
}
int getnext1()
{
nxt[1]=0;
for(int i=2;i<=m;i++)
{
int j=nxt[i-1];
while(j>0 and !cmp1(j+1,i)) j=nxt[j];
nxt[i]=j+cmp1(j+1,i);
}
return m-nxt[m];
}
bool cmp2(int row1,int row2)
{
for(int col=1;col<=m;col++)
if(s[row1][col]!=s[row2][col])
return 0;
return 1;
}
int getnext2()
{
nxt[1]=0;
for(int i=2;i<=n;i++)
{
int j=nxt[i-1];
while(j>0 and !cmp2(j+1,i)) j=nxt[j];
nxt[i]=j+cmp2(j+1,i);
}
return n-nxt[n];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
printf("%d",getnext1()*getnext2());
}

21 bzoj2288 生日礼物

7.9 难度2

请先思考后再展开

有一个灰常关键的步骤:
由贪心知,连续的正数、负数一定是同时选取的
所以可以直接合并起来考虑

把正数的段计数,我们的任务就是,
在花费最少的前提下,把正数减少到m及以下
减少的方法有两个,一是选取一个正数,然后把相邻的负数合并起来(因为必须要连续),代价为正数值
二是选取一个负数,把相邻的正数合并,这样代价是负数绝对值
综上所述,我们可以把所有数的绝对值放到小根堆里面,统计正数的数量,每次弹出直到数量在m以下即可

还有两个细节

  1. 三个数合并之后,正负性是没有意义的,我们前面是为了统计tot并确保算法正确性
  2. 对于边缘的负数,要予以忽略!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #include<vector>
    #include<map>
    #include<set>
    using namespace std;
    const int MAXN=110000;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    typedef unsigned long long ull;
    int mymax(int x,int y) {return x>y?x:y;}
    int mymin(int x,int y) {return x<y?x:y;}
    int myabs(int x) {return x>0?x:-x;}
    struct Num
    {
    int d,pos;
    Num(int t,int p) {d=t,pos=p;}
    friend bool operator > (Num a,Num b) {return myabs(a.d)>myabs(b.d);}
    };
    int f[MAXN];//值
    int l[MAXN],r[MAXN];//链表
    priority_queue< Num,vector<Num>,greater<Num> > q;
    void del(int x)
    {
    f[x]=INF;
    r[l[x]]=r[x];
    l[r[x]]=l[x];
    }
    int main()
    {
    int n,m;scanf("%d%d",&n,&m);
    int ans=0,tot=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
    int t;scanf("%d",&t);
    if( i>1 and (t>0)==(f[cnt]>0) ) f[cnt]+=t;
    else f[++cnt]=t;
    }
    for(int i=1;i<=cnt;i++)
    {
    if(f[i]>0) tot++,ans+=f[i];
    q.push( Num(f[i],i) );
    l[i]=i-1;r[i]=i+1;
    }
    while(tot>m)
    {
    tot--;//debug 要在前面
    while(!q.empty() and q.top().d!=f[q.top().pos]) q.pop();//old
    Num now=q.top();q.pop();
    int x=now.pos,lx=l[x],rx=r[x];
    if( (l[x]!=0 and r[x]!=cnt+1) or f[x]>0 )
    {
    ans-=myabs(f[x]);
    f[x]=f[lx]+f[x]+f[rx];
    q.push( Num(f[x],x) );
    del(lx);del(rx);//删除
    }
    else tot++;//忽略边缘负数
    }
    printf("%d",ans);
    }

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7248.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%