__vector__ 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-27 11:29:31
任意合法的 $n$ 必然满足：
$$
n^2+n+x = (n+k)^2,k\in \mathbb{Z}
$$
考虑枚举这个 $k$，粗略估算 $|k| \le 10^7 + 100$。
那么 $(n+k)^2-n^2-n=x$。
$n^2+2nk+k^2-n^2-n=x$。
$2nk-n = x-k^2$。
$(2k-1)n=x-k^2$。
$n = \frac{x-k^2}{2k-1}$。
然后本题就做完了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-12 11:42:57
本做法来源于一份 chemthan 在 Codeforces 上的提交，原作者的实现是 $O(n^4)$ 的，但是我发现可以将其优化到 $O(n^2)$ 从而爆标。
这份代码的思路是预处理每个子区间的左边最近的不相交的相等区间。
预处理过程，则枚举子区间的左端点 $x$，同时将所有右端点在 $x$ 左边的子区间加入字典树，对于每个字典树上的节点，记录其代表的区间在数组中最右边的出现位置。
然后，升序枚举当前子区间的右端点 $y$，通过字典树可以快速查询 $[x,y]$ 的左边最近的出现位置。
虽然字典树单词查询一个字符串的复杂度是 $O(|S|)$ 的，但是这里，前一个被查询的字符串是后一个被查询的字符串的前缀，所以后一个字符串从前一个字符串对应的末尾节点开始查找就可以了，所以复杂度等于最后一个字符串的长度。
完成预处理之后，采用 DP，令 $f_{l,r}$ 为最右边的区间是 $[l,r]$ 时的答案。
转移的话，上一个选择的区间肯定是自己左边最近的相等区间，这个已经预处理出来了。
本做法的预处理部分可以做到 $O(n^2)$，但是作者写成了 $O(n^4)$，所以我对作者的代码进行了修改。
DP 部分也可以做到 $O(n^2)$，所以总的时间复杂度是 $O(n^2)$ 的。
但是，空间复杂度仍然是 $O(n^3)$ 的，原因是最多 $O(n^2)$ 个节点，每种节点都有 $n$ 种可能的连边，所以字典树的 nxt 数组得开到 $n^2 \times n$。
但是注意到实际上只会使用 $O(n^2)$ 的空间。
所以，如果想要降低空间复杂度的话，可以考虑开 unordered_map 或者 map 等。
如果开 map 的话，就只有 $O(n^2)$ 的空间占用和 $O(n^2 \log n)$ 的时间复杂度，仍然优于官方 std。
\/\/ by chemthan
#include <bits\/stdc++.h>
using namespace std;
const int N = 305; \/\/ max number of words
const int SIG = N; \/\/ alphabet size (distinct words)
const int T = N * (N + 1) \/ 2 + 5; \/\/ upper bound of trie nodes per build
int n, m;
int id[N], lenw[N];
string w[N];
int f[N][N], dp[N][N]; \/\/ f[i][j]: previous start of block equal to [i..j]
int nxt[T][SIG], val[T], ptr; \/\/ trie
long long pref[N]; \/\/ prefix sum of word lengths
unordered_map<string, int> mp;
inline int get_id(const string &s) {
auto it = mp.find(s);
if (it != mp.end()) return it->second;
return mp[s] = ++m;
}
int rem[N];
inline void add(int l, int r) {
int u = 0;
for (int i = l; i <= r; ++i) {
if (!nxt[u][id[i]]) nxt[u][id[i]] = ++ptr;
u = nxt[u][id[i]];
val[u] = max(val[u], l);
}
rem[l]=u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
id[i] = get_id(w[i]);
lenw[i] = (int)w[i].size();
pref[i] = pref[i - 1] + lenw[i];
}
int total = (int)pref[n] + (n - 1); \/\/ original length with spaces
int ans = total;
\/\/ prepare f with -1
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) f[i][j] = -1;
}
\/\/ build f: for each split point i, trie of all segments ending at i-1
for (int i = 2; i <= n; ++i) {
for (int l = 1; l < i - 1; ++l){
int u=rem[l];
if(!nxt[u][id[i-1]])nxt[u][id[i-1]]=++ptr;
u=nxt[u][id[i-1]];
val[u]=max(val[u],l);
rem[l]=u;
}
add(i-1,i-1);
int u = 0;
for (int r = i; r <= n; ++r) {
int v = nxt[u][id[r]];
if (!v) break;
u = v;
f[i][r] = val[u]; \/\/ previous start pv of a block equal to [i..r]
}
}
\/\/ DP count of non-overlapping equal segments ending at [i..j]
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
int pv = f[i][j];
dp[i][j] = 1;
if (pv != -1) dp[i][j] = dp[pv][pv + (j - i)] + 1;
if (dp[i][j] > 1) {
\/\/ saving per occurrence: (sum len) + spaces - initials
\/\/ = (pref[j]-pref[i-1]) + (j-i) - (j-i+1) = (pref[j]-pref[i-1]) - 1
int save_one = (int)(pref[j] - pref[i - 1]) - 1;
ans = min(ans, total - save_one * dp[i][j]);
}
}
}
cout << ans << '\n';
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-12 16:40:31
考虑到对于已经选择的灯的集合，调整顺序使得能走的距离更远总是不劣的，可以反证法证明。
令 $f_{s}$ 表示已经使用了 $s$ 集合的灯，此时能走的最远距离。
转移的话，就枚举一个新的未使用的灯。
此时，新的灯的照亮的左边界必然就是 $f_s$，现在需要算出这盏灯照亮的右边界。
此时，已经知道了灯的位置 $(x_1,y_1)$，以及灯光覆盖的左边界 $(k_1,0)$，现在要求出灯光覆盖的右边界 $(k_2,0)$。
现在可以先求出 $(x_1,y_1)$ 指向 $(k_1,0)$ 的极角（极轴为 $x$ 轴正向），可以调用 C++ 函数 atan2(0-y,k-x1) 得到。
随后将这个角度加上 $\lpha$ 就能得到 $(x_1,y_1)$ 指向 $(k_2,0)$ 的极角，令其为 $\theta$。
此时考虑构造一个以 $(x_1,y_1)$ 为中心的单位圆，算出其与穿过 $(x_1,y_1)$ 和 $(k_2,0)$ 的直线的交点的横纵坐标相对于 $(x_1,y_1)$ 为 $(sin(\theta),cos(\theta))$ 。
那么可以得到穿过 $(x_1,y_1)$ 和 $(k_2,0)$ 的直线的斜率是 $\frac{\sin(\theta)}{\cos(\theta)} = \tan(\theta)$。
那么现在可以得到： $$ \tan(\theta)\cdot (k_2-x_1) = -y_1\ -\tan(\theta)x_1=-y_1 - \tan(\theta)\cdot k_2\ x_1 = \frac{y_1}{\tan(\theta)} + k_2\\ k_2 = x_1-\frac{y_1}{\tan(\theta)} $$ 上述式子成功求出了灯光覆盖的右边界，需要注意若 $\theta \ge 0$，那么右边会延伸到无穷远，因为此时灯光覆盖区域大概长这个样子：
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
typedef long double ld;
const ld pi=acos(ld(-1));
ld turn(ld jiaodu){
return jiaodu*(pi\/ld(180));
}
ld calc(pair<ld,ld> nd,ld deg,ld fir){
ld xcha=nd.fi-fir;
ld ycha=nd.se;
ld len=hypot(xcha,ycha);
xcha\/=len,ycha\/=len;
ld curdeg=atan2(-ycha,-xcha);
curdeg+=turn(deg);
ld dx=cos(curdeg),dy=sin(curdeg);
\/\/ printf("dx %.10Lf dy %.10Lf\n",dx,dy);
if(abs(dy)<1e-10){
if(dx>0)return 1e300;
return fir;
}
if(dy>0){
return 1e300;
}
return max(nd.fi+dx*(nd.se\/(-dy)),fir);
}
const int maxn=25;
int n;
ld l,r;
pair<ld,ld> nd[maxn];
ld a[maxn];
ld f[1<<21];
void solve(int id_of_test){
scanf("%d%Lf%Lf",&n,&l,&r);
FOR(i,1,n){
scanf("%Lf%Lf%Lf",&nd[i].fi,&nd[i].se,&a[i]);
}
int all=(1<<n)-1;
FOR(msk,0,all){
f[msk]=-1e18;
}
\/\/ printf("calc = %.10Lf\n",calc(nd[1],a[1],0.00001));
f[0]=l;
FOR(msk,0,all){
if(f[msk]<-1e10)continue;
FOR(i,1,n){
if(!(msk&(1<<(i-1)))){
ckmx(f[msk|(1<<(i-1))],calc(nd[i],a[i],f[msk]));
}
}
\/\/ printf("f[%d] = %.10Lf\n",msk,f[msk]);
}
printf("%.9Lf\n",min(f[all],r)-l);
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 14:18:14
给定一个 $n \times m$ 的矩形，包含 $nm$ 个方格，给定一个正整数 $k$。
有一部分格子包含目标。
现在需要选择一个位置 $(x,y)$，以及一个方向（可选范围：右下，右上，左上，左下）。选中之后，选中方向内所有与 $(x,y)$ 曼哈顿距离不超过 $k$ 的格子内的目标均被击中。
提示：$k=3$ 可能击中的区域的形态如下：
$n\times m \le 10^5,k \le 10^5$。
首先 $4$ 种方向如果分类讨论难度会上天。
此时注意到，任意一种合法的操作，均可以通过旋转矩形，对应到另一个方向的某个合法操作。
同时旋转矩形后执行的任意合法操作，总是等价于旋转前的某一个合法操作。
所以，可以仅保留一种选择方向，对矩形的 $4$ 种旋转方式分别计算答案取最大值就可以了。
此处选择什么方向无所谓，我在此以右上方向（即第一张图片）为例。
由于选择区域的形状比较特别，目标总数量难以直接通过前缀和等方式快速得到，所以考虑递推。
令 $w(i,j)$ 表示以 $(i,j)$ 为左下角的区域的目标总数。
考虑其和 $w(i-1,j)$ 的关系。
对于 $k=3$ 大概是下面的样子：
红色加号代表新增区域，蓝色减号代表减少的区域。
可以发现增加的红色区域是第 $i$ 行的 $j \sim j+k$ 列。
减少的蓝色区域是 $(i-1,j+k)$ 为结尾，$(i-k-1,1)$ 为开始的对角线。
那么对每一行预处理从左到右的前缀和，以及预处理左上到右下的对角线前缀和，就可以 $O(1)$ 从 $w(i-1,j)$ 转化到 $w(i,j)$ 了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 14:23:23
考虑分别计算每一位产生的贡献，加起来得到总和。
假设当前是从左边数第 $x$ 位，那么分类讨论两种情况。
$i \le n-x-1$。
当前作为 $10^i$ 被计入答案的次数为 $\binom{n-1-i-1}{k-1} = \binom{n-i-2}{k-1}$。
即，剩余可以放加号的空位的数量是 $n-1-i-1$，然后由于右边固定了一个加号做结尾，所以只需要再放 $k-1$ 个加号。
$i = n-x$。
当前作为 $10^i$ 被记入答案的次数为 $\binom{x-1}{k}$。
即，位置 $1$ 到 $x$ 有 $x-1$ 个空位，填 $k$ 个加号，且当前数字段一直到结尾。
考虑预处理 $p_i = \sum\limits_{j=1}^i \binom{n-j-2}{k-1}10^j$。
然后枚举每一位就能 $O(1)$ 算出贡献了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 15:24:36
现在处理左端点最小的角色，与之配对的演员需要符合以下两个要求：
在满足条件 1 的前提下，事实上演员的左端点是什么已经无所谓了，因为如果一个演员的左端点小于等于当前角色的左端点，那么说明该演员的左端点也同时小于等于其他所有角色的右端点，那么就说明所有满足条件一的演员的左端点事实上互相没有优劣之分。
既然对于满足条件一的演员集合，左端点是什么不重要，那么就关心右端点了。
此时，必定选择右端点大于等于当前角色的演员里面，右端点最小的那个（当然记得满足条件一）。
考虑怎么写程序，可以用 set 实现，不过有更简单的办法，就是将演员和角色一起按左端点升序排列，如果左端点一致就把演员放在前面。
然后，每个角色左边的所有演员就是所有左端点小于等于其的演员。
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
const int maxn=1e5+5;
int n,m;
struct INFO{
bool type;
int l,r,k;
int id;
}info[maxn*2];
void solve(int id_of_test){
read(n);
FOR(i,1,n){
info[i].type=0;
read(info[i].l);
read(info[i].r);
info[i].id=i;
}
read(m);
FOR(i,1,m){
info[i+n].type=1;
read(info[i+n].l);
read(info[i+n].r);
read(info[i+n].k);
info[i+n].id=i;
}
sort(info+1,info+n+m+1,[&](INFO& a,INFO& b){
if(a.l!=b.l)return a.l<b.l;
if(a.r!=b.r)a.r>b.r;
return a.type>b.type;
});
vi ans(n+1,0);
set<pii> rem;
FOR(i,1,n+m){
if(info[i].type==1){
rem.insert(mkpr(info[i].r,i))；
}else{
auto ptr=rem.lower_bound(mkpr(info[i].r,-1));
if(ptr==rem.end()){
puts("NO");
return;
}
int pos=ptr->se;
ans[info[i].id]=info[pos].id;
info[pos].k--;
if(!info[pos].k){
rem.erase(ptr);
}
}
}
puts("YES");
FOR(i,1,n)printf("%d ",ans[i]);
pln
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 15:49:00
给定了一棵 $n$ 个点的树，每条边都有一个 $1 \sim 10^6$ 之间的整数边权。
有 $m$ 个条件，每个形式如下：
要求构造一组合法的边权满足所有条件。
$n,m \le 5000$。
对于上述条件，首先满足 $a$ 到 $b$ 的路径上不能出现小于 $c$ 的边权。
在此基础上，每个边权应当尽可能小。
所以，为每条边赋一个初始边权 $1$，然后对于每对 $(a,b,c)$（含义见上述描述），将 $a$ 到 $b$ 路径上所有边权对 $c$ 取 max。
如果这个边权方案不符合要求，那么肯定不存在合法方案了。
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define mkpr make_pair
const int maxn=5005;
int n;
vector<pii> g[maxn];
int val[maxn];
int dep[maxn];
int fa[maxn];
int faid[maxn];
void dfs(int u,int _fa){
fa[u]=_fa;
dep[u]=dep[_fa]+1;
for(auto [v,id]:g[u]){
if(v==_fa)continue;
faid[v]=id;
dfs(v,u);
}
}
vector<pair<int,int> > rem[maxn];
tuple<int,int,int> ops[maxn];
void solve(int id_of_test){
read(n);
FOR(i,1,n)val[i]=1;
FOR(i,1,n-1){
int x,y;
read(x);
read(y);
g[x].eb(mkpr(y,i));
g[y].eb(mkpr(x,i));
}
dfs(1,0);
int m;
read(m);
FOR(i,1,m){
int a,b,v;
read(a);
read(b);
read(v);
ops[i]=tie(a,b,v);
vi path;
while(a!=b){
if(dep[a]<dep[b])swap(a,b);
path.eb(faid[a]);
a=fa[a];
}
for(int& eid:path)ckmx(val[eid],v);
}
FOR(i,1,m){
int a,b,v;
tie(a,b,v)=ops[i];
vi path;
while(a!=b){
if(dep[a]<dep[b])swap(a,b);
path.eb(faid[a]);
a=fa[a];
}
bool yes=0;
for(int& eid:path){
\/\/ printf("i = %d meet = %d\n",i,val[v]);
if(val[eid]<v){
yes=0;
break;
}else if(val[eid]==v){
yes=1;
}
}
if(!yes){
puts("-1");
return;
}
}
FOR(i,1,n-1){
printf("%d ",val[i]);
}
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:10:35
定义 $dis(i,j)$ 表示从 $i$ 走到 $j$ 的最少边数。
假设 $a \sim b$ 与 $b \sim c$ 的路径没有重合的话，那么只需要 $p$ 中最小的 $dis(a,b)+dis(b,c)$ 个数值，将它们赋到 $a \sim b$ 和 $b \sim c$ 的路径上就可以了。
但是现在的问题就在于路径重合的问题，如果还按照刚才的算法会把答案算大，甚至找到不存在的路径（即 $dis(a,b)+dis(b,c) \gt m$ 的清空）。
考虑枚举重合信息。
枚举 $md$ 作为 $b$ 到 $c$ 的路径上最后一个与 $a \sim b$ 路径重合的节点。
那么，此时路径将分为三个部分：
此时按照最优方式，上述三段路径都按照最短路计算就可以了，即路径长度分别为 $dis(a,md),dis(md,b),dis(md,c)$。
然后，优先把 $p$ 中较小的数值分配给第二部分的路径，然后再分配一，三部分的路径就行了。
尽管有可能因此不再满足路径重合的一些条件，但是这仍然是对的，由于以下两点：
对于最短路的计算，bfs 预处理 $a,c$ 到其他所有点的最小边数就可以了。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
const int maxn=2e5+5;
int n,m,a,b,c;
ll p[maxn],pre[maxn];
ll w(int l,int r){
return pre[r]-pre[l-1];
}
vi g[maxn];
int disa[maxn],disb[maxn],disc[maxn];
void bfs(int s,int* dis){
FOR(i,1,n)dis[i]=1e9;
queue<int> q;
q.push(s);
dis[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int& v:g[u]){
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
}
void clear(){
FOR(i,1,n){
g[i].clear();
}
}
void solve(int id_of_test){
read(n);
read(m);
read(a);
read(b);
read(c);
FOR(i,1,m){
read(p[i]);
}
sort(p+1,p+m+1);
FOR(i,1,m){
pre[i]=pre[i-1]+p[i];
}
FOR(i,1,m){
int u,v;
read(u);
read(v);
g[u].eb(v);
g[v].eb(u);
}
bfs(a,disa);
bfs(b,disb);
bfs(c,disc);
ll ans=1e18;
FOR(mid,1,n){
\/\/ a-->b
\/\/ b-->c
\/\/ 上述路径共同都要到达 mid
int len=disb[mid];
if(len+disa[mid]+disc[mid]>m)continue;
ll res=pre[len]*2;
res+=w(len+1,len+disa[mid]+disc[mid]);
\/\/ printf("mid = %d res = %lld\n",mid,res);
ckmn(ans,res);
}
printf("%lld\n",ans);
clear();
}
int main()
{
int T;
read(T);
FOR(_,1,T){
solve(_);
}
return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:32:19
假设答案的左端点是 $x$，那么右端点 $y$ 怎么求？
明显的，在左端点小于等于 $x$ 的区间里面选择 $k$ 个右端点最大的，其中右端点第 $k$ 大的区间的右端点就是 $y$。
即使这 $k$ 个区间没有一个左端点等于 $x$ 的也无所谓，这样只会让答案变大，但是按照这个方法枚举一遍所有可能的 $x$，最优解是一定会枚举到的。
为了快速实现这个程序，可以将升序枚举答案的左端点 $x$，每枚举一个新的 $x$ 就将左端点为 $x$ 的区间加入候选集合，然后候选集合删掉右端点最小的，直到大小不超过 $k$，可以用 set 维护这个集合。
$x$ 的数量也只有不超过 $n$ 个，因为任意一个合法的 $x$ 必然是某个区间的左端点。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
const int maxn=3e5+5;
int n,k;
struct PII{
int fi,se,id;
}seq[maxn];
void solve(int id_of_test){
read(n);
read(k);
FOR(i,1,n){
read(seq[i].fi);
read(seq[i].se);
seq[i].id=i;
}
sort(seq+1,seq+n+1,[&](PII& a,PII& b){
if(a.fi!=b.fi)return a.fi<b.fi;
return a.se<b.se;
});
multiset<pii> s;
int ans=0,ansid;
FOR(i,1,n){
if(s.size()>=k){
s.erase(s.begin());
}
s.insert(mkpr(seq[i].se,seq[i].id));
if(s.size()==k){
int j=s.begin()->fi;
if(j-seq[i].fi+1>ans){
ans=j-seq[i].fi+1;
ansid=i;
}
}
}
if(!ans){
printf("%d\n",ans);
FOR(i,1,k)printf("%d ",i);
pln
return;
}
s.clear();
FOR(i,1,n){
s.insert(mkpr(seq[i].se,seq[i].id));
if(s.size()>k)s.erase(s.begin());
if(i==ansid){
printf("%d\n",ans);
for(auto v:s)printf("%d ",v.se);
pln
return;
}
}
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 20:00:09
实际上已知最终的顺序。
考虑按照最终的顺序逐个扫描。
合法的前提是相邻后一项的最大成绩小于等于（能否等于得看 id）前一项的最大成绩。
$f_{i,j}$ 表示已经确定了前 $i$ 个选手的方案，总共隐藏 $j$ 题，此时最后一个人的最大的公开成绩。
可以粗略的估计，所有选手隐藏题目个数的总和不超过 $M$。
假设隐藏了 $M+1$ 个题目。
首先，初始情况下最高分减去最低分最多为 $M \cdot K$。
若隐藏了 $M+1$ 个问题，那么意味着中间的差值减少了 $(M+1)\cdot K$，无论如何都不能保证原来的顺序。
现在需要知道每个选手有哪些方案。
$g_{i,j,k}$：当前选手考虑了前 $i$ 道题，公开了 $j$ 个，此时公开总和为 $k$ 是否可行。
转移：逐个扫描题目：
其中 $v_i$ 表示当前选手对于第 $i$ 题的分数。
暴力转移复杂度将会是 $O(m^3k)$ 的。
加上 bitset 优化后变为 $O(\frac{m^3k}{\omega})$ 。
对于 $f$ 本身的转移，需要枚举下一个人的公开成绩，以及公开题目个数。
那么 $f$ 的求解总复杂度将会是 $O(nm^3k)$。
总复杂度 $O(nm^3k+\frac{m^3k}{\omega}) = O(nm^3k)$，期望 72pts，irris 说开 O3 优化能过。
考虑哪些状态有效。
重定义状态 $g_{i,j,s}$ 表示当前选手考虑了前 $i$ 道题，公开了 $j$ 个，真实总和减去隐藏总和的值为 $s$ 是否可行。
令 $id$ 表示当前选手编号，注意到 $s \ge score_{id+1}$。
也就是说，$s \in [score_{id+1},score_{id}]$。
仅保留有效的 $s$，那么注意到所有选手的 $g$ 的有效状态数加起来仅有 $O(m^2\sum\limits_{i=1}^n(score_i-score_{i+1})) = O(m^3k)$，其中 $score_{n+1}$ 视为 $0$。
再分析一下 $f$ 此时的转移复杂度。
每一层分别加和，得到 $\sum\limits_{i=1}^n (score_i-score_{i+1})m^2 = O(m^3k)$。
再算上一开始的排序，总复杂度将是 $O(n\log n + m^3k)$。
鲁ICP备2025150228号