北航算法第二次练习赛 | Eternal_zttz

北航算法第二次练习赛

算法练习记录系列,北航算法第二次练习赛。

A DH的字符串游戏

解题思路

这一题要求是判断字符串等价,然而给出的字符串等价的定义却有一点的坑。我们看一看他的要求:

  1. 若单个字符串长度为奇数,则两字符串只有完全相等才可称为等价
  2. 若单个字符串长度为偶数,则将a从中间分为长度相等的两半,记为a1和a2,将b从中间分为长度相等的两半,记为b1和b2,满足a1与b1等价且a2与b2等价,或者a1与b2等价且a2与b1等价,称a与b等价

毫无疑问,对于奇数字符串好求,直接依次判断一遍即可。

然而对于偶数字符串,我们可以看到,它需要前后两部分互判。对于这个过程,我们可以举一个简单例子思考一下:

如果是两个长度为8的字符串,那么首先我们要将其一分为二,判断前后长度为4是是否等价,对于长度为4的前后两部分,我们需要继续一分为二,判断为2时是否相等,长度为2时我们判断长度为1时前后是否相等··· ···

由此我们可以看到,对于偶数的判断,本质上是一个递归的过程,所以我们可以写出以下代码:

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
#include <cstdio>
#include <cstring>
const int N = 200001;
char a[N],b[N];
int cmp(char a[],char b[],int num){
int flag = 0;
if(num%2 == 1){
for (int i = 0;i<num;i++){
if(a[i] != b[i]){
flag = 1;
break;
}
}
return flag;
}
else{
int x = num/2;
char a1[x],a2[x],b1[x],b2[x];
for (int i =0 ;i<x;i++){
a1[i] = a[i];a2[i] = a[i+x];
b1[i] = b[i];b2[i] = b[i+x];
}
if((cmp(a1, b1,x)==0&&cmp(a2, b2,x)==0)||(cmp(a1, b2, x)==0&&cmp(a2, b1, x)==0))
flag = 0;
else
flag = 1;
return flag ;
}
}
int main(){
while(~scanf("%s",a)){
scanf("%s",b);
int num = strlen(a);
int ans = cmp(a, b, num);
if(ans == 0) printf("YES\n");
else printf("NO\n");
}
}

B ModricWang的布线问题 II

解题思路

本质上这是一个求最小生成树的问题,只是有一个点需要特殊处理而已。

需要注意的是,ModricWang的计算机并不全都很强。他有一台计算机的承载能力有限,只能接入一根网线。

既然只能接入一根网线,那么,毫无疑问,应该接入的是与这个点相连的最短的那根网线,那么首先应该求出除该点外n-1个点所构成的最小生成树,最后加入这条边即可。

