2020 HDU Multi-University Training Contest 4

2020 HDU Multi-University Training Contest 4

文章目录

• 2020 HDU Multi-University Training Contest 4
• 1002 Blow up the Enemy
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

1002 Blow up the Enemy

链接：HDU6803 Blow up the Enemy

代码

（队友的代码）

#include <iostream>#include <cstring>#include <cstdio>using namespace std;int data[1002];int main(void){int t;cin >> t;int n;while(t--){scanf(\"%d\", &n);int ai,di;int minn=999999999;for(int i=1;i<=n;i++){scanf(\"%d %d\", &ai, &di);if((100%ai)==0){data[i]= di*(100/ai-1);}else{data[i] = di*(100/ai);}if(minn > data[i]){minn = data[i];}}int ans = 0;for(int i=1;i<=n;i++){if(minn < data[i]){ans += 10;}else if(minn == data[i]){ans += 5;}else{ans += 0;}}double res = (double)ans/(double)n/10.0;cout << res << endl;}return 0;}

1005 Equal Sentences

链接：HDU6808 Equal Sentences

题意思路

• 简单 DPDPDP

代码

#include <bits/stdc++.h>using namespace std;#define int long longconst int MAXN = 1e5 + 7;// const int INF = ;const int MOD = 1e9 + 7;// const int DIRX[] = {};// const int DIRY[] = {};int T;int n;string str;string tmp, word;int cnt;int dp[MAXN][2];int vis[MAXN];int ans;int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){memset(vis, 0, sizeof(vis));cnt = 0;ans = 0;word = \"\";cin >> n;for (int i = 1; i <= n; ++i){cin >> str;if (str != word){cnt++;word = str;}vis[i] = cnt;}// cout << cnt << endl;dp[0][0] = dp[0][1] = 0;dp[1][0] = 1;dp[1][1] = 0;for (int i = 2; i <= n; ++i){if (vis[i] != vis[i - 1]){dp[i][0] = dp[i - 1][0] + dp[i - 1][1] % MOD;dp[i][1] = dp[i - 1][0] % MOD;}else{dp[i][0] = dp[i - 1][0] + dp[i - 1][1] % MOD;dp[i][1] = 0 % MOD;}}ans = dp[n][0] + dp[n][1];ans %= MOD;cout << ans << endl;}return 0;}

1011 Kindergarten Physics

链接：HDU6812 Kindergarten Physics

???

1004 Deliver the Cake

链接：HDU6805 Deliver the Cake

题意

• nnn 个点，mmm 条边的无向图每条边边权 ddd
• 每个点有 L,M,RL, \\ M, \\ RL,M,R 三种状态MMM 状态可以成为任何状态
• 其他两种状态转化需要 xxx 点费用

思路

• DijkstraDijkstraDijkstra （堆优化）
• 图论最关键的是建图的方式，本题可以将状态为 MMM 的点拆分为两个状态分别为 L,RL, \\ RL,R 的点

代码

