bzoj 3251
2024-09-06 03:03:43
http://www.lydsy.com/JudgeOnline/problem.php?id=3251
这道题在北京八十中的时候有人讲过。。 不过由于自己continue 写掉了一个所以调了很久。
做法是如果整个序列没有合法三角形的话,那么整个链长不超过50个(最大的情况是斐波那契数列) 所以大于50个一定成立, 小于50个排序扫一遍就好了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long ll; const ll maxn = 200010;
const ll maxv = 50; ll int_get() {
ll x = 0; char c = (char)getchar(); bool f = 0;
while(!isdigit(c)) {
if(c == '-') f = 1;
c = (char)getchar();
}
while(isdigit(c)) {
x = x * 10 + (ll)(c - '0');
c = (char)getchar();
}
if(f) x = -x;
return x;
} struct edge {
ll t; edge* next;
}e[maxn * 2], *head[maxn]; ll ne = 0; void addedge(ll f, ll t) {
e[ne].t = t, e[ne].next = head[f], head[f] = e + ne ++;
} ll h[maxn];
ll n, m, v[maxn], fa[maxn]; void dfs(ll x, ll pre) {
h[x] = h[pre] + 1; fa[x] = pre;
for(edge* p = head[x]; p; p = p-> next) {
if(p-> t != pre) dfs(p-> t, x);
}
} void read() {
n = int_get(); m = int_get();
for(ll i = 1; i <= n; ++ i) v[i] = int_get();
for(ll i = 1; i < n; ++ i) {
ll f, t;
f = int_get(), t = int_get();
addedge(f, t), addedge(t, f);
}
dfs(1, 0);
} ll sta[maxn], top = 0; void sov() {
while(m --) {
ll opt = int_get();
if(!opt) {
ll a = int_get(), b = int_get();
top = 0;
if(h[a] < h[b]) swap(a, b);
while(h[a] != h[b] && top <= maxv) sta[++ top] = v[a], a = fa[a];
if(a != b) {
while(a != b && top <= maxv) sta[++ top] = v[a], sta[++ top] = v[b], a = fa[a], b = fa[b];
}
sta[++ top] = v[a];
if(top >= maxv) {
printf("Y\n"); continue;
}
sort(sta + 1, sta + top + 1); bool f = 0;
for(ll i = 1; i < top - 1 && !f; ++ i) {
if(sta[i] + sta[i + 1] > sta[i + 2]) f = 1;
}
if(f) printf("Y\n");
else printf("N\n");
}
else {
ll p = int_get(), w = int_get();
v[p] = w;
}
}
} int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
read(), sov();
return 0;
}
最新文章
- working with fitnesse wiki pages
- Height Half Values
- JS获取当前对象大小以及屏幕分辨率等...
- contiki-进程
- js 实现ActiveXObject(";Scripting.Dictionary";) 功能
- webService调用
- Android开发-API指南-<;meta-data>;
- 在Oracle中更新数据时,抛出:ORA-01008: not all variables bound
- jquery中onclick=";fn";中$(this)所代表的对象
- HTML5-常见的事件- DOMContentLoaded事件
- zf-分页后台代码
- 关于使用JQuery追加Option标签时使用三元运算符添加选中属性的解决办法
- mysql varchar和char的根本区别深度详解
- 基于 OS X Mavericks 系统
- 6种纯css实现loading效果
- 使用tcpreply对DPDK进行压力测试(一台主机,2张网卡压测)
- C语言 &#183; 单词数统计
- 存储器结构、cache、DMA架构分析--【原创】
- mobx-state-tree 知识点
- DOS批处理中%cd%和%~dp0的异同分析