2020 HDU Multi-University Training Contest 3

2020 HDU Multi-University Training Contest 3

文章目录

• 2020 HDU Multi-University Training Contest 3
• 1004 Tokitsukaze and Multiple
• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

1004 Tokitsukaze and Multiple

链接：HDU6794 Tokitsukaze and Multiple

题意思路

• 前缀和：记录上一次余数为 ttt 的出现位置
• 贪心

代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 7;int T;int n, p;int arr[MAXN];bool vis[MAXN];int mod[MAXN];int ans;int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){ans = 0;memset(vis, 0, sizeof(vis));memset(mod, 0, sizeof(mod));cin >> n >> p;for (int i = 1; i <= n; ++i){cin >> arr[i];arr[i] %= p;if (!arr[i]){vis[i] = true;ans++;}}int s = 0; // Start of the non-visited Intervalint sum = 0; // Sum of the non-visited Intervalfor (int i = 1; i <= n; ++i){if (!vis[i]){sum += arr[i];sum %= p;if (sum == 0 || mod[sum % p] > s){ans++;vis[i] = true;s = i;sum = 0;continue;}mod[sum % p] = i;}if (vis[i]){s = i;sum = 0;}}cout << ans << endl;}return 0;}

1005 Little W and Contest

链接：HDU6795 Little W and Contest

题意思路

• 并查集，维护每个并查集内 readerreaderreader 和 codercodercoder 的数量

代码

因为负数取模的原因WA了5发

#include <bits/stdc++.h>using namespace std;#define int long longconst int MAXN = 1e5 + 7;const int MOD = 1e9 + 7;int fac[MAXN], inv[MAXN];inline void Pre(int n){fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i % MOD;inv[1] = 1;for (int i = 2; i <= n; i++)inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;inv[0] = 1;for (int i = 1; i <= n; i++)inv[i] = inv[i] * inv[i - 1] % MOD;}inline int C(int n, int m){if (m > n)return 0;return fac[n] * inv[m] % MOD * inv[n - m] % MOD;}// 计算组合数inline int Pow(int a, int b){int ret = 1;for (; b; b >>= 1, a = a * a % MOD)if (b & 1)ret = ret * a % MOD;return ret;}// 快速幂int T;int n;int pts[MAXN];int u, v;int ans;int tmp1, tmp2;struct DSU{int parent[MAXN];int n; // Num of Nodesint cnt; // Count Strongly Connected Componentsint sum1[MAXN];int sum2[MAXN];int rank[MAXN];void init_parent(int n){this -> n = n;cnt = 0;for (int i = 1; i <= n; ++i){parent[i] = i;if (pts[i] == 1){sum1[i] = 1;sum2[i] = 0;}else{sum1[i] = 0;sum2[i] = 1;}rank[i] = 0;}}int find_parent(int x){if (parent[x] == x)return x;elseparent[x] = find_parent(parent[x]);return parent[x];}bool check_unicom(int x, int y){return find_parent(x) == find_parent(y);}void merge(int x, int y){x = find_parent(x);y = find_parent(y);if (rank[x] > rank[y]){parent[y] = x;if (x != y){sum1[x] += sum1[y];sum1[x] %= MOD;sum2[x] += sum2[y];sum2[x] %= MOD;}}else{parent[x] = y;if (x != y){sum1[y] += sum1[x];sum1[y] %= MOD;sum2[y] += sum2[x];sum2[y] %= MOD;}if (rank[x] == rank[y])rank[y] += 1;}}int getsum1(int i){return sum1[find_parent(i)];}int getsum2(int i){return sum2[find_parent(i)];}}dsu;int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);Pre(100005);cin >> T;while (T--){cin >> n;ans = 0;tmp1 = tmp2 = 0;for (int i = 1; i <= n; ++i){cin >> pts[i];if (pts[i] == 1){tmp1++;}if (pts[i] == 2){tmp2++;}}dsu.init_parent(n);ans = (C(tmp2, 2) % MOD * tmp1 % MOD) % MOD + C(tmp2, 3) % MOD;ans %= MOD;cout << ans << endl;for (int i = 1; i <= n - 1; ++i){cin >> u >> v;if (!dsu.check_unicom(u, v)){int usum1 = dsu.getsum1(u);int usum2 = dsu.getsum2(u);int vsum1 = dsu.getsum1(v);int vsum2 = dsu.getsum2(v);// cout << usum1 << \" \" << usum2 << \" \" << vsum1 << \" \" << vsum2 << endl;int les2 = tmp2 - usum2 - vsum2;int les1 = tmp1 - usum1 - vsum1;// cout << les1 << \" \" << les2 << endl;ans = ans + 2 * MOD// Incorrect Pos- les2 * ((usum2 * vsum1) % MOD + (usum1 * vsum2) % MOD) % MOD- ((les2 + les1) % MOD) * (usum2 * vsum2 % MOD) % MOD;dsu.merge(u, v);}ans %= MOD;cout << ans << endl;}}return 0;}

1009 Triangle Collision

链接：HDU6799 Parentheses Matching

题意

• 给定字符串 PPP，包含

  *

  (

  )

  元素

• 括号匹配，

  *

  可以替换成任意一个括号

• 输出长度最小的匹配中字典序最小的字符串

思路

• 类似贪心，从左侧加

  (

  从右侧加

  )

代码

（队友的代码）

#include <iostream>#include <algorithm>#include <stack>using namespace std;stack<char> st;char ans[100007];int main(){int t;string s, ans;cin >> t;while (t--){cin >> s;while (!st.empty())st.pop();int cnt1 = 0, cnt2 = 0;bool flag = true;for (int i = 0; s[i]; i++){if (s[i] == \'*\')cnt1++;else if (s[i] == \'(\')st.push(s[i]);else{if (!st.empty())st.pop();else{cnt2++;if (cnt2 > cnt1){flag = false;break;}}}}if (!flag){printf(\"No solution!\\n\");continue;}else{int cnt = 0;for (int i = 0; s[i] && cnt < cnt2; i++){if (s[i] == \'*\'){cnt++;s[i] = \'(\';}}while (!st.empty())st.pop();cnt = 0;cnt1 = 0;cnt2 = 0;int len = s.length();for (int i = len - 1; i >= 0; i--){if (s[i] == \')\'){st.push(s[i]);}else if (s[i] == \'*\')cnt1++;else{if (!st.empty())st.pop();else{cnt2++;if (cnt2 > cnt1){flag = false;break;}}}}// cout << s << endl;if (!flag){printf(\"No solution!\\n\");continue;}for (int i = len - 1; i >= 0 && cnt < cnt2; i--){if (s[i] == \'*\'){cnt++;s[i] = \')\';}}// cout << s << endl;for (int i = 0; s[i]; i++){if (s[i] != \'*\')printf(\"%c\", s[i]);}cout << endl;}}return 0;}

1007 Tokitsukaze and Rescue

链接：HDU6797 Tokitsukaze and Rescue

题意

• nnn 个点，每个点间均有一条无向边 （n⋅(n−1)/2n \\cdot (n – 1) / 2n⋅(n−1)/2 条无向边）所构成的无向图

• 求删去任意 mmm 条边后，1−n1 – n1−n 最短路的最大距离

• 每条边权随机 →\\to→ 边权随机的情况下，最短路的边数很少。

  （这个怎么证啊）

思路

• Dijkstra+DFSDijkstra + DFSDijkstra+DFS每次求最短路，枚举删去任意一条边继续爆搜。

代码

#include <bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 50 + 7;const int MAXE = 1E5 + 7;int ans;struct Dijkstra{int graph[MAXN][MAXN]; // Adj Matrixint n; // Num of Nodesint s, t; // Start Pos and End Posbool vis[MAXN];int dis[MAXN];int path[7][MAXN];void init(){memset(graph, 0x3f, sizeof(graph));memset(path, -1, sizeof(path));for (int i = 1; i <= n; ++i){graph[i][i] = 0;}s = 1;t = n;}void dijkstra(int m){memset(vis, 0, sizeof(vis));memset(dis, 0x3f, sizeof(dis));vis[s] = true;dis[s] = 0;for (int i = 1; i <= n; ++i){if (dis[i] > dis[s] + graph[s][i]){dis[i] = dis[s] + graph[s][i];path[m][i] = s;}}while (true){int nxt = -1;for (int i = 1; i <= n; ++i){if (!vis[i] && (nxt == -1 || dis[nxt] > dis[i])){nxt = i;}}if (nxt == -1){break;}vis[nxt] = true;for (int i = 1; i <= n; ++i){if (!vis[i] && dis[i] > dis[nxt] + graph[nxt][i]){dis[i] = dis[nxt] + graph[nxt][i];path[m][i] = nxt;}}}}void dfs(int m){dijkstra(m);if (m == 0){ans = max(ans, dis[t]);return;}for (int i = t; path[m][i] != -1; i = path[m][i]){int fr = path[m][i];int tmp = graph[fr][i];graph[fr][i] = INF;graph[i][fr] = INF;dfs(m - 1);graph[fr][i] = tmp;graph[i][fr] = tmp;}}}djk;int T;int n, m;int u, v, val;int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){cin >> n >> m;djk.n = n;djk.init();ans = 0;for (int i = 1; i <= n * (n - 1) / 2; i++){cin >> u >> v >> val;djk.graph[u][v] = djk.graph[v][u] = val;}djk.dfs(m);cout << ans << endl;}return 0;}

1008 Triangle Collision

链接：HDU6798 Triangle Collision

（待补）

题意思路代码