使用kruskal算法求解

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge{
int u,v,w;
}edge[600005];
int fa[10001],n,m,ans,eu,ev,cnt,k;
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int find(int x){
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
void kruskal(){
sort(edge,edge+m,cmp);
for( int i=0;i<m;i++){
if(edge[i].u == k||edge[i].v == k) continue; //如果这条边与K点相连,那么跳过
eu=find(edge[i].u); ev=find(edge[i].v);
if(eu==ev)
continue;
ans+=edge[i].w;
fa[ev]=eu;
if(++cnt==n-2)//前n-1个点的最小生成树已找到
break;
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
int min = 999999999;
for( int i=1;i<=n;i++)
fa[i]=i;
for( int i=0;i<m;i++){
scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
if(edge[i].u == k||edge[i].v == k){
if(edge[i].w<min){
min = edge[i].w;
}
}
}
kruskal();
ans+=min;//接入与k点相连的最小的边
printf("%d",ans);
return 0;
}

C Mdd去旅游(II)

解题思路

深度优先遍历。以地点为点,线路为边,建立一个无向图,从任意顶点开始,对图进行深度优先遍历活着广度优先遍历,如果能够遍历到所有的顶点,那么就说明可以到所有的地点,反之说明到不了。

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
#include <cstdio>
#include <cstring>
int e[101][101],vis[101];
int k,m;
int ans;
void dfs(int x){
vis[x]=1;
ans++;
int i;
for(i=0;i<k;i++)
if(e[x][i]&&!vis[i])
dfs(i);
}
int main(){
while(~scanf("%d %d",&k,&m)){
ans =0;
memset(vis,0,sizeof(vis));
memset(e,0,sizeof(e));
for (int i =0 ;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
e[a][b] = 1;
e[b][a] = 1;
}
dfs(0);
if(ans == k)
printf("Yes\n");
else
printf("No\n");
}
}

D ModricWang的局域网

解题思路

这一题同上一题一样,也是遍历整个图。从1~n依次判断,对于其中的某个顶点i,如果没有遍历过这个顶点,那么从这个顶点开始,再进行一次遍历,看到最后需要遍历多少次,那么这个结果就是答案。

深度优先遍历或者广度优先遍历都行。

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
#include <cstdio>
const int N = 1001;
int n,m,ans;
int e[N][N],vis[N];
void dfs(int x){
vis[x] = 1;
for (int i = 1;i<=n;i++){
if(!vis[i]&&e[x][i] == 1){
dfs(i);
vis[i] = 1;
}
}
}
int main(){
scanf("%d %d",&n,&m);
for (int i = 0;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
e[a][b] = 1;
e[b][a] = 1;
}
for (int i =1;i<=n;i++){
if(!vis[i]){
dfs(i);
ans++;
}
}
printf("%d",ans);
return 0;
}

E Mdd去旅游(III)

解题思路

这一题看着和第三题的题目非常的像,所有一上来我就是邻接表+深度优先搜索,结果,果不其然,因为时间复杂度过高,TLE了。经过上网找资料blog写题法

原来这题考的是并查集!

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100001;
int ver[N],ans[N];
int n,m,u,v;
int find(int a){
if(ver[a]!=a)
ver[a] = find(ver[a]);
return ver[a];
}
int main(){
memset(ans,0,sizeof(ans));
scanf("%d %d",&n,&m);
for (int i = 0;i<n;i++)
ver[i] = i;
for (int i = 0;i<m;i++){
scanf("%d %d",&u,&v);
int eu,ev;
eu = find(u);
ev = find(v);
if(eu!=ev) ver[ev] = eu;
}
for(int i=0;i<n;i++)
ans[ver[i]]++;
sort(ans,ans+n);
printf("%d\n",ans[n-1]);
}

F DH去看球

解题思路

emmm 因为这题,成功达成两页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
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
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define M 1000005
#define N 1005
#define INF 1e13
typedef long long ll;
struct node {
ll u,v,w,next;
};
ll dis[N][N];
ll head[N],len[N],head2[N],len2[N];
bool vis[N];
ll n,m,cnt;
void add(node edge[],ll u,ll v,ll w){
edge[cnt]={u,v,w,head[u]};
head[u] = cnt++;
}
ll first,tag;
//for dijkstra
ll ddis[N];
bool dvis[N];
ll de[N][N];
void dijkstra(){
for (int i = 1;i<=n;i++){
ddis[i] = de[first][i];
dvis[i] = false;
}
dvis[first] = true;
int u =1;
for (int i =1;i<=n;i++){
long long min = INF;
for (int j =1;j<=n;j++){
if(!dvis[j]&&ddis[j]<min){
min = ddis[j];
u = j;
}
}
dvis[u] = true;
for (int v = 1;v<=n;v++){
if(de[u][v]<INF){
if(!dvis[v]&&ddis[v]>ddis[u]+de[u][v]){
ddis[v] = ddis[u]+de[u][v];
}
}
}
}
}
void SPFA(queue<ll>q,node edge[],ll s){
q.push(s);
vis[s] = true;
for (int i=1;i<=n;i++)
len[i] = INF;
len[s] = 0;
while(!q.empty()){
ll u = q.front();
q.pop();
vis[u] = false;
for (ll i = head[u];i>0;i=edge[i].next){
ll v = edge[i].v;
ll w = edge[i].w;
if(len[v]> len[u]+w){
len[v] =len[u]+w;
if(!vis[v]){
vis[v] =true;
q.push(v);
}
}
}
}
}
int main(){
while(~scanf("%lld %lld",&n,&m)){
for (int i = 0;i<=n;i++){
for (int j = 0;j<=n;j++)
dis[i][j] = INF;
}
scanf("%lld %lld",&first,&tag);
node edge[2*m+1];

cnt = 1;
memset(head,0, sizeof(head));
queue<ll>q;
queue<ll>q2;
for (int i =1;i<=m;i++){
ll u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
add(edge,u,v,w);
add(edge,v,u,w);
}
cnt = 1;
ll pri[n+1][2];
for (int i = 1;i<=n;i++)
scanf("%lld %lld",&pri[i][0],&pri[i][1]);
for (int i = 1;i<=n;i++){
memset(len,0,sizeof(len));
memset(vis,false,sizeof(vis));
SPFA(q,edge,i);
for (int j = 1;j<=n;j++){
dis[i][j] = len[j];
}
}

memset(ddis,0,sizeof(ddis));
memset(dvis,0,sizeof(dvis));
for (int i = 1;i<=n;i++){
for (int j = 1;j<=n;j++)
de[i][j] = i==j? 0:INF;
}
for (int i = 1;i<=n;i++){
for (int j =1;j<=n;j++){
if(i!=j&&dis[i][j]<=pri[i][0])
de[i][j] = pri[i][1];
}
}
dijkstra();
if(ddis[tag] == INF) printf("-1\n");
else printf("%lld\n",ddis[tag]);
}
}

其实可以只写一个最短路算法重复调用的,然而我太弱了,重复调用SPFA总是Runtime Error,迫不得已写了个dijkstra算法

G DH的魔法光束

解题思路

这题有点意思,看到最后求的是最少需要使用多少次魔法,我想的对每个再第一行的每一个#点当作顶点跑最短路算法,然后计算到第n行最少需要多少次转向。然而1000*1000的矩阵最复杂情况下有10^6个顶点,每个顶点有1999条边,果不其然,runtime error其实即使代码写对了最后也是TLE的,本着偷看题解学习的精神。原来要对行列为点建图!!!

具体做法是:第1 ~n 行看为第1~n个顶点,第1~m列看为第n+1~n+1+m个顶点,然后对于每个#,相当于边建图,比如 a[i][j] == '#',那么说明 第 i个顶点和第j+i+n个顶点是相通的,这一点很重要,理由很显然,如果 a[i][j] == '#',那么说明如果光可以到达a[i][j],便可以使用魔法到第i行或是第j列,那么根据我们建图的定义,即可以到达第i个顶点或是第j+1+n个顶点,那么他们之间肯定是相通的。

权值为1,建好图后跑一遍最短路即可

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
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define INF 9999
#define N 1010
char a[N][N];
vector<int> edge[2010];
int d[2010];
int n,m;
void dijkstra(){
int t;
priority_queue<pair<int,int>,vector<pair<int ,int>>,greater<pair<int ,int>>>q;
for (int i = 0;i<n+m;i++)
d[i] = INF;
d[0] = 0;
q.push(make_pair(0, 0));
while(!q.empty()){
t = q.top().second;
q.pop();
for (int i = 0;i<edge[t].size();i++){
if(d[edge[t][i]]>d[t]+1){
d[edge[t][i]]=d[t]+1;
q.push(make_pair(d[edge[t][i]], edge[t][i]));
}
}
}
return;
}

int main(){
while(~scanf("%d %d",&n,&m)){
memset(d, 0, sizeof(d));
for (int i =0 ;i<n;i++)
scanf("%s",a[i]);
for (int i = 0;i<n;i++)
for (int j =0 ;j<m;j++)
if(a[i][j] == '#'){
edge[i].push_back(j+n);
edge[j+n].push_back(i);
}
dijkstra();
if(d[n-1]!=INF) printf("%d\n",d[n-1]);
else printf("-1\n");
for (int i = 0;i<n+m;i++)
edge[i].clear();
}
return 0;
}

H DH的满k叉树

解题思路

传送门 走一波~
我还是太弱了

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
#include <cstdio>
#include <cstring>
#define maxN 110
#define N 1000000007
void findans(long long ansx[],int n,int x){
ansx[0] = 1;
for (int i = 1,pos = 0;i<=n;i++){
if(i>=x+1) pos -= ansx[i-x-1];
pos += ansx[i-1];
if(pos<0) pos += N;
else pos %= N;
ansx[i] = pos;
}
}
int main(){
int n,k,d;
while(~scanf("%d %d %d",&n,&k,&d)){
long long ans[maxN],ans2[maxN];
memset(ans,0,sizeof(ans));
memset(ans2,0,sizeof(ans2));
findans(ans, n, k);
findans(ans2, n, d-1);
if(ans[n]<ans2[n]) ans[n] += N;
if(d==1) printf("%lld\n",ans[n]);
else printf("%lld\n",ans[n]-ans2[n]);
}
}
-------------The End-------------