「2017-2018 ACM-ICPC NEERC」本人的第一次cf ACM-ICPC组队酱油记 | Bill Yang's Blog
0%

「2017-2018 ACM-ICPC NEERC」本人的第一次cf ACM-ICPC组队酱油记

同样的还是先写一份题解,然后再写一写我自己的情况。

比赛题目

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;
}

然后最后我们团队总分:


比赛总结

这一次比赛暴露出了一些问题。
做题始终有点思维定式,总是跟着出题人误导我们的思路走。这说明我的思维能力还是不强,需要继续锻炼与总结!

姥爷们赏瓶冰阔落吧~