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

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

阅读量：5164 次

发布时间：2019-06-13

本文共 13938 字，大约阅读时间需要 46 分钟。

A. 石油采集

题意：给你一个n*n的方格，n小于50，每个方格中'.'代表水，‘#’代表油。每次你可以收集两个相邻方格里的油。问你最多能收集几次。

观察：有点像用1*2的多米诺骨牌覆盖棋盘问题，求一下二分图最大匹配。

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 const int maxn = 50;27 int n;28 char s[maxn][maxn];29 vector
                      
                        g[maxn*maxn];30 bool vis[maxn*maxn];31 int match[maxn*maxn];32 bool dfs(int cur)33 {34 for (auto nxt : g[cur])35 if (!vis[nxt])36 {37 vis[nxt] = true;38 if (match[nxt] == -1 || dfs(match[nxt]))39 {40 match[nxt] = cur;41 return true;42 }43 }44 return false;45 }46 inline int id(int i, int j)47 {48 return i*n+j;49 }50 int main()51 {52 int T;53 scanf("%d", &T);54 for (int kase = 1; kase <= T; ++kase)55 {56 scanf("%d", &n);57 for (int i = 0; i < n; ++i)58 scanf("%s", s[i]);59 for (int i = 0; i < n*n; ++i)60 g[i].clear();61 for (int i = 0; i < n; ++i)62 for (int j = 0; j < n; ++j)63 if (s[i][j] == '#')64 {65 if (i+1 < n && s[i+1][j] == '#')66 {67 g[id(i, j)].pb(id(i+1, j));68 g[id(i+1, j)].pb(id(i, j));69 }70 if (j+1 < n && s[i][j+1] == '#')71 {72 g[id(i, j)].pb(id(i, j+1));73 g[id(i, j+1)].pb(id(i, j));74 }75 }76 memset(match, -1, n*n*sizeof(int));77 int ret = 0;78 for (int i = 0; i < n; ++i)79 for (int j = i%2; j < n; j += 2)80 {81 memset(vis, 0, n*n*sizeof(bool));82 ret += dfs(id(i, j));83 }84 printf("Case %d: %d\n", kase, ret);85 }86 }

View Code

B. 道路建设

题意：最小生成树

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 const int maxn = 1e2+1, maxm = 1e4+1;27 struct Edge28 {29 int u, v, h;30 bool operator<(const Edge &r) const31 {32 return h < r.h;33 }34 void read()35 {36 scanf("%d %d %d", &u, &v, &h);37 }38 } e[maxm];39 int p[maxn];40 int n, m, c;41 void init()42 {43 for (int i = 1; i <= n; ++i)44 p[i] = i;45 }46 int pa(int id)47 {48 return id==p[id]?id:p[id]=pa(p[id]);49 }50 bool merge(int a, int b)51 {52 a = pa(a), b = pa(b);53 if (a != b)54 {55 p[a] = b;56 return true;57 }58 return false;59 }60 int main()61 {62 scanf("%d %d %d", &c, &m, &n);63 init();64 for (int i = 0; i < m; ++i)65 e[i].read();66 sort(e, e+m);67 int cost = 0;68 for (int i = 0; i < m; ++i)69 if (merge(e[i].u, e[i].v))70 cost += e[i].h;71 puts(cost <= c ? "Yes" : "No");72 }

View Code

C. 求交集

题意：给了两个大小不超过1e6的整数集合，让你将他们的交集元素按照升序输出。

观察：好多方法：可以把其中一个集合的元素放进set/hashtable，枚举另一边的元素来查找。我的做法是两个集合都排好序之后归并输出，不如前一种方法好写。

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 deque
                      
                        a, b, c;27 28 int main()29 {30 int n, m;31 scanf("%d %d", &n, &m);32 a.resize(n), b.resize(m);33 for (auto &e : a)34 scanf("%d", &e);35 for (auto &e : b)36 scanf("%d", &e);37 sort(a.begin(), a.end());38 sort(b.begin(), b.end());39 while (!a.empty() && !b.empty())40 {41 if (a.front() == b.front())42 {43 c.pb(a.front());44 a.pop_front();45 b.pop_front();46 }47 else if (a.front() < b.front())48 a.pop_front();49 else50 b.pop_front();51 }52 if (c.empty())53 puts("empty");54 else55 {56 for (int i = 0; i < c.size(); ++i)57 printf("%d%c", c[i], i+1==c.size()?'\n':' ');58 }59 }

