寒鸽儿のBlog

T2 fst Rnk8 丢人了

T1 追击问题

判断位移和相对速度方向是否一致即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll x, a, y, b;
	cin >> x >> a >> y >> b;
	if((x - y) * (a - b) < 0) {
		cout << "YES" << '\n';	
	} else {
		cout << "NO" << '\n';
	}
	return 0;
}

T2 最短路问题

如果没有额外的边，直接在图上跑BFS即可。
对于特殊边，显然，如果一个集合的某点先被访问，那么其他点到另一个集合的边就没有更新距离的作用了。所以实际上有效的边只有$\mathcal{O(a + b)}$而不是$\mathcal{O(ab)}$。
所以动态判断这些边的处理即可。
复杂度$\mathcal{O(n + m)}$

#include <bits/stdc++.h>

using namespace std;

vector< vector<int> > edge;
vector<int> dis, c, d;
vector<bool> isC, isD;

queue<int> q;
void bfs() {
	bool visc = false, visd = false;
	q.push(1);
	dis[1] = 0;
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(int ver : edge[cur])
			if(!~dis[ver]) {
				dis[ver] = dis[cur] + 1;
				q.push(ver);
			}
		if(isC[cur] && !visd) {
			visd = true;
			for(int ver : d)
				if(!~dis[ver]) {
					dis[ver] = dis[cur] + 1;	
					q.push(ver);
				}
		}
		if(isD[cur] && !visc) {
			visc = true;
			for(int ver : c)
				if(!~dis[ver]) {
					dis[ver] = dis[cur] + 1;
					q.push(ver);	
				}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b, tmp, u, v;
	cin >> n >> m;
	edge.resize(n + 1);
	dis.assign(n + 1, -1);
	isC.assign(n, false);
	isD.assign(n, false);
	for(int i = 1; i <= m; ++i) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	cin >> a >> b;
	c.resize(a);
	d.resize(b);
	for(int i = 0; i < a; ++i) {
		cin >> tmp;
		isC[tmp] = true;
		c[i] = tmp;
	}
	for(int i = 0; i < b; ++i) {
		cin >> tmp;
		isD[tmp] = true;
		d[i] = tmp;
	}
	bfs();
	for(int i = 1; i <= n; ++i)
		cout << dis[i] << '\n';
	return 0;
}

T3 数码问题

咕咕咕。。。

T4 三角形问题

考虑构造最小的不能满足三角形的数列。
$1, 1, 2, 3, 5, 8, ...$
事斐波那契！
第84项斐波那契$\geqslant 10^{18}$, 根据抽屉原理, 树上路径长度$\geqslant 84$的一定能构成。
$\leqslant 84$的路径直接暴力求点权。
复杂度$\mathcal{O((q + n)logn)}$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 567890;
int t[maxn], k[maxn], b[maxn], head[maxn], ver[maxn<<1], nex[maxn<<1], tot;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; head[u] = tot++;	
}
int n, q;

int fa[maxn][32], dep[maxn];
void dfs(int cur, int pre) {
	dep[cur] = dep[pre] + 1; fa[cur][0] = pre;
	for(int i = 1; i <= 30; ++i) fa[cur][i] = fa[fa[cur][i-1]][i-1];
	for(int i = head[cur]; ~i; i = nex[i])
		if(!dep[ver[i]]) dfs(ver[i], cur);
	
}

int lca(int u, int v) {
	if(dep[u] < dep[v])	swap(u, v);
	for(int i = 30; ~i; --i) 
		if(dep[fa[u][i]] >= dep[v])	u = fa[u][i];
	if(u == v) return u;
	for(int i = 30; ~i; --i)
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

int main() {
	srand((unsigned)time(0));
	memset(head, -1, sizeof(head));
	ios::sync_with_stdio(false);
	cin.tie(0);
	int u, v;
	ll x;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin	>> t[i] >> k[i] >> b[i];
	for(int i = 1; i < n; ++i) {
		cin >> u >> v;
		addedge(u, v);
		addedge(v, u);
	}
	dfs(1, 1);
	cin >> q;
	while(q--) {
		cin >> u >> v >> x;
		int lc = lca(u, v);
		if(-2 * dep[lc] + dep[v] + dep[u] + 1 >= 84)
			cout << "YES" << '\n';
		else if(u == v) {
			cout << "NO" << '\n';
		} else {
			vector<ll> vec;
			while(u != lc) {
				vec.push_back(x * x * t[u] + x * k[u] + b[u]);
				u = fa[u][0];
			}
			while(v != lc) {
				vec.push_back(x * x * t[v] + x * k[v] + b[v]);
				v = fa[v][0];
			}
			vec.push_back(x * x * t[lc] + x * k[lc] + b[lc]);
			random_shuffle(vec.begin(), vec.end());
			bool flg = true;
			for(int i = 0; flg && i < vec.size(); ++i)
				for(int j = 0; flg && j < vec.size(); ++j)
					for(int k = 0; flg && k < vec.size(); ++k)
						if(i < j && j < k) {
							ll sum = vec[i] + vec[j] + vec[k];
							ll mx = max(max(vec[i], vec[j]), vec[k]);
							if(sum - mx > mx) {
								flg = false;
								break;	
							}
						}
			if(!flg) {
				cout << "YES" << '\n';	
			} else {
				cout << "NO"<< '\n';	
			}
		}
	}
	return 0;
}