CSP-S开小灶1
2022/9/5 23:25:38
本文主要是介绍CSP-S开小灶1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
居然敢嫌弃Cat的文化课不让Cat来参加半集训!?哼这是不可能的Cat哭给你看!……
A. ZZH的游戏
WA 15:emmm想到了二分,然后判断的时候我没有想到让它贪心地走到尽量小的节点,而是让它尽量跳father,我怕它尽量往小跳反而偏离了终点结束不了游戏,跳不了了就让另一棵树后退到最小的儿子(这或许是WA的原因,因为最小儿子的最小儿子不一定比次小儿子的最小儿子小,但总之还是骗到了15分),以1为根建树当然跳到根游戏就结束了。
是的是的是的我又鹤了%%%Chen_jr的题解
一开始看到正解上的从s+t开始不行了+1就好迷迷糊糊,这怎么可能比二分快,鹤完代码才知道这个+1指的是在过程中加,意思就是每组数据大模拟只有一次。
保存每个点能到达的最小位置,用它直接作为另一棵树拓展的条件,可以避免会T的后退操作,所以可以要求每个点最多经过一次。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 2; const int N = 60; const ll mod = 1e9 + 7; int T, s, t, n; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') { f = -1; } ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch^48); ch = getchar(); } return x * f; } struct tree { struct edge { int next, to; }a[maxn<<1]; int head[maxn], len; void add(int x, int y) { a[++len].to = y; a[len].next = head[x]; head[x] = len; } bool vis[maxn]; int mi = maxn + maxn + maxn; priority_queue<int, vector<int>, greater<int> > q; void clear() { for(int i=1; i<=n; i++) head[i] = 0; for(int i=1; i<=n; i++) vis[i] = 0; len = 0; mi = maxn + maxn + maxn; while(!q.empty()) q.pop(); } void build() { for(int i=1; i<n; i++) { int x = read(), y = read(); add(x, y); add(y, x); } } bool expand(int mx) { bool flag = 0; while(!q.empty()) { int x = q.top(); if(x > mx) break; q.pop(); vis[x] = 1; flag = 1; mi = min(mi, x); for(int i=head[x]; i; i=a[i].next) { int v = a[i].to; if(vis[v]) continue; q.push(v); } } return flag; } void set(int x) {mi = x; q.push(x);} }t1, t2; int solve() { n = read(); t1.build(); t2.build(); s = read(); t = read(); int ans = s + t; t1.set(s); t2.set(t); t1.expand(s); t2.expand(t); while(1) { bool f1 = 1, f2 = 1; while(f1 || f2) { if(t1.mi == 1 && t2.mi == 1) return ans; f1 = t1.expand(ans-t2.mi); f2 = t2.expand(ans-t1.mi); } ans++; } } int main() { T = read(); while(T--) { printf("%d\n", solve()); t1.clear(); t2.clear(); } return 0; }View Code
B. ZZH与背包
枚举一下每个物品选或不选TLE11***鹤个题解去……
这篇关于CSP-S开小灶1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升