- T701832 滑动窗口 /【模板】单调队列
单调队列板子题，所以显然是单调队列。
单调队列就俩操作，一个是加入队尾的时候如果破坏单调性了就把队尾一直 pop 到满足单调性，另一个是如果队首不在范围内就 pop 出去。因为每个元素会且仅会加入一次队列所以复杂度为 \(O(n)\)。
呜呜不许卡我 deque 卡我的都是坏出题人
int a[maxn];
deque<int> d1,d2;
signed main(){int n,k;read(n,k);for_(i,1,n) read(a[i]);for_(i,1,n){if(!d1.empty()&&d1.front()<i-k+1) d1.pop_front();while(!d1.empty()&&a[d1.back()]>a[i]) d1.pop_back();d1.push_back(i);if(i>=k) cout << a[d1.front()] << " ";}puts("");for_(i,1,n){if(!d2.empty()&&d2.front()<i-k+1) d2.pop_front();while(!d2.empty()&&a[d2.back()]<a[i]) d2.pop_back();d2.push_back(i);if(i>=k) cout << a[d2.front()] << " "; }
}
- T701833 【模板】单调栈
单调栈板子题，所以这道题是单调栈。
单调栈比单调队列还简单，就是如果加入的时候破坏了单调性就一直 pop 到不破坏即可，因为每个元素只会加入一次栈所以复杂度为 \(O(n)\)
总不能卡我 stack 吧那我真得控制你了
int a[maxn],ans[maxn];
stack<int> s;
signed main(){int n;read(n);for_(i,1,n) read(a[i]);for_(i,1,n){while(!s.empty()&&a[s.top()]<a[i]) {ans[s.top()]=i;s.pop();}s.push(i);}for_(i,1,n) cout << ans[i] << " ";
}
- T701835 【模板】最小生成树
哈哈我不会最小生成树。
我们对所有边进行排序，然后我们每次尝试将最小的边加入即可，如果对于两个集合已经联通那么就跳过这条边。直到加入了 \(n-1\) 条边，这样就做完了。
邪恶 CCF 总不能再考一次 MST 吧
class side{public:int x,y,z;
}Side[maxn];
#define X(i) Side[i].x
#define Y(i) Side[i].y
#define Z(i) Side[i].zint fa[maxn];bool f=0;
inline int Find(int x){return fa[x]==0?x:fa[x]=Find(fa[x]);
}
inline void Merge(int x,int y){fa[Find(x)]=Find(y);
}
signed main(){int n,m,ans=0;read(n,m);for_(i,1,m) read(X(i),Y(i),Z(i));sort(Side+1,Side+1+m,[](side A,side B){return A.z<B.z;});for_(i,1,m){if(Find(X(i))!=Find(Y(i))){ans+=Z(i);Merge(X(i),Y(i));}}for_(i,1,n-1){if(Find(i)!=Find(i+1)){cout << "orz" << endl;exit(0);}}cout << ans;
}
- T701836 【模板】最近公共祖先（LCA）
我们记录每个节点往上跳 \(2^k\) 步的父亲节点，通过二进制分解让两个节点慢慢往上跳找祖先即可。
但是我不要，因为我呜，呜呜要变成 LCT 的形状了呜....所以写一个 LCT 的做法。对于一个 \(LCA(x,y)\)，我们先 access 其中一个打通到 root 的路径，然后再对另一个点进行 access，此时遇到的第一个在路径 \((a,root)\) 上的点就是 LCA
不关 #define int long long 甚至过不去，常数这一块
namespace Link_Cut_Tree{#define fa(x) T[x].fa#define rev(x) T[x].rev#define lc(x) T[x].son[0]#define rc(x) T[x].son[1]#define son(x,i) T[x].son[i]#define val(x) T[x].valint ans[N],Stack[N];class LCT{public:int son[2],fa,rev,val;}T[N];int rt;inline bool isroot(int x){return (lc(fa(x))==x)||(rc(fa(x))==x);}inline void Reverse(int x){swap(lc(x),rc(x));rev(x)^=1;}inline void Push_Down(int x){if(rev(x)){if(lc(x)) Reverse(lc(x));if(rc(x)) Reverse(rc(x));rev(x)=0;}}inline void rotate(int x){int y=fa(x),z=fa(y),k=rc(y)==x,w=son(x,!k);if(isroot(y)) son(z,rc(z)==y)=x;son(x,!k)=y;son(y,k)=w;if(w) fa(w)=y;fa(y)=x;fa(x)=z;}inline void Splay(int x){int y=x,tot=0;Stack[++tot]=y;while(isroot(y)) Stack[++tot]=y=fa(y);while(tot) Push_Down(Stack[tot--]);while(isroot(x)){int xx=fa(x),yy=fa(xx);if(isroot(xx)) rotate((lc(xx)==x)^(lc(yy)==xx)?x:xx);rotate(x);}}inline void access(int x){for(int y=0;x;x=fa(y=x)){Splay(x);rc(x)=y;;}}inline void toroot(int x){access(x);Splay(x);Reverse(x);}inline void link(int x,int y){toroot(x);fa(x)=y; }inline int Query_LCA(int x,int y){toroot(rt);access(y);int X=0;for(;x;x=fa(X=x)){Splay(x);rc(x)=X;}return X;}
}
using namespace Link_Cut_Tree;signed main(){int n,m;read(n,m,rt);for_(i,1,n-1){int x,y;read(x,y);link(x,y);}for_(i,1,m){int x,y;read(x,y);cout << Query_LCA(x,y) << endl;}
}
- T701838 【模板】单源最短路径（标准版）
这个，dij 板子。
我们考虑遍历每个节点能到的其他节点，然后更新距离。用优先队列优化即可。
出题人能不能别出负边权求你啦
int n,m,s,tot,dis[maxn];bool vis[maxn];
int head[maxn],nxt[maxn],ver[maxn],edge[maxn];
inline void add(int x,int y,int z){ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
}
inline void dij(int S){priority_queue<pair<int,int>> q;for_(i,1,n) dis[i]=INT_MAX;dis[S]=0;q.push(make_pair(0,S));while(!q.empty()){int x=q.top().second;q.pop();if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=nxt[i]){int y=ver[i],z=edge[i];if(dis[y]>dis[x]+z){dis[y]=dis[x]+z;q.push(make_pair(-dis[y],y));}}}
}
signed main(){read(n,m,s);for_(i,1,m){int x,y,z;read(x,y,z);add(x,y,z);} dij(s);for_(i,1,n) cout << dis[i] << " ";
}