2020 HDU Multi-University Training Contest 2

文章目录

2020 HDU Multi-University Training Contest 2
1010 Lead of Wisdom
题意
思路
代码

1006 The Oculus

题意
思路
代码

1001 Total Eclipse

题意
思路
代码

1012 String Distance

题意
思路
代码

1005 New Equipments

题意
思路
代码

1010 Lead of Wisdom

链接：HDU6772 Lead of Wisdom

题意

kkk 种物品共 nnn 个 1≤n,k≤501 \\le n, \\ k \\le 501≤n,k≤50，每种选一个
每个物品拥有属性ti,ai,bi,ci,dit_i, \\ a_i, \\ b_i, \\ c_i, \\ d_iti,ai,bi,ci,di
输出 ans=(100+∑ai)∗(100+∑bi)∗(100+∑ci)∗(100+∑di)ans = (100 + \\sum a_i) * (100 + \\sum b_i) * (100 + \\sum c_i) * (100 + \\sum d_i)ans=(100+∑ai)∗(100+∑bi)∗(100+∑ci)∗(100+∑di) 的最大值

思路

数据范围很小，DFSDFSDFS 暴力
注意删除物品数量为 000 的属性

代码

#include <bits/stdc++.h>using namespace std;int T;int n, k;struct Item{int a, b, c, d;int t;Item(int t, int a, int b, int c, int d): t(t), a(a), b(b), c(c), d(d) {}};vector<Item> tmp[57];vector<Item> typ[57];int cur;long long ans;void dfs(int t, int a, int b, int c, int d){if (t == cur){long long now = (long long)(100 + a) * (100 + b) * (100 + c) * (100 + d);ans = max(ans, now);return;}for (int i = 0; i < typ[t].size(); ++i){int na = a + typ[t][i].a;int nb = b + typ[t][i].b;int nc = c + typ[t][i].c;int nd = d + typ[t][i].d;dfs(t + 1, na, nb, nc, nd);}}int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){ans = 0;cin >> n >> k;int t, a, b, c, d;for (int i = 1; i <= n; ++i){cin >> t >> a >> b >> c >> d;Item it(t, a, b, c, d);tmp[t].push_back(it);}cur = 1;for (int i = 1; i <= k; ++i){if (tmp[i].size()){typ[cur++] = tmp[i];tmp[i].clear();}}dfs(1, 0, 0, 0, 0);cout << ans << endl;}return 0;}

1006 The Oculus

链接：HDU6768 The Oculus

题意

给定A,BA, \\ BA,B两个整数的 fibonaccifibonaccifibonacci 表示，fib[1]=1,fib[2]=2fib[1] = 1, \\ fib[2] = 2fib[1]=1,fib[2]=2
给定CCC 的齐肯多夫分解表示，其中 CCC 中有一位 111 被修改成 000
输出被修改的位置

思路

齐肯多夫 (Zeckendorf)(Zeckendorf)(Zeckendorf) 定理：任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和

证明：数学归纳法

利用同余的性质，直接计算

modp,p=1e9+9mod \\ p, \\ p = 1e9 + 9modp,p=1e9+9
双 hashhashhash

代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 2e6 + 7;unsigned long long fib[MAXN];void getfib(){fib[0] = 1; fib[1] = 2;for (int i = 2; i < MAXN; ++i){fib[i] = fib[i - 1] + fib[i - 2];}}int T;long long a, b ,c;inline unsigned long long input(){int len;unsigned long long res = 0;cin >> len;bool tmp = false;for (int i = 0; i < len; ++i){cin >> tmp;if (tmp)res += fib[i];}return res;}void solve(){a = input();b = input();c = input();unsigned long long ans = a * b;int pos = 0;for (; c + fib[pos] != ans; ++pos);cout << (pos + 1) << endl;}int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);getfib();cin >> T;while (T--){solve();}return 0;}

1001 Total Eclipse

链接：HDU6763 Total Eclipse

题意

nnn 个点 mmm 条边的无向图
每个点拥有点权 bib_ibi
每一次操作：选择 kkk 个连通的点构成点集
点集中的每个点点权 −1-1−1

