2023 年 10 月做题记录
文章目录
- 1 （2023/10/4）「NOIP2013 提高组」火柴排队
- 2 （2023/10/4）「洛谷 P1595」信封问题
- 3 （2023/10/4）「QQ」某位群友提供的题目
- 4 （2023/10/4）「CF364D」Ghd
- 5 （2023/10/8）「洛谷 P1120」小木棍
- 6 （2023/10/8）「TJOI2011」卡片
- 7 （2023/10/10）「CEOI 2011」Traffic
- 8 （2023/10/10）「P1487」失落的成绩单
- 9 （2023/10/11）「洛谷 P1167」刷题
- 10 （2023/10/13）「ABC175F」Making Palindrome
- 11 （2023/10/15）「USACO06NOV」Roadblocks G
- 12 （2023/10/15）「CQOI 2014」数三角形
- 13 （2023/10/17）「ZJOI 2007」矩阵游戏
- 14 （2023/10/23）「校内模拟」病毒分裂
- 15 （2023/10/23）「校内模拟」货运公司
- 16 （2023/10/25）「校内模拟」石子合并
- 17 （2023/10/25）「校内模拟」质数查询
（2023/10/4）「NOIP2013 提高组」火柴排队
距离转化一下：
\sum (a_i – b_i)^2 = \sum ({a_i}^2 + {b_i}^2 – 2a_ib_i)
如果需要每根火柴距离最短，只需要最大化 a_i b_i 即可。
pair<int, int> target[100005], raw[100005];
int n, c[100005];
// BIT
int BIT[100005];
constexpr int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { while (x <= n) BIT[x] += v, x += lowbit(x); }
inline int query(int x) { int res = 0; while (x) res += BIT[x], x -= lowbit(x); return res; }
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> target[i].first;
target[i].second = i;
}
for (int i = 1; i <= n; i++) {
cin >> raw[i].first;
raw[i].second = i;
}
sort(target + 1, target + n + 1), sort(raw + 1, raw + n + 1);
for (int i = 1; i <= n; i++)
c[target[i].second] = raw[i].second;
i64 ans = 0;
for (int i = 1; i <= n; i++)
ans += query(n - c[i]), add(n - c[i] + 1, 1), ans %= 99999997;
cout << ans << '\n';
return 0;
}
（2023/10/4）「洛谷 P1595」信封问题
错排问题模板题。根据 WikiPedia 的「错排问题」条目，可以得到下列递推式：
D_n = (n-1)(D_{n-1} + D_{n-2})
然后就可以用 Haskell 解决了。优雅！
envelop n
| n <= 1 = 0
| n == 2 = 1
| otherwise = (n - 1) * (envelop(n - 1) + envelop(n - 2))
main = do
[n] <- (map read . words) `fmap` getLine
print (envelop(n))
（2023/10/4）「QQ」某位群友提供的题目
题意：
统计 n 个数组成的长度为 n 的排列 p 中，有多少个数至少有 4 个位置满足 p_i \neq i。
思路是这样的，正着推不好推，因为错排问题是 所有位数 不一样，但是这道题是需要至少 4 位不一样。
\begin{cases}
\ge\text{4 digits is the different}&\text{vaild cases} \\
\lt\text{4 digits is the different}&\text{invaild cases (逆命题)}
\end{cases}
那么只需要枚举 3 位一样、2 位一样、1 位一样和 0 位一样的方案数。
对于三位一样的：
- 先从 n 个数字里 钦定 3 个不一样的数字（{n \choose 3} 种可能），然后认为剩下的相同（1 种可能）。
- 那么这三个数字必定需要构成错排，这三个数字构成的错排列数可能方案数就是 2。
- 乘法原理乘起来。
对于两位一样的和一位一样的同理。
那么可以得到公式：
n! – \left(2 \times{n \choose 3} + {n \choose 2} + 1 \right)
代码就不贴了。
（2023/10/4）「CF364D」Ghd
一道随机化题。
题意是，给你一个数字集合，求出对于所有 S 满足 \operatorname{card}(S)\ge \lceil \frac{n}{2} \rceil，其中的 \gcd 的最大可能值。
咱可以先随机选一个数，然后计算它与每个数的 \gcd。然后统计这些 \gcd 的因子出现次数，如果一个因子出现次数超过 \lceil \frac{n}{2} \rceil，那么代表这个因子出现在了一个满足条件的集合 S 中。
可以看得出来，如果多选择几次，答案正确的概率还挺高的呢。
每次随机选择选择到位于最大集合 g’ 的的数字概率为 \frac{1}{2}。那么如果选择很多次那么就多半可以获得最大的答案。如果像咱一样选择 13 次，那么答案错误的概率为 \frac{1}{2^{13}}，就是 \frac{1}{8192}，万分之一多一点。
每次计算 \gcd 是 O(n) 的，因此不能选择太多次，要不然会超时呢。
为了多选几次用了小常数 binary gcd 卡常
inline i64 gcd(i64 a, i64 b)
{
i64 az = __builtin_ctzll(a),
bz = __builtin_ctzll(b),
z = az > bz ? bz : az, diff;
b >>= bz;
while (a) {
a >>= az;
diff = b - a;
az = __builtin_ctzll(diff);
if (a < b)
b = a;
a = diff < 0 ? -diff : diff;
}
return b << z;
}
i64 ar[1000005];
i64 cnt[1000005];
i64 dv[1000005];
int n, sz;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> rndp(1, n);
for (int i = 1; i <= n; i++)
cin >> ar[i];
i64 ans = 0;
for (int tm = 1; tm <= 13; tm++) {
i64 x = ar[rndp()];
sz = 0;
for (i64 i = 1; i * i <= x; i++) {
if (x % i == 0) {
dv[++sz] = i;
if (i * i != x)
dv[++sz] = x / i;
}
}
memset(cnt, 0, sizeof cnt);
sort(dv + 1, dv + sz + 1);
for (int i = 1; i <= n; i++) {
cnt[lower_bound(dv + 1, dv + sz + 1, gcd(ar[i], x)) - dv]++;
}
for (int i = 1; i <= sz; i++)
for (int j = i + 1; j <= sz; j++)
if (dv[j] % dv[i] == 0)
cnt[i] += cnt[j];
for (int i = sz; i >= 1; i--) {
if (cnt[i] * 2 >= n) {
ans = max(ans, dv[i]);
break;
}
}
}
cout << ans << '\n';
}
（2023/10/8）「洛谷 P1120」小木棍
感觉，很阴间的一道暴搜剪枝
最长的一个点 246ms/260ms。
#define init_io() std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
using namespace std;
u_short n, m, ln[66], nxt[52], len;
bool vis[66];
/// @brief 深搜。
/// @param cur_sum 当前已经放置的木棍长度之和。
/// @param length_left 当前「长棍」所剩余的长度。
/// @param stick_count 已经放置的木棍数量。
/// @param last 上一轮选择的木棍的下标。目的是剪枝，之前放过更长的不需要进行枚举。
/// @param sum 所有木棍长度之和，剪枝用。
/// @return 是否可以完全放置。
bool dfs(const u_short cur_sum, u_short length_left, const u_short stick_count, u_short last, u_short sum)
{
// 放满了或者放了恰好 n - 1 根就说明可行。
if ((stick_count == n && length_left == 0) || (sum - cur_sum == len))
return true;
if (length_left == 0)
length_left = len, last = 0;
for (u_short i = last + 1; i <= n; i++) {
if (!vis[i] && ln[i] <= length_left) {
vis[i] = true;
if (dfs(cur_sum + ln[i], length_left - ln[i], stick_count + 1, i, sum)) {
vis[i] = false;
return true;
}
vis[i] = false;
// 如果第一根最长的放不下那么更多的必然放不下。
// 如果这一根恰好放满但是之后的放不下说明需要前面的调整。
if (length_left == len || ln[i] == length_left)
return false;
// 相同木棍长度值不需要多次处理。
i = nxt[i]; // 之前这里开的值域，但是换成下标可以减少一次寻址（最后 9ms 就死在了这里）
}
}
return false;
}
int main()
{
u_short sum = 0;
init_io();
cin >> n;
for (u_short i = 1; i <= n; i++) {
cin >> ln[i];
sum += ln[i];
}
// 从大到小排。优先放大的更有可能排达到更优的答案。
sort(ln + 1, ln + n + 1, greater<u_short>());
nxt[n] = n;
for (int i = n - 1; i > 0; i--) {
if (ln[i] == ln[i + 1])
nxt[i] = nxt[i + 1];
else
nxt[i] = i;
}
u_short maxx = sum / 2;
for (len = ln[1]; len <= maxx; len++) {
// 无法整除的可以不用枚举了。
if (sum % len) [[likely]]
continue;
if (dfs(0, len, 0, 0, sum)) {
cout << len << '\n';
return 0;
}
}
cout << sum << '\n';
return 0;
}
（2023/10/8）「TJOI2011」卡片
aka 洛谷 P2065
很板的一道二分图最大匹配（？拿 Dinic/匈牙利 跑一遍就行了。
不过需要注意的是，O(n^2) 带上辗转相除法的一个 \log 可能会超时。所以这里咱用了一个小常数 binary gcd 建图。
最后跑出来最长的一个点 361ms/1000ms，大成功！
网络流板子太丑了，咱就只放建图部分了www
inline int gcd(int a, int b)
{
if (a == 0 || b == 0)
return 0;
int az = __builtin_ctz(a),
bz = __builtin_ctz(b),
z = az > bz ? bz : az, diff;
b >>= bz;
while (a) {
a >>= az;
diff = b - a;
az = __builtin_ctz(diff);
if (a < b)
b = a;
a = diff < 0 ? -diff : diff;
}
return b << z;
}
int main()
{
s = 1, t = 2;
int ts;
cin >> ts;
while (ts--) {
edcnt = 1;
cin >> m >> n;
fill(head + 1, head + n + m + 5, 0);
for (int i = 1; i <= m; i++)
cin >> gr1[i];
for (int i = 1; i <= n; i++)
cin >> gr2[i];
for (int i = 1; i <= m; i++)
addedge(s, i + 2, 1);
for (int i = 1; i <= n; i++)
addedge(m + i + 3, t, 1);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (gcd(gr1[i], gr2[j]) > 1)
addedge(i + 2, m + j + 3, 1);
}
}
cout << maxflow() << '\n';
}
return 0;
}
（2023/10/10）「CEOI 2011」Traffic
在平面直角坐标系上有 n 个点，其中第 i 个点的坐标是 (x_i,y_i) ，所有点在一个以 (0,0) 和 (A,B) 为相对顶点的矩形内。
如果 x_i=0，那么我们称这个点在西侧。如果 x_i=A ，那么我们称这个点在东侧。
这些点之间有 m 条边，每条边可能是有向边也可能是无向边，保证边在交点以外的任何地方不相交。
咱要求的是，对于每一个西侧的点，能够沿着边到达多少东侧的点。
暴力做，直接 O(n^2) 一个深搜。
如果我们需要一个线性的做法的话，那么肯定是不能考虑从西向东深搜的。如果要优化的话，咱可以观察到一个性质，对于所有可以到达点 v 的点，这些点都可以到达点 v 可以到达的点。
这个时候想到什么，拓扑。我们只需要从东侧点（出口）进行拓扑排序就行了啊！环的话，跑一遍 Tarjan 缩个点就可以啦。
很容易想到拿 bitset 维护点集，但是实现不好的话无疑会 RTE/TLE/MLE。怎么办呢？
题目不是一个矩形嘛，里面的边都不相交。感性思考一下，你可以发现，如果抛去无法被任何西点到达的东点，那么对于每一个西点，它可以到达的东点必然是一个连续的区间（按照坐标排序）。
那么这个时候只用维护可以到达的区间的东点区间端点，这道题就做完了。
inline void cond()
{
for (int i = 1; i <= n; i++)
if (!dfn[i] && west_flag[i])
tarjan(i);
for (int u = 1; u <= n; u++) {
for (int v : G[u]) {
if (sccid[u] != sccid[v]) {
ng[sccid[v]].push_back(sccid[u]);
indeg[sccid[u]]++;
}
}
}
for (int i = 1; i <= n; i++) {
if (nodes[i].x == a && sccid[i])
east.push_back(nodes[i]);
}
sort(east.begin(), east.end(), [&](const Node& lhs, const Node& rhs) { return lhs.y < rhs.y; });
for (int i = 0; i < east.size(); i++) {
east_min[sccid[east[i].id]] = min(i + 1, east_min[sccid[east[i].id]]);
east_max[sccid[east[i].id]] = i + 1;
}
}
inline void topo()
{
queue<int> q;
for (int i = 1; i <= scccnt; i++)
if (!indeg[i])
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const int v : ng[u]) {
// 更新端点
east_min[v] = min(east_min[v], east_min[u]);
east_max[v] = max(east_max[v], east_max[u]);
if (!--indeg[v])
q.push(v);
}
}
}
int main()
{
cin >> n >> m >> a >> b;
for (int i = 1; i <= n; i++) {
nodes[i].id = i;
cin >> nodes[i].x >> nodes[i].y;
if (nodes[i].x == 0) {
west.push_back(nodes[i]);
west_flag[i] = 1;
} else if (nodes[i].x == a) {
east_flag[i] = 1;
}
}
for (int i = 1; i <= m; i++) {
cin >> u >> v >> k;
G[u].push_back(v);
if (k == 2)
G[v].push_back(u);
}
memset(east_min, 0x3f, sizeof east_min);
cond();
topo();
sort(west.begin(), west.end(), [&](const Node& lhs, const Node& rhs) { return lhs.y > rhs.y; });
for (const Node x : west) {
if (east_min[sccid[x.id]] > n)
cout << 0 << '\n';
else
cout << east_max[sccid[x.id]] - east_min[sccid[x.id]] + 1 << '\n';
}
}
（2023/10/10）「P1487」失落的成绩单
A_i=\dfrac{(A_{i-1})-(A_{i+1})}{2}+d
稍微变下形：
-A_{i-1} + 2A_{i} + A_{i+1} = 2d
然后就可以当高斯约旦消元了。
double a[105][105];
double d, a1, an;
int n, m;
inline bool eq(double x, double y, double eps = 1e-6) { return fabs(x - y) < eps; }
inline bool Gauss()
{
for (int i = 1; i <= n; i++) {
int r = i;
for (int j = i + 1; j <= n; j++) {
if (fabs(a[j][i]) > fabs(a[r][i]))
r = j;
}
swap(a[i], a[r]);
if (eq(a[i][i], 0))
return 0;
for (int j = 1; j <= n; j++) {
if (i != j) {
double tp = a[j][i] / a[i][i];
for (int k = i + 1; k <= n + 1; k++) {
a[j][k] -= a[i][k] * tp;
}
}
}
}
return 1;
}
int main()
{
cin >> n >> m;
cin >> d >> a1 >> an;
if (n == 0 || m == 0) {
cout << "0.000" << '\n';
return 0;
}
a[1][1] = 1, a[1][n + 1] = a1;
a[n][n] = 1, a[n][n + 1] = an;
for (int i = 2; i < n; i++) {
a[i][i - 1] = -1;
a[i][i] = 2;
a[i][i + 1] = 1;
a[i][n + 1] = 2 * d;
}
assert(Gauss());
double res = a[m][n + 1] / a[m][m];
if (eq(res, 0, 1e-2))
res = 0;
cout << fixed << setprecision(3) << res << '\n';
}
（2023/10/11）「洛谷 P1167」刷题
今天的日期（时间）是 yyyy 年 mm 月 dd 日 hh 时 min 分，考试的时间是 yyyy2 年 mm2 月 dd2 日 hh2 时 min2 分。这之间的所有时间小 A 都用来刷题了，那么考试之前他最多能刷多少题呢？注意哦，考虑闰年。
那么只用计算出时间了！然后贪心求解。
你说得对，但是 ctime 是由 glibc 自主研发的一款全新开放世界 C++ 时间库
#include <algorithm>
#include <chrono>
#include <iostream>
using namespace std;
int n;
int problems[1000005];
time_t date_to_time_t(int year, int month, int day, int hour, int minute)
{
tm timeinfo = {};
timeinfo.tm_year = year - 1900;
timeinfo.tm_mon = month - 1;
timeinfo.tm_mday = day;
timeinfo.tm_hour = hour;
timeinfo.tm_min = minute;
timeinfo.tm_sec = 0;
return mktime(&timeinfo);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> problems[i];
sort(problems + 1, problems + n + 1);
int year, month, day, hour, minutes;
scanf("%d-%d-%d-%d:%d", &year, &month, &day, &hour, &minutes);
year += 2000;
const time_t begin_time = date_to_time_t(year, month, day, hour, minutes);
scanf("%d-%d-%d-%d:%d", &year, &month, &day, &hour, &minutes);
year += 2000;
const time_t end_time = date_to_time_t(year, month, day, hour, minutes);
long long time_diff = difftime(end_time, begin_time);
time_diff /= 60;
for (int i = 1; i <= n; i++) {
if (problems[i] <= time_diff) {
time_diff -= problems[i];
} else {
cout << i - 1 << '\n';
return 0;
}
}
cout << n << '\n';
}
（2023/10/13）「ABC175F」Making Palindrome
记得是很久很久以前的一道模拟赛题，但是好像到现在才做出来。
有 N 个仅含小写字母的字符串 S_1,S_2,\cdots,S_N。你需要把从这些字符串中选择一些以任意顺序拼接起来，同一个字符串可以被选择多次。每选择一次 S_i，你都需要花费 C_i 的代价，也就是说你选择 S_i 所花费的代价为 C_i 与 S_i 被选择的次数之积。求使拼接得到的字符串为回文串所需的最小花费。若不管如何都无法拼接成回文串，输出 -1。
1 \le N \le 50，1 \le |S_i| \le 20，1 \le C_i \le 10^9。
正着构造回文串比较困难，正难则反，倒着想。
对于最后构造出的回文串，如果消去两边长度更小的字符串，那么有以下情况：
[某一个字符串的后缀][其他的][其他的][某一个字符串的前缀][一整个回文串]
其中对于情况 3，可以认为是长度为 0 的前后缀，可以不需要特殊考虑。
那么删除到最后，剩下的一定是一个 回文的前后缀。于是可以建立这样的一个自动机，每个节点代表一个前后缀，边代表删去这个「缀」剩下的那个字符串（缀）。
所以答案就是，所有初始串连接到回文前后缀的最短路。建超级源点终点就差不多是这样了。
#define PRFIX 0
#define SUFIX 1
#define rawstr first
#define direct second
using namespace std;
using ll = long long;
using pll = pair<int, ll>;
vector<pll> G[100005];
int ndcnt = 0;
map<pair<string, int>, int> link;
int n, tcost;
string tp, st;
string S[60];
int C[60];
long long dis[100005];
int vis[100005];
/// @brief 是否是回文串
inline bool is_rev(string x)
{
if (x.length() <= 1)
return true;
for (int i = 0; i * 2 <= x.length(); i++)
if (x[i] != x[x.length() - 1 - i])
return false;
return true;
}
inline void add_egde(int u, int v, long long w) { G[u].push_back({ v, w }); }
inline void update(string a, string b, int& direction, string& ans)
{
int i = 0, j = b.length() - 1;
while (i < a.length() && j >= 0) {
if (a[i] != b[j])
return;
i++, j--;
}
if (i >= a.length() && j < 0)
direction = 0, ans = "";
else if (j >= 0)
direction = 1, ans = b.substr(0, j + 1);
else
direction = 0, ans = a.substr(i, a.length());
}
void dij(int start)
{
using node = pair<ll, int>;
priority_queue<node, vector<node>, greater<node>> q;
memset(dis, 0x3f, sizeof dis);
dis[start] = 0;
q.push({ 0, start });
while (!q.empty()) {
auto [_, u] = q.top(); q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : G[u]) {
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({ dis[v], v });
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> S[i] >> C[i];
st = "";
for (int j = S[i].length() - 1; j >= 0; j--) {
st = S[i][j] + st;
link[{ st, PRFIX }] = ++ndcnt;
}
st = "";
for (int j = 0; j < S[i].length(); j++) {
st = st + S[i][j];
link[{ st, SUFIX }] = ++ndcnt;
}
}
link[{ "", PRFIX }] = ++ndcnt;
link[{ "", SUFIX }] = ++ndcnt;
for (int i = 1; i <= n; i++) {
add_egde(ndcnt + 1, link[{ S[i], PRFIX }], C[i]);
add_egde(ndcnt + 1, link[{ S[i], SUFIX }], C[i]);
}
for (auto [k, id] : link) {
string s = k.first;
if (is_rev(s))
add_egde(id, ndcnt + 2, 0);
}
for (auto [key, id] : link) {
for (int i = 1; i <= n; i++) {
int dir = -1;
string res = "";
// 删去这个前后缀剩下的字符串，大概就是，判断最长的可能达成回文部分
if (key.direct == PRFIX)
update(key.rawstr, S[i], dir, res);
else
update(S[i], key.rawstr, dir, res);
add_egde(id, link[{ res, dir }], C[i]);
}
}
dij(ndcnt + 1);
if (dis[ndcnt + 2] >= 0x3f3f3f3f3f3f3f3fll) {
cout << -1 << '\n';
return 0;
}
cout << dis[ndcnt + 2] << '\n';
return 0;
}
（2023/10/15）「USACO06NOV」Roadblocks G
（模板 次短路（x
跑 Dij 的时候顺便记一个 subdis 存次短路（但是不能加 vis 标记，否则有些边没法松弛），然后：
- 更新 dis 时更新 subdis
- 无法更新 dis 时检查 subdis 是否可以更新
然后就没了。
priority_queue<pair<int, int>> q;
dis[1] = 0;
q.push({ 0, 1 });
while (q.size()) {
auto [d, u] = q.top();
q.pop();
d = -d;
for (auto [v, w] : G[u]) {
if (dis[v] > d + w) {
subdis[v] = dis[v];
dis[v] = d + w;
q.push({ -dis[v], v });
q.push({ -subdis[v], v });
} else {
if (subdis[v] > d + w) {
subdis[v] = d + w;
q.push({ -subdis[v], v });
}
}
}
}
cout << subdis[n] << '\n';
（2023/10/15）「CQOI 2014」数三角形
给定一个 N\times M 的网格，请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。
这个公式看看就好，没有边界。
\begin{aligned}
ans &= \text{所有情况} – \text{平行坐标轴的三点共线} – \text{斜线三点共线} \\
&= {n \times m \choose 3} – \left(m{n \choose 3} + n{m \choose 3}\right) – \text{斜线三点共线}
\end{aligned}
对于斜线三点共线，考虑枚举斜率。但是很显然枚举每个起点终点都会超时，考虑优化；具体参见代码。
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
n++, m++;
long long ans = 1ll * (n * m) * (n * m - 1) * (n * m - 2) / 6;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans = ans - 1ll * (n - i) * (m - j) * (gcd(i, j) - 1) * 2;
}
}
if (n >= 3)
ans -= 1ll * n * (n - 1) * (n - 2) / 6 * m;
if (m >= 3)
ans -= 1ll * m * (m - 1) * (m - 2) / 6 * n;
cout << ans << '\n';
}
（2023/10/17）「ZJOI 2007」矩阵游戏
据说是，匈牙利算法的模板题。但是这个算法我不会，所以就现学了一下。
题意呢，就是说给定一个黑白染色的矩阵，可以进行两种操作，「交换任意两行」和「交换任意两列」。问，能否在任意次交换内让这个矩阵「左上」到「右下」的对角线染成黑色。
不难发现给行列连边然后做一次二分图匹配就完了。
struct Edge { int v, next; } ed[500 * 500 * 3];
int head[500], cnt, n;
char vis[500];
int peer[500];
inline void addedge(int u, int v) { ed[++cnt] = { v, head[u] }, head[u] = cnt; }
bool match(int u)
{
for (int i = head[u]; i; i = ed[i].next) {
int v = ed[i].v;
if (!vis[v]) {
vis[v] = 1;
if (!peer[v] || match(peer[v])) {
peer[v] = u;
return true;
}
}
}
return false;
}
inline void solve()
{
cin >> n;
cnt = 0;
memset(head, 0, sizeof(head));
memset(peer, 0, sizeof(peer));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> matrix[i][j];
if (matrix[i][j] == '1')
addedge(i, j + n);
}
}
int match_cnt = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
if (match(i))
match_cnt++;
}
if (match_cnt >= n)
cout << "Yes\n";
else
cout << "No\n";
}
（2023/10/23）「校内模拟」病毒分裂
有一种病毒，这种病毒有一个分裂参数 K，假如现在有 x 个这种病毒，下一个分裂周期将会有 K\times x 个一模一样的病毒。一开始时只有一个病毒，这个局面算作第一个周期，求病毒分裂到第 N 个周期前（分裂到第 N-1 周期时），求病毒单体的分裂总次数。你只要输出答案对给定的 P 取模后的答案。
2 \leq N\le 10^{18}，2 \leq K,P \le 2^{31}-1。
换言之，这个题目求的是 K^0 + K^1 + K^2 + \cdots + K^n；但是这个式子其实不是很好算啊，所以看到一个递推的性质：
F_0 = 1\\
F_1 = KF_0 + F_0 = (K+1)F_0\\
F_2 = KF_1 + F_1 = (K+1)F_1\\
\cdots
考虑矩阵优化。可以写出下面的矩阵：
\begin{bmatrix}
k&0\\
1&1
\end{bmatrix}
然后矩阵快速幂就完了。
struct Matrix {
array<array<long long, 2>, 2> m;
Matrix() { m = { { { 0, 0 }, { 0, 0 } } }; }
Matrix operator*(const Matrix& b)
{
Matrix c;
(c.m[0][0] = m[0][0] * b.m[0][0] % p + m[0][1] * b.m[1][0] % p) %= p;
(c.m[0][1] = m[0][0] * b.m[0][1] % p + m[0][1] * b.m[1][1] % p) %= p;
(c.m[1][0] = m[1][0] * b.m[0][0] % p + m[1][1] * b.m[1][0] % p) %= p;
(c.m[1][1] = m[1][0] * b.m[0][1] % p + m[1][1] * b.m[1][1] % p) %= p;
return c;
}
};
Matrix fastpow(Matrix a, long long n)
{
Matrix ans;
ans.m[0][0] = 1;
ans.m[0][1] = 1;
while (n) {
if (n & 1)
ans = ans * a;
a = a * a;
n >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> k >> n >> p;
Matrix base;
base.m[0][0] = k; base.m[0][1] = 0;
base.m[1][0] = 1; base.m[1][1] = 1;
Matrix ans_mat = fastpow(base, n - 2);
cout << (ans_mat.m[0][0] + p) % p << endl;
}
（2023/10/23）「校内模拟」货运公司
给定一棵树和 q 组点 u_i, v_i，定义 u_i 到 v_i 权值为 u_i\to v_i 树上路径所经过边的边权的最大值，现在你可以使树上的一条边边权减少 L，求所有 u_i, v_i 权值之和最小的可能值。n, q\le 10^5, 1\le w, L\le 10^6。
对于每一个点组，如果路径将最大边减少 L，那么这条路径的权值就会变为 w – L 和 路径上次大边权值 的最大值。（如果不是减少最大边权值就不会变化）
那么只用处理出路径上的次大值（倍增树剖都行），记录删去每一条边可以减少的权值（删去每一条边可以产生的贡献），最后 O(n) 扫一遍取最大就行了。
树剖时间复杂度 O(n\log^2 n)。
#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
#define file_open(fn) freopen(fn ".in", "r", stdin), freopen(fn ".out", "w", stdout)
#define _lx_likely(cond) (__builtin_expect((cond), 1))
#define _lx_unlikely(cond) (__builtin_expect((cond), 0))
using namespace std;
const int MAXN = 100006;
vector<pair<int, int>> tr[MAXN];
int fa[MAXN], hvson[MAXN], dep[MAXN], sz[MAXN];
int ltop[MAXN]; // 链顶
int wei[MAXN]; // 注意，边权 -> 点权; fa -> son = w[son]
int dfn[MAXN], rnk[MAXN], cnt; // dfn: 点->排名; rnk: 排名->点
int n, q, l;
long long rem[MAXN], ans;
void dfs1(int u, int f)
{
sz[u] = 1; fa[u] = f;
dep[u] = dep[f] + 1;
for (auto [v, w] : tr[u]) {
if _lx_unlikely (v == f) continue;
wei[v] = w;
dfs1(v, u);
sz[u] += sz[v];
if (sz[hvson[u]] < sz[v]) hvson[u] = v;
}
}
void dfs2(int u, int top)
{
ltop[u] = top; dfn[u] = ++cnt;
// wei[rnk[cnt]]
rnk[cnt] = u;
if _lx_unlikely (hvson[u] == 0) return;
dfs2(hvson[u], top);
for (auto [v, _] : tr[u]) {
if _lx_unlikely (v == fa[u] || v == hvson[u]) continue;
dfs2(v, v);
}
}
struct Node { int l, r; pair<int, int> pre_max, mx; } st[800005];
struct Edge { int u, v, w; } ed[100005];
struct Query { int l, r; } qr[100005];
int edcnt;
void build(const int l, const int r, const int p = 1)
{
st[p].l = l, st[p].r = r;
if (l == r) {
st[p].mx = { wei[rnk[l]], l };
st[p].pre_max = { INT_MIN, 0 };
return;
}
int mid = (l + r) >> 1;
build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
st[p].mx = max(st[p << 1].mx, st[p << 1 | 1].mx);
st[p].pre_max = max({
st[p << 1].pre_max,
st[p << 1 | 1].pre_max,
min(st[p << 1].mx, st[p << 1 | 1].mx),
});
}
void upd_single(const int pos, const int val, const int p = 1)
{
if (st[p].l == st[p].r) {
st[p].mx.first = val;
return;
}
int mid = (st[p].l + st[p].r) >> 1;
if (pos <= mid) upd_single(pos, val, p << 1);
else upd_single(pos, val, p << 1 | 1);
st[p].mx = max(st[p << 1].mx, st[p << 1 | 1].mx);
st[p].pre_max = max({
st[p << 1].pre_max,
st[p << 1 | 1].pre_max,
min(st[p << 1].mx, st[p << 1 | 1].mx),
});
}
template <typename _Tp>
inline pair<_Tp, _Tp> merge(pair<_Tp, _Tp> a, pair<_Tp, _Tp> b)
{
pair<_Tp, _Tp> res;
res.first = max(a.first, b.first);
res.second = max({ a.second, b.second, min(a.first, b.first) });
return res;
}
pair<pair<int, int>, pair<int, int>> query(const int l, const int r, const int p = 1)
{
if (l <= st[p].l && st[p].r <= r) return { st[p].mx, st[p].pre_max };
if (r < st[p].l || st[p].r < l) return { { INT_MIN, 0 }, { INT_MIN, 0 } };
return merge(query(l, r, p << 1), query(l, r, p << 1 | 1));
}
inline pair<pair<int, int>, pair<int, int>> get_path(int u, int v)
{
pair<pair<int, int>, pair<int, int>> ret = { { INT_MIN, 0 }, { INT_MIN, 0 } };
while (ltop[u] != ltop[v]) {
if (dep[ltop[u]] < dep[ltop[v]]) swap(u, v);
ret = merge(ret, query(dfn[ltop[u]], dfn[u]));
u = fa[ltop[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret = merge(ret, query(dfn[hvson[u]], dfn[v]));
return ret;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> q >> l;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
tr[u].push_back({ v, w });
tr[v].push_back({ u, w });
}
dfs1(1, 0); dfs2(1, 1); build(1, n);
long long ans = 0, res = 0;
for (int i = 1; i <= q; i++) {
cin >> qr[i].l >> qr[i].r;
auto p = get_path(qr[i].l, qr[i].r);
auto [mx, pre_mx] = p;
rem[mx.second] += min(1ll * mx.first - pre_mx.first, 1ll * l);
ans = ans + mx.first;
}
for (int i = 1; i <= n; i++)
res = max(res, rem[i]);
cout << ans - res << '\n';
}
（2023/10/25）「校内模拟」石子合并
给定正整数 n 和正整数数组 A_i(1\le i \le n)，表示 n 堆石子排成一列，第 i 堆石子有 A_i 个，其中对于任一正整数 i(i<n) ，第 i 堆石子与第 i+1 堆石子相邻。
每次你可以将任意两堆石子合并成一堆，新堆的石子数是原来两堆石子数之和，代价是原来两堆石子数之积，求合并 n-1 次将 n 堆石子合并成一堆的代价和最小是多少。
1\le n\le 10^5
诈骗题。
一开始说，这不就是「模板」区间 DP？但是好像会出问题啊。又说是什么四边形不等式优化，不会。（但是好像又不是？）
然后赛时就被骗了。打了 O(n^3) 的暴力然后走人。80 分，还行。
手玩一下数据会发现，无论怎么决策，cost 都是一样的。对于任意的三个相邻石子：a_1\space a_2\space a_3，可能的决策方式有：
- (1, 2) 3
- 1, (2, 3)
然后分别算一下：
- $(a_1\cdot a_2) + a_3(a_1 + a_2) = a_1a_2 + a_1a_3 + a_2a_3$
- $a_1(a_2 + a_3) + (a_2 \cdot a_3) = a_1a_2 + a_1a_3 + a_2a_3$
然后开个队列算一下就完了。
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a; q.push(a);
}
while (q.size() > 1) {
unsigned long long x = q.front(); q.pop();
unsigned long long y = q.front(); q.pop();
q.push(x + y);
sum += x * y;
}
cout << sum << '\n';
return 0;
}
noʎ ʇɹnɥ puɐ ǝᴉl ɐ llǝʇ ɐuuoƃ ɹǝʌǝN
（2023/10/25）「校内模拟」质数查询
10^5 次询问，查询区间 L, R 间有多少个数的质因子数量 \le 2。1\le L, R\le 10^7。
注意到数据范围 1e7，这个范围有大约 66 万个素数，而且到第 \sqrt{10^7} \approx 3163 个素数左右的时候，自己的平方已经超过 1e7。
所以筛素数之后，暴力地将相乘 \le 10^7 的素数预处理出来打个标记，预处理出来然后前缀和处理查询。
int prime_list[665000], prcnt;
int flag[10000001];
char not_prime[10000001];
inline void get_prime(int maxn)
{
not_prime[1] = 1;
for (int i = 2; i <= maxn; i++) {
if _lx_unlikely (!not_prime[i]) {
prime_list[++prcnt] = i;
flag[i] = 1;
if _lx_unlikely (i < 3200)
for (int j = i * i; j <= maxn; j += i)
not_prime[j] = 1;
}
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
get_prime(10000000);
for (int i = 1; i < 3200; i++) {
for (int j = i; j <= prcnt; j++) {
if (prime_list[i] * prime_list[j] <= 10000000) {
flag[prime_list[i] * prime_list[j]] = 1;
} else
break;
}
}
for (int i = 2; i <= 10000000; i++)
flag[i] = flag[i - 1] + flag[i];
int q, l, r;
cin >> q;
while (q--) {
cin >> l >> r;
cout << flag[r] - flag[l - 1] << '\n';
}
}
后面还有题暂时没补上来，先发这么多qwq