View Code

D. 小明的挖矿之旅

题意：有一个1000*1000迷宫，里面有墙和空地，每块空地上都有金子。开始时你会被放在地图的任意空地，之后你只可以往右走或者往下走，边走可以边把路过的金子收入囊中。游戏开始时允许你在地图的一些格子放一些传送门，对于每一个传送门，你也要规定一个传送的位置，当你在游戏开始之后到达某个传送门，可以传送到该传送门的指定位置。问你一开始最少放置多少个传送门可以保证无论开局时你的位置在哪里，都可以把所有金子拿走。

观察：我们只需要把传送门安放在无路可走的位置，传送的位置只需要选择没有前驱（没有任何其他格子可以到达）的位置。看起来像是一个经典题：给你一个有向图，问你最少加多少条边可以使图强连通。但是这道题更简单一些。首先我们先特判只有一个空地的情况，此时我们不需要加任何传送门。排除了特殊情况之后，所有的连通分量都必定有一个出度为0的点和一个入度为0的点。所以保证每个连通分量都有接口。答案是max（入度为0的点的个数，出度为0的点的个数）。

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 27 const int maxn = 1e3+1;28 int n, m;29 char s[maxn][maxn];30 inline int id(int i, int j)31 {32 return i*m+j;33 }34 int in[maxn][maxn], out[maxn][maxn];35 int main()36 {37 scanf("%d %d", &n, &m);38 for (int i = 0; i < n; ++i)39 scanf("%s", s[i]);40 int cnt = 0;41 for (int i = 0; i < n; ++i)42 for (int j = 0; j < m; ++j)43 if (s[i][j] == '.')44 {45 ++cnt;46 if (i+1 < n && s[i+1][j] == '.')47 out[i][j] = in[i+1][j] = true;48 if (j+1 < m && s[i][j+1] == '.')49 out[i][j] = in[i][j+1] = true;50 }51 if (cnt <= 1)52 {53 puts("0");54 return 0;55 }56 int a = 0, b = 0;57 for (int i = 0; i < n; ++i)58 for (int j = 0; j < m; ++j)59 if (s[i][j] == '.')60 {61 if (!in[i][j])62 ++a;63 if (!out[i][j])64 ++b;65 }66 printf("%d\n", max(a, b));67 68 69 }

View Code

E. 通知小弟

题意：有一个n个点的有向图，n不超过500。初始时给你一个点集，让你选出最少的点，使得从这些点可以到达图中任何一个点。输出最小的点数，如果无解输出-1。

观察：我们先强连通分量缩点，得到一个DAG，这样DAG上入度为0的强连通分量必须都选。

code：

1 /*  2  by skydog  3  */  4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 #include 
          
             9 #include 
           
             10 #include 
            
              11 #include 
              12 #include 
              
                13 #include 
               
                 14 #include 
                
                  15 #include 
                 
                   16 #include 
                  
                    17 #include 
                   
                     18 using namespace std; 19 typedef long long ll; 20 typedef pair
                    
                      ii; 21 typedef pair
                     
                       l4; 22 typedef unsigned long long ull; 23 #define mp make_pair 24 #define pb push_back 25 26 27 const int maxn = 5e2+1; 28 int n, m; 29 vector
                      
                        g[maxn], rg[maxn]; 30 int scc[maxn], scc_cnt, in[maxn], rep[maxn]; 31 int p[maxn]; 32 void init() 33 { 34 for (int i = 1; i <= n; ++i) 35 p[i] = i; 36 } 37 int pa(int id) 38 { 39 return id==p[id]?id:p[id]=pa(p[id]); 40 } 41 void merge(int a, int b) 42 { 43 p[pa(a)] = pa(b); 44 } 45 bool vis[maxn]; 46 stack
                       
                         stk; 47 void dfs(int cur) 48 { 49 vis[cur] = true; 50 for (auto nxt : g[cur]) 51 if (!vis[nxt]) 52 dfs(nxt); 53 stk.push(cur); 54 } 55 void rdfs(int cur) 56 { 57 scc[cur] = scc_cnt; 58 for (auto nxt : rg[cur]) 59 if (!scc[nxt]) 60 rdfs(nxt); 61 } 62 int main() 63 { 64 scanf("%d", &n); 65 for (int i = 0; i <= n; ++i) 66 { 67 int sz; 68 scanf("%d", &sz); 69 g[i].resize(sz); 70 for (auto &e : g[i]) 71 { 72 scanf("%d", &e); 73 if (i) rg[e].pb(i); 74 } 75 } 76 memset(vis, 0, sizeof(vis)); 77 for (int i = 1; i <= n; ++i) 78 if (!vis[i]) 79 dfs(i); 80 while (!stk.empty()) 81 { 82 int cur = stk.top(); 83 stk.pop(); 84 if (!scc[cur]) 85 { 86 ++scc_cnt; 87 rdfs(cur); 88 } 89 } 90 init(); 91 for (int i = 1; i <= n; ++i) 92 for (auto j : g[i]) 93 if (scc[i] != scc[j]) 94 ++in[scc[j]]; 95 int ans = 0; 96 for (auto e : g[0]) 97 if (in[scc[e]] == 0) 98 { 99 ++ans;100 in[scc[e]] = 1;101 }102 for (int i = 1; i <= scc_cnt; ++i)103 if (in[i] == 0)104 {105 puts("-1");106 return 0;107 }108 printf("%d\n", ans);109 }

