发表更新计算机 / 算法竞赛12 分钟读完 (大约1839个字)0次访问

2018年计算机科学与工程学院新生赛2

ACM新生赛总结2，加油！

A#

336. 酋雷姆
这题想法很好，把看似两种不同的毁灭世界方法统一成一种。
假想一个世界0，它在开始时就已经毁灭，并且把世界0和世界$i$连接需要花费$w_i$。
这样问题就变成求完全图的最小生成树了。

Kruskal算法#

时间复杂度$O(E\lg E)$，可能常数偏大，并查集并未写按秩合并的功能。

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
#include <bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,w;
	edge(int u,int v,int w):u(u),v(v),w(w){}
};
vector<edge> E;
int Set[505];
bool cmp(edge x,edge y){
	return x.w<y.w;
}
int Find(int x){
	return Set[x]=((x==Set[x])?x:Find(Set[x]));
}
void Union(int x,int y){
	Set[Find(x)]=Find(y);
}
int main(){
	//freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int w;
		scanf("%d",&w);
		E.push_back(edge(0,i,w));
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int w;
			scanf("%d",&w);
			if(i>j)E.push_back(edge(i,j,w));
			//E.push_back(edge(i,j,w));
		}
	}
	sort(E.begin(),E.end(),cmp);
	for(int i=0;i<=n;i++){
		Set[i]=i;
	}
	long long ans=0;
	for(auto i:E){
		if(Find(i.u)!=Find(i.v)){
			ans+=i.w;
			Union(i.u,i.v);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Prim算法#

时间复杂度$O(E\lg V)$，采用了优先队列优化，若用斐波那契堆实现优先队列可优化到$O(V\lg V)$。

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
#include <bits/stdc++.h>
using namespace std;
struct edge{
	int v,w;
	edge(int v,int w):v(v),w(w){}
};
vector<edge> G[505];
struct cmp{
	bool operator()(edge a,edge b){
		return a.w>b.w;
	}
};
int vis[505];
priority_queue<edge,vector<edge>,cmp> Q;
int main(){
	//freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int w;
		scanf("%d",&w);
		G[0].push_back(edge(i,w));
		G[i].push_back(edge(0,w));
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int w;
			scanf("%d",&w);
			if(i>j){
				G[i].push_back(edge(j,w));
				G[j].push_back(edge(i,w));
				//printf("add edge(%d,%d) and edge(%d,%d)\n",j,w,i,w);
			}
		}
	}
	vis[0]=1;
	for(auto i:G[0])Q.push(i);
	int count=1;
	long long ans=0;
	while(count<=n){
		while(vis[Q.top().v])Q.pop();
		edge u=Q.top();
		vis[u.v]=1;
		for(auto i:G[u.v]){
			Q.push(i);
		}
		ans+=u.w;
		count++;
		//printf("u.v=%d,u.w=%d,ans=%d\n",u.v,u.w,ans);
	}
	printf("%lld\n",ans);
	return 0;
}

B#

337. 岩殿居蟹
把题目给的式子拆开，可以发现只要维护$A_i$与$i\times A_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
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100005;
const long long M=1000000007ll;
long long n,a[N],b[N];
int lowbit(int x){
	return x&(-x);
}
void add(long long *arr,int x,int v){
	while(x<=n){
		arr[x]+=v;
		x+=lowbit(x);
	}
}
long long sum(long long *arr,int x){
	long long ans=0;
	while(x>0){
		ans+=arr[x];
		while(ans>=M)ans-=M;
		//ans%=M;
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//cin>>n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int x;
		//cin>>x;
		scanf("%d",&x);
		add(a,i,x);
		add(b,i,i*x);
	}
	/*for(int i=1;i<=n;i++){
		printf("a[%d]=%lld,b[%d]=%lld\n",i,sum(a,i)-sum(a,i-1),i,sum(b,i)-sum(b,i-1));
	}*/
	int m;
	cin>>m;
	for(int i=1;i<=m;i++){
		char s;
		int x,y;
		//cin.get();
		//cin>>s>>x>>y;
		scanf(" %c%d%d",&s,&x,&y);
		if(s=='C'){
			int temp=sum(a,x)-sum(a,x-1);
			add(a,x,-temp+y);
			add(b,x,-x*temp+x*y);
		}else if(s=='Q'){
			long long ans=sum(b,y)-sum(b,x-1)-((x-1)*sum(a,y))+((x-1)*sum(a,x-1));
			while(ans<0)ans+=M;
			while(ans>=M)ans-=M;
			//cout<<ans<<endl;
			printf("%lld\n",ans);
		}
		/*printf("after i=%d\n",i);
		for(int i=1;i<=n;i++){
			printf("a[%d]=%lld,b[%d]=%lld\n",i,sum(a,i)-sum(a,i-1),i,sum(b,i)-sum(b,i-1));
		}*/
	}
	
	return 0;
}

C#

