T1
现在你站在坐标轴的一个整点上，给你 \(n\) 种技能，每个技能是整数对 \((p,c)\) 的形式， 学会它需要花费 \(c\)，但是学会了可以无限用。用的意思是可以向左或向右 \(p\) 个单位长度。求最小的学技能开销，使得你可以访问到坐标轴的所有整点。
\(n\leq 10^5, x\leq 10^9\)
随便玩了一下，感觉需要所有学会的 \(p\) 的 \(\gcd\) 是 1 才行，不然只能一个一个 \(\gcd\) 地跳。也就是说我得选一些技能让他们互质，然后最小化开销。
有一个 DP 的想法是把值开进状态里去转移。
\[f_{i,\gcd(p_i,j)}=f_{i-1,j}+c_i \]感觉这玩意值不是很多的样子，起码超不过所有的因数和，\(n\) 这么小，用 unordered_map 直接冲了。过了。
吐槽一下 imposib1e，虽然提醒了但是什么玩意。
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n;
pair<int,int> a[MAXN];
unordered_map<int,int> f[1005];
signed main(){
n=RIN;
foru(i,1,n){
a[i].fi=RIN;
// a[i].fi=73513440;
}
foru(i,1,n){
a[i].se=RIN;
}
// sort(a+1,a+1+n,[&](pair<int,int> p,pair<int,int> q){
// return p.se<q.se;
// });
int ans=INT_MAX;
// foru(i,1,n){
// foru(j,i+1,n){
// // if(__gcd(a[i].fi,a[j].fi)==1){
// // ans=min(ans,a[i].se+a[j].se);
// // }
// if(a[i].se+a[j].se==3327){
// cout<<a[i].fi<<' '<<a[i].se<<endl;
// cout<<a[j].fi<<' '<<a[j].se<<endl;
// }
// }
// }
// foru(i,1,n){
// for(int i=1;i*i<=a[i])
// }
f[0][0]=0;
foru(i,1,n){
for(auto [x,y]:f[i-1]){
int g=x;
if(f[i].find(g)==f[i].end()) f[i][g]=INT_MAX;
f[i][g]=min(f[i][g],f[i-1][x]);
g=__gcd(a[i].fi,x);
if(f[i].find(g)==f[i].end()) f[i][g]=INT_MAX;
f[i][g]=min(f[i][g],f[i-1][x]+a[i].se);
}
}
if(f[n].find(1)==f[n].end()){
ans=INT_MAX;
}else{
ans=f[n][1];
}
if(ans==INT_MAX){
cout<<"imposib1e";
}else{
cout<<ans;
}
return 0;
}
T2
笨比的一题
从 \(1\) 到 \(n\)，从 \(i\) 到 \(i+1\) 要花费 \(nxt_i\)，在一个地方停留可以获得权值 \(V\)，权值会衰减，是个随停留时间的一次函数，但斜率可以为 \(0\)。现在你一共有 \(m\) 的时间，问最大权值。
\(n\leq 100, m\leq 2\times 10^4, V\leq 1000\)
被 T1 做昏了，上来就 DP 了。
\[f_{i,j}=f_{i-1,k}+val(i-1,j-nxt_{i-1}-k) \]定义 \(f_{i,j}\) 为在第 \(j\) 秒末抵达 \(i\) 时的最大权值。
\(val(i,time)\) 是一个计算在 \(i\) 停留 \(time\) 秒获得的权值的函数，大概就是判一下上限再减一下等差数列。（埋下伏笔了）
直接暴力转移，当 \(b_i=0\) 时最坏，复杂度是 \(nm^2\)，非常完蛋。但是赛时好像有小登设计了神秘 DP，定义变了之后改变一下顺序就可以优化掉最坏情况变成 \(nmV\)，不过 \(2\times 10^9\) 能过依然出乎我意料了，太牛，暂且不谈。
赛时观察了一下，试了很多神秘优化，后来感觉这个转移有决策单调性。也就是说随着 \(f_{i,j}\) 的 \(j\) 的增加，最优的 \(k\) 也增加。但我并不知道怎么证，只是感觉增函数加减函数的形式，同时减函数向右平移，于是打了个表发现有点牛，写了一下发现有点太牛，写了个拍，过了拍就交了。
但是挂了 30 分，怎么回事呢，原来是我的 \(val\) 函数堂堂挂掉了，我的拍也是用的这个函数。我万万没想到我的等差数列求和挂掉了。去掉一个取模就过了。（不过他是怎么过 70 分的）
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 10005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,m;
int nxt[MAXN];
LL a[MAXN];
LL b[MAXN];
LL f[105][20005];
LL get(int i,LL t){
if(b[i]==0) return a[i]*t;
// LL A=a[i],B=b[i];
// LL ret=0;
// foru(i,1,t){
// ret+=A;
// A-=B;
// A=max(A,0ll);
// }
// return ret;
// if(t<0) return 0;
LL x=a[i]/b[i];
if(t<=x+1){
return a[i]*t-((t-1)*t*b[i])/2;
}else{
return a[i]*(x+1)-((x+1)*x*b[i])/2;
}
}
void work(int i,int l,int r,int nl,int nr){
int mid=(l+r)>>1;
int pos=-1;
for(LL k=max(nl,0);k<=min(mid-nxt[i-1],nr);k++){
if(f[i-1][k]==LLONG_MIN) continue;
LL t=mid-k-nxt[i-1];
// if(t*b[i-1]>a[i-1]) break;
// LL x=a[i-1]/b[i-1];
// LL val=a[i-1]*t-((t-1)*t*b[i-1])/2;
LL val=get(i-1,t);
if(f[i-1][k]+val>=f[i][mid]){
f[i][mid]=f[i-1][k]+val;
pos=k;
}
}
if(l==r) return ;
if(l<=mid-1) work(i,l,mid-1,nl,pos);
if(mid+1<=r) work(i,mid+1,r,pos,nr);
}
signed main(){
n=RIN,m=RIN;
foru(i,1,n-1){
nxt[i]=RIN;
}
foru(i,1,n){
a[i]=RIN;
}
foru(i,1,n){
b[i]=RIN;
}
foru(i,1,n){
foru(j,0,m){
f[i][j]=LLONG_MIN;
}
}
f[1][0]=0;
// foru(i,1,n-1){
// foru(j,0,m-nxt[i]){
// if(f[i][j]==LLONG_MAX) continue;
// int L=j+nxt[i];
// int R;
// if(b[i]==0) R=m;
// else if(a[i]%b[i]==0){
// R=min(m,j+nxt[i]+a[i]/b[i]+1);
// foru(k,L,m){
// f[i+1][k]=max(f[i+1][k],f[i][j]+get(i,k-nxt[i]-j));
// }
// }else{
//
// }
// }
// }
if(n<=100 && m<=500){
foru(i,2,n){
foru(j,0,m){
// int pos=-1;
for(LL k=0;k<=j-nxt[i-1];k++){
if(f[i-1][k]==LLONG_MIN) continue;
LL t=j-k-nxt[i-1];
// if(t*b[i-1]>a[i-1]) break;
// LL x=a[i-1]/b[i-1];
// LL val=a[i-1]*t-((t-1)*t*b[i-1])/2;
LL val=get(i-1,t);
if(f[i-1][k]+val>=f[i][j]){
f[i][j]=f[i-1][k]+val;
}
// f[i][j]=max(f[i][j],);
}
}
}
// foru(i,2,n){
// foru(j,0,m){
// int pos=-1;
// for(LL k=0;k<=j-nxt[i-1];k++){
// if(f[i-1][k]==LLONG_MIN) continue;
// LL t=j-k-nxt[i-1];
// // if(t*b[i-1]>a[i-1]) break;
// // LL x=a[i-1]/b[i-1];
// // LL val=a[i-1]*t-((t-1)*t*b[i-1])/2;
// LL val=get(i-1,t);
// if(f[i-1][k]+val>=f[i][j]){
// f[i][j]=f[i-1][k]+val;
// }
// // f[i][j]=max(f[i][j],);
// }
// }
// }
}else{
foru(i,2,n){
work(i,0,m,0,m);
// foru(j,0,m){
// int pos=-1;
// for(LL k=0;k<=m;k++){
// if(f[i-1][k]==LLONG_MIN) continue;
// LL t=j-k-nxt[i-1];
// // if(t*b[i-1]>a[i-1]) break;
// // LL x=a[i-1]/b[i-1];
// // LL val=a[i-1]*t-((t-1)*t*b[i-1])/2;
// LL val=get(i-1,t);
// if(f[i-1][k]+val>=f[i][j]){
// f[i][j]=f[i-1][k]+val;
// }
// // f[i][j]=max(f[i][j],);
// }
// }
}
}
LL ans=0;
foru(i,1,n){
foru(j,0,m){
if(f[i][j]==LLONG_MIN) continue;
LL t=m-j;
LL val=get(i,t);
// LL val=a[i-1]*t-((t-1)*t*b[i-1])/2;
ans=max(ans,f[i][j]+val);
}
}
// cout<<get(5,2)<<endl;
// cout<<f[5][8]<<endl;
cout<<ans;
return 0;
}
赛后发现有高妙贪心，题解也不是 DP，才意识到我是笨比。
直接枚举 \(n\) 表示最后停在哪，然后把前缀的都扔进堆里，贪心取，取完时间为止，复杂度就已经是 \(nm\log n\)的了，决策单调性小丑完了。
交上去发现竟然过不了，一想发现确实有点常熟的，特判一下堆顶的 \(b_{top}=0\)，再改成取出堆顶后不只操作一次，而是操作直至它放回时不再是堆顶或者时间耗尽，过了，绷不住了。
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 10005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,m;
LL nxt[MAXN];
LL a[MAXN];
LL b[MAXN];
priority_queue<pair<LL,int>> q;
signed main(){
n=RIN,m=RIN;
foru(i,1,n-1){
nxt[i]=RIN;
}
foru(i,1,n){
a[i]=RIN;
}
foru(i,1,n){
b[i]=RIN;
}
LL ans=0;
foru(i,1,n){
while(!q.empty()) q.pop();
LL tm=m;
foru(j,1,i-1){
tm-=nxt[j];
}
foru(j,1,i){
q.push({a[j],j});
}
LL sum=0;
while(tm--){
auto [val,pos]=q.top();
// if(b[pos]==0){
// sum+=val;
// continue;
// }
q.pop();
if(val==0) break;
// cout<<val<<' '<<pos<<endl;
q.push({max(0ll,val-b[pos]),pos});
sum+=val;
}
ans=max(ans,sum);
}
cout<<ans;
return 0;
}
这启示我们不要被 DP 蒙蔽了双眼，同时一定要记准等差数列求和的公式（）
T3
原 神启动了。但是部分分给的足的离谱，比原题高好多。
\(m\leq 16\) 的包一眼丁真，先开写了。枚举完之后开始判，用 \(set\) 维护连续段，只要实现 \(del(pos)\) 和 \(timepass(t)\) 两个函数就行。很遗憾这个包赛时彻底挂掉了，让我们来欣赏一下。
赛时代码：
for(int S=0;S<(1<<m)-1;S++){
ls.clear();
LL sum=0;
foru(i,1,n){
if(S&(1<<(i-1))){
ls.push_back(a[i]);
sum+=a[i].c;
}
}
if(check(ls)){
ans=min(ans,sum);
}
}
正确代码：
for(int S=0;S<(1<<m);S++){
ls.clear();
LL sum=0;
foru(i,1,m){
if(S&(1<<(i-1))){
ls.push_back(a[i]);
sum+=a[i].c;
}
}
if(check(ls)){
ans=min(ans,sum);
}
}
把枚举上限搞错了，循环的 \(m\) 习惯性写成 \(n\) 了，\(n\) 可是 \(10^9\) 级别，直接爆爆爆了。
然后是第二个包。\(t_i=1\)，意味着我们其实是要选一些区间，并起来是 \(1 \cdots n\)，最小化代价。直接上 DP，然后线段树优化转移。还好这个包没挂，不然烂完了。
赛时期望的60分代码：
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,m;
class Work{
public:
int t,l,r;
LL c;
}a[MAXN];
vector<Work> ls;
set<pair<int,int>> st;
void del(int l,int r){
// cout<<"del "<<l<<' '<<r<<endl;
auto it=st.lower_bound({l,0});
if(it->fi>l){
if(prev(it)->se>=l){
auto res=*prev(it);
st.erase(prev(it));
st.insert({res.fi,l-1}).fi;
if(res.se>r){
it=st.insert({r+1,res.se}).fi;
}
}
}
while(1){
if(it->fi>r) break;
if(it->se<=r){
it=st.erase(it);
}else{
auto res=*it;
res.fi=r+1;
st.erase(it);
st.insert(res);
break;
}
}
}
void timepass(int x){
// cout<<"time passed "<<x<<endl;
if(st.size()==2) return ;
auto ed=prev(st.end());
for(auto it=next(st.begin());next(it)!=ed;){
auto lf=*it;
auto rf=*next(it);
st.erase(next(it));
st.erase(it);
if(rf.fi-lf.se-1<=2*x){
it=st.insert({lf.fi,rf.se}).fi;
}else{
lf.se+=x;
rf.fi-=x;
st.insert(lf);
it=st.insert(rf).fi;
}
}
//spe for 1 and n
pair<int,int> res(0,0);
auto it=next(st.begin());
if(it->fi>1){
res=*it;
st.erase(it);
res.fi=max(1,res.fi-x);
st.insert(res);
}
it=prev(ed);
if(it->se<n){
res=*it;
st.erase(it);
res.se=min(n,res.se+x);
st.insert(res);
}
}
void out(){
printf("--set--\n");
for(auto [x,y]:st){
printf("[%d,%d]\n",x,y);
}
printf("-------\n");
}
bool check(vector<Work>& ls){
sort(All(ls),[&](Work p,Work q){
return p.t<q.t;
});
st.clear();
st.insert({0,0});
st.insert({1,n});
st.insert({n+1,n+1});
// out();
for(int i=0;i<ls.size();){
if(i!=0){
//work for time
int x=ls[i].t-ls[i-1].t;
timepass(x);
// out();
}
int j=i;
while(j+1<ls.size() && ls[j+1].t==ls[i].t) j++;
foru(k,i,j){
del(ls[k].l,ls[k].r);
}
// out();
i=j+1;
}
return st.size()==2;
}
vector<int> X,Y;
unordered_map<int,int> id;
vector<Work> rs[MAXN];
LL f[MAXN];
LL suf[MAXN];
class SegTree{
public:
int l,r;
LL Min;
}tr[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
void push_up(int p){
// cout<<tr[p].Min<<' '<<tr[lc(p)].Min<<' '<<tr[rc(p)].Min<<endl;
tr[p].Min=min(tr[lc(p)].Min,tr[rc(p)].Min);
// cout<<tr[p].Min<<' '<<tr[lc(p)].Min<<' '<<tr[rc(p)].Min<<endl;
}
void Build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
if(l==r){
tr[p].Min=f[l];
return ;
}
int mid=(l+r)>>1;
Build(lc(p),l,mid);
Build(rc(p),mid+1,r);
push_up(p);
}
void Modify(int p,int pos,LL k){
// cout<<p<<' '<<k<<endl;
if(tr[p].l==tr[p].r){
tr[p].Min=k;
// cout<<tr[p].Min<<endl;
return ;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(pos<=mid) Modify(lc(p),pos,k);
else Modify(rc(p),pos,k);
push_up(p);
}
LL Query(int p,int l,int r){
if(l<=tr[p].l && tr[p].r<=r){
// cout<<tr[p].Min<<endl;
return tr[p].Min;
}
int mid=(tr[p].l+tr[p].r)>>1;
LL ret=1e15;
if(l<=mid) ret=min(ret,Query(lc(p),l,r));
if(r>mid) ret=min(ret,Query(rc(p),l,r));
return ret;
}
signed main(){
n=RIN,m=RIN;
foru(i,1,m){
a[i]={RIN,RIN,RIN,RIN};
}
if(m<=16){
LL ans=LLONG_MAX;
// ls.clear();
// LL sum=0;
// foru(i,1,5){
// if(i%2==0) continue;
// ls.push_back(a[i]);
// sum+=a[i].c;
// }
// if(check(ls)){
// ans=min(ans,sum);
// }
for(int S=0;S<(1<<m);S++){
ls.clear();
LL sum=0;
foru(i,1,m){
if(S&(1<<(i-1))){
ls.push_back(a[i]);
sum+=a[i].c;
}
}
if(check(ls)){
ans=min(ans,sum);
}
}
if(ans==LLONG_MAX){
cout<<(-1);
}else{
cout<<ans;
}
return 0;
}
bool A=1;
foru(i,1,m){
if(a[i].t!=1){
A=0;
}
}
if(A){
X.push_back(0);
foru(i,1,m){
X.push_back(a[i].l);
X.push_back(a[i].r);
}
sort(All(X));
X.erase(unique(All(X)),X.end());
int N=X.size()-1;
foru(i,0,N){
id[X[i]]=i;
}
foru(i,1,m){
rs[id[a[i].r]].push_back(a[i]);
}
f[0]=0;
// suf[0]=0;
foru(i,1,N){
// suf[i]=1e15;
f[i]=1e15;
}
Build(1,0,N);
foru(i,1,N){
for(auto &[t,l,r,c]:rs[i]){
int L=0;
if(id.find(l-1)==id.end()) L=id[l];
else L=id[l-1];
// cout<<"Try "<<i<<' '<<l<<' '<<r<<' '<<L<<endl;
// f[i]=min(f[i],suf[L]+c);
// LL ret=Query(1,L,i-1);
// cout<<"Query "<<L<<' '<<i-1<<' '<<ret<<endl;
// cout<<"Query "<<L<<' '<<i-1<<endl;
// f[i]=min(f[i],ret);
f[i]=min(f[i],Query(1,L,i-1)+c);
}
// foru(j,0,i){
// suf[j]=min(suf[j],f[i]);
// }
// cout<<"Modify f "<<i<<' '<<f[i]<<endl;
Modify(1,i,f[i]);
// cout<<X[i]<<' '<<f[i]<<endl;
}
if(id.find(n)==id.end() || f[id[n]]==1e15){
cout<<(-1);
}else{
cout<<f[id[n]];
}
return 0;
}
cout<<"-1";
return 0;
}
\(m^2\) 的包赛时没想出来，其实和正解差不多了，是留给暴力建图的包，直接考虑正解。
我们考虑把一个治疗方案放到 时间-村民 坐标系内考虑，横轴是时间。发现治疗方案是一个向右突出的等腰直角三角形，这个很好理解。当然，\(l=1\) 或 \(r=n\) 的方案会是一个向左上方的三角形，不过不是很影响。
如果把这些方案都画出来，就可以意识到一个完全治愈的情形其实是纵向被我们选择的方案 “封锁” 了。也就是治愈的范围从 \(1 \cdots n\) 连成了一条带，而这条带其实是由三角形们接起来的。我们先来刻画一下什么情况下两个三角形拼起来 “没有缝”。
自然地，首先将它们按时间排好序。在这之后，在他们之间连边。\(i\) 向 \(j\) 连一条单向边仅当：
\(i\geq j\) 时，需要满足 \(r_i-l_j+1\geq t_j-t_i\)
\(i< j\) 时，需要满足 \(r_i-l_j+1\geq t_i-t_j\)
满足这些条件并不一定没有缝，事实上只要 \(i\) 总体上是在 \(j\) 上方一个区域内就符合要求。但我们是要从 \(1\) 一直连到 \(n\)，是一个单向的过程，同时注意到我们的式子中 \(i\) 和 \(j\) 并不对称，因此即使出现非法边也是不优的。
然后我们容易想到把每个三角形看做一个点，点权是 \(c_i\)，于是我们要做的事情变成了从所有 \(l=1\) 的三角形开始跑点权最短路，最后答案就是 \(\min_{r_i=n}dis_i\)。
暴力连边需要 \(m^2\) 时间 & 空间，包爆的，寄，我们考虑一些性质。
点权最短路有一个性质是，跑 dijkstra 的时候，一个点只会被松弛一次。换句话说，一个点从 \(inf\) 变了之后就固定了，这就是它的最短路。这在边权最短路上显然是错误的，不过点权最短路却成立。证明的话可以想象，对于一个目前 \(dis_u=inf\) 的点 \(u\)，有一个入边来更新了它，既然入边能来更新，那它的那个对应前驱一定是当前的全局最短路，又因为没有边权，所以 \(dis_u\) 的更新就非常对。同时也可以想到在这之后 \(u\) 的其他前驱更新它一定是不优的。本质上是因为，在点权最短路中，\(u\) 的 \(\Delta dis\) 对于所有前驱来说都是 \(c_u\)；而如果是边权最短路，\(u\) 的 \(\Delta dis\) 对于前驱 \(v\) 来说就是 \(w(v,u)\)，这是因边而异的。
因此，我们可以让一个点在更新 \(dis\) 之后严格入队一次，具体实现是在它被确定最短路之后就把他从图里扬了。因为一个点只会被访问一次，于是现在我们的复杂度和边数无关了，所以不是 \(O(m^2\log m)\) 了？并不是，我们虽然能较快地求最短路，但是我们找边——也就是建图的时间依然居高不下。具体卡法可以考虑构造一长条没缝的三角形，这个情况只有 \(m\) 个边，但我们每次都不得不遍历所有三角形来找边。同时，删除一个点意味着要修改它的所有前驱，在一般的存图方式里这同样是不可接受的。
有没有什么办法不访问到无效的建边尝试呢？
我们来变形一下刚才的式子。\(i\) 向 \(j\) 连一条单向边仅当：
\(i\geq j\) 时，需要满足 \(r_i+t_i+1\geq t_j+l_j\)
\(i< j\) 时，需要满足 \(r_i-t_i+1\geq l_j-t_j\)
发现两侧分别只和 \(i,j\) 有关，于是可以把它看做点的固有坐标，从而抽象为二维平面（因为有两维限制）的一个点，向另一个区域内的所有点连边的问题。
数据结构优化建图堂堂登场
可以想到用线段树套值域线段树来优化二维的建图，但这样空间需要 \(O(m\log^2m)\)，同时实现不简便，我们不妨在内层平衡树或者使用 \(set\) 来在 \(O(m\log m)\) 的空间复杂度内隐式建图。
但我们真的需要使用平衡树吗？现在我们有 $m\log m $ 个点，这些点分散在线段树中。一般来说，我们需要找到线段树的区间，再在到 set 里二分定位到其内部的一个区间来获得所有后继，并需要 \(\log\) 级别的时间才能完成一个点的删除操作。但对于这个题来说，第二维的限制无论查询还是删除都是一个前缀，于是我们可以使用 vector 来降序存储第二维的元素，使用 pop_back 来 \(O(1)\) 进行删除操作，获得 \(O(m\log^2 m)\) 的超牛时间复杂度（使用 \(set\) 实现为 \(O(m\log^3 m)\)）。
哪怕需要前后缀删除，我们也可以使用
deque，不过这位兄弟的常熟并不理想，实测不如set，甚至某些情况下劣于set。
这其中有隐式建图的思想。既然数据结构内部的边都无权值，我们干脆不建边，只是把数据结构当成 ”找后继的工具“ 即可。同时这样做也有一个好处，一旦我们在数据结构内删除了某个点，那么我们就瞬间删除了它的所有入度，这是链式前向星等建图方式所不能具备的。
其实会出现当前在 \(u\) 点，来到线段树上查后继，查到的后继已经被删除。这是因为每个点都被复制了 \(\log\) 份。不过这并不影响，因为我们会判断 \(dis_v\) 是否已经是最短路。
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> q;
LL dis[MAXN];
bool vis[MAXN];
int n,m;
class Work{
public:
int t,l,r;
LL c;
}a[MAXN];
class SegTree{
public:
int l,r;
bool _sort;
// set<pair<LL,int>> ls;
vector<pair<LL,int>> ls;
}tr1[MAXN<<2],tr2[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
void Build(SegTree* tr,int p,int l,int r){
tr[p]._sort=0;
tr[p].l=l,tr[p].r=r;
if(l==r){
return ;
}
int mid=(l+r)>>1;
Build(tr,lc(p),l,mid);
Build(tr,rc(p),mid+1,r);
}
void Insert(SegTree* tr,int p,int pos,LL k){
// tr[p].ls.insert({k,pos});
tr[p].ls.push_back({k,pos});
if(tr[p].l==tr[p].r){
return ;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(pos<=mid) Insert(tr,lc(p),pos,k);
else Insert(tr,rc(p),pos,k);
}
void Update(SegTree* tr,int p,int l,int r,LL top,int u){
if(l<=tr[p].l && tr[p].r<=r){
auto &ls=tr[p].ls;
if(!tr[p]._sort){
tr[p]._sort=1;
sort(All(ls),[&](pair<LL,int> p,pair<LL,int> q){
return p>q;
});
}
while(!ls.empty() && ls.back().fi<=top){
auto v=ls.back().se;
ls.pop_back();
if(dis[v]==LLONG_MAX){
dis[v]=dis[u]+a[v].c;
// cout<<u<<"->"<<v<<' '<<dis[u]<<' '<<dis[v]<<endl;
q.push({dis[v],v});
}
}
return ;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) Update(tr,lc(p),l,r,top,u);
if(r>mid) Update(tr,rc(p),l,r,top,u);
}
signed main(){
n=RIN,m=RIN;
foru(i,1,m){
a[i]={RIN,RIN,RIN,RIN};
}
sort(a+1,a+1+m,[&](Work p,Work q){
return p.t<q.t;
});
Build(tr1,1,1,m);
Build(tr2,1,1,m);
foru(i,1,m){
Insert(tr1,1,i,a[i].t+a[i].l);
Insert(tr2,1,i,a[i].l-a[i].t);
}
foru(i,1,m){
if(a[i].l==1){
dis[i]=a[i].c;
q.push({dis[i],i});
}else{
dis[i]=LLONG_MAX;
}
}
while(!q.empty()){
auto [ds,u]=q.top();
q.pop();
if(vis[u]) continue;
vis[u]=1;
//do edge update
if(u>1){
Update(tr2,1,1,u-1,a[u].r-a[u].t+1,u);
}
if(u<m){
Update(tr1,1,u+1,m,a[u].r+a[u].t+1,u);
}
}
LL ans=LLONG_MAX;
foru(i,1,m){
if(a[i].r==n){
ans=min(ans,dis[i]);
// cout<<i<<' '<<dis[i]<<endl;
}
}
cout<<(ans==LLONG_MAX?-1:ans);
return 0;
}
T4
写完 T3 两个包还剩一个小时开 T4。赛后被同学提醒才想起来是今年省选 Day1 T1，我还没做出来，真事烂完了。题面不放了。
理解成了多个向量相加，移项什么的，变成一个点/圈同时移动/扩大，类似追及的一个问题，果断开分讨。讨论点所在的象限，查答案就行。写的时候写崩溃了，写成大粪了。
联合省选赛时的代码写的是二分，跑了 400+ms，90分因为开小了二分范围。这次赛后调过了，大分讨跑了 140ms，但是赛时获得 0 分高分，输完了。
//%^~
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
LL n,k;
pair<LL,LL> ed,a[MAXN],pre[MAXN],dx;
LL get(pair<LL,LL> x){
return abs(x.fi)+abs(x.se);
}
pair<LL,LL> add(pair<LL,LL> p,pair<LL,LL> q){
return {p.fi+q.fi,p.se+q.se};
}
pair<LL,LL> mul(pair<LL,LL> p,LL q){
return {p.fi*q,p.se*q};
}
LL upc(LL a,LL b){
LL ret=a/b;
if(a!=ret*b) ret++;
return ret;
}
LL out(pair<LL,LL> A,pair<LL,LL> B,LL a,LL b){
if(get(A)<=k*a) return a;
LL v=get(add(A,B))-get(A);
// cout<<"!"<<k*b-v<<endl;
if(v<k*b){
return a+b*upc(get(A)-k*a,k*b-v);
}else{
// cout<<"sad"<<endl;
return LLONG_MAX;
}
}
LL oneout(pair<LL,LL> A,pair<LL,LL> B,LL a,LL b){
if(get(A)<=k*a) return a;
LL num=A.se/(-B.se);
if(get(add(A,mul(B,num)))<=k*(a+b*num)){
LL l=1,r=num,ans=0;
while(l<=r){
LL mid=(l+r)>>1ll;
if(get(add(A,mul(B,mid)))<=k*(a+b*mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
return a+ans*b;
}else{
auto nA=add(A,mul(B,num+1));
auto nB=B;
nA.se=-nA.se;
nB.se=-nB.se;
return out(nA,nB,a+b*(num+1),n);
}
}
LL check(LL i){
auto A=pre[i];
auto B=dx;
if(pre[i].fi<0){
A.fi=-A.fi;
B.fi=-B.fi;
}
if(pre[i].se<0){
A.se=-A.se;
B.se=-B.se;
}
if(get(A)<=k*i) return i;
// if(get(add(A,B))<=k*(i+n)) return i+n;
LL ret=LLONG_MAX;
if(B.fi>=0 && B.se>=0){
// cout<<' '<<out(A,B,i,n)<<endl;
ret=min(ret,out(A,B,i,n));
}
if(B.fi<0 && B.se>=0){
swap(A.fi,A.se);
swap(B.fi,B.se);
}
if(B.fi>=0 && B.se<0){
// cout<<' '<<oneout(A,B,i,n)<<endl;
ret=min(ret,oneout(A,B,i,n));
// LL num=A.se/(-B.se);
// if(get(add(A,mul(B,num)))<=k*(i+n*num)){
// LL l=1,r=num,ans=0;
// while(l<=r){
// LL mid=(l+r)>>1ll;
// if(get(add(A,mul(B,mid)))<=k*(i+n*mid)){
// r=mid-1;
// ans=mid;
// }else{
// l=mid+1;
// }
// }
// ret=min(ret,ans);
// }else{
// auto nA=add(A,mul(B,num+1));
// auto nB=B;
// nA.se=-nA.se;
// nB.se=-nB.se;
// ret=min(ret,out(A,B,i+n*(num+1),n));
// }
}
if(B.fi<0 && B.se<0){
if(A.fi/(-B.fi)<A.se/(-B.se)){
swap(A.fi,A.se);
swap(B.fi,B.se);
}
LL num=A.se/(-B.se);
if(get(add(A,mul(B,num)))<=k*(i+n*num)){
LL l=1,r=num,ans=0;
while(l<=r){
LL mid=(l+r)>>1ll;
if(get(add(A,mul(B,mid)))<=k*(i+n*mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
ret=min(ret,i+ans*n);
}else{
auto nA=add(A,mul(B,num+1));
auto nB=B;
if(nA.fi<=0 && nA.se<=0){
nA.fi=-nA.fi;
nA.se=-nA.se;
nB.fi=-nB.fi;
nB.se=-nB.se;
ret=min(ret,out(nA,nB,i+n*(num+1),n));
}else{
if(nA.fi>0 && nA.se<=0){
swap(nA.fi,nA.se);
swap(nB.fi,nB.se);
}
// cout<<nA.fi<<' '<<nA.se<<endl;
// cout<<nB.fi<<' '<<nB.se<<endl;
// if(get(add(nA,nB))<=k*(i+n)) return i+n;
nA.fi=-nA.fi;
nB.fi=-nB.fi;
// cout<<nA.fi<<' '<<nA.se<<endl;
// cout<<nB.fi<<' '<<nB.se<<endl;
// if(get(add(nA,nB))<=k*(i+n)) return i+n;
ret=min(ret,oneout(nA,nB,i+n*(num+1),n));
}
}
}
return ret;
}
signed main(){
int T=RIN;
while(T--){
n=RIN,k=RIN;
ed={RIN,RIN};
foru(i,1,n){
a[i]={RIN,RIN};
pre[i]=pre[i-1];
pre[i].fi+=a[i].fi;
pre[i].se+=a[i].se;
}
if(ed.fi==0 && ed.se==0){
cout<<0<<'\n';
continue;
}
dx.fi=-pre[n].fi;
dx.se=-pre[n].se;
foru(i,1,n){
pre[i].fi=ed.fi-pre[i].fi;
pre[i].se=ed.se-pre[i].se;
}
LL ans=LLONG_MAX;
foru(i,1,n){
ans=min(ans,check(i));
}
// if(ans==8){
// cout<<n<<' '<<k<<' '<<ed.fi<<' '<<ed.se<<endl;
// foru(i,1,n){
// cout<<a[i].fi<<' '<<a[i].se<<endl;
// }
// }
if(ans==LLONG_MAX){
cout<<(-1)<<'\n';
}else{
cout<<ans<<'\n';
}
}
return 0;
}