居然敢嫌弃Cat的文化课不让Cat来参加半集训!?哼这是不可能的Cat哭给你看!……
A. ZZH的游戏
WA 15:emmm想到了二分,然后判断的时候我没有想到让它贪心地走到尽量小的节点,而是让它尽量跳father,我怕它尽量往小跳反而偏离了终点结束不了游戏,跳不了了就让另一棵树后退到最小的儿子(这或许是WA的原因,因为最小儿子的最小儿子不一定比次小儿子的最小儿子小,但总之还是骗到了15分),以1为根建树当然跳到根游戏就结束了。
是的是的是的我又鹤了%%%Chen_jr的题解
一开始看到正解上的从s+t开始不行了+1就好迷迷糊糊,这怎么可能比二分快,鹤完代码才知道这个+1指的是在过程中加,意思就是每组数据大模拟只有一次。
保存每个点能到达的最小位置,用它直接作为另一棵树拓展的条件,可以避免会T的后退操作,所以可以要求每个点最多经过一次。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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***鹤个题解去……
标签:ch,int,mi,t2,t1,read,开小灶,CSP From: https://www.cnblogs.com/Catherine2006/p/16659444.html