传送门 $\looparrowright$

A-最短路

题目描述

牛能在家里遇到了一个问题，他现在想要去找牛可乐并向他请教这个问题，现在他已经知道了牛可乐家的坐标，并且他很容易找到了通往牛可乐家里的最短路（一条直线）。
但是，平面上有一个圆形区域，这个圆形区域内是被诅咒过的地方，所以牛能不能进入这块圆形区域的内部，所以牛能现在找不到通往牛可乐家的最短路了，请帮助他解决这个问题！
保证牛能家和牛可乐家不在诅咒区域内。

输入描述

第一行四个整数 $x_1, y_1, x_2, y_2$ ， $(x_1, y_1)$ 表示牛能家的坐标， $(x_2, y_2)$ 表示牛可乐家的坐标。
第二行三个整数 $x_3, y_3, r$ ， $(x_3, y_3)$ 表示被诅咒的圆形区域的位置的圆心坐标， $r$ 表示这个圆形区域的半径。

输出描述

在一行中输出牛能从家到牛可乐家的最短路。

示例1

输入
-1 -1 1 1
0 0 1
输出
3.570796

示例2

输入
1 1 2 2
0 0 1
输出
1.414214

备注

$-10^5\le x_1,y_1,x_2,y_2,x_3,y_3\le 10^5$
$1\le r\le 10^5$
如果标准答案是 $a$ ，你的答案是 $b$ ，当满足 $\frac{|a-b|}{\max(|a|,1.0)}\le10^{-6}$ 你的答案被认为是正确的。

分析

当线段 $AB$ 不穿过圆，最短路即为 $|AB|$ 。

过点 $A,B$ 分别引两条圆 $O$ 的切线，切点分别为 $H_1,H_2$ 。设 $\angle AOH_1=\alpha,\angle BOH_2=\beta,\angle AOB=\gamma$ ，那么当线段 $AB$ 穿过圆， $\alpha+\beta<\gamma$ 。最短路为 $|AH_1|+|BH_2|+|\stackrel{{\mbox{$\Large{\frown}$}}}{H_1H_2}|$。
实际上，在圆外一点引切线可以有两条，可以证明，上述的方法是最优的。

代码

#include<iostream>
#include<cmath>
#include<cstdio>
#define dis(a,b,c,d) sqrt((a-c)*(a-c)+(b-d)*(b-d))
using namespace std;
int main()
{
	double x1,y1,x2,y2,x3,y3;
	double r;
	cin>>x1>>y1>>x2>>y2>>x3>>y3>>r;
	double AB=dis(x1,y1,x2,y2);
	double OA=dis(x1,y1,x3,y3);
	double OB=dis(x2,y2,x3,y3);
	double alpha=acos(r/OA);
	double beta=acos(r/OB);
	double gamma=acos((OA*OA+OB*OB-AB*AB)/(2*OA*OB));//余弦定理
	if(alpha+beta>gamma) printf("%.6lf\n",AB);//判断是否穿过圆
	//勾股定理
	else printf("%.6lf\n",sqrt(OA*OA-r*r)+sqrt(OB*OB-r*r)+(gamma-alpha-beta)*r);
	return 0;
}

B-组队

题目描述

你的团队中有 $n$ 个人，每个人有一个能力值 $a_i$ ，现在需要选择若干个人组成一个团队去参加比赛，由于比赛的规则限制，一个团队里面任意两个人能力的差值必须要小于等于 $k$ ，为了让更多的人有参加比赛的机会，你最多能选择多少个人参加比赛？

输入描述

第一行一个整数 $T$ ，表示案例组数。
每个案例有两行,第一行两个正整数 $n,k$ ，表示人的数量。第二行 $n$ 个以空格分隔的整数 $a_i$ ，表示每个人的能力值。

输出描述

每个案例输出一行，表示可以参加比赛的最多人数。

示例1

输入
1
5 3
8 3 5 1 6
输出
3
说明
选择能力值为 $3,5,6$ 或者 $5,6,8$

备注

$T \leq 10$
$1 \leq n \leq 2\times10^5, 1 \leq k \leq 10^9$
$1\le a_i \le 10^9$

