2022.8.4 颓废记录
2022/8/5 6:24:00
本文主要是介绍2022.8.4 颓废记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Preface
太蒻了QAQ
Content
[CF76A]Gift
\(N\) 个点,\(M\) 条边的无向图,第 \(i\) 条边有两个权值 \(g_i,s_i\),给定两数 \(G,S\)。
求一棵生成树 \(T\),使得 \(ans=G\times \max\limits_{i\in T}(g_i)+S\times \max\limits_{i\in T} (s_i)\) 最小,无解输出 \(-1\)。
\(1\le N \le 200,1\le M \le 5\times 10^4,1\le g_i,s_i,G,S \le 10^9\)。
(注:并查集的时间复杂度当作常数,不计入时间复杂度)
这个东西初看找不到什么思路可以直接求解,毕竟有两个权值。
遇到这种情况,一种比较通用的想法是固定某个权值,找另一个权值的最优解。
在这题中,将所有边按 \(g_i\) 升序排序。依次求出前 \(i(1\le i \le M)\) 条边以 \(s\) 为权值的最小生成树,更新答案即可。
直接这样做是 \(O(M^2)\) 的,但显然这个思路很可做,考虑优化。
发现对于一条边 \(i\),如果前 \(k\) 条边的最小生成树不包括 \(i\),则前 \(k+1\) 条边的最小生成树也不可能包含 \(i\)。
正确性显然,不作证明。
那么有效的边的数量是 \(O(N)\) 级别的,此时这个算法就已经有通过此题的希望了。
考虑如何删边。使用 std::multiset
单次操作 \(O(\log N)\),则时间复杂度 \(O(MN\log N)\)。
但这个算法我时间复杂度实现错了 还能优化。
发现每次只会加进来一条边,那完全可以使用冒泡排序 \(O(N)\) 地进行排序。
时间复杂度可以优化到 \(O(MN)\)。
Code
// Problem: CF76A Gift // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF76A // Memory Limit: 250 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; const int maxn = 205; const int maxm = 50005; typedef long long ll; struct edge { int u,v; ll g,s; edge() { u = v = g = s = 0; } edge(int u,int v,ll g,ll s):u(u),v(v),g(g),s(s){} bool operator < (const edge& p)const { return s ^ p.s ? s < p.s : (u ^ p.u ? u < p.u : v < p.v); } }E[maxm]; int n,m,pre[maxn],cnt; edge a[maxm]; ll G,S; int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); } int main() { scanf("%d %d %lld %lld",&n,&m,&G,&S); for(int i = 1;i <= m;++ i) { scanf("%d %d %lld %lld",&E[i].u,&E[i].v,&E[i].g,&E[i].s); } sort(E + 1 , E + 1 + m , [&](edge p,edge q) { return p.g < q.g; }); ll ans = 5e18; ll curS; int sumEdge,newcnt; for(int i = 1;i <= m;++ i) { a[++ cnt] = E[i];//bubble-sort for(int k = cnt;k > 1;-- k) if(a[k - 1].s > a[k].s)swap(a[k - 1] , a[k]); if(cnt < n - 1)continue ; curS = sumEdge = newcnt = 0; for(int k = 1;k <= n;++ k)pre[k] = k;//init for(int k = 1;k <= cnt;++ k) { if(find(a[k].u) == find(a[k].v)) { continue ; } ++ sumEdge; pre[find(a[k].u)] = find(a[k].v); curS = max(curS , a[k].s); a[++ newcnt] = a[k]; if(sumEdge >= n - 1)break ; } cnt = newcnt; if(sumEdge < n - 1)continue ; ans = min(ans , G * E[i].g + S * curS); } printf("%lld",ans == 5e18 ? -1 : ans); return 0; }
给大家找点乐子:
每天的固定节目了属于是 /fn
[CF1292C]Xenon‘s Attack on the Gangs
给定一棵 \(N\) 个结点的树,将 \([0,n-2]\) 中的每个数分配为每条边的权值。
使得 \(\sum\limits_{1\le s\lt t\le n} \operatorname{MEX}_{(u,v)\in path(s,t) } w(u,v)\) 最大。
\(2 \le n \le 3000\)。
差点做出来 *2300
的题QAQ。
这个数据范围明显是要 \(O(N^2)\) 的算法。
首先要注意到 \(0\),因为没有 \(0\) 的话 \(\operatorname{MEX}\) 值始终为 \(0\)。
将 \(0\) 随意放在某条边上,接下来考虑 \(1\) 的位置,因为没有 \(1\) 其它数的贡献必然更劣。
发现 \(1\) 必然和 \(0\) 接在一起,否则对答案不起作用。
再考虑 \(2\),显然 \(2\) 要放在 \(0,1\) 两条边形成的链旁边。
(说一下我的思路是怎么跑歪的:我只注意到 \(2\) 不能在 \(1\) 之前放置,但没注意到链有两端,我把注意力全放在了其中一端,另一端完全没注意 QAQ,由于思路不连贯,即使看到样例 \(2\) 注意到这点了也想不出来 qwq,后悔死了)
依次类推,可以发现,这些数所在的边组成了一条链,并且链上的权值呈单谷状。
具体而言,假设链的两端点固定在 \((s,t)\),将 \(s\to t\) 路径上的权值存入序列 \(a_{1\sim k}\),则 \(\exist j,\forall i \in [1,j),a_i \gt a_{i+1}\land \forall i \in [j,k),a_i\lt a_i+1\)。
(当然,这个玩意其实作用并没有那么大。。)
考虑怎样计算这条链的贡献。
设 \(sz(u,v)\) 表示原树中以 \(u\) 为根节点时 \(v\) 的子树大小,\(f(u,v)\) 表示以 \(u\) 为根时 \(v\) 的父亲。
若权值为 \(0\) 的边两端点为 \(u,v\),则 \((u,v)\) 对答案的贡献为 \(sz(v,u)\times sz(u,v)\)。
这并不难理解,其实就是经过 \((u,v)\) 这条边的路径数量,显然这些路径 \(\operatorname{MEX}\) 值至少为 \(1\)。
接下来,考虑权值为 \(1\) 的边,设其两端点为 \(v,t\)。
则 \((v,t)\) 对答案的贡献为 \(sz(u,t)\times sz(t,u)\)。
这其实代表着经过 \(u\to v \to t\) 这条链的路径数量,这些路径 \(\operatorname{MEX}\) 值至少为 \(2\)。
手玩几步就能发现统计答案的方法,开三个数组:
-
\(dp(u,v)\):表示链的两段为 \(u,v\) 时答案的最大值。
-
\(sz(u,v),f(u,v)\),含义见上文。
初始状态:\(\forall i \in [1,n],dp(i,i)=0\)
状态转移方程:\(dp(u,v)=\max\{dp(f(u,v),u),dp(f(v,u),v)\}+sz(u,v)\times sz(v,u)\)
\(sz\) 数组和 \(f\) 数组可以 \(O(N^2)\) 预处理,DP 的顺序不太好搞,用记忆化搜索会轻松不少。
时间复杂度 \(O(N^2)\)。
Code
答案的最大值没算对,结果不开 long long
见祖宗了 QAQ。
// Problem: CF1292C Xenon's Attack on the Gangs // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF1292C // Memory Limit: 500 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define pb emplace_back using namespace std; typedef long long ll; const int maxn = 3005; vector<int> G[maxn]; int n,ans; int sz[maxn][maxn],f[maxn][maxn]; ll dp[maxn][maxn]; void dfs(int u,int s) { sz[s][u] = 1; for(auto& v : G[u]) { if(v == f[s][u])continue ; f[s][v] = u; dfs(v , s); sz[s][u] += sz[s][v]; } return ; } ll DP(int u,int v) { if(u == v)return 0; if(dp[u][v])return dp[u][v]; if(dp[v][u])return dp[v][u]; return dp[u][v] = dp[v][u] = max(DP(f[u][v] , u) , DP(f[v][u] , v)) + 1ll * sz[u][v] * sz[v][u]; } int main() { scanf("%d",&n); for(int i = 2;i <= n;++ i) { int u,v; scanf("%d%d",&u,&v); G[u].pb(v); G[v].pb(u); } ll ans = 0; for(int i = 1;i <= n;++ i) { dfs(i , i); } for(int i = 1;i <= n;++ i) for(int j = 1;j <= n;++ j)ans = max(ans , DP(i , j)); printf("%lld\n",ans); return 0; }
[luogu P3987]我永远喜欢珂朵莉~
当初立的 flag,现在来填坑。
首先要注意到:\(x=1\) 时,操作可以直接跳过。
那么 \(a_i\) 最多只会被操作 \(\log a_i\) 次。
那么怎样操作不关键,怎样快速找到操作的数才是关键。
由于 \(a_i \in [0,5\times 10^5]\),约数至多约 \(200\) 个,我们可以对每个 \(x\) 开一个 std::vector
存储其倍数出现的位置。
每次操作的时候二分出操作的区间,直接暴力操作,暴力删除。
要注意的是,由于 std::vector.erase
操作的特殊性,删除要从后往前。
Code
// Problem: P3987 我永远喜欢珂朵莉~ // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3987 // Memory Limit: 1250 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define VEC vector<int>::iterator #define pb emplace_back using namespace std; const int maxn = 1e5 + 5; const int maxm = 5e5 + 5; typedef long long ll; int n,m,a[maxn]; ll c[maxn]; vector<int> s[maxm]; inline int read() { int s = 0; char c = getchar(); for(;!isdigit(c);c = getchar()); for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0'); return s; } void write(ll x) { if(x > 9)write(x / 10); putchar(x % 10 + '0'); return ; } int lowbit(int x) { return x & -x; } void add(int x,int y) { for(;x <= n;x += lowbit(x))c[x] += y; return ; } ll query(int x) { ll ans = 0; for(;x;x -= lowbit(x))ans += c[x]; return ans; } int main() { n = read(); m = read(); for(int i = 1;i <= n;++ i) { a[i] = read(); add(i , a[i]); for(int j = 1;j * j <= a[i];++ j) { if(a[i] % j)continue ; s[j].pb(i); if(j * j != a[i])s[a[i] / j].pb(i); } } while(m --) { int op = read(),l = read(),r = read(),x; if(op & 1) { x = read(); if(x == 1||s[x].empty())continue ; VEC itl = lower_bound(s[x].begin() , s[x].end() , l); VEC itr = upper_bound(s[x].begin() , s[x].end() , r); if(itl == s[x].end())continue ; vector<VEC> G; for(VEC it = itl;it != itr;++ it) { if(a[*it] % x)continue ; add(*it , -a[*it] + a[*it] / x); a[*it] /= x; if(a[*it] % x)G.pb(it); } for(int i = G.size() - 1;~ i;-- i)s[x].erase(G[i]); } else { write(query(r) - query(l - 1)); puts(""); } } return 0; }
晚上用小号打了场 CF Edu Round,太坑了 QAQ,手速场,C 题毒瘤吃了两发罚时,DF 不会,E 压根没看 /kel
为什么和大佬们的差距这么遥不可及 qwq。
这篇关于2022.8.4 颓废记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行