2022国防科技大学程序设计竞赛预选赛题解

本场题目难度 && 建议做题顺序：ED GNBFH IJLCM AK

代码在最后。每道题目标题后的括号代表前置知识。

E:This is an easy problem

纯签到题，直接输出答案即可。

D:Limit

简单的高数题，可以用泰勒展开 or 洛必达。
不要忘了a!=0

G:Fibonacci (线性dp)

要求的是十位数，那么只需要记录每个数%100的结果就好，查询的时候输出结果/10。

N:

将图形分为以下的区域:

在二维字符数组中全初始化为空格，在平行四边形区域内修改空格为1即可。
其输入的大小n用来计算平行四边形的长和高，长均为 n ，高对于最左边的平行四边形为 $\frac{3}{4}n$，三个平行的较大的平行四边形为 $\frac{5}{4}n$ ，最后小的为 $\frac{n}{4}$

B: 银河杂货铺与月湖大市场采购

我们可以将这个环直接从月湖大市场门口剪开，实际上问题可以化成一个序列，我有一系列询问，对于每个询问我可以在序列上或顺序或逆序查找询问的值，统计每次查找中逆序或顺序查找时比对次数中比较大的那个次数的和。

相对简单的序列预处理题目。

我们注意此时序列中和询问的值的大小都不超过 $100000$ ，我们可以对于顺序和逆序分别用 $100000$ 个桶来记录，对于每个值来说，顺序查找时第一个这个值是在哪个位置，对于逆序亦然。这样我们得到询问的值时，就可以直接比对对于询问的值顺序和逆序的桶哪个桶中位置离两端距离更大，就统计哪个答案即可。

F： 五四银河展和文案编辑

对于每个操作 $1$ ，我们记录一个数组，数组分别代表 $abcd...yzABCD...XYZ$ 中第 $i$ 个字符最终变成了哪个字符，数组初始化为每个字符自己。每次操作 $1$ ，我不修改原字符串，只修改数组，对于数组中的各个值，把数组中每个值为 $c_1$ 的位置设为 $c_2$。对于每个操作 $2$，我直接将数组清空，将原字符串用新字符串覆盖。操作结束后，将字符串中每个字符按照数组记录的值修改即可。时间复杂度 $O(52m+100n)$

H：薛定谔的猫与量子纠缠 （DFS）

我们将每个实验装置看做一个节点，每个量子纠缠关系看做连接两节点的边，于是该题可看做一个图。

然后我们通过DFS，从已经有0/1状态的节点开始，给相邻节点标上不同于上一个节点的状态即可，最后按1~n的顺序输出即可。

I：宣传海报组与海报制作

一道比较显然但不太好证明的贪心。

问题简述：将 $n$ 个数分组，每组仅可有 $1$ 个或 $2$ 个，如何分组使得其每个组中数和的最大值与最小值的差最小。
我们枚举有多少组含2个，记为 $i$ 。对于枚举的每个 $i$ ,最优策略一定是:
在这 $n$ 个数中，取前 $n-2i$ 大的数单独成组，然后每次取剩下数中最大的和最小的数作为一组。
证明：
最初$n$个数时，考虑选1个数的人，当前最优策略一定可以是选则最大的数，记为$a$。证明：假设不选$a$选$b$，这个前提下的最优策略记为$F_b$. 可以构造一个策略$F_a$，与$F_b$的唯一不同是其中的$a$,$b$交换位置。记某策略中组内和的最小值为min,最大值为max。容易得到 $F_b(min)\le F_a(min)$，$F_b(max)\ge F_a(max)$。那么$F_a$一定比$F_b$优。
这样可以安排完所有选1个数的人。接下来对于剩下最大的数，一定和最小的数配对，证明方法和上面类似。

如有更好的解决方案可直接在群里给出QwQ或给出题人。

J： 天河开放日与参观路线设计 (Flyod)

多源最短路。

$O(n^3)$解法：魔改 $Floyd$。

对于以下 $Floyd$：

for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) mp[i][j] = max(mp[i][j] , mp[i][k] + mp[k][j]);

