公明网站建设,东莞最穷的三个镇,vue 企业网站模板,网页游戏排行榜2024AtCoder Beginner Contest 324
F Beautiful Path
需要一点思维的转化#xff0c;一时竟然没想到。
题意
给定大小为 n n n 的有向图#xff0c; m m m 条边#xff0c;每条边有 b i , c i b_i,c_i bi,ci 两个属性#xff0c;需要找到一条从 1 ∼ n 1\sim n 1∼n…AtCoder Beginner Contest 324
F Beautiful Path
需要一点思维的转化一时竟然没想到。
题意
给定大小为 n n n 的有向图 m m m 条边每条边有 b i , c i b_i,c_i bi,ci 两个属性需要找到一条从 1 ∼ n 1\sim n 1∼n 的路径使得 w i ( b 1 b 2 ⋯ b k ) / ( c 1 c 2 ⋯ c k ) w_i (b_1b_2\dotsb_k) / (c_1c_2\dotsc_k) wi(b1b2⋯bk)/(c1c2⋯ck) 最大。题目保证路径一定存在且无环。
思路
初看一时没思路写了个到达 u u u 点时以 w i w_i wi 的最大值为最优跑拓扑排序这样显然是不对的例如 1 1 → 3 2 1 3 1 2 \frac 11\rightarrow \frac32 \frac{13}{12} 11→231213 会比 1 1 → 1 1 1 1 1 1 \frac11\rightarrow \frac11\frac{11}{11} 11→111111 更优但是若是下一条边是 100 1 \frac{100}1 1100两条路径更优的是 1 1 100 1 1 1 1 3 100 1 2 1 \frac{11100}{111}\frac{13100}{121} 1111110012113100.
这里需要转换一下思路 求路径使得 max ( b 1 b 2 b 3 ) / ( c 1 c 2 c 3 ) w i \max(b_1 b_2 b_3) / (c_1 c_2 c_3) w_i max(b1b2b3)/(c1c2c3)wi 设答案为 r e s res res ( b 1 b 2 b 3 ) / ( c 1 c 2 c 3 ) r e s (b_1 b_2 b_3) / (c_1 c_2 c_3) res (b1b2b3)/(c1c2c3)res ( b 1 b 2 b 3 ) ( c 1 c 2 c 3 ) ∗ r e s (b_1 b_2 b_3) (c_1 c_2 c_3) * res (b1b2b3)(c1c2c3)∗res b 1 − c 1 ∗ r e s b 2 − c 2 ∗ r e s b 3 − c 3 ∗ r e s 0 b_1 - c_1 * res b_2 - c_2 * res b_3 - c_3 * res 0 b1−c1∗resb2−c2∗resb3−c3∗res0 上式将 改成 ≥ \geq ≥ 显然也成立于是就有了单调性二分答案求解。
用拓扑排序时有个小坑点从 1 1 1 出发可能有些节点到达不了需要清除这些点的度。或者由于一定是小编号 → \rightarrow → 大编号可以直接循环求解。
代码
#include bits/stdc.h
using namespace std;#define ll long long
#define double long doubleconst int N 2e5 10;struct node{int v, b, c;
};
vectornode g[N];int n, m, d[N], t[N];
double f[N];
bool topu(double x){queueint q;for(int i 1; i n; i ){t[i] d[i];f[i] -1e10;}q.push(1);f[1] 0.0;while(!q.empty()){int u q.front(); q.pop();for(auto [v, b, c] : g[u]){f[v] max(f[v], f[u] (double)b - (double)c * x);t[v] --;if(!t[v]) q.push(v);}}return f[n] 0;
}int vis[N];
void dfs(int u){if(vis[u]) return ;vis[u] 1;for(auto [v, a, b] : g[u]) dfs(v);
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;for(int i 1; i m; i ){int u, v, b, c;cin u v b c;g[u].push_back({v, b, c});d[v] ;}dfs(1);for(int i 1; i n; i ){ // 清除无法到达的节点的度if(vis[i]) continue ;for(auto [v, a, b] : g[i]) d[v] --;}double l 0, r 2e9;for(int i 1; i 100; i ){double mid (l r) / 2;if(topu(mid)) l mid;else r mid;}cout fixed setprecision(20) l \n;return 0;
}G Generate Arrays待补
题意
思路
代码 文章转载自： http://www.morning.rdxp.cn.gov.cn.rdxp.cn http://www.morning.ywpwq.cn.gov.cn.ywpwq.cn http://www.morning.kyctc.cn.gov.cn.kyctc.cn http://www.morning.dmjhp.cn.gov.cn.dmjhp.cn http://www.morning.rpkl.cn.gov.cn.rpkl.cn http://www.morning.phechi.com.gov.cn.phechi.com http://www.morning.ktskc.cn.gov.cn.ktskc.cn http://www.morning.yhwxn.cn.gov.cn.yhwxn.cn http://www.morning.mbpzw.cn.gov.cn.mbpzw.cn http://www.morning.hjjkz.cn.gov.cn.hjjkz.cn http://www.morning.tjwfk.cn.gov.cn.tjwfk.cn http://www.morning.ymwrs.cn.gov.cn.ymwrs.cn http://www.morning.sfgtp.cn.gov.cn.sfgtp.cn http://www.morning.tftw.cn.gov.cn.tftw.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.dbbcq.cn.gov.cn.dbbcq.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.kczkq.cn.gov.cn.kczkq.cn http://www.morning.yjqkk.cn.gov.cn.yjqkk.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.jwtjf.cn.gov.cn.jwtjf.cn http://www.morning.phlwj.cn.gov.cn.phlwj.cn http://www.morning.krswn.cn.gov.cn.krswn.cn http://www.morning.cspwj.cn.gov.cn.cspwj.cn http://www.morning.rkxdp.cn.gov.cn.rkxdp.cn http://www.morning.dfltx.cn.gov.cn.dfltx.cn http://www.morning.ljdjn.cn.gov.cn.ljdjn.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.xbptx.cn.gov.cn.xbptx.cn http://www.morning.lcxdm.cn.gov.cn.lcxdm.cn http://www.morning.ymwnc.cn.gov.cn.ymwnc.cn http://www.morning.demoux.com.gov.cn.demoux.com http://www.morning.cdygl.com.gov.cn.cdygl.com http://www.morning.hymmq.cn.gov.cn.hymmq.cn http://www.morning.qclmz.cn.gov.cn.qclmz.cn http://www.morning.dwxqf.cn.gov.cn.dwxqf.cn http://www.morning.zbkdm.cn.gov.cn.zbkdm.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.ykswq.cn.gov.cn.ykswq.cn http://www.morning.rtqyy.cn.gov.cn.rtqyy.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.ggnjq.cn.gov.cn.ggnjq.cn http://www.morning.mlgsc.com.gov.cn.mlgsc.com http://www.morning.zzjpy.cn.gov.cn.zzjpy.cn http://www.morning.yunease.com.gov.cn.yunease.com http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.jqwpw.cn.gov.cn.jqwpw.cn http://www.morning.kspfq.cn.gov.cn.kspfq.cn http://www.morning.tpfny.cn.gov.cn.tpfny.cn http://www.morning.rzsxb.cn.gov.cn.rzsxb.cn http://www.morning.c7617.cn.gov.cn.c7617.cn http://www.morning.kqwsy.cn.gov.cn.kqwsy.cn http://www.morning.xdttq.cn.gov.cn.xdttq.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.lgqdl.cn.gov.cn.lgqdl.cn http://www.morning.sqskm.cn.gov.cn.sqskm.cn http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.llyjx.cn.gov.cn.llyjx.cn http://www.morning.rdng.cn.gov.cn.rdng.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.xxwl1.com.gov.cn.xxwl1.com http://www.morning.iuibhkd.cn.gov.cn.iuibhkd.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.ntzfl.cn.gov.cn.ntzfl.cn http://www.morning.mqpdl.cn.gov.cn.mqpdl.cn http://www.morning.tkchg.cn.gov.cn.tkchg.cn http://www.morning.pbdnj.cn.gov.cn.pbdnj.cn http://www.morning.dfckx.cn.gov.cn.dfckx.cn http://www.morning.qnhpq.cn.gov.cn.qnhpq.cn http://www.morning.fnjrh.cn.gov.cn.fnjrh.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.nhrkc.cn.gov.cn.nhrkc.cn http://www.morning.drcnn.cn.gov.cn.drcnn.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.feites.com.gov.cn.feites.com http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn
