编程开发 购物 网址 游戏 小说 歌词 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 编程语言 -> 忧桑三角形 -> 正文阅读
 

[编程语言]忧桑三角形[第1页]

【题目描述】: 
小 J 是一名 OI 退役滚粗文化课选手,他十分喜欢做题,尤其是裸题。有 一棵树,树上每个点都有点权,现在有以下两个操作: 1. 修改某个点的点权 2. 查询点 u 和点 v 构成的简单路径上取三个点权,以这三个权值为边长 是否能构成一个三角形。 
##【输入描述】:
 第一行两个整数 N,Q,代表点数和询问数。 第二行 N 个整数表示点权。 以下 N-1 行,每行 2 个整数 a、b,表示 a 是 b 的父亲(以 1 为根的情况下)
 以下 q 行,每行 3 个整数 t、a、b 若 t=0,则询问(a,b) 否则将点 a 的权值修改为 b 
##【输出描述】:
 对于每个询问输出 Y 表示能构成三角形,输出 N 表示不能构成三角形 
##【样例输入】: 
 5 5
1 2 3 4 5 
1 2
2 3  
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3 
##【样例输出】:  
N
Y
Y

##【时间限制、数据范围及描述】:
 时间:1s 空间:256M 
对于 30%的数据有 N,Q<= 1000  
对于 100%的数据有 N,Q<= 10^5,点权范围在 32 位整数范围内 
题解Here!
一开始想到了LCA,但是判断能否构成三角形时,莫名其妙地写了个线段树维护书上区间最值,结果写炸了。。。
于是不知所措地打暴力。。。
看了题解,竟然剪枝能剪那么多,崩溃。。。
顺便吐糟一句:现在的题怎么都喜欢夹点数论。。。
附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,c=1;
int num[MAXN],head[MAXN],deep[MAXN],f[MAXN][20];
struct node{
	int next,to;
}a[MAXN<<1];
inline int read(){
       int date=0,w=1;char c=0;
       while(c<'0'|c>'9'){if(c=='-')w=-1;c=getchar();}
       while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
       return date*w;
}
bool cmp(const int &x,const int &y){
	return x<y;
}
void add(int x,int y){
	a[c].to=y;
	a[c].next=head[x];
	head[x]=c++;
	a[c].to=x;
	a[c].next=head[y];
	head[y]=c++;
}
void buildtree(int rt){
	int will;
	for(int i=head[rt];i;i=a[i].next){
		will=a[i].to;
		if(!deep[will]){
			deep[will]=deep[rt]+1;
			f[will][0]=rt;
			buildtree(will);
		}
	}
}
void step(){
	for(int i=1;i<=19;i++)
	for(int j=1;j<=n;j++)
	f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	for(int i=19;i>=0;i--)
	if(deep[f[x][i]]>=deep[y])
	x=f[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)
	if(f[x][i]!=f[y][i]){
		x=f[x][i];
		y=f[y][i];
	}
	return f[x][0];
}
bool work(int x,int y){
	int fa=LCA(x,y),u=x,v=y;
	if(deep[x]+deep[y]-2*deep[fa]>=50)return true;
	int d=1,angle[55];
	while(u!=fa){angle[d++]=num[u];u=f[u][0];}
	while(v!=fa){angle[d++]=num[v];v=f[v][0];}
	angle[d]=num[fa];
	sort(angle+1,angle+d+1,cmp);
	if(d<3)return false;
	for(int i=3;i<=d;i++)
	if(angle[i]<angle[i-1]+angle[i-2])
	return true;
	return false;
}
int main(){
	int f,x,y;
	n=read();m=read();
	for(int i=1;i<=n;i++)num[i]=read();
	for(int i=1;i<n;i++){
		x=read();y=read();
		add(x,y);
	}
	deep[1]=1;
	buildtree(1);
	step();
	while(m--){
		f=read();x=read();y=read();
		if(f==0){
			if(work(x,y))printf("Y\n");
			else printf("N\n");
		}
		else num[x]=y;
	}
	return 0;
}

阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。
本文已收录于以下专栏:

发表评论
HTML/XML objective-c Delphi Ruby PHP C# C++ JavaScript Visual Basic Python Java CSS SQL 其它
相关文章推荐

绘制三角形
2016-03-26 16:34 6KB 下载

矩形,圆形和三角形
2014-12-30 17:47 2KB 下载
5th 【基础题】组合三角形
组合三角形 【题目描述】: 桌面上凌乱地摆放着N个木棍,长度分别为{a1,a2…,ai,…an},N 【输入描述】: 第一行,一个整数N。 第二行N个木棍的长度。 【输出描述】: 只有一...
qq_39260917 2017-06-22 17:52 53

空心三角形
2017-07-17 09:12 885B 下载

动态等待层(三角形,圆,正方形交替跳动)
2016-04-08 19:00 2.76MB 下载
第三周项目一——三角形类2
int main() { Triangle tri1; //定义三角形类的一个实例(对象) double x,y,z; cout<>x>>y>>z; ...
nufangdongde 2015-03-25 13:14 371

C#杨辉三角形写入读出实例
2015-11-09 18:40 1KB 下载

计算器,单位转换,解三角形融为一体
2014-12-02 14:17 52KB 下载
[蓝桥杯]特殊的数字+杨辉三角形
一、特殊的数字 问题描述   153是一个非常特殊的数,它等于它的每位数字的立方和,即153=1*1*1+5*5*5+3*3*3。编程求所有满足这种条件的三位十进制数。 输出格式   按从小到大的顺序...
wzhCAlex 2017-03-10 10:58 101

打印杨辉三角形
2015-06-06 23:30 321B 下载
yangrui2002 +关注
原创 63 粉丝 0 喜欢 0 码云  
他的最新文章 更多文章
忧桑三角形 洛谷P3916 图的遍历_graph 洛谷P1559 运动员最佳匹配问题 洛谷P1440 求m区间内的最小值
在线课程

【免费】搜狗机器翻译技术分享
讲师:

深度学习在推荐领域的应用和实践
讲师:吴岸城
热门文章 肥得更高
520
洛谷P1546 最短网络 Agri-Net
357
洛谷P2504 [HAOI2006]聪明的猴子
209
洛谷P1558 色板游戏
205
洛谷P2951 [USACO09OPEN]捉迷藏Hide and Seek
166
0
  编程语言 最新文章
洛谷P3916 图的遍历_graph
Java_7
C#使用UdpClient发送和接收UDP数据示例 16进
php必会基础
Java判断是否为整数的5种方法
Socket 双向传输问题
腾讯手QQ核心技术-NDK开发语音消息变声功能
遍历枚举接口的元素
多线程-ThreadLocal
翻译 Spring Boot How To
上一篇文章      下一篇文章      查看所有文章
加:2017-10-30 04:01:06  更:2017-10-30 04:02:55 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年10日历
2018-10-19 0:55:13
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库