bzoj

题意是严格次小生成树。 想了一下发现应该是一条不在最小生成树上的边构成的环上替换一条边就行了。感觉好想noi那道lct，哈。其实不用那么复杂的。 就用倍增就可以了。不过我还是比较倾向于用链剖。感觉链剖空间小而且写起来倍爽。不像倍增写挂了不只一次了。 要注意的是不仅要找最大值还要找严格次大值，因为要找严格次小。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct edge_g { int a, b, v, mk; }; struct edge_t { int t, v; edge_t *next; }; struct dat { int a, b; dat(int v0 = -1) { a = v0, b = -1; } dat(int a0, int b0) { a = a0, b = b0;...

OTL写manacher的mhy。 我没有那么高端去研究st怎么搞，所以就用了一个二维hash。从四个角各来一遍真是爽翻了。需要注意的是hash的时候行之间和列之间的值要不同才能区别，不然有数据随便可以卡掉。 代码么，巨丑无比。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; #define uint _uint_ typedef unsigned long long int uint; const int maxn = 1009; const uint bh = 1e9 + 93; const uint bv = 1e9 + 7; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } int n, m, a[maxn][maxn]; uint h[4][maxn][maxn], ph[maxn * 2], pv[maxn * 2];...

考场上只想到暴力。 如果只是一条链的话怎么乱搞一搞？ 如果没有深度限制的话简单的斜率优化+链剖就行了。 有深度限制就把hull扔到线段树里用可持久化栈来维护一下。DFS的时候塞进线段树里，然后完了再扔出来。总的复杂度O(n*log^2(n))， 代码也不怎么复杂。 #include <cstdio> #include <cctype> #include <memory.h> #include <vector> #include <algorithm> using namespace std; struct edge { int t; edge* next; }; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct oper { int p, v, t;...