NOIP2015提高组 解题报告
Day1
神奇的幻方
【题目描述】略。
思路分析
幻方问题是一个经典的数学问题，这道题叙述的是奇数幻方的构造方法。
题目中已经很明确地说明了构造的方法，只要一条条转换为代码即可。
具体代码
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
| /*
Magic
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n;
int mid;
int a[50][50];
void fill()
{
/*
1.若(K-1)在第一行但不在最后一列，则将K填在最后一行，(K-1)所在列的右一列；
2.若(K-1)在最后一列但不在第一行，则将K填在第一列，(K-1)所在行的上一行；
3.若(K-1)在第一行最后一列，则将K填在(K-1)的正下方；
4.若(K-1)既不在第一行，也不在最后一列，如果(K-1)的右上方还未填数，
则将K填在(K-1)的右上方，否则将K填在(K?1)的正下方。
*/
a[1][mid]=1;
int tx=1,ty=mid;
for(int i=2;i<=n*n;++i)
{
if(tx==1)
{
if(ty==n)
{
++tx;
}
else
{
tx=n,++ty;
}
}
else if(ty==n)
{
ty=1;
--tx;
}
else
{
if(a[tx-1][ty+1]==0)
{
--tx,++ty;
}
else
{
++tx;
}
}
a[tx][ty]=i;
}
}
void output()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
printf("%d",a[i][j]);
if(j!=n)
printf(" ");
}
printf("\n");
}
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d",&n);
mid=(n+1)>>1;
fill();
output();
return 0;
}
|
信息传递
【题面描述】略。
思路分析
根据题意，给定每个点的出度为1的一个有向图，求最小环的长度。
暴力
暴力DFS，枚举每个点能搜到的环，如果能搜到起始点则更新答案最小值并退出。
退出的原因是继续搜下去会重复之前的路径。
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
| /*
message NOIP 2015 day1 t2
在给定有向图中求最小环的长度
正解用Tarjan强连通
此处尝试 暴力
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
using namespace std;
void read(int& A);
const int maxn=200003;
const int inf=2147483647;
int n,to[maxn];
inline void input()
{
read(n);
for(int i=1;i<=n;++i)
{
read(to[i]);
}
}
bool vis[maxn];
int dfs(int start)
{
for(int i=1;i<=n;++i)vis[i]=false;
int t=0;
int now;
for(now=start;(t==0||now!=start)&&!vis[to[now]];now=to[now])
{
++t;
if(now!=start)vis[now]=true;
}
if(now==start)
return t;
else return inf;
}
int main()
{
//freopen("message1.in","r",stdin);
//freopen("message.out","w",stdout);
input();
int ans=2147483647;
for(int i=1;i<=n;++i)
{
int tans=dfs(i);
if(tans<ans)
ans=tans;
}
printf("%d\n",ans);
return 0;
}
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
|
暴力+
我们分析一下，在某一次搜索中，如果没有搜到起始点s而是搜到了本次搜索之前访问过的点b，那么这时候对于b也已经形成了一个环。并且对于每个在这次搜索中访问过的点，再次访问的时候一定也会按照这次一样的路径，所以就不用再次访问了。
另外，入度为零的点一定不再环中，所以不用从它开始搜索。
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
| /*
message NOIP 2015 day1 t2
在给定有向图中求最小环的长度
正解用Tarjan强连通
此处尝试 暴力 +
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
using namespace std;
void read(int& A);
const int maxn=200003;
const int inf=2147483647;
int n,to[maxn],in[maxn];
inline void input()
{
read(n);
for(int i=1;i<=n;++i)
{
read(to[i]);
++in[to[i]];
}
}
bool vis[maxn];
int vistime[maxn];
int dfs(int start)
{
for(int i=1;i<=n;++i)vistime[i]=-1;
int t=0;
int now;
for(now=start;vistime[now]==-1;now=to[now])
{
vistime[now]=t;
++t;
vis[now]=true;
}
return t-vistime[now];
}
int main()
{
freopen("message.in","r",stdin);
//freopen("message.out","w",stdout);
input();
int ans=2147483647;
for(int i=1;i<=n;++i)
{
if(!vis[i]&&in[i]!=0)
{
int tans=dfs(i);
if(tans<ans)
ans=tans;
}
}
printf("%d\n",ans);
return 0;
}
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
|
暴力+queue
进一步深入思考，我们发现当一个节点被删除之后，它所指向的点的入度就会减1，它就又有可能入度为0。于是我们可以大批删除点。
这里我们使用queue来完成这个操作：
1
2
3
4
5
6
7
| 将初始的入度为零的点入队
While（队不为空）
设v为队首指向的点
Indge[v]=indge[v]-1;
If（indge[v]等于0）
将v入队
弹出队首元素
|
代码：（使用STL）
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
| /*
message NOIP 2015 day1 t2
在给定有向图中求最小环的长度
正解用Tarjan强连通
此处尝试 暴力+ +queue删除入度为0
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include <queue>
using namespace std;
void read(int& A);
const int maxn=200003;
const int inf=2147483647;
int n,to[maxn],in[maxn];
inline void input()
{
read(n);
for(int i=1;i<=n;++i)
{
read(to[i]);
++in[to[i]];
}
}
bool vis[maxn];
int vistime[maxn];
int dfs(int start)
{
for(int i=1;i<=n;++i)vistime[i]=-1;
int t=0;
int now;
for(now=start;vistime[now]==-1;now=to[now])
{
vistime[now]=t;
++t;
vis[now]=true;
}
return t-vistime[now];
}
int main()
{
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
input();
int ans=2147483647;
queue<int> q;
for(int i=1;i<=n;++i)
{
if(in[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
--in[to[q.front()]];
if(in[to[q.front()]]==0)
{
q.push(to[q.front()]);
}
q.pop();
}
for(int i=1;i<=n;++i)
{
if(!vis[i]&&in[i]!=0)
{
int tans=dfs(i);
if(tans<ans)
ans=tans;
}
}
printf("%d\n",ans);
return 0;
}
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
|
暴力-queue
其实……再想一下，上面的队列如果改变一下搜的方法，不是将所有点都一次加入，而是每次枚举入度为零的点并删除当前所有能删除的点，就可以去掉那个queue。不过会稍稍变慢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| for(int i=1;i<=n;++i)
{
if(in[i]==0&&to[i]!=0)
{
int k=i,tmp=-1;
while(k!=tmp)
{
--in[to[k]];
tmp=k;
if(in[to[k]]==0)
{
k=to[tmp];
}
to[tmp]=0;
}
}
}
|
Tarjan-
Tarjan的求极大强连通子图算法是一个适用于所有图的算法。
对于这道题，所有点的出度都为1，那么Tarjan的代码可以大大简化。
注意到一点，Tarjan求的是极大强连通子图，题目要求的是最小环。但是还是由于所有点的出度都为1，那么就不会出现环套环的情况。
我们求出所有的强连通子图（本题中也就是环）然后更新答案即可。
需要注意的是，由于对每个点都递归搜索了一次，在windows下自己运行n=200000的数据时会栈溢出。提交评测时是可以过的。
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<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200005;
int low[maxn],num[maxn];
int minNum=2147483647;
bool instack[maxn];
bool vis[maxn];
stack<int> s;
int e[maxn];
int tim=0;
int n;
inline void push(int v)
{
vis[v]=true;
instack[v]=true;
s.push(v);
}
inline void tarjan(int v)
{
//init
push(v);
low[v]=num[v]=++tim;
int w=e[v];//下一个节点
if(!vis[w])
{
tarjan(w);
low[v]=min(low[v],low[w]);
}
else if(instack[w])
{
low[v]=min(low[v],num[w]);
}
//judge
if(low[v]==num[v])
{
int sum=0;
while(s.top()!=v)
{
instack[s.top()]=false;
s.pop();
++sum;
}
s.pop();
instack[v]=false;
++sum;
if(sum<minNum&&sum>1)minNum=sum;
}
}
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
int main()
{
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
read(n);
for(int i=1;i<=n;++i)
{
read(e[i]);
}
for(int i=1;i<=n;++i)
{
if(!vis[i])
{
tarjan(i);
}
}
printf("%d\n",minNum);
return 0;
}
|
Kosaraju-
这是一种实现较为简单的算法，分为两次DFS，一次在原图中遍历，一次在反向图中遍历。
该算法基于以下原理：如果A在原图和反向图中都能到达B，那么A、B强连通。
具体实现略。
斗地主
有人说这题是不用考虑什么的大搜索。而且由于数据是随机生成的，所以大部分可能不那么严谨的算法都可以过了。
思路分析
不过大概还是有几个有用的点：
花色几乎是没有用的，这里题目描述的不是很清楚，没有说两张大王不能当对子。
如果当可以的话代码中就可以只考虑码数了。
因为“2”这张牌不能当做顺子，所以它没有什么作为“2”的必要，而“A”可以排在JQK后面作为顺子，我们可以在读入的时候将所有的牌的码数转换一下：
| 王 | A | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | J | Q | K |
|---|
| 0 | 12 | 13 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
这样在代码中可以大大简化顺子的部分以及减少很多特判。
剪枝。常用的剪枝是一旦当前使用的步数大于等于ans而牌还没有打完就直接回退。
代码顺序。这里采用一点点贪心的技巧，将可以一次打出较多牌的选法排在前面，这样在后面的运行中可以大量的剪枝。
处理单牌和对子。单牌和对子在最后会剩下比较多，所以如果直接继续递归的话会浪费很多时间。我们可以发现只剩单牌和对子时最少的步骤就是依次将每种码数的牌全部打出，答案也就是有余牌的码数个数。
具体代码
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
| /*
Landlords
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
inline void read(int& A)
{
/*
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
*/
scanf("%d",&A);
}
const int maxn=25;
const int inf=2147483647;
int T,n,ans;
int card[14];
inline int recode(int k)
{
if(k==1)return 12;
if(k>=3&&k<=13)
return k-2;
if(k==0)return 0;
if(k==2)return 13;
}
void input()
{
int num,color;
for(int i=1;i<=n;++i)
{
read(num),read(color);
++card[recode(num)];
}
}
void dfs(int t,int rest)
{
//cout<<t<<' '<<rest<<endl;
if(t>ans)return;
if(rest==0)
{
if(t<ans)ans=t;
return;
}
int cnt[24];
memset(cnt,0,sizeof(cnt));
//init
for(int i=0;i<=13;++i)
{
for(int j=card[i];j>=1;--j)
{
++cnt[j];
}
}
//if(cnt[1]+t>ans)return; it's wrong
//4 carry 2
if(rest>=6)
{
for(int i=0;i<=13&&cnt[4];++i)
{
if(card[i]>=4)
{
card[i]-=4;
for(int r=1;r<=2;++r)
{
//choose two different
for(int j=0;j<=13&&cnt[r];++j)
{
if(card[j]>=r)
{
card[j]-=r;
for(int k=0;k<=13;++k)
{
if(k!=j&&card[k]>=r)
{
card[k]-=r;
dfs(t+1,rest-4-2*r);
card[k]+=r;
}
}
card[j]+=r;
}
}
//choose two same
for(int j=0;j<=13&&cnt[2*r];++j)
{
if(card[j]>=2*r)
{
card[j]-=2*r;
dfs(t+1,rest-4-2*r);
card[j]+=2*r;
}
}
}
dfs(t+1,rest-4);
card[i]+=4;
}
}
// 3*3+
for(int i=1;i<=11&&cnt[3]>=2;++i)
{
if(card[i]>=3)
{
int yan;
for(yan=i+1;yan<=12&&card[yan]>=3;++yan);
for(int j=yan-1;j>=i+1;--j)
{
for(int k=i;k<=j;++k)
{
card[k]-=3;
}
dfs(t+1,rest-(j-i+1)*3);
for(int k=i;k<=j;++k)
{
card[k]+=3;
}
}
i=yan;
}
}
//3*2+
for(int i=1;i<=10&&cnt[2]>=3;++i)
{
if(card[i]>=2)
{
int yan;
for(yan=i+1;yan<=12&&card[yan]>=2;++yan);
for(int j=yan-1;j>=i+2;--j)
{
for(int k=i;k<=j;++k)
{
card[k]-=2;
}
dfs(t+1,rest-(j-i+1)*2);
for(int k=i;k<=j;++k)
{
card[k]+=2;
}
}
i=yan;
}
}
}
// 5*1+
if(rest>=5)
{
for(int i=1;i<=8&&cnt[1]>=5;++i)
{
int yan;
if(card[i]>=1)
{
for(yan=i+1;yan<=12&&card[yan]>=1;++yan);
for(int j=yan-1;j>=i+4;--j)
{
for(int k=i;k<=j;++k)
{
--card[k];
}
dfs(t+1,rest-(j-i+1));
for(int k=i;k<=j;++k)
{
++card[k];
}
}
}
}
// 3carry 2
for(int i=0;i<=13&&cnt[3]&&cnt[2];++i)
{
if(card[i]>=3)
{
card[i]-=3;
for(int j=0;j<=13&&cnt[2];++j)
{
if(card[j]>=2)
{
card[j]-=2;
dfs(t+1,rest-5);
card[j]+=2;
}
}
card[i]+=3;
}
}
}
//tnt 4
if(rest>=4)
{
//3carry 1
for(int i=0;i<=13&&cnt[3];++i)
{
if(card[i]>=3)
{
card[i]-=3;
for(int j=0;j<=13;++j)
{
if(j!=i&&card[j]>=1)
{
card[j]-=1;
dfs(t+1,rest-4);
card[j]+=1;
}
}
dfs(t+1,rest-3);
card[i]+=3;
}
}
}
// 2 and 1
if(cnt[3]==0)
{
dfs(t+cnt[1],0);
}
}
int main()
{
freopen("landlords.in","r",stdin);
//freopen("landlords.out","w",stdout);
read(T),read(n);
for(int e=1;e<=T;++e)
{
ans=inf;
memset(card,0,sizeof(card));
input();
dfs(0,n);
printf("%d\n",ans);
}
return 0;
}
|
Day2
跳石头
思路分析
首先将输入的d数组转为差分数组a，注意要将l-d[n]也加入；
然后由于这是一道求最小值的最大值，我们可以二分答案转换为一个判定性问题。
然后问题就转换成了：
给定一串n+1个数，每次可以合并相邻两数，求m次合并后是否能使得各个数均不小于ans。
我们可以采用略带贪心的思想，在差分数组中自前向后枚举，如果当前数比ans小，就花费一次将下一个数与当前数合并；最后如果合并次数没有超过ans就是可行的。
具体代码
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
| /*
stone BinarySearch
*/
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=50003;
const int inf=2147483647;
int ll,n,m,d[maxn],a[maxn];
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
void input()
{
read(ll),read(n),read(m);
for(int i=1;i<=n;++i)
{
read(d[i]);
}
for(int i=1;i<=n;++i)
{
a[i]=d[i]-d[i-1];
}
++n;
a[n]=ll-d[n-1];
}
bool can(int k)
{
int rest=0;
for(int i=1;i<=n;)
{
int j,tsum=a[i];
for(j=i+1;tsum<k&&j<=n;++j)
tsum+=a[j],++rest;
i=j;
}
if(rest>m)return false;
else return true;
}
int BS()
{
int l=1,r=ll,mid;
int ans;
while(l<=r)
{
mid=(l+r)>>1;
if(can(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
return ans;
}
int main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
input();
printf("%d\n",BS());
return 0;
}
|
子串
容易想到这是动态规划的题目。
读入
既然是动态规划，我们为了写动态方程的方便和代码的简洁，在读入的时候可以让a、b从下标1开始（scanf(“%s%s”,a+1,b+1);）。
但是需要注意，这样读入之后使用strlen(a)来获取a的长度的时候会返回0。因为该函数默认将’\0’作为字符串的结束标志，从1下标开始存放时a[0]一般为0。
不过题目已经给出了a、b的长度n、m，直接使用即可。
动态规划
开始想状态转移方程。
设f[j][k][i]表示a串匹配到i位置，b串匹配到j位置时选择k个子串的方案数。这里我们约定a[i]和b[j]都被选中，那么必定有a[i]==b[j]。所以首先确定a[i]!=b[j]时f[j][k][i]=0;
接下来我们考虑a[i]==b[j]时的递推过程，有两种情况：
- a[i]作为单独的一个子串。
那么既然a[i]一定是选定的，在a前面i-1个位置一定要选出k-1个子串。
又a[i]是与b[j]配对的，所以一定是在b前面j-1个位置匹配。
也就转换成：a串匹配到i之前，b串匹配到j-1时选出k-1个子串的方案数。
**注意：**这里并没有要求a[i-1]==b[j-1]，所以上述问题的答案并不是f[j-1][k-1][i-1]。
那么我们应该用什么呢？仔细思考一下，发现不管i在前面什么位置，只要已经选出了k-1个子串并且在b串中匹配完了前j-1个位置，在当前这样的情况下就符合递推的条件。
换句话说，f[j-1][k-1][1]、f[j-1][k-1][2]、……f[j-1][k-1][i-1]都要加到f[j][k][i]中。
怎么操作？前缀和。
我们再维护一个$\mathrm{s}[\mathrm{j}][\mathrm{k}][\mathrm{i}]=\sum_{x=1}^{i} f[\mathrm{j}][\mathrm{k}][\mathrm{x}]$，每次算出f[j][k][i]时加上即可。
在当前这样的情况下，我们满足的方案数就是s[j-1][k-1][i-1]。
a[i]和a[i-1]在同一个子串中。根据要求，则有a[i-1]==b[i-1]。
也就是：a串匹配到i-1，b串匹配到j-1时选择k个子串时的方案数，而且a[i-1]==b[j-1]。
（因为a[i]与a[i-1]共享一个子串，所以没有增加子串个数）
我们可以发现它正好符合f[j-1][k][i-1]的定义。
综上所述，
状态转移方程
$$
\begin{cases}f[j][k][i]=\begin{cases}0,a[i]\neq b[j]\\f[j-1][k][i-1]+s[j-1][k-1][i-1],a[i]=b[j]\end{cases}\\s[j][k][i]=s[j][k][i-1]+f[j][k][i]\end{cases}
$$
初始化
虽然题目中说取出的是非空子串，但是在递推的过程中我们发现需要将s[0][0][i]赋为1。
代码片段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve()
{
s[0][0][0]=1;
for(int i=1;i<=n;++i)
{
s[0][0][i]=1;
for(int j=1;j<=m&&j<=i;++j)
{
for(int k=1;k<=j&&k<=kk;++k)//kk为输入的k
{
if(a[i]==b[j])
f[j][k][i]=f[j-1][k][i-1]%p+s[j-1][k-1][i-1]%p,
f[j][k][i]%=p;
else f[j][k][i]=0;
s[j][k][i]=s[j][k][i-1]%p+f[j][k][i]%p;
s[j][k][i]%=p;
}
}
}
}
|
答案为s[m][k][n]%p。
空间计算
maxn=1000,maxm=200,maxk=200;
共f、s两个int数组，一个int为32位，4Byte。
空间大小=maxn*maxm*maxk*2*4 (B)
=1000*200*200*2*4 (B)
=320000000 (B)
=312500 (KB)
=305.17 (MB)
可是比赛时的空间限制是128MB，超了。
我们要想办法降低空间复杂度。
滚动数组
再一次观察状态转移方程，我们发现每次计算i的时候都只用到了i-1的值。所以我们可以将原来maxn的一维降到2。这样原来的方程就变成：
状态转移方程II
$$
\begin{cases}f[j][k][i\%2]=\begin{cases}0,a[i]\neq b[j]\\f[j-1][k][(i+1)\%2]+s[j-1][k-1][(i+1)\%2],a[i]=b[j]\end{cases}\\s[j][k][i\%2]=s[j][k][(i+1)\%2]+f[j][k][i\%2]\end{cases}
$$
在代码中，我们可以用位运算加速%2，即用i&1代替i%2，用i&1^1代替(i+1)%2。
这样空间瞬间减小为原来的$\frac{1}{500}$，可以过了。
代码实现
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
| /*
Substring
DP
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
using namespace std;
const int maxn=1003;
const int maxm=203;
const int p=1000000007;
int n,m,kk;
char a[maxn],b[maxm];
int f[maxm][maxm][2];
int s[maxm][maxm][2];
void solve()
{
s[0][0][0]=1;
register int i,j,k,now,nxt;
for(i=1;i<=n;++i)
{
now=i&1;
nxt=now^1;
s[0][0][now]=1;
for(j=1;j<=m&&j<=i;++j)
{
for(k=1;k<=j&&k<=kk;++k)
{
if(a[i]==b[j])
f[j][k][now]=f[j-1][k][nxt]%p+s[j-1][k-1][nxt]%p,
f[j][k][now]%=p;
else f[j][k][now]=0;
s[j][k][now]=s[j][k][nxt]%p+f[j][k][now]%p;
s[j][k][now]%=p;
}
}
}
}
int main()
{
freopen("substring.in","r",stdin);
//freopen("substring.out","w",stdout);
scanf("%d%d%d",&n,&m,&kk);
scanf("%s%s",a+1,b+1);
solve();
printf("%d\n",s[m][kk][n&1]%p);
return 0;
}
|
滚动数组II
再仔细想一下，我们发现其实还可以把最后的一维完全去掉，即只开s[j][k]、f[j][k]。
因为前面在计算f[j][k][i]时只用到了f[j-1][k]和s[j-1][k-1][i-1]，我们只要保证这两个值在计算f[j][k][i]时没有被新的值更新。
所以我们可以让j、k倒着循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve()
{
s[0][0]=1;
for(int i=1;i<=n;++i)
{
s[0][0]=1;
for(int j=Min(i,m);j>=1;--j)
{
for(int k=Min(kk,j);k>=1;--k)//kk为输入的k
{
if(a[i]==b[j])
f[j][k]=f[j-1][k]%p+s[j-1][k-1]%p,
f[j][k]%=p,
s[j][k]=s[j][k]%p+f[j][k]%p;
s[j][k]%=p;
else f[j][k]=0;
}
}
}
}
|
一个小优化
在读入a、b之后，我们的b[1]必须至少匹配a中第一个满足a[i]==b[1]的位置。
设x为a中第一次出现b[1]的位置，那么a中x前的字符都是没有用的，可以全部删去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| inline void Init()
{
int be;
for(be=1;a[be]!=b[1]&&be<=n;++be);
if(be==n+1)
{
printf("0\n");
exit(0);//程序直接退出并返回0
}
if(be!=1)
{
for(int i=be;i<=n;++i)
{
a[i-be+1]=a[i];
}
n-=be-1;
}
}
|
运输计划
思路分析
分析一下题意，由于所有的运输计划都是同时进行而且互不影响的，那么最终的时间就是时间花费最久的计划的时间。我们发现这道题又是求最大值的最小值，果断二分答案。
于是又转变成了一个判定性问题，即给出一个答案，判断是否在改造一条航线为虫洞的条件下能够使时间最大值小于等于答案。我们使用树链剖分的模型来处理这些问题。
具体步骤
树链剖分
将给的树树链剖分一下，不多说。
计算耗时
在进行其他所有操作之前，我们要算出所有计划的耗时。也就是在树上求出两点间的权值和。
平时用树链剖分时我们处理这样的操作时会使用线段树，但是经过分析我们发现，输入这颗树并树链剖分之后，所有的数据就已经没有发生变化，而使用的区间操作只有在链上的区间和。
那么我们大可不必打麻烦的线段树，只要一个前缀和数组来维护即可。
这里用到了一个重要的性质，在树链剖分中，在同一条重链上的节点的新编号是连续的。
其他的操作就是普通的树链剖分，按深度大的逐渐向上爬，累加上经过的边的时间。
另外，我们在读入时将边的权值放到较下方的节点上。
二分答案
我们取l=0,r=maxlen.
之所以取0是因为有可能出现只有一条航线的情况，这时答案为0.
Maxlen是所有计划中耗时最长的一条的耗时。
判断答案
在判断时，对于耗时已经小于等于ans的计划我们就不用再考虑了。
所以问题就变成：对于若干条耗时大于ans的计划，能否找到这样一条航线使它成为虫洞后这些计划的耗时都小于等于ans。思考后我们得出几个条件：
这条航线包括在所有耗时超出ans的计划中。
显然，如果有一条计划没有经过这条航线，那么这个计划就失去了缩短时间的机会。
耗时最长的计划的耗时减去这条航线之后小于等于ans。
如果耗时最长的计划减去后都满足，那么其他的计划也都满足。
那么如何计算某条航线被经过的次数呢？我们对于每条耗时大的计划直接按树链剖分查询的模板跟进。这里也涉及到一个区间操作，即将区间内所有的数加上一个数。
当然线段树也是可以实现这样的操作的（需要加上lazy-tag）。
不过还是稍加分析，我们想起了差分数组。在差分数组中，每个元素表示的是原数组中相同位置的元素与前一元素的差。（第一个元素不变）。设原数组为a[]，差分数组为d[]，那么有：
a[i]=d[1]+d[2]+d[3]+d[4]+……+d[i]=d[ ].sum(1,i)
这样对于我们的操作带来了极大的方便，当要在区间l,r的所有数都加上x时，我们只用做这样两个操作：
d[l]=d[l]+x,
d[r+1]=d[r+1]-x.
于是在走完所有的计划后，我们只要依次累加d数组就能还原a数组。
如果a[i]==原来的耗时大于ans的计划数，就说明第i条节点对应的航线被这些计划经过。如果减去它的时间能使得耗时最久的计划的耗时小于ans，就说明ans是可行的。
至此，我们将二分的答案输出即可。
实现代码
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
| /*
transport
luogu2680
Heavy-Light Decomposition
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
// some useful tools
void read(int &A)
{
char r;bool f=false;
for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
if(r=='-')
f=true,r=getchar();
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
if(f)A=-A;
}
template<typename T>
inline void Swap(T& a,T& b){T t=a;a=b,b=t;}
template<typename T>
inline T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
inline T Min(const T& a,const T& b){return a<b?a:b;}
const int maxn=300003;
const int inf=2147483647;
typedef const int& cint;
//edge
int n,m;
int u[maxn],v[maxn];
struct EDGE
{
int from,to,len,nxt;
void init(cint fromm,cint too,cint lenn,cint nxtt)
{
from=fromm,to=too,len=lenn,nxt=nxtt;
}
}edge[maxn<<1];
int ek=0;
//the tree
struct node
{
int edge1,size,num,newid;
int top,hson,depth,f,lenf;
inline void init(cint numm,cint dep,cint ff)
{
num=numm,depth=dep,f=ff;
}
inline void clear()
{
edge1=size=num=lenf=0;
top=hson=depth=f=newid=0;
}
}tree[maxn];
int tk,tid,reid[maxn];
inline void addEdge(cint whose,cint too,cint lenn)
{
edge[++ek].init(whose,too,lenn,tree[whose].edge1);
tree[whose].edge1=ek;
}
//the Heavy-Light Decomposition
void findHeavySon(cint k,cint fa,cint dep)
{
#define now tree[k]
now.init(k,dep,fa);
now.size=1;
now.hson=-1;
for(int i=now.edge1;i!=0;i=edge[i].nxt)
{
#define v (edge[i].to)
#define son tree[v]
if(v!=now.f)
{
findHeavySon(v,k,dep+1);
now.size+=son.size;
if(now.hson==-1||son.size>tree[now.hson].size)
{
now.hson=v;
}
}
#undef v
}
}
void linkHeavyChain(cint k,cint topp)
{
#define now tree[k]
now.top=topp;
if(k!=1)
{
now.newid=++tid;
reid[tid]=k;
}
else now.newid=0;
if(now.hson!=-1)
{
linkHeavyChain(now.hson,topp);
}
for(int i=now.edge1;i!=0;i=edge[i].nxt)
{
#define v (edge[i].to)
#define son tree[v]
if(v!=now.f&&v!=now.hson)
{
linkHeavyChain(v,v);
}
else if(v==now.f)now.lenf=edge[i].len;
#undef v
}
}
struct SEG//为了与习惯的线段树的写法兼容，其实这只是个前缀和
{
int sum[maxn];
inline void build(int ll,int rr);
inline int asksum(int ll,int rr);
}root;
inline void SEG::build(int ll,int rr)
{
memset(sum,0,(n+1)*sizeof(int));
for(int i=ll;i<=rr;++i)
{
sum[i]=sum[i-1]+tree[reid[i]].lenf;
}
}
inline int SEG::asksum(int ll,int rr)
{
return sum[rr]-sum[ll-1];
}
struct PLAN
{
int u,v,len;
void measure();
}plan[maxn];
int pk=0;
bool cmp(const PLAN& a,const PLAN& b)
{
return a.len>b.len;
}
void PLAN::measure()
{
int a=u,b=v;
len=0;
int ta=tree[a].top,tb=tree[b].top;
while(ta!=tb)
{
if(tree[ta].depth<tree[tb].depth)
{
Swap(ta,tb);
Swap(a,b);
}
len+=root.asksum(tree[ta].newid,tree[a].newid);
a=tree[ta].f;
ta=tree[a].top;
}
if(tree[a].depth<tree[b].depth)
Swap(a,b);
len+=root.asksum(tree[tree[b].hson].newid,tree[a].newid);
}
int maxl=-inf;
void input()
{
read(n),read(m);
int x,y,z;
for(int i=1;i<=n-1;++i)
{
read(x),read(y),read(z);
addEdge(x,y,z);
addEdge(y,x,z);
}
}
void inputPlan()
{
int x,y;
for(int i=1;i<=m;++i)
{
read(x),read(y);
plan[++pk].u=x;
plan[pk].v=y;
plan[pk].measure();
if(plan[pk].len>maxl)
maxl=plan[pk].len;
}
sort(plan+1,plan+pk+1,cmp);
}
int vis[maxn];
void go(int k)
{
int a=plan[k].u,b=plan[k].v;
int lens=0;
int ta=tree[a].top,tb=tree[b].top;
while(ta!=tb)
{
if(tree[ta].depth<tree[tb].depth)
{
Swap(ta,tb);
Swap(a,b);
}
vis[tree[ta].newid]+=1;
if(tree[a].newid!=n-1)
vis[tree[a].newid+1]-=1;
a=tree[ta].f;
ta=tree[a].top;
}
if(tree[a].depth<tree[b].depth)
Swap(a,b);
if(tree[b].newid!=n-1)
vis[tree[tree[b].hson].newid]+=1;
if(tree[a].newid!=n-1)
vis[tree[a].newid+1]-=1;
}
bool judge(int k)
{
int rb;
for(rb=0;rb+1<=pk&&plan[rb+1].len>k;++rb);
if(rb==0)return true;
memset(vis+1,0,n*sizeof(int));
for(int i=1;i<=rb;++i)
{
go(i);
}
int sum=vis[1];
for(int i=2;i<=n;++i)
{
sum+=vis[i];
if(sum==rb
&&plan[1].len-tree[reid[i]].lenf<=k)
{
return true;
}
}
return false;
}
int BS()
{
int l=0,r=maxl,mid,ans=-33169;
while(l<=r)
{
mid=(l+r)>>1;
if(judge(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
int main()
{
freopen("transport.in","r",stdin);
//freopen("transport.out","w",stdout);
input();
findHeavySon(1,0,0);
linkHeavyChain(1,1);
root.build(1,tid);
inputPlan();
printf("%d\n",BS());
return 0;
}
|
