旅行路线
Source：CF459E。
憨憨题。
按 \(w\) 排序后，考虑 DP，设 \(f_u\) 表示目前在点 \(u\)，可以走出的最长路线。
按阶段转移的时候稍微注意一下相同边权的处理，具体的，开一个 \(g_u\) 表示这里的预存答案，然后集体转移就行了。
时间复杂度 \(O(m\log m)\)。
Code
const int N=3e5+5,M=3e5+5,V=1e6+5;
int f[N],g[N],ans;
vector<pii> ed[V];
int main() {
int n=read(),m=read();
FOR(i,1,m) {
int x=read(),y=read(),v=read();
ed[v].pb(x,y);
}
FOR(i,1,V-5) {
for(pii j:ed[i]) chkmax(g[j.se],f[j.fi]+1);
for(pii j:ed[i]) chkmax(f[j.se],g[j.se]),g[j.se]=0;
}
int ans=0;
FOR(i,1,n) chkmax(ans,f[i]);
printf("%d\n",ans);
}
剧毒礼物
Source：「CTSC2017」吉夫特。
显然结论：\(\binom{n}{m} \bmod 2=[n\And m=0]\)，证明考虑 Lucas 定理，此处略去。
问题可以转变为寻找最长的子序列满足 \(a_1\supseteq a_2\supseteq a_3\supseteq\ldots\supseteq a_n\)，倒过来做，条件就是子集条件，可以直接枚举子集 DP。
时间复杂度 \(O(3^{\log a_i})\)。
Code
int a[N],f[V];
void Add(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int main() {
int n=read();
FOR(i,1,n) a[i]=read();
reverse(a+1,a+n+1);
FOR(i,1,n) {
for(int j=a[i];j;j=(j-1)&a[i]) Add(f[a[i]],f[j]);
Add(f[a[i]],1);
}
int ans=0;
FOR(i,1,n) Add(ans,f[a[i]]);
printf("%d\n",(ans-n+mod)%mod);
}
信息网络
Source：CF1270H。
结论一：每个连通块均是一个区间。
证明：设 \(i<j,a_i<a_j\)，则在 \([i,j]\) 中的点要么与 \(i\) 有边要么与 \(j\) 有边，可以分类讨论证明，此处不表。
维护区间很困难，我们考虑维护区间交点个数，这个问题等价于求出 \(\min_{i=1}^x a_i>\max_{i=x+1}^n a_i\) 的元素个数，枚举 \(\max_{i=x+1}^n a_i\) 的值，则其能满足上述限制当且仅当将比他大的数设为 \(1\)，比他小的数设为 \(0\)，序列形如 \(11\ldots1100\ldots00\)。
这个序列的形态看起来就很难维护，考虑维护 \(10\) 段的个数，发现这个很好维护。
于是，按值域建立线段树，维护全局最小值和最小值个数，答案即为最小值个数。
具体的更新，考虑修改 \(x\) 会造成什么样的影响就行了，细节请参照代码。
Code
const int N=5e5+5,V=1e6+5;
int a[N];
int mi[V*4],cnt[V*4],add[V*4];
void pushup(int p) {
mi[p]=min(mi[p*2],mi[p*2+1]),cnt[p]=0;
if(mi[p]==mi[p*2]) cnt[p]+=cnt[p*2];
if(mi[p]==mi[p*2+1]) cnt[p]+=cnt[p*2+1];
}
void pushadd(int p,int v) {mi[p]+=v,add[p]+=v;}
void pushdown(int p) {
if(add[p]) pushadd(p*2,add[p]),pushadd(p*2+1,add[p]),add[p]=0;
}
void update_cnt(int p,int l,int r,int x,int v) {
if(l==r) return cnt[p]+=v,void();
int mid=(l+r)>>1;pushdown(p);
if(x<=mid) update_cnt(p*2,l,mid,x,v);
else update_cnt(p*2+1,mid+1,r,x,v);
pushup(p);
}
void update(int p,int l,int r,int x,int y,int v) {
if(x<=l&&r<=y) return pushadd(p,v);
int mid=(l+r)>>1;pushdown(p);
if(x<=mid) update(p*2,l,mid,x,y,v);
if(y>mid) update(p*2+1,mid+1,r,x,y,v);
pushup(p);
}
void work(int x,int v) {update(1,0,1e6,min(a[x],a[x+1]),max(a[x],a[x+1])-1,v);}
int main() {
int n=read(),q=read();
int vv=1e6;
a[0]=vv+1,a[n+1]=0;
FOR(i,1,n) a[i]=read();
FOR(i,1,n) update_cnt(1,0,vv,a[i],1);
FOR(i,0,n) work(i,1);
FOR(i,1,q) {
int x=read(),v=read();
work(x-1,-1),work(x,-1),update_cnt(1,0,vv,a[x],-1);
a[x]=v;
work(x-1,1),work(x,1),update_cnt(1,0,vv,a[x],1);
printf("%d\n",cnt[1]);
}
}
调兵遣将
Source：「ICPC 2018 WF」Conquer The World
反悔贪心。
考虑从上往下的考虑每一个点作为 LCA 进行一个周转，从 \(x\) 到 \(y\) 的周转的费用是 \(dep_x+dep_y-2*dep_{lca}\)。
选定一个的代价是这么多，选定了之后在 \(x\) 对应的堆中插入 \(-dep_y+2*dep_{lca}\)，\(y\) 对应的堆中插入 \(-dep_x+2*dep_{lca}\)，用于反悔。
另外我们不能选定两个反悔操作，换句话说，我们希望优先满足真正的周转，我们直接将 \(x\) 插入的东西变成 \(dep_x-inf\)，最后的时候加进来就行。
需要支持对的合并，直接使用 pbds 即可。
过掉测试题要树剖模拟费用流，不写。
Code
const int N=250005;
const ll inf=1e13;
vector<pii> G[N];
int a[N],b[N],tot;
__gnu_pbds::priority_queue<ll,greater<ll> > A[N],B[N];
ll ans=0,dep[N];
void dfs(int u,int fa) {
int cc=abs(a[u]-b[u]);
if(a[u]<b[u]) while(cc) A[u].push(dep[u]-inf),tot++,cc--;
else while(cc) B[u].push(dep[u]),cc--;
for(auto [v,d]:G[u]) if(v!=fa) {
dep[v]=dep[u]+d,dfs(v,u);
A[u].join(A[v]),B[u].join(B[v]);
}
while(sz(A[u])&&sz(B[u])&&A[u].top()+B[u].top()-2*dep[u]<0) {
ll t1=A[u].top(),t2=B[u].top();
A[u].pop(),B[u].pop();
ans+=t1+t2-2*dep[u];
A[u].push(-t2+2*dep[u]),B[u].push(-t1+2*dep[u]);
}
}
int main() {
int n=read();
FOR(i,1,n-1) {
int x=read(),y=read(),c=read();
G[x].pb({y,c}),G[y].pb({x,c});
}
FOR(i,1,n) a[i]=read(),b[i]=read();
dfs(1,0),printf("%lld\n",ans+inf*tot);
}