View Code

WA：有一个地方应该写scc的编号，但是写成了输入点的编号。

F. Call to your mother

题意：无向图判断1和n是否在同一个连通分量。

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 const int maxn = 50+1;27 vector
                      
                        g[maxn];28 int n, m;29 bool vis[maxn];30 void dfs(int cur)31 {32 vis[cur] = true;33 for (auto e : g[cur])34 if (!vis[e])35 dfs(e);36 }37 int main()38 {39 scanf("%d %d", &n, &m);40 for (int i = 0; i < m; ++i)41 {42 int u, v;43 scanf("%d %d", &u, &v);44 g[u].pb(v);45 }46 dfs(1);47 puts(vis[n]?"Yes":"No");48 }

View Code

G. 老子的意大利炮呢

题意：题目说的比较详细。一个100*100的地图，图上有两种点，空地和墙。给你五个点的坐标，分别指向是起点，三种零件所在地，终点。同时告诉你三个时间，t1, t2, t3。人在地图中可以上下左右走，每次走一步的基础耗时是1，如果身上携带物品，那么就会加上相应的ti。同时你可以走墙壁，但是如果三件物品都拿齐了，就不能走墙壁了。经过一个物品时你可以选择拿或者不拿。最后让你输出物品都拿齐到达终点的最短时间。