分析

不妨设选出来的那几个人中最小值为 $p$ ，那么最大值就为 $q(p\le q\le p+k)$ 。
设正整数区间 $[1,n]$ 构成的集合为 $A$ 。
对于一个 $a_i$ ，集合 $\{j\in A|a_i\le a_j\le a_i+k\}$ 的大小，就是将 $a_i$ 置为 $\{a_n\}$ 的子集中的最小元素时，可选择的最大人数。
于是我们只需要枚举 $a_i$ ，就能找到最大的可选元素。
为了降低时间复杂度，可将数组排序，对于每一个 $a_i$ ，将其置为最小值，二分得到一段完整的区间，区间中最小值为 $a_i$ ，那么最大值就为 $q (a_i\le q\le a_i+k)$ 。

代码

#include<algorithm>
#include<cstdio>
#include<iostream>
#define N 200004
using namespace std;
int a[N];
int n,k;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d%d",&n,&k);
		int i;
		for(i=1;i<=n;i++) scanf("%d",a+i);
		int ans=-1;
		sort(a+1,a+1+n);//排序
		for(i=1;i<=n;i++) 
		{
			int pos=upper_bound(a+1,a+1+n,a[i]+k)-a-1;
			ans=max(ans,pos-i+1);
		}
		printf("%d\n",ans);
	}
}

C-十面埋伏

题目描述

经过多年的征战，牛牛在与牛可乐的对决渐渐处于下风，于是牛牛决定对牛可乐来一次大围剿。
战场可以看作一张 $n\times m$ 的地图，牛可乐的士兵只能上下左右移动，不能斜着移动，牛牛决定挖一圈陷阱包围牛可乐的士兵。牛牛想知道包围牛可乐的士兵所需要的最少的陷阱数量是多少，但是牛牛并不会排兵布阵，于是只能求助于你了。
保证地图的边界处不会有士兵。
保证牛可乐的士兵是连通的。
要求牛可乐使用的陷阱构成的包围圈与牛可乐的士兵之间要求是紧密接触的，即求出包围并且紧挨牛可乐士兵的最少陷阱数的方案。

输入描述

第一行输入两个整数 $n$ 和 $m$ ，表示地图的大小。
下面 $n$ 行每行 $m$ 个字符， $\text{.}$ 表示空地，# 表示士兵。
保证输入的字符串只包含 $\text{.}$ 和 #

输出描述

输出挖完陷阱后的地图，陷阱用 $\text{*}$ 来表示。

示例1

输入
6 5
.....
.###.
.#.#.
.###.
..##.
.....
输出
.***.
*###*
*#.#*
*###*
.*##*
..**.

示例2

输入
10 10
..........
..######…
.#######…
.#######…
.##.###...
.##..##...
.....##...
..........
..........
..........
输出
..******..
.*######*.
*#######*.
*#######*.
*##*###*..
*##**##*..
.**.*##*..
.....**...
..........
..........

备注

$1\leq n,m\leq500$

分析

由于边界上不存在士兵，那么我们只需要对士兵外围进行一次 $\text{BFS}$ ，然后对所有能从边界上到达的节点，判断他周围四个方向是否有士兵，若有士兵，则说明这个点需要放置陷阱；因为如果这个点能从边界到达，那么士兵一定也能通过这个点走到边界，必须将这个点堵住。

后记

题面的描述出锅了，然而一次都没提交的我连 $\text{wa}$ 的机会都没有，菜是原罪 $\text{Orz}$ 。

代码

