cms网站模板下载,为什么建设银行的网站打不开,网页截图快捷键可拉动,wordpress启用主题500错误C - Humidifier 3
Description
一个 h w h \times w hw 的网格#xff0c;每个格子可能是墙、空地或者城堡。 一个格子是好的#xff0c;当且仅当从至少一个城堡出发#xff0c;走不超过 d d d 步能到达。#xff08;只能上下左右走#xff0c;不能穿墙#xff09;每个格子可能是墙、空地或者城堡。 一个格子是好的当且仅当从至少一个城堡出发走不超过 d d d 步能到达。只能上下左右走不能穿墙求好格子的数量。
Solution
从每一个城堡出发进行 bfs对所有 d 步内能走到的点进行标记。 为了效率可以把所有城堡丢入队列中一次搜完。
Code
// Problem: C - Humidifier 3
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024AtCoder Beginner Contest 383
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;using i64 long long;
using ui64 unsigned long long;
using i128 __int128;
using ui128 unsigned __int128;
using f4 float;
using f8 double;
using f16 long double;templateclass T
bool chmax(T a, const T b){if(a b){ a b; return true; }return false;
}templateclass T
bool chmin(T a, const T b){if(a b){ a b; return true; }return false;
}const int dx[] {0, -1, 0, 1}, dy[] {1, 0, -1, 0};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int h, w, d;cin h w d;vectorstring a(h);for (int i 0; i h; i) {cin a[i];}queuetupleint, int, int que;vector visit(h, vectorbool(w, false));auto check [](int x, int y) {return x 0 x h y 0 y w a[x][y] ! # !visit[x][y];};auto enque [](int x, int y, int step) {if (check(x, y)) {que.emplace(x, y, step);visit[x][y] true;}};for (int i 0; i h; i) {for (int j 0; j w; j) {if (a[i][j] H) {enque(i, j, 0);}}}while (!que.empty()) {auto [x, y, step] que.front();que.pop();if (step d) continue;for (int i 0; i 4; i) {int nx x dx[i], ny y dy[i];enque(nx, ny, step 1);}}int ans 0;for (int i 0; i h; i) {ans accumulate(visit[i].begin(), visit[i].end(), 0);}cout ans;return 0;
}D - 9 Divisors
Description
给定 n n n求 [ 1 , n ] [1, n] [1,n] 中正好有 9 9 9 个因数的数的数量。 1 ≤ n ≤ 1 0 12 1 \le n \le 10^{12} 1≤n≤1012
Solution
由因数个数定理知满足条件的数 t t t只有两种可能 t p 8 tp^8 tp8 t p 1 2 × p 2 2 tp_1^2 \times p_2^2 tp12×p22
显然 p p p 一定 ≤ n \le \sqrt{n} ≤n 所以只需筛出 n \sqrt{n} n 内的质数即可。 显然答案远小于 n \sqrt{n} n 看大样例也知道因此枚举即可。 注意及时跳出循环特别是情况2否则会 TLE
Code
// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024AtCoder Beginner Contest 383
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;using i64 long long;
using ui64 unsigned long long;
using i128 __int128;
using ui128 unsigned __int128;
using f4 float;
using f8 double;
using f16 long double;templateclass T
bool chmax(T a, const T b){if(a b){ a b; return true; }return false;
}templateclass T
bool chmin(T a, const T b){if(a b){ a b; return true; }return false;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);i64 n;cin n;vectorbool isp;vectorint primes;auto sieve [](int n) {isp.assign(n 1, true);primes.clear();isp[0] isp[1] false;for (int i 2; i n; i) {if (isp[i]) {primes.push_back(i);for (int j i i; j n; j i) {isp[j] false;}}}};int m sqrt(n);sieve(m);int ans 0;for (auto p : primes) {if (1LL * p * p * p * p m) {ans;}else {break;}}for (int i 0; i primes.size(); i) {for (int j i 1; j primes.size() 1LL * primes[i] * primes[j] m; j) {ans;}}cout ans;return 0;
}E - Sum of Max Matching
Description
定义 f ( s , t ) f(s,t) f(s,t) 为 s , t s,t s,t 间的最小瓶颈路。路径上最大边权的最小值。 给定 n n n 点 m m m 边的无向图和两个序列 a ( a 1 , a 2 , ⋯ , a k ) a(a_1,a_2,\cdots,a_k) a(a1,a2,⋯,ak) b ( b 1 , b 2 , ⋯ , b k ) b(b_1,b_2,\cdots,b_k) b(b1,b2,⋯,bk)重排 b b b 使得 ∑ i 1 k f ( a i , b i ) \displaystyle \sum_{i1}^k f(a_i,b_i) i1∑kf(ai,bi) 最小。
Solution
关于最小瓶颈路有一个结论两点间的最小瓶颈路就是最小生成树上两点间的最大边权。
据此可以得到一个思路 首先将每个点 u u u 看成一个集合其中有 c n t a u cnta_u cntau 个红点和 c n t b u cntb_u cntbu 个蓝点。 然后仿照最小生成树的做法在合并集合时将红蓝点对配对消去答案加上消去的点对数 × w \times w ×w。 由上面结论可知这个方法是正确的。
Code
// Problem: E - Sum of Max Matching
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024AtCoder Beginner Contest 383
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_e
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;using i64 long long;
using ui64 unsigned long long;
using i128 __int128;
using ui128 unsigned __int128;
using f4 float;
using f8 double;
using f16 long double;templateclass T
bool chmax(T a, const T b){if(a b){ a b; return true; }return false;
}templateclass T
bool chmin(T a, const T b){if(a b){ a b; return true; }return false;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, k;cin n m k;vectorarrayint, 3 edges(m);for (auto [u, v, w] : edges) {cin u v w;u--, v--;}sort(edges.begin(), edges.end(), [](const arrayint, 3 a, const arrayint, 3 b) {return a[2] b[2];});vectorint ca(n), cb(n);for (int i 0, x; i k; i) {cin x;x--;ca[x];}for (int i 0, x; i k; i) {cin x;x--;cb[x];}vectorint p(n);iota(p.begin(), p.end(), 0);auto find [](auto self, int x) - int {if (x ! p[x]) p[x] self(self, p[x]);return p[x];};i64 ans 0;for (auto [u, v, w] : edges) {int x find(find, u), y find(find, v);if (x y) {continue;}ca[x] ca[y];cb[x] cb[y];int t min(ca[x], cb[x]);ans 1LL * t * w;ca[x] - t;cb[x] - t;p[y] x;}cout ans;return 0;
}F - Diversity
Description
有 n n n 个物品第 i i i 个的价格为 p i p_i pi价值为 u i u_i ui颜色为 c i c_i ci。 定义一种选择的价值为 ∑ u t × k \sum ut \times k ∑ut×k其中 t t t 是所选物品的不同颜色种类数 k k k 为给定常数。 你需要选择一些物品可以不选在所选物品总价格不超过 x x x 的前提下求最大价值。
Solution
容易看出是 0-1背包 的变式首先按颜色对物品分组。 设 d p i , j dp_{i,j} dpi,j 为考虑前 i i i 种颜色总价格在 j j j 以内的最大价值。 对于第 i i i 个颜色额外考虑从上一个颜色即 d p i − 1 , j − p u k dp_{i-1,j-p}uk dpi−1,j−puk 转移过来即可。 注意要跳过不存在的颜色。
Code
滚掉了第一维。
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024AtCoder Beginner Contest 383
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;using i64 long long;
using ui64 unsigned long long;
using i128 __int128;
using ui128 unsigned __int128;
using f4 float;
using f8 double;
using f16 long double;templateclass T
bool chmax(T a, const T b){if(a b){ a b; return true; }return false;
}templateclass T
bool chmin(T a, const T b){if(a b){ a b; return true; }return false;
}const i64 inf 1e18;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, v, k;cin n v k;vectorvectorpairint, int adj(n);for (int i 0, p, u, c; i n; i) {cin p u c;c--;adj[c].emplace_back(p, u);}vectori64 dp(v 1, -inf);dp[0] 0;for (int c 0; c n; c) {if (adj[c].empty()) {continue;}vectori64 dp2 dp;for (auto [p, u] : adj[c]) {for (int i v; i p; i--) {dp2[i] max({dp2[i], dp2[i - p] u, dp[i - p] u k});}}dp.swap(dp2);}cout *max_element(dp.begin(), dp.end());return 0;
}
文章转载自： http://www.morning.qptbn.cn.gov.cn.qptbn.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.xyyplp.cn.gov.cn.xyyplp.cn http://www.morning.pzqnj.cn.gov.cn.pzqnj.cn http://www.morning.gswfs.cn.gov.cn.gswfs.cn http://www.morning.nmqdk.cn.gov.cn.nmqdk.cn http://www.morning.srltq.cn.gov.cn.srltq.cn http://www.morning.qwbtr.cn.gov.cn.qwbtr.cn http://www.morning.mqxrx.cn.gov.cn.mqxrx.cn http://www.morning.dpwcl.cn.gov.cn.dpwcl.cn http://www.morning.yhpl.cn.gov.cn.yhpl.cn http://www.morning.hrpmt.cn.gov.cn.hrpmt.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.lpsjs.com.gov.cn.lpsjs.com http://www.morning.mfct.cn.gov.cn.mfct.cn http://www.morning.lqytk.cn.gov.cn.lqytk.cn http://www.morning.rrwft.cn.gov.cn.rrwft.cn http://www.morning.hpkr.cn.gov.cn.hpkr.cn http://www.morning.gsjw.cn.gov.cn.gsjw.cn http://www.morning.rjhts.cn.gov.cn.rjhts.cn http://www.morning.gppqf.cn.gov.cn.gppqf.cn http://www.morning.mqghs.cn.gov.cn.mqghs.cn http://www.morning.dpbgw.cn.gov.cn.dpbgw.cn http://www.morning.xrpjr.cn.gov.cn.xrpjr.cn http://www.morning.ymdhq.cn.gov.cn.ymdhq.cn http://www.morning.rjmg.cn.gov.cn.rjmg.cn http://www.morning.bdypl.cn.gov.cn.bdypl.cn http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.lcwhn.cn.gov.cn.lcwhn.cn http://www.morning.dlgjdg.cn.gov.cn.dlgjdg.cn http://www.morning.qnbgk.cn.gov.cn.qnbgk.cn http://www.morning.qnbgh.cn.gov.cn.qnbgh.cn http://www.morning.wqpm.cn.gov.cn.wqpm.cn http://www.morning.yxlhz.cn.gov.cn.yxlhz.cn http://www.morning.nwcgj.cn.gov.cn.nwcgj.cn http://www.morning.jmllh.cn.gov.cn.jmllh.cn http://www.morning.cwrnr.cn.gov.cn.cwrnr.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.ydnxm.cn.gov.cn.ydnxm.cn http://www.morning.dydqh.cn.gov.cn.dydqh.cn http://www.morning.nzzws.cn.gov.cn.nzzws.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.iqcge.com.gov.cn.iqcge.com http://www.morning.xtqr.cn.gov.cn.xtqr.cn http://www.morning.bhqlj.cn.gov.cn.bhqlj.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.xzlp.cn.gov.cn.xzlp.cn http://www.morning.lnbcg.cn.gov.cn.lnbcg.cn http://www.morning.sffwz.cn.gov.cn.sffwz.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.zzjpy.cn.gov.cn.zzjpy.cn http://www.morning.cfnsn.cn.gov.cn.cfnsn.cn http://www.morning.hphrz.cn.gov.cn.hphrz.cn http://www.morning.tclqf.cn.gov.cn.tclqf.cn http://www.morning.fwcnx.cn.gov.cn.fwcnx.cn http://www.morning.qzglh.cn.gov.cn.qzglh.cn http://www.morning.qxxj.cn.gov.cn.qxxj.cn http://www.morning.dxhdn.cn.gov.cn.dxhdn.cn http://www.morning.zckhn.cn.gov.cn.zckhn.cn http://www.morning.ghjln.cn.gov.cn.ghjln.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.qfzjn.cn.gov.cn.qfzjn.cn http://www.morning.qjtbt.cn.gov.cn.qjtbt.cn http://www.morning.jrtjc.cn.gov.cn.jrtjc.cn http://www.morning.zfwjh.cn.gov.cn.zfwjh.cn http://www.morning.znmwb.cn.gov.cn.znmwb.cn http://www.morning.webife.com.gov.cn.webife.com http://www.morning.mgtrc.cn.gov.cn.mgtrc.cn http://www.morning.hbfqm.cn.gov.cn.hbfqm.cn http://www.morning.yzktr.cn.gov.cn.yzktr.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.gtbjf.cn.gov.cn.gtbjf.cn http://www.morning.lqffg.cn.gov.cn.lqffg.cn http://www.morning.ykyfq.cn.gov.cn.ykyfq.cn http://www.morning.jklns.cn.gov.cn.jklns.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.jzykw.cn.gov.cn.jzykw.cn http://www.morning.bnlch.cn.gov.cn.bnlch.cn
