The 2017 ACM-ICPC Asia Beijing Regional Contest（重现赛）
分类:
IT文章
•
2022-05-09 08:35:27
比赛链接：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
题意：给你一个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 }
