赵嘉熠的博客

题目链接（洛谷）

题目大意

小a在一座雪山滑雪，这里分布着\(m\)条供滑行的轨道和\(n\)个轨道之间的交点（同时也是景点），而且每个景点都有一个编号\(i\)和一个高度\(h_i\) 。给出每条轨道的长度\(k_i\)小a能从景点\(i\)滑到景点\(j\)当且仅当存在\(i\)和\(j\)之间的边，且\(i\)的高度不小于\(j\)。

题目链接（洛谷）

题目大意

有\(n\le 150\)个节点，节点之间有\(m(m\le 5000)\)条无向边，使得任意两个节点可以互相到达。

现在要去掉一条边，使得图中存在两个节点无法相互到达。

输出所有可以去掉的边。

题目链接（洛谷）

题目大意

有\(n\)个村庄，编号从\(0\)~\(n−1\)。给出\(m\)条双向公路连接这些村庄。

发生了一次地震，对所有村庄造成了一些损毁，但对公路没有影响。

现在要重建村庄，给出第\(i\)个村庄重建完成的时间\(t_i\)。之后又\(Q\)个询问\((x,y,t)\)，对于每个询问。你要回答在第\(t\)天，从村庄\(x\)到村庄\(y\)的最短路长度为多少。如果无法找到路径或者\(x,y\)没有重建完成，输出\(−1\)。

\(N\le 200,M\le \frac{N\times (N-1)}{2}, Q\le 50000\)

题目链接（洛谷）

题目大意

给出一个\(n\)个节点\(m\)条边的图，求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

\(1\le n \le 100,1\le m\le \frac{n\times (n−1)}{2}\)

题目链接（洛谷）

题目大意

有一座岛上有\(n\)个景点，从\(1-n\)编号，现在需要修公路将这些景点连接起来，可以修一级或二级的公路，一级公路的花费大于二级公路。

现在要修\(n−1\)条公路将景点连接，且在这\(n−1\)条公路中有\(k\)条是一级公路。

现给出\(n,k\)以及可以修的景点对和修一级公路和二级公路的花费。求满足要求的最小花费。

\(1\le n \le 10000, k\le n−1,m\le 30000\)

（题目链接）

题目大意

给出\(n\)个节点，编号为\(0\)~\(n-1\)，给出\(m\)条无向边。接下来给出包含\(k\)个数的数列\(p\)，\(p_i\)表示第\(i\)步要删除编号为\(p_i\)的节点。

求每一步图中连通块的个数

\(1\le m \le 2\times 10^5, 1\le n\le 2\times m\)

题目链接（洛谷）

题目大意

给出一些城市，从西向东排成一排，每个城市有一个海拔\(h_i\)，定义城市\(i,j\)间的距离位海拔之差的绝对值，即\(d(i,j)=|h(i)-h(j)|\)。

小\(A\)和小\(B\)轮流开车，第一天小\(A\)开车，之后每天换一次。他们计划选择一个城市\(s\)作为起点，一直向东，并且最多行驶\(x\)公里就结束旅行。

题目链接（洛谷）

题目大意

给定\(n\)个数，第\(i\)个数为\(v_i\)。

现在要把它分成数目之差不超过1的两部分，问这样的两部分数字和之差最小是多少？

\(n \le 30\)

题目链接（洛谷）

题目大意

已知一个\(n\)元高次方程： \[ \sum_{i=1}^nk_ix_i^{p_i}=0 \] 已知未知数\(x_i\in \[1,m](i\in[1,n])\)。给定\(n,m,k_i,p_i\)，求方程的整数解数。

\(1 \le n \le 6, 1 \le m \le 150, \sum_{i=1}^n|k_im^{p_i}<2^{31}|\)

题目大意

已知一个三角形的周长\(n\)，三角形的边长是整数，求三角形的边长有多少种可能。

\(1\le n \le 10^{18}\)