最外层枚举 $k$ 的循环中的节点的顺序可以调整，我们将其调整为我们删点的顺序，也就是说，我们倒着考虑，我们将删点看做加点，$k$ 层的循环中用于松弛的节点按照加点的顺序，每次加点完进行 $i,j$ 层松弛操作，统计答案，记录该点已加入，在计算总和时记录已加入点得答案。
这样做是正确的，因为：
根据对 $floyd$ 的理解我们可以明白，记集合 $S$ 为已经作为最外层循环的点集，那么只含 $S$ 内点的图中，最短路已经是正确的。
而为了保证复杂度的正确性，我们在内层循环时仍要更新除了 $S$ 以外的点的最短路。

$O(n^{3}logn)$解法：直接暴力 $Dijkstra+heap$

直接将某些仍存在的点标记，每次对 $n$ 个点各进行一次 $Dijkstra$，要用优化，否则 $O(n^4)$ 无法通过。

推荐 $O(n^3)$ 做法，帮助理解 Floyd。

L:银河讲堂与座位安排 （数据结构：线段树 or 并查集等）

直接建 $m$ 个线段树，区间赋值成0，维护区间最大值（有没有1）就能过，复杂度$O((q\ast m+n)logn)$。（不过赛时好多TLE,应该是常数太大）

这里再介绍std做法：（区间and，维护区间or）

我们发现 $m\le 30$ ，即不超过 $31$ ，考虑将每排压缩成一个 $int$ 类型的值，第 $i$ 列座位在此值中表现为二进制的第 $i-1$ 位数。我们最初设为 $2^m-1$，即各个数位上全为 $1$ 。对于 $n$ 个值，我们建一颗线段树。

每个修改也可压缩为一个 $int$ 类型的值 $y$，对于每个不可坐人的列 $j$，将 $y$ 的第 $j-1$ 位设为 $0$，其他为设为 $1$ ，

修改即为对于区间每个数均 $and$ 上 $y$。

对于每个询问，在线段树上统计区间 $or$ 的值，并转化为各个位置的值，并统计答案即可。

另外并查集也可做，复杂度是$O(m\ast n)$。大致思路：每列一个并查集，区间赋值时，把区间的所有点指向$fa[r+1]$，查询时判断$fa[l]$是否大于$r+1$，具体见这里

C：counting rhombus

对于菱形，入手点是对角线垂直平分。
可以把所有中点相同的对角线分成一类。 分类时，按中点(x,y)排序即可。
处理一类中的个数，方法有很多，一种通用的思路可以是：先按对角线的斜率大小排序，遍历一遍，对于当前斜率为 $k$ , 答案+=斜率 $-\frac{1}{k}$ 的个数。这个过程可以用map维护 (注意尽量不要引入浮点数以免产生误差。斜率可用分数表示，注意斜率不存在，最简分数等问题)。
本题其实不用严格按斜率排序。一种实现方法如下：
考虑计入答案的一对斜率，分数表示为 $\frac{x}{y}$ , $-\frac{y}{x}$ ($x,y\ge 0$)。如果按分子排序，一定有先遍历 $-y$ 再轮到 $x$. 遍历过程中用 map记录 $\frac{x}{y}$ 的个数，遍历到 $\frac{x}{y}$ 时加上 $-\frac{y}{x}$的个数即可。这样做是正确的必须要保证 分母>=0 且 为最简分数。
时间复杂度O( $n^{2}logn$)

M：Fluorescent night running (树形dp)

以给定的k作为根节点。设：
$d{p}_i$ : 子树 $i$ 中，以 $i$ 为一条路径起点，两条路径之和的最大值。
$d_i$：子树 $i$中，以 $i$ 为起点最长的一条路径的长度。
$f_i$ : 子树 $i$ 中，最长的一条路径的长度。
则答案为 $d{p}_i$ .
如何转移?
$d_i$ 最简单， $d_i$ = max( $d_{son}$+ length(i,son) ).
$f_i$ 的转移有两种情况：最大的 $f_{son}$ 或子树中最长的以 $i$ 为起点的两条路径。
$d{p}_i$：考虑以 $i$ 为起点的路径，其向下指向 $son$。分两种：
当另一条路径在 $son$ 的子树中时: 将$d{p}_{son}$ + length(i,son) 转移给 $d{p}_i$;
当另一条路径不在 $son$ 的子树中时：此时以 $i$ 为起点的路径可以随意取最长，为$d_{son}$。而另一条路径要么是在不为 $son$ 的某个子树中，要么是除去 $d_{son}$ 外的两条到 $i$ 的最长路径拼接。
时间复杂度O($n$)。
实现细节可参考代码。

