同样的还是先写一份题解，然后再写一写我自己的情况。
比赛题目
A. Union of Doubly Linked Lists
题目大意： 给出若干个双向链表，将其合并为一个。
题目分析： 随便搞搞，模拟一下即可。
B. Preparing for Merge Sort
题目大意： 给出一个不含重复元素的序列，按照以下方式将这个序列拆成若干个递增序列。
- 如果有一个未选元素，就重复如下过程：
- 从左往右扫描序列，若当前数字未选且大于这一轮上一个选择的元素，就选择它。
输出每一轮选出的元素。
题目分析： 用元素去找合法的链表（轮数），即初始化所有轮的链表表头为-inf，然后从左往右遍历元素，二分这些链表找到第一个比当前元素小的链表插到末尾，输出方案即可。
C. Sum of Nestings
题目大意： 给出整数$n$,$k$，要求求出有$n$个左括号，有$k$个括号嵌套的合法括号序列。
题目分析： 考虑一下，我们可以让多个()嵌套也可以让它们并列，如果嵌套相当于嵌套个数加上了中间()的个数，而()的个数是一定的，也就是说相当于用1~$n$这$n$个数组成$k$。可以随意构造然后输出方案。
D. Dog Show
题目大意： 一条直线上有一只狗和一些食物，食物必须冷却后才能吃（每个食物有它的冷却时间）。开始狗在$x=0$的位置且只能往右走，走一步需要1的单位时间，走到食物的位置可以选择等待食物冷却或放弃它继续前走。问在规定时间内能吃到多少食物。
题目分析： 旋转坐标系然后用树状数组维护一下？尚未AC。
E. Packmen
题目大意： 一条直线上有一些星号和一些人，人可以走到星号的位置然后把它吃掉，人可以同时移动，问人吃掉星号花费的最少时间。
题目分析： 二分答案，然后转为判定性问题。可以考虑使用贪心解决这个判定性问题，用双指针维护一下搞定。（具体的我还没写）
F做不来略
G. University Classes
题目大意： 有一些班级要去上课，给出他们那些时间上课，求出最少使用多少教室。
题目分析： 暴力模拟统计每节课1出现的最大个数。
H. Load Testing
题目大意： 给出一个序列，可以对任意元素加上$x$，花费$x$的代价，现在让这个序列变成严格单峰的，求最小代价。
题目分析： 从前往后维护一个严格递增的最小代价，从后往前维护一个严格递增的最小代价。然后枚举连接位置，将代价相加，注意如果两边高度相同代价还要+1。
I/J/K/L做不来略
M. Weather Tomorrow
题目大意： 给出一个等差数列，求后一项。若不是等差数列输出数列最后一项。
题目分析： 维护公差$d$。
比赛经历
我和achen和KEKE_046组队打这次比赛，发扬了优秀的团队合作精神。
首先拿到A题，发现这题可以模拟，于是就交给KEKE_046做了，KEKE大概做了20~30分钟解决。
A题代码 by KEKE_046
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200;
int L[maxn],R[maxn],N;
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++)scanf("%d%d",&L[i],&R[i]);
for(int i=1,lst=0;i<=N;i++){
if(L[i]==0){
int p=i;while(R[p])p=R[p];
R[lst]=i;L[i]=lst;lst=p;R[0]=0;
}
}
for(int i=1;i<=N;i++)printf("%d %d\n",L[i],R[i]);
return 0;
}
|
然后开始思考B题，B题刚开始感觉挺水，模拟是$O(n^2)$的，肯定不行，然后就开始各种思考高级数据结构优化模拟，初步感觉不怎么样，achen说他来想想，于是就交给achen思考了。（事实上achen思考了1个半小时左右，于是剩下的题交给了我和KEKE）
然后我开始思考C题，发现C题类似一个构造，可以尽量的把嵌套堆在前面，然后再留下单个的放在后面。因为是等差数列增长非常快，所以说可以做。
然后我开始写C题，被罚3次时死活过不了，放弃了思考其他题。
此时KEKE已经A掉了A题，开始看D题，于是我开始看E题。
发现E题不就是以前做过的骑士？用3次状压Dp解决。However,$n\le10^5$，所以不行，重新思考另外的方法。
A*？似乎数据量太大。二分答案？似乎可以，二分答案后每个人走的只可能是一段区间，做个区间覆盖？不行，区间是动态的，长度不定，怎么办呢？听其他人说G、M题比较水，所以说先去用了20分钟把它们A了，将E题暂时放下。
G题代码 by Bill_Yang
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,cnt[15],Ans;
int main() {
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=7; j++) {
char x;
cin>>x;
if(x=='1')cnt[j]++;
}
for(int i=1; i<=7; i++)Ans=max(Ans,cnt[i]);
printf("%d\n",Ans);
return 0;
}
|
M题代码 by Bill_Yang
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,pre,d,bj=1;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
if(i>1) {
if(i==2)d=x-pre;
else if(x-pre!=d)bj=0;
}
pre=x;
}
if(bj)printf("%d\n",pre+d);
else printf("%d\n",pre);
return 0;
}
|
接下来KEKE想出了D题的做法，于是回来帮助achen思考B题，KEKE反过来思考就思考出来了：
每次迭代倒过来不就变成了区间找最大？线段树树状数组维护一下就可以了。（最后我们看题解发现都想复杂了，用元素去找链表就解决了）
然后就下三晚了，我们都回家了。
回家后achen将B题A了，然后开始思考H题。
B题代码 by achen
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
const int MAXN=200005;
int b[MAXN];
int A[MAXN];
struct SegTree
{
int l,r,mx;
}Tree[MAXN*4];
void Maintain(int v){Tree[v].mx=max(Tree[v<<1].mx,Tree[v<<1|1].mx);}
void Build(int v,int L,int R)
{
Tree[v].l=L;Tree[v].r=R;
if(L==R)
{
Tree[v].mx=A[L];
return;
}
int mid=(L+R)>>1;
Build(v<<1,L,mid);
Build(v<<1|1,mid+1,R);
Maintain(v);
}
void Update(int v,int x,int d)
{
if(Tree[v].l>x||Tree[v].r<x)return;
if(Tree[v].l>=x&&Tree[v].r<=x)
{
Tree[v].mx=d;
return;
}
Update(v<<1,x,d);
Update(v<<1|1,x,d);
Maintain(v);
}
int Query(int v,int L,int R)
{
if(Tree[v].l>R||Tree[v].r<L)return 0;
if(Tree[v].l>=L&&Tree[v].r<=R)return Tree[v].mx;
return max(Query(v<<1,L,R),Query(v<<1|1,L,R));
}
int H[MAXN];
int h[MAXN];
stack<int> S;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i];
b[i]=A[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
A[i]=lower_bound(b+1,b+n+1,A[i])-b;
H[A[i]]=i;
}
Build(1,1,n);
for(int i=1;i<=n;i++)
{
if(h[i])continue;
h[i]=1;
int mx=Query(1,i,n);
while(H[mx]!=i)
{
S.push(mx);
Update(1,H[mx],0);
mx=Query(1,i,H[mx]-1);
}
Update(1,i,0);
cout<<b[A[i]]<<' ';
while(!S.empty()){cout<<b[S.top()]<<' ';h[H[S.top()]]=1;S.pop();}
cout<<'\n';
}
return 0;
}
|
H题看了题后被我秒了，然而已经很晚了并不想敲键盘，于是交给achen写代码，achen第一次提交忘了开long long，第二次过了。
H题代码 by achen
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const ll MAXN=100005;
ll A[MAXN],fL[MAXN],fR[MAXN];
ll B[MAXN];
int main()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++)cin>>A[i];
memcpy(B,A,sizeof(A));
ll Ans=1e15;
A[0]=A[n+1]=-1e8;
for(ll i=1;i<=n;i++)
{
fL[i]=fL[i-1]+max(0ll,(A[i-1]+1)-A[i]);
A[i]=max(A[i-1]+1,A[i]);
}
B[0]=B[n+1]=-1e8;
for(ll i=n;i>0;i--)
{
fR[i]=fR[i+1]+max(0ll,(B[i+1]+1)-B[i]);
B[i]=max(B[i+1]+1,B[i]);
}
for(ll i=0;i<=n;i++)Ans=min(Ans,fL[i]+fR[i+1]+(A[i]==B[i+1]));
cout<<Ans;
return 0;
}
|
接下来我们回来思考C题，发现我最初的想法有问题，因为等差数列并不一定可以构成$k$，我当时脑袋发抽觉得只可能是纯嵌套，不可能有$(()())$的情况，然后achen写了一会儿两次A了。
C题代码 by achen
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const ll MAXN=300005;
bool h[MAXN];
char Ans[MAXN*4];
int main()
{
ll n,k;
cin>>n>>k;
if(n*(n-1)/2<k){cout<<"Impossible";return 0;}
for(ll i=n-1;i>0;i--)if(k>=i){h[i+1]=1;k-=i;}
int L=n,R=n-1;
for(ll i=1;i<=n;i++)
{
if(h[i])
{
Ans[--L]='(';
Ans[++R]=')';
}
else
{
Ans[++R]='(';
Ans[++R]=')';
}
}
for(int i=L;i<=R;i++)cout<<Ans[i];
return 0;
}
|
然后我去睡了，achen接过我的想法开始思考E题，他首先觉得这是个Dp，写了四次，被罚四次时…
然后achen发现二分答案过后可以双指针贪心，然后就开始这样写了。可是比赛已经结束了，比赛后achen提交了代码成功AC。
E题代码 by achen
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<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
const int MAXN=100005;
int A[MAXN],P[MAXN],h[MAXN],cntA,cntP;
bool Check(int T)
{
int st=1,ed=1;
for(int i=1;i<=cntP;i++)
{
while(ed<=cntA&&A[ed]-A[st]+min(abs(A[st]-P[i]),abs(A[ed]-P[i]))<=T)ed++;
st=ed;
}
return st>cntA;
}
int main()
{
int n;
cin>>n;
char x;
for(int i=1;i<=n;i++)
{
cin>>x;
if(x=='*')A[++cntA]=i;
if(x=='P')P[++cntP]=i;
}
int L=0,r=2*n,Ans;
while(L<=r)
{
int mid=(L+r)>>1;
if(Check(mid)){Ans=mid;r=mid-1;}
else L=mid+1;
}
cout<<Ans;
return 0;
}
|
然后最后我们团队总分：
比赛总结
这一次比赛暴露出了一些问题。
做题始终有点思维定式，总是跟着出题人误导我们的思路走。这说明我的思维能力还是不强，需要继续锻炼与总结！