求使得所有点的点权为 000，的最少操作数 ansansans

PS: 对于每次操作必须选择图中的极大连通块

思路

比赛的时候想到并查集了，可惜只在想并查集的删除操作

对点按照点权 bib_ibi 从大到小排序
基于贪心的思想，首先删去权值最小的点，此时原先的一个强连通分量可能会转化为多个较小的强连通分量
对于上述操作逆向进行，将每个强连通分量看作多极值的函数，对于每个极值由大到小操作，显然对于一个强连通分量中权值最大的点需要单独 k=bmax⁡−bmax−k = b_{\\max} – b_{max^-}k=bmax−bmax− 次操作，对于答案的贡献即为 kkk；之后将其加入并查集
对于任意的一个点 nownownow，与其相连的边的另一点 nxtnxtnxt，若 nxtnxtnxt 已在被访问 (bnxt>bnow)(b_{nxt} > b_{now})(bnxt>bnow)，则判断两者是否连通，若不连通则更新 nownownow 节点的父节点成为最小值所需进行的操作次数

代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 5;struct DSU{int parent[MAXN];int n; // Nums of Nodesint cnt; // Count Strongly Connected Componentsvoid init_parent(int n){this -> n = n;cnt = 0;for (int i = 1; i <= n; ++i)parent[i] = i;}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){int parent_x = find_parent(x);int parent_y = find_parent(y);if (parent_x != parent_y){parent[parent_x] = parent_y;cnt++;}}}dsu;int T;int n, m;long long ans;int val[MAXN];int id[MAXN];vector<int> graph[MAXN];bool vis[MAXN];int frm[MAXN]; // from which Node\'s Valbool cmp(int x, int y){return val[x] > val[y];}int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){memset(vis, 0 ,sizeof(vis));memset(frm, 0, sizeof(frm));ans = 0;val[0] = 0;cin >> n >> m;dsu.init_parent(n);for (int i = 1; i <= n; ++i){cin >> val[i];id[i] = i;graph[i].clear();}int u, v;for (int i = 0; i < m; ++i){cin >> u >> v;graph[u].push_back(v);graph[v].push_back(u);}sort(id + 1, id + n + 1, cmp);for (int i = 1; i <= n; ++i){int now = id[i];vis[now] = true;for (int j = 0; j < graph[now].size(); ++j){int nxt = graph[now][j];if ((!vis[nxt]) || dsu.check_unicom(nxt, now))continue;frm[dsu.find_parent(nxt)] = now;dsu.merge(nxt, now);}}for (int i = 1; i <= n; ++i)ans += (long long)(val[i] - val[frm[i]]);cout << ans << endl;}return 0;}

1012 String Distance

链接：HDU6774 String Distance

题意

给定两个字符串 AAA 和 BBB，其中串长分别为 nnn 和 mmm (1≤n≤1e5,1≤m≤20)(1 \\le n \\le 1e5, \\ 1 \\le m \\le 20)(1≤n≤1e5,1≤m≤20)
两个操作：删除一个字符
插入一个字符

q(1≤q≤1e5)q \\ (1 \\le q \\le 1e5)q(1≤q≤1e5) 次询问，求 Al→rA_{l \\to r}Al→r 到 BBB 的最小编辑距离

思路

想到了 LCS+DPLCS + DPLCS+DP 可惜不会

编辑距离 ans=len(Al→r)+len(B)−LCS(Al→R,B)ans = len(A_{l \\to r}) + len(B) – LCS(A_{l \\to R}, \\ B)ans=len(Al→r)+len(B)−LCS(Al→R,B)
显然需要通过 DPDPDP 求解，问题在于Len(Al→r)Len(A_{l \\to r})Len(Al→r) 可能很大，若每次均对两个字符串 DPDPDP 必然超时
观察到，Len(B)≤20Len(B) \\le 20Len(B)≤20 那么是否存在一种思路只对于 BBB 即可求得所需的 LCSLCSLCS
首先预处理出 Ai→nA_{i \\to n}Ai→n 中每一个小写字母出现的最靠前的位置 pos[i][char]pos[i][char]pos[i][char]

复杂度：O(26∗n)O(26 * n)O(26∗n)

对于每次询问，我们建立一种状态 dp[i][j]=posdp[i][j] = posdp[i][j]=pos ，指在 B1→iB_{1 \\to i}B1→i 的子串中，满足长度为 jjj 的 LCSLCSLCS 的末尾下标的位置 pospospos 中最靠前的一个

个人认为难点在于状态的设计，设计好了状态，状态转移方程并不难理解

状态转移方程

状态	状态	方程
dp[i][j]=posdp[i][j] = posdp[i][j]=pos	dp[i+1][j]dp[i + 1][j]dp[i+1][j]	dp[i+1][j]=dp[i][j]dp[i + 1][j] = dp[i][j]dp[i+1][j]=dp[i][j]
dp[i][j]=posdp[i][j] = posdp[i][j]=pos	dp[i+1][j+1]dp[i + 1][j + 1]dp[i+1][j+1]	dp[i+1][j+1]=pos[dp[i][j]+1][b[i+1]]dp[i + 1][j + 1] = pos[ \\ dp[i][j] + 1 \\ ][ \\ b[i + 1] \\ ]dp[i+1][j+1]=pos[dp[i][j]+1][b[i+1]]

第一个方程：B1→i+1B_{1 \\to i + 1}B1→i+1 较于原先状态 B1→iB_{1 \\to i}B1→i 串末尾增加了 b[i+1]b[i + 1]b[i+1] 显然对于最靠前的 pospospos 没有影响，若 dp[i][j]<rdp[i][j] < rdp[i][j]<r 则直接转移

第二个方程：4000LCSLCSLCS 长度增加显然为 b[i+1]b[i + 1]b[i+1] 处和 AAA 匹配，且 dp[i][j]dp[i][j]dp[i][j] 为前部分匹配的末尾位置，那么我们去寻找在 Adp[i][j]+1→nA_{dp[i][j] + 1 \\to n}Adp[i][j]+1→n 中出现 b[i+1]b[i + 1]b[i+1] 最早的位置
最后，注意这两个转移方程成立的条件

代码

# include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 7;int T;int n, m;string stra, strb;int a[MAXN];int b[30];int q;int l, r;int pos[MAXN][30];int dp[30][30];int ans;void pre(){n = stra.length();m = strb.length();for (int i = 0; i < n; ++i){a[i + 1] = stra[i] - \'a\';}for (int i = 0; i < m; ++i){b[i + 1] = strb[i] - \'a\';}memset(pos[n + 1], 0x3f, sizeof(pos[n + 1]));for (int i = n; i > 0; --i){for (int j = 0; j < 26; ++j){pos[i][j] = pos[i + 1][j];}pos[i][a[i]] = i;}}int solve(){memset(dp, 0x3f, sizeof(dp));dp[0][0] = l - 1;for (int i = 0; i < m; ++i){for (int j = 0; j <= i; ++j){if (dp[i + 1][j] > dp[i][j])dp[i + 1][j] = dp[i][j];if (dp[i][j] < r && dp[i + 1][j + 1] > pos[dp[i][j] + 1][b[i + 1]])// dp[i + 1][j] is incorrectdp[i + 1][j + 1] =  pos[dp[i][j] + 1][b[i + 1]];}}for (int j = m; j > 0; --j){for (int i = m; i >= j; --i){if (dp[i][j] <= r)return j;}}return 0;}int main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while (T--){cin >> stra >> strb;pre();cin >> q;while (q--){cin >> l >> r;ans = r - l + 1 + m - 2 * solve();cout << ans << endl;}}return 0;}

1005 New Equipments

链接：HDU6767 New Equipments

题意

给定 nnn 个工人，mmm 件物品 (1≤n≤50,n≤m≤108)(1 \\le n \\le 50, n \\le m \\le 10^8)(1≤n≤50,n≤m≤108)
每个工人选择第 jjj 件物品需要付工资 ai⋅j2+bi⋅j+cia_i \\cdot j^2 + b_i \\cdot j + c_iai⋅j2+bi⋅j+ci，物品不能重复使用
求最小的工资之和

资本家的丑恶而嘴脸

思路

建图的思想比较重要，剩下来的算法抄板子就行

网络流最小费用最大流
链式前向星存图

建立源点 – 员工 – 员工对应最小费用的 lenlenlen 件物品 – 汇点

员工 – 物品：mmm 很大并不需要所有的物品，故 len=min(n+7,m)len = min(n + 7, m)len=min(n+7,m)
边权 cost=ai⋅j2+bi⋅j+cicost = a_i \\cdot j^2 + b_i \\cdot j + c_icost=ai⋅j2+bi⋅j+ci
流量 capacity=1capacity = 1capacity=1 （每件物品只能使用一次）

代码

#include <bits/stdc++.h>using namespace std;#define int long longconst int MAXN = 1e4 + 7;const int MAXE = 1e5 + 7;const long long INF = 1e18 + 7;struct MCMF_SPFA{struct Edge{int v, cap, cost, nxt;} edge[MAXE << 1];int cntedge, sumflow;int head[MAXN];void init(){cntedge = 0;memset(head, -1, sizeof(head));}void addEdge(int u, int v, int cap, int cost){edge[cntedge].v = v;edge[cntedge].cap = cap;edge[cntedge].cost = cost;edge[cntedge].nxt = head[u];head[u] = cntedge++;edge[cntedge].v = u;edge[cntedge].cap = 0;edge[cntedge].cost = -cost;edge[cntedge].nxt = head[v];head[v] = cntedge++;}int dis[MAXN], pre[MAXN];bool vis[MAXN];bool spfa(int s, int t, int n){int u, v;queue<int> q;memset(vis, false, sizeof(vis));memset(pre, -1, sizeof(pre));for (int i = 0; i <= n; ++i)dis[i] = INF;vis[s] = true;dis[s] = 0;q.push(s);while (!q.empty()){u = q.front();q.pop();vis[u] = false;for (int i = head[u]; i != -1; i = edge[i].nxt){v = edge[i].v;if (edge[i].cap && dis[v] > dis[u] + edge[i].cost){dis[v] = dis[u] + edge[i].cost;pre[v] = i;if (!vis[v]){q.push(v);vis[v] = true;}}}}return dis[t] != INF;}void mincostmaxflow(int s, int t, int n, int num){int flow = 0;int minflow, mincost;mincost = 0;while (spfa(s, t, n)){minflow = INF + 1;for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v])if (edge[i].cap < minflow)minflow = edge[i].cap;flow += minflow;for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v]){edge[i].cap -= minflow;edge[i ^ 1].cap += minflow;}mincost += dis[t] * minflow;cout << mincost;if (flow < num)cout << \" \";}sumflow = flow;cout << endl;// return mincost;}}mcmf;int T;int n, m;int a, b ,c;int s, t;int len; //Lens of Minumum Nums in Funcint cnt; //Count Node in NetworkFlow, node [1, n] are workersunordered_map<int, int> mp;void quad(int id, int a, int b, int c){int ctr = - b / (2 * a);int lft, rgt;lft = ctr - len / 2 - 3;rgt = lft + len - 1;if (lft < 1){rgt += 1 - lft;lft = 1;}else if (rgt > m){lft -= rgt - m;rgt = m;}// Incorrect Posfor (int i = lft; i <= rgt; ++i){int cost = a * i * i + b * i + c;if (!mp.count(i)){cnt++;mp[i] = cnt;mcmf.addEdge(cnt, t, 1, 0);}int nxt = mp[i];mcmf.addEdge(id, nxt, 1, cost);}}void solve(){mp.clear();mcmf.init();cin >> n >> m;len = min(n + 7, m);s = 0;t = n * (len + 1) + 1;cnt = n;for (int i = 1; i <= n; ++i){cin >> a >> b >> c;mcmf.addEdge(s, i, 1, 0);quad(i, a, b, c);}mcmf.mincostmaxflow(s, t, t, n);}int32_t main(void){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> T;while(T--){solve();}}

2020 HDU Multi-University Training Contest 2