#include<queue>
#include<iostream>
#include<cstdio>
#define N 504
using namespace std;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
struct node
{
	int x;
	int y; 
};
char G[N][N];
bool vis[N][N];
int n,m;
void bfs()
{
	queue<node>q;
	q.push((node){1,1});
	vis[1][1]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		int i;
		for(i=0;i<4;i++)
		{
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x<1||x>n) continue;
			else if(y<1||y>m) continue;
			else if(G[x][y]=='#') continue;
			else if(vis[x][y]) continue;
			else
			{
				vis[x][y]=1;
				q.push((node){x,y});
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	int i,j;
	/*-===读操作注意行末回车===-*/
	getchar();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%c",&G[i][j]);
			if(j==m) getchar();
		}
	}
	bfs();//从边界开始bfs
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			//周围有士兵，而且该点能从边界走到
			if(G[i-1][j]=='#'||G[i][j-1]=='#'||G[i+1][j]=='#'||G[i][j+1]=='#')
			{
				if(G[i][j]!='#'&&vis[i][j])
				{
					G[i][j]='*';
				}
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			printf("%c",G[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

D-牛牛吃豆子

题目描述

牛妹为了打比赛经常不吃饭，但是牛妹非常喜欢吃豆子，她经常会吃很多很多的豆子，所以牛妹不会感觉到饿，自然就不想吃饭了。
现在牛妹有一个 $n\times m$ 个格子的棋盘。左下角的格子坐标为 $(1, 1)$ ，右上角的格子坐标为 $(n,m)$ 。棋盘的每个格子都能放任意个豆子。
这时牛可乐带着一袋豆子走了过来，打算跟牛妹分享这些豆子，但是牛可乐并不想就这么简单的让牛妹吃到豆子，所以牛可乐给牛妹出了一个难题。
现在牛可乐有 $k$ 次操作，每次操作给出四个数字 $x_1$ , $y_1$ , $x_2$ , $y_2$ 。表示牛可乐会将所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上放一个豆子。
牛可乐放完豆子后给出了 $q$ 次询问，每次询问给出四个数字 $x_1$ , $y_1$ , $x_2$ , $y_2$ 。表示询问所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上中总共有多少个豆子。
这个问题可难住牛妹了，牛妹想要吃到豆子就必须答对牛可乐的所有询问。

输入描述

输入一行四个数字 $n,m,k,q$ 。
$n,m$ 表示棋盘的大小。有 $k$ 次操作和 $q$ 次询问。
下面 $k$ 行,每行四个数字 $x_1$ , $y_1$ , $x_2$ , $y_2$ 。
表示牛可乐会将所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上放一个豆子。
下面 $q$ 行,每行四个数字 $x_1,y_1,x_2,y_2$ 。
表示询问所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上中总共有多少个豆子。

输出描述

每次询问，输出一行一个数字表示答案。

示例1

输入
2 2 1 1
1 1 2 2
1 1 2 1
输出
2

备注

$1\leq n,m\leq 2000$
$1\leq k,q\leq 200000$
$1\leq x_1 \leq x_2 \leq n,1\leq y_1\leq y_2 \leq m$
$n,m,k,q,x_1,y_1,x_2,y_2$ 均是整数

分析

二维差分和二维前缀和的模板题。
将所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上放一个豆子，采取差分操作。
询问所有满足 $x_1\leq x\leq x_2$ , $y_1\leq y \leq y_2$ 这两个条件的位置上中总共有多少个豆子，采取前缀和操作。
两者之间的纽带是求两次二维前缀和。

二维差分

左上角是 $(x_1,y_1)$ ，右下角是 $(x_2,y_2)$ 的矩形区间每个值都加上 $a$ 。如上图所示，可以先在我们要的区间开始位置 $(x_1,y_1)$ 处加 $a$ ，表示以 $(x_1,y_1)$ 为左上角整个黄色部分都加上了 $a$ ，但是这样就多影响了两个蓝色部分，所以在两个蓝色部分减 $a$ 消除加 $a$ 的影响，而两个蓝色部分重叠的绿色部分多受了个减 $a$ 的影响，所以绿色部分加 $a$ 消除影响。这样就标记了左上角是 $(x_1,y_1)$ ，右下角是 $(x_2,y_2)$ 的矩形区间每个值都加上 $a$ 。
于是求一次前缀和，将标记下放到每一个坐标，就能得到真正的矩阵。

二维前缀和

我们要求紫色部分的值，我们已知的是黄色部分的值，但它多了两个蓝色部分的值，而两个蓝色部分有重叠了个绿色部分。所以要求的区间内的值就是 $f(x_2,y_2)$ $-$ $f(x_2,y_1-1)$ $-$ $f(x_1-1,y_2)$ $+$ $f(x_1-1,y_1-1)$ （ $f(i,j)$ 表示坐标 $(i,j)$ 的二维前缀和）。

代码

#include<iostream>
#include<cstdio>
#define N 2003
using namespace std;
long long f[N][N];
int n,m,k,q;
//求二维前缀和  
inline void get_prefix_sum()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
		}
	}
}
int main()
{
	cin>>n>>m>>k>>q;
	while(k--)
	{
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		//二维差分
		f[x1][y1]++;
		f[x1][y2+1]--;
		f[x2+1][y1]--;
		f[x2+1][y2+1]++;
	}
	get_prefix_sum();
	get_prefix_sum();
	while(q--)
	{
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%lld\n",f[x2][y2]-f[x2][y1-1]-f[x1-1][y2]+f[x1-1][y1-1]);
	}
	return 0;
}

