2018年全国多校算法寒假训练营练习比赛（第四场）

刚开始题目读错了，乱交了4发，然后终于读对题目，想用匈牙利算法跑2分匹配，但是比赛的时候不会跑，赛后学了一下，补了一下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 55*55;
 4 string str[55];
 5 int cnt = 0, tot, n;
 6 int dx[4] = {1,-1,0,0};
 7 int dy[4] = {0,0,1,-1};
 8 int head[N], to[N], nt[N], link[N];
 9 bool vis[N];
10 int id(int x, int y)
11 {
12     return x*n+y;
13 }
14 void add_edge(int u, int v)
15 {
16     to[tot] = v;
17     nt[tot] = head[u];
18     head[u] = tot++;
19 }
20 bool hun(int u)
21 {
22     for(int i = head[u]; ~i; i = nt[i]){
23         if(!vis[to[i]]){
24             vis[to[i]] = 1;
25             if(-1 == link[to[i]]|| hun(link[to[i]])){
26                 link[u] = to[i];
27                 link[to[i]]=u;
28                 return 1;
29             }
30         }
31     }
32     return 0;
33 }
34 int main()
35 {
36     ios::sync_with_stdio(false);
37     cin.tie(0);
38     cout.tie(0);
39     int T, Case = 1;
40     cin >> T;
41     while(T--)
42     {
43         tot = 0, cnt = 0;
44         memset(head, -1, sizeof(head));
45         memset(link, -1, sizeof(link));
46         cin >> n;
47         for(int i = 0; i < n; i++)
48             cin >> str[i];
49         for(int i = 0; i < n; i++){
50             for(int j = 0; j < n; j++){
51                 if(str[i][j] == '#'){
52                     for(int k = 0; k < 4; k++){
53                         int tx = i + dx[k];
54                         int ty = j + dy[k];
55                         if(tx < 0 || tx >= n || ty < 0 || ty >= n) continue;
56                         if(str[tx][ty] == '#') add_edge(id(i,j), id(tx,ty));
57                     }
58                 }
59             }
60         }
61         for(int i = 0; i < n; i++){
62             for(int j = 0; j < n; j++){
63                 if(str[i][j] == '#'){
64                     if(-1 == link[id(i,j)]){
65                         memset(vis, 0, sizeof(vis));
66                         if(hun(id(i,j)))
67                             cnt++;
68                     }
69                 }
70             }
71         }
72         cout <<"Case " << Case++ <<": " <<cnt << endl;
73     }
74     return 0;
75 }

View Code

B: 道路建设

一道很裸的最小生成数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int pre[1000];
 4 struct Node
 5 {
 6     int u, v, c;
 7     bool operator < (const Node & x) const
 8     {
 9         return c < x.c;
10     }
11 }E[10000];
12 int n, m, Max;
13 int Find(int x)
14 {
15     if(x == pre[x]) return x;
16     return pre[x] = Find(pre[x]);
17 }
18 int main()
19 {
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     cout.tie(0);
23     while(cin >> Max >> n >> m )
24     {
25         for(int i = 1; i <= m; i++)
26             pre[i] = i;
27         for(int i = 1; i <= n; i++)
28         {
29             cin >> E[i].u >> E[i].v >> E[i].c;
30         }
31         sort(E+1, E+1+n);
32         for(int i = 1; i <= n; i++)
33         {
34             int x = Find(E[i].u), y = Find(E[i].v);
35             if(x == y)continue;
36             Max -= E[i].c;
37             if(Max < 0) break;
38             pre[x] = y;
39         }
40         if(Max < 0)
41             cout << "No
";
42         else
43         {
44             int cnt = 0;
45             for(int i = 1; i <= n; i++)
46                 if(Find(i) == i) cnt++;
47             if(cnt == 1) cout <<"Yes
";
48             else cout <<"No
";
49         }
50     }
51     return 0;
52 }

View Code

C:求交集

