比赛链接：https://vjudge.net/contest/378025#overview
这场在期末考试前打的，后面一直复习期末考试去了，今天才补完。感觉现场赛的题都挺难的，还是自己太菜了。
E - Cats and Fish
题意：有n只猫，m条鱼，每只猫都有吃鱼的时间，吃的时候相对少的优先。问x分钟后，有多少条鱼没被吃，有多少鱼正在被吃。用优先队列模拟过程即可。
1 #include
2 #include
3 #include
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
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\n", m + 1, ans);
42 }
43 return 0;
44 }
View Code
F - Secret Poems
题意：按照矩阵模拟。
1 #include
2 #include
3 #include
4 #include
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 22 for(int j=0; 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 33 c[cnt++] =s[i-j][j]; 34 } 35 else 36 { 37 for(int j=0; j<=i; j++) 38 if(i-j 39 c[cnt++] =s[i-j][j]; 40 } 41 } 42 tot=0; 43 while(tot 44 { 45 while(y+1 46 p[x][++y]=c[++tot]; 47 while(x+1 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 55 { 56 for(int j=0; j 57 cout< 58 cout< 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 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\n", f[1][n][1]); 44 } 45 } View Code C - Graph 题意：给你一个n个顶点，m条边的无向图，q次询问。问你l到r之间，有多少不同的路径是联通的。考虑一次询问，就是并查集维护下联通块的数量，考虑是很多询问，用莫队+可删除并查集（倒着模拟一遍）。 1 #include 2 using namespace std; 3 const int N = 1e5 + 10; 4 5 int T; 6 int n, m, t; 7 vector 8 int p[N], cnt[N]; 9 int ans[N]; 10 int size, belong[N], L[N], R[N], num; 11 stack 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 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\n", ans[i]); 118 } 119 } View Code