E-旅旅旅游

题目描述

牛牛国有 $n$ 个城市， $m$ 条无向道路，每条道路三个属性 $a_i,b_i,c_i$ ，表示城市 $a_i$ 与城市 $b_i$ 之间有一条长为 $c_i$ 的道路，现在牛可乐在城市 $1$ ，他想去城市 $n$ 。同时牛可乐非常聪明，他会将所有从 $1$ 到 $n$ 可能的最短路径全都走一遍，之后便不再走了。
现在牛妹在城市 $1$ ，他想把所有城市走一遍，可是他不想走牛可乐走过的路，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？

输入描述

第一行两个数字 $n,m$ ，表示城市的数量和道路的数量。
接下来 $m$ 行，每行 $3$ 个数字 $a_i,b_i,c_i$ ，表示城市 $a_i$ 与城市 $b_i$ 之间有一条长为 $c_i$ 的道路 (题目保证无自环，可能有重边)

输出描述

如果牛妹能走遍所有城市，输出 “YES” ，否则输出 “NO”。

示例1

输入
4 5
1 2 2
1 3 2
2 3 1
2 4 2
3 4 1
输出
YES
说明
城市 $1$ 到城市 $4$ 最短路距离是 $3(1\rightarrow 3\rightarrow 4)$ ，牛妹不能走这些边也能走遍所有城市。

备注

$1\leq n\leq 10^5,1\leq m\leq 5\times 10^5$
$1\leq a_i,b_i\leq n,1\leq c_i\leq 10^9$
建议使用 $\text{scanf}$ 读入

分析

先求出以 $1$ 为起点单源最短路 $dis1[i]$ 和以 $n$ 为起点的单源最短路 $disn[i]$ ，然后枚举每条边 $Eege(u,v)$ ，若满足 $dis1[u]$ $+$ $w(u,v)$ $ +$$disn[v]$$=$$\text{shortest}$ 或者 $disn[u]$ $+$ $w(u,v)$ $+$ $dis1[v]$ $=$ $\text{shortest}$ ，其中 $\text{shortest}$ 指 $1\rightarrow n$ 的最短路径长度，那么就说明这条边在最短路上，否则不在最短路上。
之后我们用一个 $\text{set}$ 来维护所有不在最短路上的边（即将这条边的两个点放在一个集合中），若所有点都在一个集合内，则说明牛妹可以将所有城市走一遍；反之，不可以。

代码

