The 2017 ACM-ICPC Asia Beijing Regional Contest（重现赛）

比赛链接：https://vjudge.net/contest/378025#overview

这场在期末考试前打的，后面一直复习期末考试去了，今天才补完。感觉现场赛的题都挺难的，还是自己太菜了。

E - Cats and Fish

题意：有n只猫，m条鱼，每只猫都有吃鱼的时间，吃的时候相对少的优先。问x分钟后，有多少条鱼没被吃，有多少鱼正在被吃。用优先队列模拟过程即可。

 1 #include <iostream>
 2 #include <queue>
 3 #include <stdio.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int v,w;
 8     bool operator<(const node&b)const
 9     {
10         if(w==b.w)return v>b.v;
11         return w>b.w;
12     }
13 } temp;
14 int n,m,x,c,ans;
15 int main()
16 {
17     while(~scanf("%d%d%d",&m,&n,&x))
18     {
19         ans=0;
20         priority_queue<node>q;
21         for(int i=1; i<=n; i++)
22         {
23             scanf("%d",&c);
24             q.push(node{c,0});
25         }
26         while(m --)
27         {
28             if(q.top().w >= x) break;
29             auto t = q.top();
30             q.pop();
31             t.w += t.v;
32             q.push(t);
33         }
34         while(!q.empty())
35         {
36             auto t = q.top();
37             q.pop();
38             if(t.w > x)
39             ans ++;
40         }
41         printf("%d %d
", m + 1, ans);
42     }
43     return 0;
44 }

View Code

F - Secret Poems

题意：按照矩阵模拟。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn = 110;
 8 char s[maxn][maxn];
 9 char p[maxn][maxn];
10 int vis[maxn][maxn];
11 char c[maxn*maxn];
12 int x,y,tot,n;
13 int cnt;
14 int main()
15 {
16     while(cin>>n)
17     {
18         memset(s,0,sizeof s);
19         memset(p,0,sizeof p);
20         memset(c,0,sizeof c);
21         for(int i=0; i<n; i++)
22             for(int j=0; j<n; j++)
23                 cin>>s[i][j];
24         p[0][0]=s[0][0];
25         x=0;y=0;
26         cnt = 0;        // 折线读取
27         for(int i=0; i<2*n - 1; i++)
28         {
29             if(i%2)
30             {
31                 for(int j=i; j>=0; j--)
32                     if(i-j<n&&j<n)
33                         c[cnt++] =s[i-j][j];
34             }
35             else
36             {
37                 for(int j=0; j<=i; j++)
38                     if(i-j<n&&j<n)
39                         c[cnt++] =s[i-j][j];
40             }
41         }
42         tot=0;
43         while(tot<n*n-1)//紫书上的蛇形填数
44         {
45             while(y+1<n&&!p[x][y+1])//右
46                 p[x][++y]=c[++tot];
47             while(x+1<n&&!p[x+1][y])//下
48                 p[++x][y]=c[++tot];
49             while(y-1>=0&&!p[x][y-1])//左
50                 p[x][--y]=c[++tot];
51             while(x-1>=0&&!p[x-1][y])//上
52                 p[--x][y]=c[++tot];
53         }
54         for(int i=0; i<n; i++)
55         {
56             for(int j=0; j<n; j++)
57                 cout<<p[i][j];
58             cout<<endl;
59         }
60     }
61     return 0;
62 }

View Code

J - Pangu and Stones

题意：给n堆石头，每堆石头有一定的重量，每次合并的花费是重量之和，每次只能合并l-r堆变成1堆，求最小的花费，若不存在输出0。

区间Dp,用dp[i][j][k]表示i到j分成k堆。以为只能变成1，所以每次必然是用1去更新最后一维k。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 110;
 5 const int INF = 0x3f3f3f3f;
 6 int n, l, r;
 7 int f[N][N][N];
 8 int a[N];
 9 int sum[N];
10 int main()
11 {
12     while(scanf("%d%d%d", &n, &l, &r)!= EOF)
13     {
14         for (int i = 1; i <= n; i ++)
15             for (int j = 1; j <= n; j ++)
16                 for (int k = 1; k <= n; k ++)
17                     f[i][j][k] = INF; 
18         for (int i = 1; i <= n; i ++)
19         {
20             scanf("%d", &a[i]);
21             sum[i] = sum[i - 1] + a[i];
22             f[i][i][1] = 0;
23         }
24         for (int len = 2; len <= n; len ++)
25         {
26             for (int i = 1; i + len - 1 <= n; i ++)
27             {
28                 int j = i + len - 1;
29                 f[i][j][len] = 0;
30                 for (int k = 2; k <= len; k ++)
31                 {
32                     for (int p = i; p < j; p ++)
33                     {
34                         f[i][j][k] = min(f[i][j][k], f[i][p][1] + f[p + 1][j][k - 1]);
35                     }
36                     if(k >= l && k <= r)
37                         f[i][j][1] = min(f[i][j][1], f[i][j][k] + sum[j] - sum[i - 1]);
38                 }
39                 
40             }
41         }
42         if(f[1][n][1] == 0x3f3f3f3f) f[1][n][1] = 0;
43         printf("%d
", f[1][n][1]);
44     }
45 }

View Code

C - Graph

题意：给你一个n个顶点，m条边的无向图，q次询问。问你l到r之间，有多少不同的路径是联通的。考虑一次询问，就是并查集维护下联通块的数量，考虑是很多询问，用莫队+可删除并查集（倒着模拟一遍）。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N = 1e5 + 10;
  4 
  5 int T;
  6 int n, m, t; 
  7 vector<int>g[N];
  8 int p[N], cnt[N];
  9 int ans[N];
 10 int size, belong[N], L[N], R[N], num;
 11 stack<int>st;
 12 int find(int x)
 13 {
 14     if(x == p[x]) return x;
 15     return find(p[x]);
 16 }
 17 
 18 struct query{
 19     int l, r, id;
 20 }q[N];
 21 
 22 int cmp(query a, query b)
 23 {
 24     return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : a.r < b.r;
 25 }
 26 int tmp;
 27 void merge(int x,int y,int flag)
 28 {
 29     int fx = find(x),fy=find(y);
 30     if(fx==fy)
 31         return ;
 32     if(cnt[fx] > cnt[fy]) 
 33     {
 34         swap(x,y); 
 35         swap(fx,fy);
 36     }
 37     tmp += cnt[fx]*cnt[fy];
 38     p[fx]=fy;
 39     cnt[fy]+=cnt[fx];
 40     if(!flag) 
 41           st.push(fx);
 42 }
 43 
 44 int main()
 45 {
 46     scanf("%d", &T);
 47     while(T --)
 48     {
 49         scanf("%d%d%d", &n, &m, &t);
 50             size = sqrt(n);
 51         num = (n - 1)/ size + 1;
 52         while(!st.empty()) st.pop();
 53         for (int i = 1; i <= n; i ++)
 54         {
 55             g[i].clear();
 56             belong[i] = (i - 1) / size + 1;
 57         }
 58         for (int i = 1; i <= num; i ++)
 59             L[i] = (i - 1) * size + 1, R[i] = i * size;
 60         R[num] = n;
 61         for (int i = 1; i <= m; i ++)
 62         {
 63             int x, y;
 64             scanf("%d%d", &x, &y);
 65             g[x].push_back(y), g[y].push_back(x);
 66         }
 67         for (int i = 1; i <= t; i ++)
 68         {
 69             scanf("%d%d", &q[i].l, &q[i].r);
 70             q[i].id = i;
 71         }
 72         sort(q + 1, q + t + 1, cmp);
 73         int now = 0;
 74         int posr = 0, posl = 0;
 75         for(int i=1;i<=t;i++)
 76         {        
 77             if(belong[q[i].l]!=belong[q[i-1].l])
 78             {
 79                 posr=posl=R[belong[q[i].l]];
 80                 for(int j=1;j<=n;j++)
 81                 {
 82                     p[j]=j;
 83                     cnt[j]=1;
 84                 } 
 85                 tmp = 0;             
 86             }
 87             while(posr<q[i].r)
 88             {    
 89                 posr++;
 90                 for (auto j : g[posr])
 91                 {
 92                     if(j>R[belong[q[i].l]]&&j<=q[i].r)
 93                         merge(posr,j,1);
 94                 }
 95             }
 96             now = tmp;
 97             for(posl=min(q[i].r,R[belong[q[i].l]]);posl>=q[i].l;posl--)
 98             {
 99                 for (auto j : g[posl])
100                 {
101                     if(j>=q[i].l&&j<=q[i].r)
102                         merge(posl,j,0);
103                 }
104             }
105             ans[q[i].id]=tmp;
106             while(!st.empty())
107             {
108                 int u=st.top();
109                 st.pop();
110                 cnt[p[u]]-=cnt[u];
111                 p[u]=u;            
112             }
113             tmp = now;
114             posl=R[belong[q[i].l]];
115         }
116         for (int i = 1; i <= t; i ++)
117             printf("%d
", ans[i]); 
118     }
119 }

View Code