观察：一个状态压缩有向图最短路。用queue（spfa）或者priority_queue(Dijkstra）都能过。

code：

Dijkstra：

1 /*  2  by skydog  3  */  4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 #include 
          
             9 #include 
           
             10 #include 
            
              11 #include 
              12 #include 
              
                13 #include 
               
                 14 #include 
                
                  15 #include 
                 
                   16 #include 
                  
                    17 #include 
                   
                     18 using namespace std; 19 typedef long long ll; 20 typedef pair
                    
                      ii; 21 typedef pair
                     
                       l4; 22 typedef unsigned long long ull; 23 #define mp make_pair 24 #define pb push_back 25 26 27 const int maxn = 1e2+1; 28 char s[maxn][maxn]; 29 const int N = 3; 30 int x[3], y[3], t[3]; 31 const int maxs = 1<
                      
                        r.dis; 41 } 42 }; 43 int get(int mask) 44 { 45 int ret = 1; 46 for (int i = 0; i < 3; ++i) 47 if ((mask>>i)&1) 48 ret += t[i]; 49 return ret; 50 } 51 int dx[4] = { 1, 0, -1, 0}; 52 int dy[4] = { 0, 1, 0, -1}; 53 int main() 54 { 55 scanf("%d %d", &n, &m); 56 for (int i = 0; i < n; ++i) 57 scanf("%s", s[i]); 58 memset(d, -1, sizeof(d)); 59 scanf("%d %d", &sx, &sy), --sx, --sy; 60 for (int i = 0; i < 3; ++i) 61 scanf("%d %d", x+i, y+i), --x[i], --y[i]; 62 scanf("%d %d", &ex, &ey), --ex, --ey; 63 for (int i = 0; i < 3; ++i) 64 scanf("%d", t+i); 65 priority_queue
                       
                         q; 66 d[sx][sy][0] = 0; 67 q.push((State){sx, sy, 0, 0}); 68 while (!q.empty()) 69 { 70 int cx = q.top().x, cy = q.top().y, mask = q.top().mask; 71 int t = d[cx][cy][mask]; 72 if (t != q.top().dis) 73 { 74 q.pop(); 75 continue; 76 } 77 //cerr << cx << " " << cy << " " << mask << " " << t << endl; 78 q.pop(); 79 for (int i = 0; i < 3; ++i) 80 if (((mask>>i)&1) == 0 && cx == x[i] && cy == y[i]) 81 { 82 int &nxt = d[cx][cy][mask|(1<
                        
                          t) 84 { 85 nxt = t; 86 q.push((State){cx, cy, mask|(1<
                         
                          = n || ny >= m) 94 continue; 95 if (mask == 7 && s[nx][ny] == '#') 96 continue; 97 int &nxt = d[nx][ny][mask]; 98 if (nxt == -1 || nxt > tmp) 99 {100 nxt = tmp;101 q.push((State){nx, ny, mask, nxt});102 }103 }104 }105 106 printf("%d\n", d[ex][ey][(1<<3)-1]);107 108 }

View Code

spfa：

1 /*  2  by skydog  3  */  4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 #include 
          
             9 #include 
           
             10 #include 
            
              11 #include 
              12 #include 
              
                13 #include 
               
                 14 #include 
                
                  15 #include 
                 
                   16 #include 
                  
                    17 #include 
                   
                     18 using namespace std; 19 typedef long long ll; 20 typedef pair
                    
                      ii; 21 typedef pair
                     
                       l4; 22 typedef unsigned long long ull; 23 #define mp make_pair 24 #define pb push_back 25 26 27 const int maxn = 1e2+1; 28 char s[maxn][maxn]; 29 const int N = 3; 30 int x[3], y[3], t[3]; 31 const int maxs = 1<
                      
                        r.dis; 41 } 42 }; 43 int get(int mask) 44 { 45 int ret = 1; 46 for (int i = 0; i < 3; ++i) 47 if ((mask>>i)&1) 48 ret += t[i]; 49 return ret; 50 } 51 int dx[4] = { 1, 0, -1, 0}; 52 int dy[4] = { 0, 1, 0, -1}; 53 int main() 54 { 55 scanf("%d %d", &n, &m); 56 for (int i = 0; i < n; ++i) 57 scanf("%s", s[i]); 58 memset(d, -1, sizeof(d)); 59 scanf("%d %d", &sx, &sy), --sx, --sy; 60 for (int i = 0; i < 3; ++i) 61 scanf("%d %d", x+i, y+i), --x[i], --y[i]; 62 scanf("%d %d", &ex, &ey), --ex, --ey; 63 for (int i = 0; i < 3; ++i) 64 scanf("%d", t+i); 65 queue
                       
                         q; 66 d[sx][sy][0] = 0; 67 q.push((State){sx, sy, 0, 0}); 68 while (!q.empty()) 69 { 70 int cx = q.front().x, cy = q.front().y, mask = q.front().mask; 71 int t = d[cx][cy][mask]; 72 if (t != q.front().dis) 73 { 74 q.pop(); 75 continue; 76 } 77 //cerr << cx << " " << cy << " " << mask << " " << t << endl; 78 q.pop(); 79 for (int i = 0; i < 3; ++i) 80 if (((mask>>i)&1) == 0 && cx == x[i] && cy == y[i]) 81 { 82 int &nxt = d[cx][cy][mask|(1<
                        
                          t) 84 { 85 nxt = t; 86 q.push((State){cx, cy, mask|(1<
                         
                          = n || ny >= m) 94 continue; 95 if (mask == 7 && s[nx][ny] == '#') 96 continue; 97 int &nxt = d[nx][ny][mask]; 98 if (nxt == -1 || nxt > tmp) 99 {100 nxt = tmp;101 q.push((State){nx, ny, mask, nxt});102 }103 }104 }105 106 printf("%d\n", d[ex][ey][(1<<3)-1]);107 108 }

View Code

H. 老子的全排列呢

题意：输出1-8的全排列

方法：next_permuation

code：

1 /* 2  by skydog 3  */ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 using namespace std;19 typedef long long ll;20 typedef pair
                    
                      ii;21 typedef pair
                     
                       l4;22 typedef unsigned long long ull;23 #define mp make_pair24 #define pb push_back25 26 const int maxn = 10;27 int a[maxn];28 int n;29 int main()30 {31 n = 8;32 for (int i = 0; i < n; ++i)33 a[i] = i+1;34 do35 {36 for (int i = 0; i < n; ++i)37 printf("%d%c", a[i], i==n-1?'\n':' ');38 } while (next_permutation(a, a+n));39 }