#include<queue>
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<cstring>
#define N 100004
#define M 500003
using namespace std;
int n,m;
struct E
{
	int from;
	int to;
	int Next;
	long long w;
}edge[M<<1];
int head[N],tot;
inline void add(int u,int v,long long w)
{
	tot++;
	edge[tot].from=u;
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
struct node
{
	int id;
	long long dis;
	bool operator<(const node &x)const
	{
		return x.dis<dis;
	}
};
bool vis[N];
long long dis1[N],disn[N];
void dijkstra(long long dis[],int s)//模板
{
	memset(vis,0,sizeof(vis));
	int i;
	fill(dis+1,dis+1+n,1LL<<60);//初始化
	dis[s]=0;
	priority_queue<node>q;
	q.push((node){s,0});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		int x=now.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].w)
			{
				dis[y]=dis[x]+edge[i].w;
				q.push((node){y,dis[y]});
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	int i;
	memset(head,-1,sizeof(head));//初始化
	for(i=1;i<=m;i++)//建图
	{
		int a,b;
		long long c;
		scanf("%d%d%lld",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	//Dijkstra算法求单源最短路径  
	dijkstra(dis1,1);
	dijkstra(disn,n);
	long long shortest=dis1[n];//最短路径长度
	set<int>ex;
	for(i=1;i<=tot;i++)
	{
		int u=edge[i].from;
		int v=edge[i].to;
		long long w=edge[i].w;
		if(dis1[u]+w+disn[v]==shortest) continue;
		else if(dis1[v]+w+disn[u]==shortest) continue;
		//边不是最短路，将这两个点放入集合中
		ex.insert(u);
		ex.insert(v);
	}
	if(ex.size()==n) puts("YES");
	else puts("NO");
	return 0;
}

后记

建立双向边，小心不要 $\text{RE}$ 。

F-斗兽棋

题目描述

牛牛喜欢牛妹，而喜欢的最高境界就是舔，牛牛作为一个舔狗，终于在不断的舔之中获得了牛妹的真心，但是牛牛还是没有舔舒服，于是他们今天又在玩游戏。
每个人有四个棋子，分别是 “elephant”，“tiger”，“cat”，“mouse”，分别代表大象、老虎、猫、老鼠，（大象吃老虎，老虎吃猫，猫吃老鼠，老鼠吃大象），每次出一个棋子。
你能知道谁能获得胜利吗？

输入描述

输入包含一行，两个以空格分隔的字符串分别代表牛牛和牛妹出的棋子，保证两个字符串一定在上述的四个字符串中。

输出描述

如果牛牛赢了或者平局，输出“tiangou yiwusuoyou”，牛妹赢了输出“tiangou txdy”。

示例1

输入
tiger elephant
输出
tiangou txdy

备注

如果牛牛出大象，牛妹出猫，那么我们认为这一局是平局，其他同理。

分析

按题意模拟，枚举所有牛妹胜利的情况，其余情况为平局或者牛牛胜利。

代码

#include<iostream>
#include<string>
#define s cout<<"tiangou txdy";
#define f cout<<"tiangou yiwusuoyou";
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	/*----------牛妹胜出情况----------*/
	if(a=="elephant"&&b=="mouse") s
	else if(a=="tiger"&&b=="elephant") s
	else if(a=="cat"&&b=="tiger") s
	else if(a=="mouse"&&b=="cat") s
	/*-------================-------*/
	//其余情况
	else f
	return 0;
}

后记

记得看备注，不然按照斗兽棋一般套路就 wa 了。

G-做题

题目描述

众所周知，牛可乐最喜欢说的一句话是

然后大家开始了愉快的做题之旅。
有 $n$ 个题目， $m$ 分钟，做完每个题目所花费的时间是不一样的，求牛可乐最多可以做出多少个题目。

输入描述

第一行是空格分隔的两个整数 $n,m$ ，表示有 $n$ 个题目和 $m$ 分钟。
第二行有 $n$ 个非负整数 $a_1,a_2,a_3,...,a_n$ ，表示牛可乐做出第 $i$ 个题目所需要的时间。

输出描述

输出一行一个整数表示牛可乐能做出的最多的题目数量。

示例1

输入
5 2
2 3 0 1 1
输出
3

备注

$1 \leq n \leq 5\times 10^5, 1 \leq m \leq 5\times 10^10$
$0 \leq a_i \leq 10^5$
建议使用 $\text{scanf}$ 读入

分析

简单贪心。
在总时间固定的情况下，为了在有限的时间内做出来更多的题，显然是先做费时间少的题目。

代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll a[500003];
int n;
ll m;
int main()
{
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++) scanf("%lld",a+i);
	sort(a+1,a+1+n);
	ll all=0;
	for(i=1;i<=n;i++) 
	{
		all+=a[i];
		if(all>m)//找到临界点
		{
			cout<<i-1<<endl;
			return 0;
		}
	}
	//特判能做所有题的情况
	cout<<n<<endl;
	return 0;
}