#include <bits/stdc++.h>using namespace std;#define int long longint T;int n, m, s, t, x, u, v, val;char str[200007];vector<pair<int, int>> graph[200007]; // graph[fr] {to, val}int dis[200007];int cnt; // Nums of Nodeint ans;unordered_map<int, int> mp; // Node \'M\' Divide into Doublevoid dijkstra(int st){priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;// {dis[node], node}dis[st] = 0;que.push({dis[st], st});while (!que.empty()){int now = que.top().second;int tmpval = que.top().first;que.pop();if (dis[now] < tmpval)continue;for (int i = 0; i < graph[now].size(); i++){int nxt = graph[now][i].first;int val = graph[now][i].second;int tmp = ((str[nxt] == str[now]) ? 0 : x);if (dis[nxt] > val + dis[now] + tmp){dis[nxt] = val + dis[now] + tmp;que.push({dis[nxt], nxt});}}}return;}int32_t main(void){cnt = 0;scanf(\"%lld\", &T);while (T--){memset(dis, 0x3f, sizeof(dis));mp.clear();scanf(\"%lld%lld%lld%lld%lld\", &n, &m, &s, &t, &x);scanf(\"%s\", str + 1);for (int i = 1; i <= cnt; ++i)graph[i].clear();cnt = n;for (int i = 1; i <= m; ++i){scanf(\"%lld%lld%lld\", &u, &v, &val);// Build Mapif (str[u] == \'M\'){mp[u] = ++cnt;str[u] = \'L\';str[mp[u]] = \'R\';graph[u].push_back({mp[u], 0});graph[mp[u]].push_back({u, 0});}if (str[v] == \'M\'){mp[v] = ++cnt;str[v] = \'L\';str[mp[v]] = \'R\';graph[v].push_back({mp[v], 0});graph[mp[v]].push_back({v, 0});}if (mp.count(u)){graph[mp[u]].push_back({v, val});graph[v].push_back({mp[u], val});if (mp.count(v)){graph[mp[u]].push_back({mp[v], val});graph[mp[v]].push_back({mp[u], val});}}if (mp.count(v)){graph[mp[v]].push_back({u, val});graph[u].push_back({mp[v], val});}graph[u].push_back({v, val});graph[v].push_back({u, val});}dijkstra(s);if (mp.count(s))dijkstra(mp[s]);// Incorrect Posans = dis[t];`if (mp.count(t))ans = min(ans, dis[mp[t]]);printf(\"%lld\\n\", ans);}return 0;}

1012 Last Problem

链接：HDU6813 Last Problem

题意

• 在平面点上填满足：

  	n−1n – 1n−1
  n−2n – 2n−2	nnn	n−3n – 3n−3
  	n−4n – 4n−4

• 输出构造方案，方案步骤数少于 1e51e51e5

思路

• 构造 DFSDFSDFS

代码

#include <bits/stdc++.h>using namespace std;int T;int n;map<pair<int, int>, int> mp;// canNot use Unordered Map// Hash Function must be invocable with an argument of key typevoid dfs(int x, int y, int n){if (n < 1)return;if (mp[{x, y + 1}] != n - 1)dfs(x, y + 1, n - 1);if (mp[{x - 1, y}] != n - 2)dfs(x - 1, y, n - 2);if (mp[{x + 1, y}] != n - 3)dfs(x + 1, y, n - 3);if (mp[{x, y - 1}] != n - 4)dfs(x, y - 1, n - 4);mp[{x, y}] = n;cout << x << \" \" << y << \" \" << n << \"\\n\";}int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;mp.clear();dfs(0, 0, n);return 0;}

1003 Contest of Rope Pulling

链接：HDU6804 Contest of Rope Pulling

题意

• 背包容积 VVV

• n+mn + mn+m 个物品，重量 weightiweight_iweighti​ 价值 valival_ivali​

• 在 nnn 个物品与 mmm 个物品中选择总重量相同的物品

• 求这些物品价值的最大值

思路

• mmm 件物品价值取 vali=−valival_i = – val_ivali​=−vali​，问题转化为普通的 010101背包
• 010101背包 复杂度为 O((n+m)2⋅weightmax⁡)O((n + m) ^ {2} \\cdot weight_{\\max})O((n+m)2⋅weightmax​) 显然会超时，但是本问题只需要 weight=0weight = 0weight=0 时的 valmax⁡val_{\\max}valmax​，故可以对物品随机化

如果我们以一种相对随机的方式安排物品的加入顺序，那么可以发现，最优解在每一阶段对应的状态都在 000 附近振荡。设最优解的子集为 SSS，在物品全集的加入顺序被等概率重排之后，子集 SSS 的加入顺 序也被等概率重排。我们只需要设一个足够大的上界 TTT，只考虑 [−T,T][-T, T][−T,T] 的 ∑weighti\\sum weight_i∑weighti​，做原来的 DPDPDP 即可。

确实想不到背包可以这样做，本题与普通背包问题不同之处在于最终所需的 weight=0weight = 0weight=0 在整个区间中间，故可以缩减 TTT 的值降低时间复杂度。

代码

