NOIP2017 逛公园&列队 [DP/最短路/动态开点线段树]
坑 -2
填坑计划持续进行中咻
Problem
逛公园
https://www.luogu.org/problemnew/show/P3953
列队
https://www.luogu.org/problemnew/show/P3960
Solution
逛公园
这里讲的挺好:https://zhzh2001.github.io/2017/12/02/noip2017-solution/
列队
考虑每次操作,会往一行最后一个加人和最后一列的最后一个加人
于是维护 n + 1 棵线段树(动态开点)
然后查询线段树的第 k 大值,并把第 k 大值减去。
这里有几个小细节,一是一开始权值不是 0 而是 1,这样不好维护。
那么我们假设一开始权值都是 0,然后删掉的话就把权值改成 -1,就好维护了。
二是对于 n 棵线段树的查询,如果查到的是未开点的部分,那么对于这个点手动算坐标。如果查到了开点部分,直接返回插入的坐标。对于最后一列的线段树,直接暴力插入初始化就行。
三是爆 int 注意。
啊以及空间复杂度是个玄学来着。
Code
逛公园
// Code by ajcxsu
// Problem: park
#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;
const int N=1e5+2, M=5e5+2, K=51;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
typedef long long ll;
int f[N][K];
int T, n, m, k, mo;
int d1[N], d2[N];
char S[N];
typedef pair<int, int> mpair;
priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
void dij(int dist[], int s, int d) {
memset(dist, 0x3f, sizeof(d1)), CLR(S);
dist[s]=0;
pq.push(mpair(0, s));
int na;
while(!pq.empty()) {
na=pq.top().second, pq.pop();
if(S[na]) continue;
S[na]=1;
for(int u=h[na];u;u=nexp[u])
if(u%2==d && dist[to[u]]>dist[na]+W[u])
dist[to[u]]=dist[na]+W[u], pq.push(mpair(dist[to[u]], to[u]));
}
}
char vis[N][K], flag;
int dfs(int x, int nk) {
flag=vis[x][nk];
if(f[x][nk]!=-1) return f[x][nk];
vis[x][nk]=1, f[x][nk]=(x==n);
for(int u=h[x]; u && !flag; u=nexp[u])
if((u&1) && nk+d1[x]-d1[to[u]]+W[u]<=k && d1[x]+nk+d2[to[u]]+W[u]<=d1[n]+k)
f[x][nk]=(f[x][nk]+dfs(to[u], nk+d1[x]-d1[to[u]]+W[u]))%mo;
vis[x][nk]=0;
return f[x][nk];
}
void ini() { CLR(h), p=1, memset(f, -1, sizeof(f)), flag=0; }
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin>>T;
while(T--) {
cin>>n>>m>>k>>mo, ini();
int u, v, w;
for(int i=0;i<m;i++) cin>>u>>v>>w, ins(u, v, w), ins(v, u, w);
dij(d1, 1, 1), dij(d2, n, 0);
int ans=dfs(1, 0); ans=flag?-1:ans;
cout<<ans<<endl;
}
return 0;
}
列队
// Code by ajcxsu
// Problem: sylvia
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10, M=1e7+10;
struct Node *nil;
struct Node {
Node *ls, *rs;
ll v;
int c;
} *nd[N], *co, po[M], *pp=po;
void ini() { nil=pp++, nil->ls=nil->rs=nil, nil->v=0, nil->c=0, fill(nd, nd+N, nil), co=nil; }
void updata(Node *&x, int l, int r, int d, int v, ll w) {
if(x==nil) { Node *nd=pp++; *nd=*x, x=nd; }
x->c+=v;
if(l==r) {x->v=w; return;}
int mid=(l+r)>>1;
if(d<=mid) updata(x->ls, l, mid, d, v, w);
else updata(x->rs, mid+1, r, d, v, w);
}
pair<int, ll> query(Node *x, int l, int r, int k) {
if(l==r) return pair<int, ll>(l, x->v);
int mid=(l+r)>>1;
if(k<=mid-l+1+x->ls->c) return query(x->ls, l, mid, k);
else return query(x->rs, mid+1, r, k-(mid-l+1+x->ls->c));
}
int len[N], colen;
int main() {
ios::sync_with_stdio(false), cin.tie(0), ini();
int n, m, q, k;
cin>>n>>m>>q, k=max(n, m)+q+1, fill(len, len+N, m-1), colen=n;
for(int i=1;i<=n;i++) updata(co, 1, k, i, 0, 1ll*i*m);
int x, y;
ll wh;
pair<int, ll> pr, pr2;
while(q--) {
cin>>x>>y;
if(y==m) {
pr=query(co, 1, k, x);
cout<<pr.second<<endl;
updata(co, 1, k, pr.first, -1, 0), updata(co, 1, k, ++colen, 0, pr.second);
}
else {
pr=query(nd[x], 1, k, y), wh=pr.second;
if(!wh) cout<<(wh=1ll*(x-1)*m+pr.first)<<endl;
else cout<<wh<<endl;
pr2=query(co, 1, k, x);
len[x]++, updata(nd[x], 1, k, pr.first, -1, 0);
updata(nd[x], 1, k, len[x], 0, pr2.second);
updata(co, 1, k, pr2.first, -1, 0), updata(co, 1, k, ++colen, 0, wh);
}
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/faq-noip-2017.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