H-人人都是好朋友

题目描述

牛可乐作为三军统帅，是要时时刻刻关照着下属的。
现在牛可乐想要知道自己的手下之间的友好关系，所以他收集了 $n$ 张纸条，上面写着三个整数 $a_i,b_i,c_i$ ，表示如果 $c_i$ 为 $1$ ，表示手下 $a_i$ 和手下 $b_i$ 是朋友，反之则是敌人。
牛可乐想要知道这些信息有没有互相矛盾的地方，可是这个问题太难了，只好来问你了。
如果 $\text{A}$ 与 $\text{B}$ 友好， $\text{B}$ 又与 $\text{C}$ 友好，那么 $\text{A}$ 与 $\text{C}$ 也是友好的。
如果两个人既是友好的又是不友好的则视为相互矛盾的。
牛可乐的手下有 $10^9$ 个。

输入描述

输入第一行给出一个正整数 $T$ ，表示测试案例的数量。
对于每个测试用例。第一行给出一个正整数 $n$ ，表示有 $n$ 个友好关系。
接下来每 $n$ 行给出三个正整数 $a_i,b_i,c_i$ ，表示手下 $a_i$ 和手下 $b_i$ 之间的友好关系。

输出描述

每组案例输出一行，若这些关系没有矛盾，输出 "YES”，否则输出 “NO”。

示例1

输入
2
3
1 2 1
1 3 1
2 3 1
3
1 2 1
1 3 1
2 3 0
输出
YES
NO

备注

$1\leq T\leq 10$
$1\leq n\leq 10^6$
$1 \leq a,b \leq 10^9$

$c\in\{0,1\}$

对于每组样例，保证 $\sum n \leq 1010000$
建议使用 $\text{scanf}$ 读入

分析

$\text{A,B,C}$ 之间有传递性的链式关系显然可以用并查集来维护。
先读入所有友好关系，将 $c_i=1$ 的一对进行并集操作。再查询所有友好关系，若 $c_i=0$ 就要检查这一对数字是否在同一个集合中。
由于数据达到了 $10^9$ 的规模，需要进行离散化操作，简单来说就是排序，去重，接着二分位置得到映射。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 1010004
using namespace std;
int father[N<<1];
int find(int x)
{
	if(x==father[x]) return x;
	else return father[x]=find(father[x]);
}
void unions(int a,int b)
{
	a=find(a);
	b=find(b);
	if(a==b) return;
	else father[b]=a;
}
struct query
{
	int a,b;
	int c;
}q[N<<1];
int p[N<<1];
int main()
{
	int _;
	for(cin>>_;_;_--)//多组数据
	{
		int n;
		int cnt=0;
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
			p[++cnt]=q[i].a;
			p[++cnt]=q[i].b;
		}
		//离散化所有编号，排序并去重。
		sort(p+1,p+1+cnt);
		//得到独立的变量个数
		int nn=unique(p+1,p+1+cnt)-p-1;
		for(i=1;i<=nn;i++) father[i]=i;//初始化
		for(i=1;i<=n;i++)
		{
			//二分位置
			int a=lower_bound(p+1,p+1+nn,q[i].a)-p;
			int b=lower_bound(p+1,p+1+nn,q[i].b)-p;
			if(q[i].c) unions(a,b);
		}
		bool ok=1;
		for(i=1;i<=n;i++)
		{
			int a=lower_bound(p+1,p+1+nn,q[i].a)-p;
			int b=lower_bound(p+1,p+1+nn,q[i].b)-p;
			//检查
			if(!q[i].c) 
			{
				if(father[a]==father[b])
				{
					ok=0;
					break;
				}
			}
		}
		if(ok) puts("YES");
		else puts("NO");
	}
	return 0;
}

I-求和

题目描述