#include <bits/stdc++.h>using namespace std;#define int long longconst int MAXN = 1e5 + 7;int T;int n , m, w, v;int len;int ans;int dp[MAXN];struct Node{int w, v;}node[2007];int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){ans = 0;memset(dp, 0xBF, sizeof(dp));//0xBF= 10111111 = 191cin >> n >> m;for (int i = 1; i <= n; ++i){cin >> w >> v;node[i] = {w, v};}for (int i = n + 1; i <= n + m; ++i){cin >> w >> v;node[i] = {-w, v};}len = n + m;random_shuffle(node + 1, node + len + 1);// random_shuffle(node + 1, node + len + 1);dp[30000] = 0;for (int i = 1; i <= len; ++i){if(node[i].w > 0){for (int j = 60000; j >= node[i].w; --j)dp[j] = max(dp[j], dp[j - node[i].w] + node[i].v);}else{for (int j = 0; j <= 60000 + node[i].w; ++j)dp[j] = max(dp[j], dp[j - node[i].w] + node[i].v);}ans = max(ans, dp[30000]);}cout << ans << endl;}return 0;}

1007 Go Running

链接：HDU6808 Go Running

题意

• 给定参数 ttt 与 xxx，求至少需要多少个匹配可以将平面上所有的 (x,t)(x, t)(x,t) 覆盖
• 直线 t−xt – xt−x 与 t+xt + xt+x 上的点可以视作同一个点

思路

• 二分图匹配二分图的最大匹配 === 二分图的最小点覆盖
• Ho−KashyapHo – KashyapHo−Kashyap 算法

代码

（二分图匹配的相关算法还没有完全理解，先放一个套板子的代码）

#include <bits/stdc++.h>using namespace std;// #define int long longconst int MAXN = 5e5 + 7;// const int MOD = ;const int INF = 0x3f3f3f3f;// const int DIRX[] = {};// const int DIRY[] = {};struct HK{int cntx, cnty; // Num of Set 1 && Set 2vector<int> graph[MAXN]; // Edge Set 1 to Set 2int lnkx[MAXN], lnky[MAXN];int depx[MAXN], depy[MAXN]; // Depthbool vis[MAXN];int dep;bool bfs(){queue<int> q;dep = INF;memset(depx, -1, sizeof(depx));memset(depy, -1, sizeof(depy));memset(vis, 0, sizeof(vis));for (int i = 1; i <= cntx; ++i){if (lnkx[i] == -1){q.push(i);depx[i] = 0;}}while (!q.empty()){int now = q.front();q.pop();if (depx[now] > dep)break;for (int i = 0; i < graph[now].size(); ++i){int nxt = graph[now][i];if (depy[nxt] == -1){depy[nxt] = depx[now] + 1;if (lnky[nxt] == -1)dep = depy[nxt];else{depx[lnky[nxt]] = depy[nxt] + 1;q.push(lnky[nxt]);}}}}return dep != INF;}bool dfs(int now){for (int i = 0; i < graph[now].size(); ++i){int nxt = graph[now][i];if (!vis[nxt] && depy[nxt] == depx[now] + 1){vis[nxt] = true;if(lnky[nxt] != -1 && depy[nxt] == dep)continue;if(lnky[nxt] == -1 || dfs(lnky[nxt])){lnky[nxt] = now;lnkx[now] = nxt;return true;}}}return false;}int Ho_Kashyap(){int ans = 0;memset(lnkx, -1, sizeof(lnkx));memset(lnky, -1, sizeof(lnky));while (bfs()){for (int i = 1; i <= cntx; ++i){if (lnkx[i] == -1 && dfs(i))ans++;}}return ans;}}hk;unordered_map<int, int> mpx, mpy;int T;int n;int t, x;int rx, ry;int cntx, cnty;int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){mpx.clear();mpy.clear();cntx = 0;cnty = 0;for (int i = 0; i <= 5e5; ++i)hk.graph[i].clear();cin >> n;for (int i = 1; i <= n; ++i){cin >> t >> x;int rx = t + x;int ry = t - x;if (!mpx.count(rx))mpx[rx] = ++cntx;if (!mpy.count(ry))mpy[ry] = ++cnty;hk.graph[mpx[rx]].push_back(mpy[ry]);}hk.cntx = cntx;hk.cnty = cnty;cout << hk.Ho_Kashyap() << endl;}return 0;}