338. 三首恶龙
问至少有多大，显然可以二分x，对每个x判断是否可行。
判断x时贪心选择即可。

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
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100005;
int n,m,a[N];
int check(int x){
	int i=1,d=0;
	while(1){
		d++;
		int mm=a[i++];
		while(i<=n&&mm+a[i]<=x){
			mm+=a[i];
			i++;
		}
		if(d>m)return 0;
		if(i>n)break;
	}
	return 1;
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n>>m;
	int Max=0,Sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>Max)Max=a[i];
		Sum+=a[i];
	}
	int l=Max,r=Sum;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
		//printf("l=%d,r=%d,mid=%d\n",l,r,mid);
	}
	cout<<l<<endl;
	return 0;
}

D#

339. 谜拟Ｑ

E#

340. 单首龙
题解说是dp，但我暴力二分也过了。
显然只需考虑最大沿主对角线对称子矩阵。
同样是求最大，而且注意到，这个最大的子矩阵的子矩阵也必然是沿主对角线对称的。
对每一个x暴力判断是否存在大小为x的沿主对角线对称子矩阵。
复杂度有点难分析，可能约为$O(n^3\lg 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
#include <iostream>
#include <cstdio>
using namespace std;
const int N=505;
int n,a[N][N];
int check(int x){
	for(int i=1;i<=n-x+1;i++){
		for(int j=1;j<=n-x+1;j++){
			int flag=1;
			for(int ii=1;ii<=x;ii++){
				for(int jj=ii+1;jj<=x;jj++){
					if(a[i+ii-1][j+jj-1]!=a[i+jj-1][j+ii-1]){
						flag=0;
						break;
					}
				}
				if(flag==0)break;
			}
			if(flag==1)return 1;
		}
	}
	return 0;
}
int main(){
	//freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
		//printf("l=%d,r=%d,mid=%d\n",l,r,mid);
	}
	cout<<l<<" 1\n";
	return 0;
}

dp做法#

此题也可利用dp，用$f[i][j]$表示以原矩阵第$i$行第$j$列为右下角的最大沿主对角线对称子矩阵边长。
则计算$f[i][j]$时只需从小到大枚举一个边长$k$，比较第$i$行第$j$列对应数值是否相同，同时判断$f[i-1][j-1]\ge k-1$是否成立即可。
复杂度为$O(n^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
#include <bits/stdc++.h>
using namespace std;
int a[505][505],f[505][505];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=n;j>=1;j--){
			scanf("%d",&a[i][j]);
			f[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int op=f[i-1][j+1];
			int flag=1,k;
			for(k=1;k<=op;k++){
				if(a[i-k][j]!=a[i][j+k]){
					flag=0;
					break;
				}
			}
			if(flag==0)f[i][j]=k;
			else f[i][j]=op+1;
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans=max(ans,f[i][j]);
	printf("%d 1\n",ans);
	return 0;
}

F#

341. 爆香猴
广搜。。。
为什么我广搜都不会。

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 <bits/stdc++.h>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;
int x[N],y[N],r[N],vis[N][N];
struct node{
	int x,y,t;
	node(int x,int y,int t):x(x),y(y),t(t) {}
};
queue<node> Q;
int main(){
	//freopen("input.txt","r",stdin);
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&x[i],&y[i],&r[i]);
	}
	int sx,sy,gx,gy;
	scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
	for(int t=1;t<=k;t++){
		for(int i=-r[t];i<=r[t];i++){
			for(int j=-r[t];j<=r[t];j++){
				if(x[t]+i>=1&&x[t]+i<=n&&y[t]+j>=1&&y[t]+j<=m&&abs(i*i)+abs(j*j)<=r[t]*r[t])vis[x[t]+i][y[t]+j]=1;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ",vis[i][j]);
		}
		puts("");
	}*/
	if(vis[sx][sy]||vis[gx][gy]){
		puts("-1");
		return 0;
	}
	//BFS
	Q.push(node(sx,sy,0));
	int ans=INF;
	while(!Q.empty()){
		node u=Q.front();
		//printf("When BFS (%d,%d):\n",u.x,u.y);
		Q.pop();
		if(vis[u.x][u.y])continue;
		vis[u.x][u.y]=1;
		if(u.x==gx&&u.y==gy&&u.t<ans){
			ans=u.t;
			continue;
		}
		if(u.t>=ans)continue;
		if(u.x>1&&!vis[u.x-1][u.y]){
			Q.push(node(u.x-1,u.y,u.t+1));
			//printf("\tpush(%d,%d)\n",u.x-1,u.y);
		}
		if(u.y>1&&!vis[u.x][u.y-1]){
			Q.push(node(u.x,u.y-1,u.t+1));
			//printf("\tpush(%d,%d)\n",u.x,u.y-1);
		}
		if(u.x<n&&!vis[u.x+1][u.y]){
			Q.push(node(u.x+1,u.y,u.t+1));
			//printf("\tpush(%d,%d)\n",u.x+1,u.y);
		}
		if(u.y<m&&!vis[u.x][u.y+1]){
			Q.push(node(u.x,u.y+1,u.t+1));
			//printf("\tpush(%d,%d)\n",u.x,u.y+1);
		}
	}
	if(ans!=INF)printf("%d\n",ans);
	else puts("-1");
	return 0;
}