已知有 $n$ 个节点，有 $n-1$ 条边，形成一个树的结构。
给定一个根节点 $k$ ，每个节点都有一个权值，节点i的权值为 $v_i$ 。
给 $m$ 个操作，操作有两种类型。
$\text{1 a x}$ ：表示将节点 $a$ 的权值加上 $x$
$\text{2 a}$ ：表示求 $a$ 节点的子树上所有节点的和（包括 $a$ 节点本身）

输入描述

第一行给出三个正整数 $n,m,k$ ，表示树的节点数、操作次数、和这棵树的根节点。
第二行给出 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个节点的权值 $val_i$ 。
下面 $n-1$ 行每行两个正整数 $u,v$ ，表示边的两个端点。
接下来 $m$ 行，每行给出一个操作。

输出描述

对于每个类型为 $2$ 的操作,输出一行一个正整数,表示以 $a$ 为根的子树的所有节点的权值和。

示例1

输入
5 6 1
1 2 3 4 5
1 3
1 2
2 4
2 5
1 2 10
1 3 10
1 4 5
1 5 1
2 3
2 2
输出
13
27

备注

$1\leq n,m\leq 1e6,1\leq k\leq n$
$1\leq u,v \leq n$
$1\leq a\leq n$
$−10^6\leq val_i,x\leq 10^6$
建议使用 $\text{scanf}$ 读入

分析

考虑利用一次 $\text{DFS}$ 对整棵树重新编号，编号后，可以使得任意一颗子树的序号连续。然后使用树状数组或者线段树维护单点修改和求和操作即可。类似于树链剖分。
对树进行遍历时，定义两个数组 $l[i],r[i]$ ，分别表示以 $i$ 为根节点的子树的所有节点中的最小最大编号，修改一个节点相当于对 $l_i$ 的单点修改，查询一棵子树相当于查询区间 $[l_i,r_i]$ 。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 1000004
using namespace std;
struct E//链式前向星
{
	int to;
	int Next;
}edge[N<<1];
int tot,head[N];
inline void add(int u,int v)
{
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	head[u]=tot;
}
int lowbit(int x) {return x&-x;}
int l[N],r[N];
int val[N];//节点权值
long long sum[N];//前缀和
int n,m,k;
inline void update(int a,int x)
{
	while(a<=n)
	{
		sum[a]+=x;
		a+=lowbit(a);
	}
}
inline long long query(int a)
{
	long long res=0;
	while(a)
	{
		res+=sum[a];
		a-=lowbit(a);
	}
	return res;
}
int id=0;
void dfs(int x,int father)
{
	l[x]=++id;//赋予编号，x为根节点的子树中编号最小的节点
	int i;
	for(i=head[x];~i;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(y==father) continue;
		else dfs(y,x);
	}
	r[x]=id;//赋予编号，x为根节点的子树中编号最大的节点
}
int main()
{
	cin>>n>>m>>k;
	memset(head,-1,sizeof(head));
	int i;
	for(i=1;i<=n;i++) scanf("%d",val+i);
	for(i=1;i<=n-1;i++)//建图
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(k,-1);//遍历树，重新编号
	for(i=1;i<=n;i++) update(l[i],val[i]);//赋予初值
	while(m--)
	{
		int opt,a;
		scanf("%d",&opt);
		switch(opt)
		{
			case 1:
				int x;
				scanf("%d%d",&a,&x);
				update(l[a],x);//更新
				break;
			case 2:
				scanf("%d",&a);
				printf("%lld\n",query(r[a])-query(l[a]-1));//查询
				break;
			default:
				break;
		}
	}
	return 0;
}

J-建设道路

题目描述

牛牛国有 $n$ 个城市，编号为 $1$ 到 $n$ ，第 $i$ 个城市有一个价值 $a_i$ ，牛国的国王牛阔落特别喜欢在牛牛国旅游，并且他不想每次旅游的时候都计算一遍走哪条路最短，于是他决定在任意两个城市之间建立一条双向道路，在第 $i$ 座城市和第 $j$ 座城市之间建立双向道路的代价是 $(a_i-a_j)^2$ ，牛阔落希望你能算出这项工程的花费。由于答案太大，你只需要输出答案模 $1000000007$ 的余数。

输入描述

