先挖在这里,2022年2月前一定通关!
这个游戏好像有点BUG,不一定保证所有题目都被写到。
默认省略头文件

暑假集训

D1(单调栈)

POJ3250

题意:所有奶牛都面朝东边,它们可以看到严格比自己矮的所有奶牛的头发,但是一旦有不是严格比它矮的奶牛出现后面的所有奶牛(含这头不是严格比它矮的奶牛)它都无法看到。求所有奶牛可以看到其他奶牛头发的数量的和。
思路:
既然被放在单调栈这里,肯定是单调栈了。 (笑哭)
我们换一个等价的问法,我们考虑每头奶牛会被多少头奶牛看到头发。这不就是问前面有多少奶牛比它高吗?并且还是有条件限制的”高”——>单调,所以从左到右遍历过程中,只需要考虑一个元素在出栈时,栈里面有多少个元素,对元素个数求和即可!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int _,n,m,ans;
int tmp;
int stk[maxn];
int main()
{
cin>>n;
ans=0;
for(int i=1;i<=n;i++)
{
cin>>tmp;
while(stk[0]>0 && stk[stk[0]]<=tmp)
{
stk[0]--;
}
stk[stk[0]+1]=tmp;
ans+=stk[0];
stk[0]++;
}
cout<<ans<<endl;
return 0;
}

POJ2559

题意:给你n个宽度为1,高度为a[i]的矩形,求最大能围成一个面积为多少的矩形。
思路:很明显,对于任意一个小矩形,若以它的高度为长边,那么面积将是左右高度不小于它的个数加上自己后与高度的乘积。
如此一来,我们就可以考虑一个单调栈维护每个小矩形在它出栈时,左右加上自己有多少个高度不小于它的矩形。
用一个pair来存,first表示高度,second表示左边加上自己有多少个高度不小于它的矩形。
设p为在这个元素进栈前弹出元素的个数。
当前高度小于等于栈顶时,弹出栈顶元素,维护答案,ans=max(ans,first*(second+p)),为什么+p,因为弹出几个就说明在它右边有多少个高度大于等于它。进栈的时候,second=1+p。
最后把栈清空的过程中也注意p的维护即可。

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
pair<ll ,ll > stk[100005];
ll ans;
ll sz;
ll n,m;
int main()
{
while(1)
{
sz=ans=0;
scanf("%lld",&n);
if(n==0)
{
break;
}
int p=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&m);
p=0;
while(sz>0&&stk[sz].first>=m)
{
ans=max(ans,stk[sz].first*(stk[sz].second+p));
p+=stk[sz].second;
sz--;

}
stk[++sz].first=m;
stk[sz].second=1+p;
}
p=0;
while(sz>0)
{
ans=max(ans,stk[sz].first*(stk[sz].second+p));
p+=stk[sz].second;
sz--;
}
printf("%lld\n",ans);
}
}

D2(动态规划)

用到了单调的性质,D1和D2连接起来了,开发者很用心。

POJ2533

题意:裸的求最长上升子序列
思路:对于每个数,我们考虑以它结尾的最长上升序序列长度为dp[i],那么你就需要在找到所有a[j] < ai使得dp[i]为max(dp[j])+1,枚举实在太慢了,我们不妨让前面有序,这样就可以二分查找维护。
我们设b为当前获得的最长子序列,对于每个数,它只要大于b的最后一个元素,就可以直接加到末尾,如果不是,他可以去替换掉里面的最小的比它大的元素,替换掉之后,你会发现这个b不是有序的了,顺序乱掉了,但是因为我们没有改变b的大小,输出答案时相当于没有替换。但是却又使得整个b中每个元素都尽可能变小了,也就使得后面的元素更容易进到b中来。从而最大化了答案。
这是我第一次在程序里面去使用lower_bound。之前都是自己手写二分函数。

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
int a[maxn];
int LIS()
{
vector<int > vec;
vec.push_back(a[1]);
for(int i=2;i<=n;i++)
{
if(vec.back()<a[i]) //只在这里改变了长度
vec.push_back(a[i]);
else//这里没有改变长度
vec[lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()]=a[i];//这样是不符合序列的要求,但是因为是替换,所以对答案没影响
}
return int(vec.size());
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int ans=LIS();
cout<<ans<<endl;
return 0;
}