比赛的时候题目没仔细读，没注意到输入的时候2个集合就是升序的，然后偷懒用set瞎几把搞了一发，然后MLE了，最后还是写了瞎几把写了一个2分查找，勉强Ac了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 int a[1000000+5];
 5 int ans[1000000+5];
 6 int n, m;
 7 bool check(int tmp)
 8 {
 9     int l = 1, r = n;
10     while(l <= r)
11     {
12         int m = r+l >> 1;
13         if(tmp == a[m]) return true;
14         if(tmp < a[m]) r = m-1;
15         else l = m+1;
16     }
17     return false;
18 }
19 int main()
20 {
21     while(~scanf("%d%d",&n,&m))
22     {
23         int tot = 0;
24         int tmp;
25         for(int i = 1; i <= n; i++)
26         {
27             scanf("%d",&a[i]);
28         }
29         sort(a+1, a+n+1);
30         for(int i = 1; i <= m; i++)
31         {
32             scanf("%d",&tmp);
33             if(check(tmp)) ans[tot++] = tmp;
34         }
35         if(tot==0) printf("empty
");
36         else
37         {
38             sort(ans,ans+tot);
39             for(int i = 0; i < tot; i++)
40                 printf("%d%c",ans[i]," 
"[tot==i+1]);
41         }
42     }
43     return 0;
44 }

View Code

D：小明的挖矿之旅

也是赛后补的，直接看别人的规律补的，算出到达这个'.'点传送门数和出去这个'.'的传送门数（都是无法往外走的情况下），最后进来和出去的门数取大就好了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string str[1005];
 4 int n, m;
 5 bool check1(int x, int y)
 6 {
 7     if(x > 0 && str[x-1][y] == '.')return true;
 8     if(y > 0 && str[x][y-1] == '.')return true;
 9     return false;
10 }
11 bool check2(int x, int y)
12 {
13     if(x+1 < n && str[x+1][y] == '.') return true;
14     if(y+1 < m && str[x][y+1] == '.') return true;
15     return false;
16 }
17 int main()
18 {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cout.tie(0);
22     while(cin >> n >> m)
23     {
24         for(int i = 0; i < n; i++)
25             cin >> str[i];
26         int cnt = 0, tohere = 0, lefthere = 0;
27         for(int  i = 0; i < n; i++)
28         {
29             for(int j = 0; j < m; j++)
30             {
31                 if(str[i][j] == '.')
32                 {
33                     cnt++;
34                     if(!check1(i,j)) tohere++;
35                     if(!check2(i,j)) lefthere++;
36                 }
37             }
38         }
39         if(cnt <= 1) cout << 0 << endl;
40         else cout << max(tohere, lefthere) << endl;
41     }
42     return 0;
43  
44 }

View Code

E:通知小弟

赛后补的，比赛的时候也想到了强连通缩点，但是和A一样，赛前也只是了解这个算法，没有具体实现过，赛后补的时候不小心写错了2个字符，修改了不下20发，才修改结束(自以为是的很了解了这个算法），然后早上队长说瞎几把乱贪心就可以过了（233，但是我还是想研究一下这个Tarjan算法）。
将每个强连通图锁点，然后找到入读为0的点，如果每个入读为0的点都能被Boss通知，那么所有人都能收到通知。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N =1100;
  4 int cnt = 0, tot, n, m, rtcnt, top;
  5 int head[N], to[N*250], nt[N*250];
  6 bool vis[N], ok[N];
  7 int a[N], rt[N], low[N];
  8 int dfn[N], in[N], ind[N], Stack[N];
  9 void init()
 10 {
 11     memset(vis, 0, sizeof(vis));
 12     memset(ind, 0, sizeof(ind));
 13     memset(ok, 0, sizeof(ok));
 14     memset(head, -1, sizeof(head));
 15     memset(low, 0, sizeof(low));
 16     memset(rt, 0, sizeof(rt));
 17     tot = 0;
 18     top = 0;
 19     cnt = 0;
 20     rtcnt = 0;
 21 }
 22 void add_edge(int u, int v)
 23 {
 24     to[tot] = v;
 25     nt[tot] = head[u];
 26     head[u] = tot++;
 27 }
 28 void dfs(int u)
 29 {
 30     low[u] = dfn[u] = ++cnt;
 31     vis[u] = in[u] = 1;
 32     Stack[++top] = u;
 33     for(int i = head[u]; ~i; i = nt[i])
 34     {
 35         int v = to[i];
 36         if(!vis[v])
 37         {
 38             dfs(v);
 39             low[u] = min(low[v], low[u]);
 40         }
 41         else if(in[v]) low[u] = min(low[v], low[u]);
 42     }
 43     if(low[u] == dfn[u])
 44     {
 45         rtcnt++;
 46         int v;
 47         while(top > 0)
 48         {
 49             v = Stack[top--];
 50             in[v] = 0;
 51             rt[v] = rtcnt;
 52             if(v == u) break;
 53         }
 54     }
 55 }
 56 void tarjan()
 57 {
 58     for(int i = 1; i <= n; i++)
 59         if(!vis[i]) dfs(i);
 60     for(int i = 1; i <= n; i++)
 61     {
 62         for(int j = head[i]; ~j; j=nt[j])
 63         {
 64             if(rt[i] != rt[to[j]])
 65                 ind[rt[to[j]]]++;
 66         }
 67     }
 68     int ret = 0;
 69     for(int i = 0; i < m; i++)
 70         ok[rt[a[i]]] = 1;
 71     for(int i = 1; i <= rtcnt; i++)
 72     {
 73         if(ind[i] == 0)
 74         {
 75             if(ok[i]) ret++;
 76             else
 77                 {
 78                     cout << -1 << endl;
 79                     return ;
 80                 }
 81         }
 82     }
 83     cout << ret << endl;
 84     return ;
 85 }
 86 int main()
 87 {
 88     ios::sync_with_stdio(false);
 89     cin.tie(0);
 90     cout.tie(0);
 91     while(cin >> n >> m)
 92     {
 93         init();
 94         for(int i = 0; i < m; i++)
 95             cin >> a[i];
 96         for(int i = 1; i <= n; i++)
 97         {
 98             int k, v;
 99             cin >> k;
100             for(int j = 1; j <= k; j++)
101             {
102                 cin >> v;
103                 add_edge(i,v);
104             }
105         }
106         tarjan();
107     }
108     return 0;
109 }

View Code

F：Call to your teacher

注意有向图，然后搜索就好了，记得每次这个人被通知过了就标记一下，免得重复搜索。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 2005;
 4 bool vis[55];
 5 int head[55], cnt = 0,n,m;
 6 struct Node
 7 {
 8     int to;
 9     int nt;
10 }E[N];
11 void add(int u, int v)
12 {
13     E[cnt].to = v;
14     E[cnt].nt = head[u];
15     head[u] = cnt++;
16 }
17 void bfs()
18 {
19     queue<int> q;
20     q.push(1);
21     vis[1] = 1;
22     while(!q.empty())
23     {
24         int tmp = q.front();
25         q.pop();
26         if(tmp == n) return ;
27         for(int i = head[tmp]; ~i; i = E[i].nt)
28         {
29             int v = E[i].to;
30             if(vis[v]) continue;
31             vis[v] = 1;
32             q.push(v);
33         }
34     }
35 }
36 int main()
37 {
38     ios::sync_with_stdio(false);
39     cin.tie(0);
40     cout.tie(0);
41     while(cin >> n >> m )
42     {
43        cnt = 0;
44        int u, v;
45        memset(vis, 0, sizeof(vis));
46        memset(head, -1, sizeof(head));
47        for(int i = 1; i <= m; i++)
48        {
49            cin >> u >> v;
50            add(u,v);
51        }
52        bfs();
53        if(vis[n]) cout << "Yes
";
54        else cout << "No
";
55     }
56     return 0;
57 }

View Code

G:老子的意大利炮呢

比赛的时候想着反向BFS，让李云龙去走路，写了半天MLE了。

MLE代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int N = 505;
 5 string str[105];
 6 int dx[4] = {1,-1,0,0};
 7 int dy[4] = {0,0,-1,1};
 8 int vis[2][2][2][105][105];
 9 int pos[5][2];
10 int v1, v2, v3, ans, n, m;
11 struct Node
12 {
13     int x, y, v;
14     int f1, f2, f3;
15     int t;
16 }tmp, nt;
17 void BFS()
18 {
19     tmp.x = pos[4][0], tmp.y = pos[4][1];
20     tmp.f1 = tmp.f2 = tmp.f3 = 1;
21     tmp.v = v1 + v2 + v3 + 1;
22     tmp.t = 0;
23     queue<Node> q;
24     q.push(tmp);
25     while(!q.empty())
26     {
27         tmp = q.front();
28         q.pop();
29         if(tmp.x == pos[0][0] && tmp.y == pos[0][1] && !tmp.f1 && !tmp.f2 && !tmp.f3)
30         {
31             ans = min(ans, tmp.t);
32             continue;
33         }
34         if(ans < tmp.t) continue;
35         nt.t = tmp.v + tmp.t;
36         for(int i = 0; i < 4; i++)
37         {
38             nt.x = tmp.x + dx[i];
39             nt.y = tmp.y + dy[i];
40             nt.v = tmp.v;
41             nt.f1 = tmp.f1, nt.f2 = tmp.f2, nt.f3 = tmp.f3;
42             if(nt.x < 0 || nt.x >= n || nt.y < 0 || nt.y >= m ) continue;
43             if(nt.x == pos[1][0] && nt.y == pos[1][1] && nt.f1) nt.f1 = 0, nt.v -= v1;
44             if(nt.x == pos[2][0] && nt.y == pos[2][1] && nt.f2) nt.f2 = 0, nt.v -= v2;
45             if(nt.x == pos[3][0] && nt.y == pos[3][1] && nt.f3) nt.f3 = 0, nt.v -= v3;
46             if(nt.f1 && nt.f2 && nt.f3 && str[nt.x][nt.y] == '#') continue;
47             if(vis[nt.f1][nt.f2][nt.f3][nt.x][nt.y] < nt.t) continue;
48             vis[nt.f1][nt.f2][nt.f3][nt.x][nt.y] = nt.t;
49             q.push(nt);
50         }
51     }
52 }
53 int main()
54 {
55     ios::sync_with_stdio(false);
56     cin.tie(0);
57     cout.tie(0);
58     while(cin >> n >> m)
59     {
60         ans = 1e9;
61         memset(vis, INF, sizeof(vis));
62         for(int i = 0; i < n; i++)
63             cin >> str[i];
64         for(int i = 0; i < 5; i++)
65         {
66             cin >> pos[i][0] >> pos[i][1];
67             pos[i][0]--; pos[i][1]--;
68         }
69         cin >> v1 >> v2 >> v3;
70         BFS();
71         cout << ans << endl;
72     }
73     return 0;
74 }

View Code

后面烦恼的时候，突然想到更好的优化，墨迹了几分钟，修改了一下，就AC了，

还是让李云龙去走，走到“最后一个零件”，然后让和尚从自己的位置最短的距离跑到另外2个零件在跑到这个零件，取最小耗时就好了。因为和尚可以带着零件翻墙，不包括意大利炮，所以走到其他2个位置的距离是定下来的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int N = 505;
 5 string str[105];
 6 int dx[4] = {1,-1,0,0};
 7 int dy[4] = {0,0,-1,1};
 8 int vis[105][105];
 9 int pos[5][2];
10 int v[5], ans, n, m;
11 struct Node
12 {
13     int x, y;
14     int t;
15 }tmp, nt;
16 int dis(int u, int v)
17 {
18     return abs(pos[u][0]-pos[v][0]) + abs(pos[u][1]-pos[v][1]);
19 }
20 void BFS()
21 {
22     tmp.x = pos[4][0], tmp.y = pos[4][1];
23     tmp.t = 0;
24     vis[tmp.x][tmp.y];
25     queue<Node> q;
26     q.push(tmp);
27     while(!q.empty())
28     {
29         tmp = q.front();
30         q.pop();
31         for(int i = 1; i <= 3; i++)
32         {
33             if(tmp.x == pos[i][0] && tmp.y == pos[i][1])
34             {
35                 int tt = tmp.t * (v[1]+v[2]+v[3]+1);
36                 int l = i-1;
37                 int r = i+1;
38                 if(l == 0) l = 3;
39                 if(r == 4) r = 1;
40                 int t1 = (v[l]+v[r]+1)*dis(l,i)+ (v[r]+1)*dis(l,r) + 1*dis(r,0);
41                 int t2 = (v[l]+v[r]+1)*dis(r,i)+(v[l]+1)*dis(l,r)+1*dis(l,0);
42                 tt = tt+ min(t1,t2);
43                 ans = min(ans,tt);
44             }
45         }
46         nt.t = tmp.t+1;
47         for(int i = 0; i < 4; i++)
48         {
49             nt.x = tmp.x + dx[i];
50             nt.y = tmp.y + dy[i];
51             if(nt.x < 0 || nt.x >= n || nt.y < 0 || nt.y >= m) continue;
52             if(str[nt.x][nt.y] == '#' || vis[nt.x][nt.y]) continue;
53             vis[nt.x][nt.y] = 1;
54             q.push(nt);
55         }
56     }
57     return ;
58 }
59 int main()
60 {
61     ios::sync_with_stdio(false);
62     cin.tie(0);
63     cout.tie(0);
64     while(cin >> n >> m)
65     {
66         ans = 1e9;
67         memset(vis, 0, sizeof(vis));
68         for(int i = 0; i < n; i++)
69             cin >> str[i];
70         for(int i = 0; i < 5; i++)
71         {
72             cin >> pos[i][0] >> pos[i][1];
73             pos[i][0]--; pos[i][1]--;
74         }
75         cin >> v[1] >> v[2] >> v[3];
76         BFS();
77         cout << ans << endl;
78     }
79     return 0;
80 }

View Code

H:老子的全排列呢

全场最水的题，但是我不知道STL函数，最后手写的dfs搜索过的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool vis[10];
 4 int put[10];
 5 void P()
 6 {
 7     for(int i = 1; i <= 8; i++)
 8     {
 9         printf("%d%c",put[i]," 
"[i == 8]);
10     }
11 }
12 void dfs(int cnt)
13 {
14     if(cnt == 9)
15     {
16         P();
17         return;
18     }
19     for(int i = 1; i <= 8; i++)
20     {
21         if(!vis[i])
22         {
23             vis[i] = 1;
24             put[cnt] = i;
25             dfs(cnt+1);
26             vis[i] = 0;
27         }
28     }
29 }
30 int main()
31 {
32     ios::sync_with_stdio(false);
33     cin.tie(0);
34     cout.tie(0);
35     memset(vis, 0, sizeof(vis));
36     dfs(1);
37     return 0;
38 }

View Code

总结，比赛前的确了解AE2道题目的算法，但是没有自己去写过，还是要多联系联系，还有就是A题题目，没有仔细读，然后就乱交了4发，下次注意。总的来说还不错，比较是这4次比赛来的最好名次，但是很多小小的细节没有注意。