G#

342. 战槌龙
2018 ICPC沈阳站 热身赛B——CLS and LCS
题意 ： A和B两字符串的LCS长度是k，现给定A和k，输出一个B。
思路 ： 统计A中出现次数最少的字母，例如是a，就将B置为N个a，然后从前往后把A中不是a的字母替换B中字母，替换k-a个即可。
例如 A ：acbdbaaad N = 9， K = 8.
其中c个数最少，则B = ccccccccc
K - c个数 = 7
则B = acbdbaaac。
构造题很玄学。。
思路不是很清晰，慢慢想一下。。

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 <bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N],b[N],c[N];
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		c[a[i]]++;
	}
	int mini=1;
	for(int i=2;i<=m;i++){
		if(c[i]<c[mini])mini=i;
	}
	if(c[mini]>k||k>n){
		puts("-1");
		return 0;
	}
	//printf("mini=%d\n",mini);
	for(int i=1;i<=n;i++){
		if(a[i]==mini)b[i]=mini;
	}
	int cnt=k-c[mini];
	for(int i=1;i<=n;i++){
		if(a[i]!=mini){
			b[i]=a[i];
			cnt--;
		}
		if(cnt==0)break;
	}
	for(int i=1;i<=n;i++){
		if(b[i]==0)b[i]=mini;
	}
	for(int i=1;i<=n;i++){
		printf("%d ",b[i]);
	}
	puts("");
	return 0;
}

H#

343. 牙牙

I#

344. 基格尔德
暴力匹配。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int N=10005;
char S[N],T[12];
int main(){
	//freopen("input.txt","r",stdin);
	cin>>S;
	int n,len=strlen(S);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>T;
		int cnt=0,lent=strlen(T);
		for(int j=0;j<lent;j++){
			if(T[j]=='A')T[j]='T';
			else if(T[j]=='T')T[j]='A';
			else if(T[j]=='G')T[j]='C';
			else if(T[j]=='C')T[j]='G';
		}
		for(int j=0;j<=len-lent;j++){
			int f=1;
			for(int k=0;k<lent;k++){
				if(T[k]!=S[j+k]){
					f=0;
					break;
				}
			}
			if(f)cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

J#

345. 变隐龙
大坑题。题意非常简单，就是数字有点大。
但是我没注意到在unsigned long long范围内。
一开始用两个long long 计算一直WA。
含泪打了个高精度模版通过。
后来才听说long double也能过。

C++高精度模版做法：#

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int base=10000;
const int width=4;
const int N=1000;
struct bint{
	int ln,v[N];
	bint (long long r=0){
		for(ln=0;r>0;r/=base)v[ln++]=r%base;
	}
	bint& operator=(const bint&r){
		memcpy(this,&r,(r.ln+1)*sizeof(int));
		return *this;
	}
};
bool operator<(const bint&a,const bint&b){
	int i;
	if(a.ln!=b.ln) return a.ln<b.ln;
	for(i=a.ln-1;i>=0&&a.v[i]==b.v[i];i--);
	return i<0?0:a.v[i]<b.v[i];
}
bint operator+(const bint&a,const bint&b){
	bint res;int i,cy=0;
	for(i=0;i<a.ln||i<b.ln||cy>0;i++){
		if(i<a.ln)cy+=a.v[i];
		if(i<b.ln)cy+=b.v[i];
		res.v[i]=cy%base;
		cy/=base;
	}
	res.ln=i;
	return res;
}
void write(const bint&v){
	int i;
	printf("%d",v.ln==0?0:v.v[v.ln-1]);
	for(i=v.ln-2;i>=0;i--)
		printf("%04d",v.v[i]);
	printf("\n");
}
int main(){
	//freopen("input.txt","r",stdin);
	int n;
	cin>>n;
	bint ans(0);
	for(int i=1;i<=n;i++){
		long long x;
		cin>>x;
		if(x<0)x=-x;
		bint tx(x);
		ans=ans+tx;
	}
	write(ans);
	return 0;
}

C++unsigned long long 做法：#

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	unsigned long long ans=0;
	scanf("%d",&n);
	while(n--){
		long long x;
		scanf("%lld",&x);
		ans+=abs(x);
	}
	printf("%llu\n",ans);
}

C++long double做法#

这里x的读入用long long也行，取绝对值最好用fabs，但经过测试用abs也可通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	long double ans=0;
	cin>>n;
	while(n--){
		long double x;
		cin>>x;
		ans+=fabs(x);
	}
	cout<<fixed<< setprecision(0)<<ans;
}

参考资料#

题解
优秀代码

2018年计算机科学与工程学院新生赛2

https://blog.tootal.xyz/posts/scutpc2018-summary2/

作者

黄智权

本文发布于

2018-12-02

本文更新于

2018-12-02

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

×