POJ1141

在做这题之前,建议先去练习一下POJ2955
题意:给定一个括号序列,要你输出一个最短的合法括号序列,使得输入是输出的子序列。
思路:先说一个坑点,可能输入空串,这时候需要输出空串,其他情况就是从右到左做遍历的过程中,确定当前位置能获得的最大括号序列数量,获取方式和POJ2955一样,但是,不是直接取最大值而是再更大的时候记录这里的右端点,用于接下来的路径输出,在路径输出里面,如果我们的a为-1,表示i和j形成一个合法括号,此时直接i+1.若此时不为-1,表示i和a[i][j]形成一个括号序列。但这里是我们自己添加的。最后打印新的括号序列即可。

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
int _,n,m,len;
char str[1005];
int dp[300][300],a[300][300],b[300];
void print(int i,int j)
{
if(i>=j) return ;
if(a[i][j]==-1)//直接转移的,没有匹配成,需要自己补一个
print(i+1,j);
else
{
b[i]=1;
b[a[i][j]]=1;
print(i+1,a[i][j]-1);
print(a[i][j],j);
}
}
int main()
{
while(gets(str+1)>0)
{

memset(a,-1,sizeof(a));
memset(b,0,sizeof(b));
memset(dp,0,sizeof(dp));
len=strlen((str+1));
for(int i=1;i<=len;i++)
dp[i][i]=1;
for (int i=len-1;i>=1;i--)// 左端点
{
for(int j=i+1;j<=len;j++)// 右端点
{
dp[i][j]=dp[i+1][j]+1;
a[i][j]=-1;
for(int k=i+1;k<=j;k++)
{
if( (str[i]=='(' && str[k]==')' )||(str[i]=='[' && str[k]==']' ) )
{
if(dp[i][j]>dp[i+1][k-1]+dp[k][j]-1)
{
dp[i][j]=dp[i+1][k-1]+dp[k][j]-1;
a[i][j]=k;
}
}
}
}
}
print(1,len);

//我们知道dp[1][len] 就是 1~len 中需要补充的数量
for(int i=1;i<=len;i++)
{
if(b[i]==1)
{
printf("%c",str[i]);
}
else
{
if(str[i]=='('||str[i]==')')
{
printf("()");
}
else
{
printf("[]");
}
}
}
printf("\n");
}
return 0;
}


D3(状态空间搜索-1)

UVALive2026

题意:输入n,按照字典序输出1~n的全排列。
思路:先说坑点,这道题要在Run2和Run1这种形式之间输出一个空行,注意是之间!所以最后一次是不用输出的,返回形式是WA很坑,不明白可以去看岛娘的提交,从WA到AC很容易想到在每个位置枚举每一个数,因为要按字典序,所以每个位置我们都从小到大去枚举,对于每个数看它之前是否已经出现了,没出现就填在这里,然后去枚举下一位。当枚举完最后以为以后输出答案。

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
int _,n,m;
int a[15];
bool vis[15];
void dfs(int now)
{
if(now==n)
{
for(int i=1;i<=n-1;i++)
{
printf("%d ",a[i]);
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
printf("%d\n",i);
}
}
}
else
{
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
a[now]=i;
dfs(now+1);
vis[i]=0;
}
}
}
return ;
}
int main()
{
int cas=1;
while(scanf("%d",&n))
{
if(n==0)
{
break;
}
if(cas>1)
{
printf("\n");
}
printf("Run %d n=%d\n",cas++,n);
dfs(1);

}
return 0;
}

打完收工之后卡死了

D4(状态空间搜索-2)

POJ1475