赵嘉熠的博客

题目链接（洛谷）

题目大意

给定一个长度不超过\(105\)的字符串（小写英文字母），和不超过 \(50000\)个操作。

每个操作\(L,R,K\)表示给区间\([L,R]\)的字符串排序，\(K=1\)为升序， \(K=0\)为降序。

最后输出最终的字符串。

题目链接（洛谷）

题目大意

考虑排好序的\(N(1\le N \le 31)\)位二进制数，且包含所有长度为\(N\)且这个二进制数中\(1\)的个数小于等于\(L(l\le N)\)的数。

现在输出满足长度为\(N\)，且\(1\)的个数小于等于\(L\)的第\(k\)小的那个二进制数。

比赛链接（BNDSOJ）

题目链接（洛谷）

题目大意

给出三类函数，分别可以实现下面三种功能：

1. 单点加；

2. 全局乘；

3. 依次执行若干次函数调用，保证不会出现递归。

给出\(n\)个数据的出初始值，并给出\(m\)个函数调用，求最后的数据。

\(1\le n \le 10^5\)

题目链接（洛谷）

题目大意

给出\(n(1\le n \le 5\times 10^5)\)个点和\(n-1\)条连着它们的路径，每一条道路都连接某两个点，且通过这些道路可以走遍所有的点。

有\(m(1 \le m \le 10^5)\)组人分散在这些点上，每组有三个人。给出每组中三人的初始位置。每组确定一个位置使每组内三人到这个点的距离和最小，输出这个距离和。

题目链接（洛谷）

题目大意

有\(n\)个城市\(m\)条道路，每条道路连接这\(n\)个城市中的某两个城市。任意城市之间最多只有一条道路相连。

这\(m\)条道路中有一部分为单向通行的道路，一部分为双向通行的道路。双向道路在统计时记为一条。

同一商品在不同城市价格\(c\)不同，但同一商品在城市中的买入和卖出价格是相同的。商人想要通过赚差价赚出旅费，且他只进行一次贸易，求最多能赚多少。

$$

1n ,~1m

$$

题目链接（洛谷）

题目大意

给出一个有\(n\)个节点\(m\)条边的无向图，节点编号为\(1-n\)，边编号为\(1-m\)。初始时小E同学在\(1\)号节点。数据可能包含重边和自环。

每条边都有一个妖怪住在边上。在节点\(1\)处有两种守护精灵A，B，每种都有无数个。无向图中每条边都有权值\(a_i\)和\(b_i\)，当且仅当小E身上携带的A守护精灵不少于\(a_i\)，且B守护精灵不少于\(b_i\)，这条边上的妖怪不会对通过这条边的人发起攻击。

求在不被妖怪袭击的情况下，到\(n\)号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

\(2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000\)

题目链接（洛谷）

题目大意

小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\)