K: game of number (素数筛，逆元，思维)

本题想起来其实不难，但细节多，码量大。
首先是如何求一个整数 $x$ 的因子个数，即 $f(x)$:
将 $x$ 分解质因数：$x=p_1^{k_1}{p}_2^{k_2}...p_n^{k_n}$ ,其中$p_1,p_2,...,p_n$为素数。则$f(x)=(k_1+1)(k_2+1)...(k_n+1).$
对于$[1,1e7]$以内的质因子可以线性筛 $O(n)$ 预处理。
将 $x$ 分解质因数的方法：底数的话遍历 $sqrt(x)$ 以内的质数，最后如果$x>1$则除剩下的 $x$ 也为素数。指数最多和为$log$级别，复杂度为 $O(sqrt(x)以内的质数+log(x))$。

然后考虑一个重要的性质：若 $y=kx$，且 $k$ 为素数，则 $f(x)\le f(y)$。证：从$x$乘$k$到$y$,分数结果中，分母乘$k$，而分子乘 $((num[k]+1)/num[k]$，最大为2$，其中num[k]$ 表示 $x$ 以 $k$ 为底数的指数。
首先线性筛，并得到初始 $n$ 的所有素因子，复杂度 $O(1e7)$。
首先Bob的最优操作一定可以是，先操作完所有乘法再操作除法。
考虑Alice不提前declare,等到所有卡片取完的情况：此时最终的数恒定，与取卡片的顺序无关，结果记为 $ans$。可以先操作所有乘法的卡片，再操作除法，最终得到此数的各个素因子及其指数。此部分复杂度$O(446\ast q)$ ,446为 $sqrt(1e7)$ 以内的素数个数。注意乘法是指数加，除法是指数减，且不能减到负数。
考虑提前declare结束游戏：易知一定是在第一轮declare。此时Bob要最小化$f(n)$，那么一定是操作一次乘法。枚举所有乘法操作得到对应结果，比较选择最小的结果即可，记为$res$。此部分复杂度$O(446\ast q)$。同时注意特判没有乘法卡片存在的情况。
Alice的最优策略是比较 $res$ 与 $ans$ 选择较大的那个即可。对于 $res$, 其分母最大为 $1e14\ast 1e7$级别，要用int128存。对于 $ans$的分子分母，太大而int128$（1e38级别）$都远远存不下，怎么办？ 可以注意到当$n$，$f(n)相对于n很小$，此时$ans$一定小于 $res$. int128范围内一个整数的因子个数上限为 $3e8$（证明见代码最下方），那么分母大于 $1e31$时，$3e8/1e31<1/1e21$。

具体细可参考代码。

A：dir -C （二分答案+单调队列优化dp）

首先容易看出要二分答案,因为对于$l_1$<$l_2$,如果$l_1$符合要求，那么$l_2$一定符合要求。那么对于一个答案k，如何check呢？
考虑如下的dp:
记 $d{p}_i$ 为以 $i$ 作为某block结尾，此block之前（包括此block）的宽度之和。则转移方程：
$d{p}_i=min(d{p}_j+max[j+1,i]),i-k\le j<i$.
其中 $max[l,r]$ 代表 $l\le i\le r$ 中最大的$f_i$.
容易知道dp序列单调不降。
从枚举$[j+1,i]$中的最大值入手。对于当前$i$，首先考虑 $[i-k+1,i]$ 中的最大值为转移到 $d{p}_i$ 中的$max[j+1,i]$ ，这个最大值所在位置记为 $i_1$ ,则对应的 $d{p}_j$ 可以取到 $i-k\le j<i_1$，由于dp单调不降，自然是取$d{p}_{i-k}最优$ ; 继续，将区间缩为$[i_1+1,i]$，此时区间内最大值记为$i_2$，则对应地取 $d{p}_{i1}$ ; 一直这样下去直到区间变为$[i+1,i]$。
可知上面的 $i_1$,$i_2$,$i_3$,$i_4$ 序列单调不增。于是可以在遍历的过程中用单调栈维护此序列。序列每当新加入或删除元素，其对应的贡献（即$d{p}_j+max[j+1,i]$）也要更新。维护所有贡献可以用优先队列 or 线段树等。最后check的就是 $d{p}_n-1\le w$ 。
一次check的复杂度O($nlogn$)，总时间复杂度O（$nlo{g}^{2}n$ ）。

代码

E

#include<stdio.h>
int main(){puts("12:00");puts("2022/5/21"); 
}

D

#include<iostream>
using namespace std;
int a,b;
int main(){cin>>a>>b;if(a==0)cout<<0;else if(b==0)cout<<0;else if(b==1)cout<<a;else cout<<"INF";
}

G

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
const int N=1e6,mod=100;
int ans[N+5];
int main(){IOSans[1]=1; ans[2]=1;rep(i,3,N)ans[i]=(ans[i-1]+ans[i-2])%mod;int q,x;cin>>q;while(q--){cin>>x;cout<<ans[x]/10<<'\n';}
}

N

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char ch[52][142];
int n;
inline void solve() {scanf("%d", &n);for (int i = 1; i <= n * 2 + n / 4; ++i)for (int j = 1; j <= 6 * n + n / 2; ++j)ch[i][j] = ' ';for (int x = 1; x <= (n / 2 + n / 4); ++x) for (int i = 1; i <= n; ++i)ch[x][i + (x - 1)] = '1';for (int x = 1; x <= (n * 2 + n / 2); ++x) for (int i = 1; i <= n; ++i)ch[x][i + n * 2 - (x - 1)] = '1',ch[x][i + n * 3 + n / 2 - (x - 1)] = '1',ch[x][i + n * 5 + n / 2 - (x - 1)] = '1';for (int x = (n / 2) + 1; x <= (n / 2) + (n / 4); ++x)for (int i = 1; i <= n; ++i)ch[x][i + n * 4 + (n >> 1) - (x - 1)] = '1';for (int i = 1; i <= n + n / 4; ++i) {for (int j = 1; j <= (6 * n + n / 2 - (i - 1)); ++j)   putchar(ch[i][j]); puts("");}
}
inline void init() {}
int main() {init(), solve();return 0;
}

B

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int mn = 1000010;int n, m;
int A[mn], s2[mn], s1[mn], b[mn];int main() {scanf("%d%d", &m, &n);for(int i = 1; i <= m; ++i) scanf("%d", b + i);for(int i = 1; i <= n; ++i) scanf("%d", A + i);for(int i = 1; i <= 100000; ++i) s1[i] = n + 1, s2[i] = 0;for(int i = 1; i <= n; ++i) s1[A[i]] = min(s1[A[i]], i), s2[A[i]] = max(s2[A[i]], i);long long sum = 0;for(int i = 1; i <= m; ++i) sum += 1ll * max(s1[b[i]], (n - s2[b[i]] + 1));printf("%lld\n", sum);return 0;
}

F

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;typedef long long ll;
const int mn = 100010;int fa[55], n, m;
string str;int main() {    ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;cin >> str;char c1[10], c2[10];for(int _ = 1, opt; _ <= m; ++_) {cin >> opt;if(opt == 1) {cin >> c1 >> c2;int x1 = c1[0] >= 'a' ? c1[0] - 'a' + 26 : c1[0] - 'A';int x2 = c2[0] >= 'a' ? c2[0] - 'a' + 26 : c2[0] - 'A';for(int i = 0; i < 52; ++i) if(fa[i] == x1) fa[i] = x2;} else if(opt == 2) {cin >> str; for(int i = 0; i < 52; ++i)fa[i] = i;} }int nn = str.size();for(int i = 0; i < nn; ++i) {int x1 = str[i] >= 'a' ? str[i] - 'a' + 26 : str[i] - 'A';char c2 = fa[x1] >= 26 ? fa[x1] - 26 + 'a' : fa[x1] + 'A';str[i] = c2;}cout << str;return 0;
}

H

#include <cstdio>
#include <cstring>const int mn = 100010;int n, m, l, k;
struct edge {int v, nxt;
} e[mn << 1];
int h[mn], p = -1;
inline void add(int a, int b) { e[++p].nxt = h[a], h[a] = p, e[p].v = b; }bool vis[mn], col[mn];
void dfs(int x, int c) {if(vis[x]) return;col[x] = c;vis[x] = 1;for(int i = h[x]; i != -1; i = e[i].nxt) {int v = e[i].v;dfs(v, c ^ 1);}
}int main() {memset(h, -1, sizeof h);scanf("%d%d%d%d", &n, &m, &l, &k);for(int x, y, i = 0; i < m; ++i) {scanf("%d%d", &x, &y);add(x, y), add(y, x);}dfs(l, k);for(int i = 1; i <= n; ++i) printf("%d%c", col[i], " \n"[i == n]);return 0;
}

I

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<int,int>
const int N=3e3+5,inf=2e9;
int n,t[N];
int res=inf,idx,sum;
int main(){IOScin>>n;rep(i,1,n)cin>>t[i];sort(t+1,t+n+1);rep(i,(n+1)/2,n){ //招i-1个人int two=n-i,one=i-two;int minv=t[n-one+1],maxv=t[n];  //当one=0,不能这么定义!!下面修改if(one==0){minv=inf;maxv=0;}rep(j,1,two){sum=t[j]+t[2*two+1-j];minv=min(minv,sum); maxv=max(maxv,sum);}if(res>=maxv-minv){res=maxv-minv;idx=i;}}cout<<res;
}

J

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>using namespace std;typedef long long ll;
const int mn = 505;
const ll inf = (1ll << 60);int n, m, p[mn];
ll mp[mn][mn], ans[mn];
bool vis[mn];
set<int> se;int main() {memset(vis, 0, sizeof(vis));memset(mp, 0x3f, sizeof(mp));scanf("%d%d", &n, &m);for (int i = 2; i <= n; ++i)for (int j = 1; j < i; ++j)scanf("%lld", &mp[i][j]), mp[j][i] = mp[i][j];for (int i = 1; i <= n; ++i)mp[i][i] = 0;for (int i = 1; i <= m; ++i)scanf("%d", p + i), vis[p[i]] = 1;for (int k = 1; k <= n; ++k) if (!vis[k])for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i != j && j != k && i != k)if (mp[i][j] > mp[i][k] + mp[k][j])mp[i][j] = mp[i][k] + mp[k][j];for (int i = 1; i <= n; ++i)vis[i] = !vis[i];ll an = 0ll;for (int i = 1; i <= n; ++i)for (int j = 1; j < i; ++j)if (vis[i] && vis[j])an ^= mp[i][j];ans[m + 1] = an;for (int k, l = m; l > 0; --l) {k = p[l], vis[k] = 1;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (i != j && j != k && i != k)if (mp[i][j] > mp[i][k] + mp[k][j])mp[i][j] = mp[i][k] + mp[k][j];an = 0ll;for (int i = 1; i <= n; ++i)for (int j = 1; j < i; ++j)if (vis[i] && vis[j])an ^= mp[i][j];ans[l] = an;}for(int i = 2; i <= m + 1; ++i)printf("%lld%c", ans[i], " \n"[i == m + 1]);return 0;
}

L

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int mn = 100010;
const ll mod = 998244353;#define lson l, mm, rt << 1
#define rson mm + 1, r, rt << 1 | 1
#define bson l, r, rt
#define root 1, n, 1
#define Max_M ((1 << m) - 1)int z[mn << 2], col[mn << 2];
int n, m, K;
inline void update(int rt) { z[rt] = z[rt << 1] | z[rt << 1 | 1]; }inline void color(int l, int r, int rt, int v) { z[rt] &= v, col[rt] &= v; }inline void push_col(int l, int r, int rt) {if(col[rt] != ((1 << m) - 1)) { int mm = (l + r) >> 1;color(lson, col[rt]);color(rson, col[rt]);col[rt] = ((1 << m) - 1);}
}void build(int l, int r, int rt) {col[rt] = (1 << m) - 1;if(l == r) { z[rt] = (1 << m) - 1; return; }int mm = (l + r) >> 1;build(lson), build(rson), update(rt);
}void modify(int l, int r, int rt, int nowl, int nowr, int v) {if(nowl <= l && r <= nowr) { color(bson, v); return; }int mm = (l + r) >> 1;push_col(bson);if(nowl <= mm) modify(lson, nowl, nowr, v);if(mm < nowr)  modify(rson, nowl, nowr, v);update(rt);
}int query(int l, int r, int rt, int nowl, int nowr) {if(nowl <= l && r <= nowr) return z[rt];int mm = (l + r) >> 1;push_col(bson);if(nowl <= mm) {if(mm < nowr) return query(lson, nowl, nowr) | query(rson, nowl, nowr);else return query(lson, nowl, nowr);} else return query(rson, nowl, nowr);
}int main() {scanf("%d%d%d", &n, &m, &K);build(root);for (int x, l, r, op, k, _ = 1; _ <= K; ++_) {scanf("%d%d%d%d", &op, &l, &r, &k);if (!op) {x = Max_M;for (int j, i = 0; i < k; ++i)scanf("%d", &j), x ^= (1 << (j - 1));modify(root, l, r, x);} else {x = query(root, l, r);int ans = 0;for (int j, i = 0; i < k; ++i)scanf("%d", &j), ans += ((x & (1 << (j - 1))) ? 1 : 0);if (ans == 0) puts("G");else printf("%d\n", ans);}}return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<int,int>
unordered_map<ll,int>mp;
const int N=1005,inf=4e5+5;
int n,ans,cnt,Gcd;
pair<ll,P> q[N*N/2];
P p[N],temp;
ll Hash(int x,int y){  //将两个[-2e5,2e5]范围内的整数加密，记录一对(x,y)return 1ll*x*inf+y;
}
int main(){IOScin>>n;rep(i,1,n){cin>>p[i].first>>p[i].second;}rep(i,1,n){rep(j,i+1,n){q[++cnt].first=Hash(p[i].first+p[j].first,p[i].second+p[j].second);temp={p[i].first-p[j].first,p[i].second-p[j].second};if(temp.first==0)temp.second=1;  //(0,1)else if(temp.second==0)temp.first=1; //(1,0)else{ //(x,y),满足x,y互质,且y>0Gcd=__gcd(abs(temp.first),abs(temp.second));temp.first/=Gcd; temp.second/=Gcd;if(temp.second<0){temp.first=-temp.first;temp.second=-temp.second;}}q[cnt].second=temp;}}sort(q+1,q+cnt+1);q[0].first=Hash(inf,inf);rep(i,1,cnt){if(q[i].first!=q[i-1].first)mp.clear(); //对于不同类要clearans+=mp[Hash(-q[i].second.second,q[i].second.first)];mp[Hash(q[i].second.first,q[i].second.second)]++;}cout<<ans;
}

M

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<int,int>
#define vi vector<int>
const int N=1e5+5;
vector<P>tu[N];
int n,k,u,v,w,dp[N],f[N],d[N];
void Max(int & a,int b){a=max(a,b);}
void dfs(int now,int pre){P f1={0,0},f2={0,0},d1={0,0},d2={0,0},d3={0,0}; //置为0(不要为负),顺带处理了子树为空树的转移情况.for(P k:tu[now]){int son=k.first;if(son==pre)continue;dfs(son,now);Max(dp[now],dp[son]+k.second);int temp=d[son]+k.second;Max(d[now],temp);if(temp>d1.first){d3=d2;d2=d1;d1={temp,son};}else if(temp>d2.first){d3=d2;d2={temp,son};}else if(temp>d3.first){d3={temp,son};}Max(f[now],f[son]);if(f[son]>f1.first){f2=f1;f1={f[son],son};}else if(f[son]>f2.first){f2={f[son],son};}}Max(f[now],d1.first+d2.first);int maxf,sumd;for(P k:tu[now]){int son=k.first;if(son==pre)continue;if(son==f1.second)maxf=f2.first;else maxf=f1.first;if(son==d1.second)sumd=d2.first+d3.first;else if(son==d2.second)sumd=d1.first+d3.first;else sumd=d1.first+d2.first;Max(dp[now],d[son]+k.second+max(maxf,sumd));}
}
int main(){IOS// freopen("in.txt","r",stdin);cin>>n>>k;per(i,n-1,1){cin>>u>>v>>w;tu[u].push_back({v,w});tu[v].push_back({u,w});}dfs(k,0);cout<<dp[k];
}

K

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<int,int>
const int N=1e7,mod=1e9+7;
int pri[N+5],notpri[N+5],cnt;
int num[N+5],py[N+5];//num[i]:素因子i的个数,py是num的拷贝
int q,y; ll n;
P card[1000005];
int qp(int x,int y){ //快速幂int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;
}
struct frac{//分数结构体ll x; __int128_t y; //分子，分母bool operator < (const frac & t)const &{return x*t.y<t.x*y;}int val(){  //取模结果return x%mod*qp(y%mod,mod-2)%mod;}
};
int main(){IOSrep(i,2,N){ //线性筛法求素数if(!notpri[i])pri[++cnt]=i;ll temp;for(int j=1;temp=1ll*i*pri[j],temp<=N;++j){notpri[temp]=1;if(i%pri[j]==0)break;}}cin>>n>>q;ll t1=1,nn=n;//处理初始n的素因子rep(i,1,cnt){while(nn%pri[i]==0){nn/=pri[i]; ++num[pri[i]];}t1*=(num[pri[i]]+1);py[pri[i]]=num[pri[i]];}if(nn>1)t1*=2;rep(i,1,q)cin>>card[i].first>>card[i].second;sort(card+1,card+q+1);frac res={1,1};per(i,q,1){  //倒序,先操作x=1的卡片int temp=card[i].second;if(card[i].first){frac ret; ret.y=(__int128_t)card[i].second*n; ret.x=t1;rep(j,1,446){if(temp%pri[j]==0){int cnt=0;while(temp%pri[j]==0){++cnt; temp/=pri[j];}ret.x/=py[pri[j]]+1;ret.x*=py[pri[j]]+1+cnt;num[pri[j]]+=cnt;}}if(temp>1){ret.x/=py[temp]+1;ret.x*=py[temp]+2;++num[temp];}if(ret<res)res=ret;}else{rep(j,1,446){if(temp%pri[j]==0){int cnt=0;while(temp%pri[j]==0){++cnt; temp/=pri[j];}num[pri[j]]=max(0,num[pri[j]]-cnt);}}if(temp>1)num[temp]=max(0,num[temp]-1);}}int t3=1; __int128_t t2=1; //因子个数 , 最终nconst __int128_t M=1e31;int flag=0; //最终的数是否爆1e31  实际数据没怎么卡,1e24就过了rep(i,1,cnt){if(flag)break;t3*=num[pri[i]]+1;rep(j,1,num[pri[i]]){t2*=pri[i];if(t2>M){flag=1;break;}}}if(nn>1)t3*=2,t2=t2%mod*nn;frac ans=frac{t3,t2};//两种选择: 1、第一轮declare:res   2、选完所有card:ansif(!card[q].first){  //没有x=1的卡片,Alice直接等所有选完即可.cout<<ans.val();}else if(flag){ //最终n过大,一定不如第一轮选更优  cout<<res.val();}else{   //比较t3/t2 与 resif(ans<res)cout<<res.val();else cout<<ans.val(); }
}
/*
int128范围内的一个数的最大因子数: (可以如下判断)
cout<<log(pow(2.0,64))/log(3); 则2^128 = 3^40,除2以外最多40个质因子.
假设最多128个2,剩40个因数集中在i个数上,均分时乘积最大.
long double ans=0; int res;
rep(i,1,40){if(ans<pow(40/i,i)){ans=pow(40/i,i); res=i;}
}
cout<<ans*128<<" "<<res; 
//ans<3e8,则上限3e8个因子(实际上绰绰有余)
*/

A

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<ll,int>
const int N=1e5+5;
int n,w,q[N],l,r,f[N];
ll v[N],dp[N];  //v[]用来判断堆中的值是否仍合法
bool check(int k){l=1,r=0;priority_queue<P>Q;rep(i,1,n){if(l<=r && q[l]<i-k+1){v[q[l]]=0; l++;}if(l<=r){ //每次都要更新最左端的，因为i-k在变换!v[q[l]]=f[q[l]]+1+dp[max(i-k,0)]; Q.push({-v[q[l]],q[l]});}while(l<=r && f[i]>=f[q[r]]){v[q[r]]=0; r--;}if(l<=r){v[i]=dp[q[r]]+f[i]+1;q[++r]=i;}else{v[i]=dp[max(i-k,0)]+f[i]+1;q[++r]=i;}Q.push({-v[i],i});P tem;while(Q.size()){tem=Q.top();if(v[tem.second]!=-tem.first)Q.pop();else break;}dp[i]=-tem.first;}return dp[n]-1<=w;
}
int main(){IOScin>>n>>w;rep(i,1,n)cin>>f[i];int L=1,R=n,mid;while(L<=R){mid=(L+R)>>1;if(check(mid))R=mid-1;else L=mid+1;}cout<<L;
}