hk_cnyali's Blog

又是一个全机房只有我不会的知识点

同样，这篇文章也不适用于对这个知识点一无所知，且需要大量严谨证明的同学阅读

给出$k$，请你构造一个结点数不超过 $100$ 的无向图，使得这个无向图中生成树的个数对$998244353$取模后恰好等于$k$

$k\in [0, 998244353)$

给你一个$n$个点$m$条边的混合图（既有有向边也有无向边）

你需要给所有无向边定向，使得新图中任意点两两可达

输出任意一种方案，数据保证有解

$n, m\le 5000$

请注意，此文章内不含任何证明，因为我懒的写也不会，就先记着个结论好了

比较详细但易懂的证明可见这里

你在一座由$n$个点构成的山脉中爬山，第$i$个点坐标为$(x_i, y_i)$

你的爬山策略是：

• 一直往当前可见的最高点的方向走，也就是说你的策略是不断动态变化的

求从每个顶点出发，到达所能到达的最高点的路程分别是多少

加强版：

题意太长，就放里面了

给出$n$个点，和每个点的度让你构造出一张无向图满足以下两条性质：

1. 点$1$到点$i$仅有唯一一条最短路

2. 点$1$到点$i$的最短路长度大于等于点$1$到点$i-1$的最短路长度

求能构成满足条件的无重边无自环的无向图的个数

原题：$n\le 50$

加强版：$n \le 400$

线性基是常用来解决子集异或/线性空间中一些题目的算法

给定长度为$n$的序列$a_i$，有次$q$询问$(l,r)$，求在中选取任意个，使得它们的异或和最大

$n\le 500000, a_i\le 10^6$

给出一个长度为$n$的序列$\{a_i\}$，试将其划分为尽可能多的非空子段，满足每一个元素出现且仅出现在其中一个子段中，且在这些子段中任取若干子段，它们包含的所有数的异或和不能为$0$．

$n\le10^5, a_i\le 10^9$