第一行一个整数 $n$ ，表示城市的数量。
第二行 $n$ 以空格分隔的整数 $a_1,a_2,...,a_n$ ，表示第 $i$ 座城市的价值。

输出描述

输出一行一个数字，表示工程的花费模 $1000000007$ 的余数。

示例1

输入
3
1 2 3
输出
6
说明
城市 $1$ 到城市 $2$ 的道路价值是 $(2 - 1)^ 2 = 1$ ；
城市 $2$ 到城市 $3 $ 的道路价值是 $(3 - 2)^ 2 = 1$ ；
城市 $1$ 到城市 $3$ 的道路价值是 $(3 - 1)^ 2 = 4$ ；
总的花费 $1 + 1 + 4 = 6$ 。

备注

$1\leq n\leq 5\times 10^5$
$1\leq a_i\leq 10^9$
建议使用 $\text{scanf}$ 读入

分析

给一个数列 $\{a_n\}$。要求计算 $\sum\limits_{i=1}^n\sum\limits_{j=i}^n(a_i-a_j)^2$ 。
$\sum\limits_{i=1}^n\sum\limits_{j=i}^n(a_i-a_j)^2=\sum\limits_{i=1}^n(a_1-a_i)^2+\sum\limits_{i=2}^n(a_2-a_i)^2+\cdots+\sum\limits_{i=n}^n(a_n-a_i)^2$
讲上式的每一项展开，得到
$\sum\limits_{i=1}^n\sum\limits_{j=i}^n(a_i-a_j)^2=(n-1)\sum\limits_{i=1}^na_i^2-2\times\left(a_1\sum\limits_{i=2}^na_i+a_2\sum\limits_{i=3}^na_i+\cdots+a_{n-1}\sum\limits_{i=n}^na_i\right)$
$(n-1)\sum\limits_{i=1}^na_i^2$ 可以 $O(n)$ 求得， $\left(a_1\sum\limits_{i=2}^na_i+a_2\sum\limits_{i=3}^na_i+\cdots+a_{n-1}\sum\limits_{i=n}^na_i\right)$ 通过预处理（类似前缀和）也可以 $O(n)$ 求得。

代码

import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
	public static void main(String args[])
	{
		BigInteger a[]=new BigInteger[500005];
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		int i;
		for(i=1;i<=n;i++) a[i]=cin.nextBigInteger();
		BigInteger all=new BigInteger("0");
		for(i=1;i<=n;i++) all=all.add(a[i]);//求和预处理
		BigInteger ans=new BigInteger("0");
		for(i=1;i<=n;i++) ans=ans.add(a[i].multiply(a[i]));//得到平方和
		ans=ans.multiply(BigInteger.valueOf(n-1));
		for(i=1;i<=n-1;i++) 
		{
			all=all.subtract(a[i]);
			ans=ans.subtract(all.multiply(a[i].multiply(new BigInteger("2"))));
		}
		ans=ans.mod(new BigInteger("1000000007"));
		System.out.println(ans);
	}
}

后记

一开始用 $\text{C++}$ 取模歪了，于是写了一手 $\text{Java}$ ，这 $\text{2}$ 秒的时间限制真的危险。

传送门 ↬\looparrowright↬

A-最短路

题目描述

输入描述

输出描述

示例1

示例2

备注

分析

代码

B-组队

题目描述

输入描述

输出描述

示例1

备注

分析

代码

C-十面埋伏

题目描述

输入描述

输出描述

示例1

示例2

备注

分析

后记

代码

D-牛牛吃豆子

题目描述

输入描述

输出描述

示例1

备注

分析

二维差分

二维前缀和

代码

E-旅旅旅游

题目描述

输入描述

输出描述

示例1

备注

分析

代码

后记

F-斗兽棋

题目描述

输入描述

输出描述

示例1

备注

分析

代码

后记

G-做题

题目描述

输入描述

输出描述

示例1

备注

分析

代码

H-人人都是好朋友

题目描述

输入描述

输出描述

示例1

备注

分析

代码

I-求和

题目描述

输入描述

输出描述

示例1

备注

分析

代码

传送门 $\looparrowright$