<div class="post_brief"><p> 最初感觉好多状态怎么做。</p>   然后发现（其实是瞟了一下题解）如果把一个数分成2a*3b*c，那么c只影响上界。2a*3b中a最大是16，b最大是10，列一张17*11的表出来，然后发现右下方还有很多空东西。于是直接像插头一样状压一下轮廓线呗。反正对一个数有影响的只有它的上面和左边。最近写插头写得有点疯啊。其实它的很多思想都是可以推广出来用的。比如最小表示啥的。   于是如果直接这样写的话大概要跑30000多次dp，还是比较悬。然后再想想发现只有表里能取的数的形状发生改变的时候才会改变dp的答案。表里面的数很少所以改变次数也应该很少。所以记一下上一次的形状是什么然后比较相不相同，相同就直接沿用。   然后跑得飞快。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) #define pow2(x) (1<<(x)) const int maxn = 19; const int maxm = 15; const int maxv = 100000; const int maxst = pow2(11) + 9; const int mod = 1e9 + 1; int f[2][maxst], vl[maxn][maxm], n, m, v; int dis[maxn], ldis[maxn], lans, ans; void pre() { for (int i = 0; i < maxn; ++ i) { vl[i][0] = (1 << i); if (vl[i][0] > maxv) vl[i][0] = -1; for (int j = 1; j < maxm; ++ j) if (vl[i][j - 1] > -1) { vl[i][j] = vl[i][j - 1] * 3; if (vl[i][j] > maxv) vl[i][j] = -1; } else vl[i][j] = -1; } }...

<div class="post_brief"><p> 好吧我的本意是想学习一下dp的。然后发现了这道纠结了一年半还多的题。</p>   首先把环找出来。然后环上会长一些树。先把树的答案求了，因为它很好求。   然后考虑环，那么答案应该是随便断一条边之后答案的最小值（而不是最大值）。于是乎记录一下每个点按某个方向到起点的距离，记为d[i]。算一下每个点的树的深度，记为l[i]。于是每次要最大化l[i]+l[j]+|d[i]-d[j]|。反正是最大化所以顺序是没有关系的，但是不能自交。这是个比较容易错的地方。于是就去写个线段树来维护吧。只查询不修改让我总有能线性搞的想法，虽然没想清楚具体怎么实现。   #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; struct edge { int t, v; edge *next; }; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 100009; edge elst[maxn << 1], *ep(elst), *head[maxn]; int n, fa[maxn], df[maxn], ol[maxn], d[maxn]; int tlp, lp[maxn << 1]; dint lv[maxn << 1], le[maxn << 1], md[maxn], ans;...

<div class="post_brief"><p> 看上去比较不可做的DP。好像别人写的记搜跑得飞快。</p>   我看我是写最小表示写上瘾了。   压一下状态，有点像今天第二题。算每种值的有多少。然后直接跑。   感觉废状态比较多啊，跑得好慢。另外用memset清空高维数组会比较快。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int mod = 1e9 + 7; const int maxn = 17; const int maxst = 16009; #define mbit(a,b) ((a)<<((b)<<2)) #define gbit(a,b) (((a)>>((b)<<2))&0xf) #define _l (long long int) int m, c[maxn], n, mt, tots, slst[maxst]; int f[2][7][maxst]; void dfsState(int t, int l, int v) { if (l == mt + 1) { slst[tots ++] = v | t; } else { for (int i = 0; i <= t; ++ i) dfsState(t - i, l + 1, v | mbit(i, l)); } }...

<div class="post_brief"><p> 今天考试题的弱化版。只用求LCA是谁，不用求它的深度。所以直接用线段树找下区间最值就搞定了。然后long的范围有负数坑了一发。</p>   好像在不平衡的平衡树上的题也比较热啊。而且我还做得比较少。是要补一补。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef pair <int, int> vpr; typedef pair <bool, vpr> dpr; struct seg { int l, r; dpr d; seg *ls, *rs; }; struct query { int t, a, b; }; const int maxn = 400009; int n, m, vl[maxn], tv; vpr a[maxn]; query q[maxn]; seg slst[maxn * 3], *sp(slst), *rt; inline int gpos(int x) { return lower_bound(vl, vl + tv, x) - vl; }...

<div class="post_brief"><p> 我的第二道插头DP。差不多纠结了一天。</p>   这道题网上的题解都讲的好简略啊。最后还得自己yy。没有用括号序列法让我觉得自己比较厉害。   考虑轮廓线上的m个格子，有3种情况：没有插头，有且只能往一边走，有且要往两边走。对于第二种，要用最多3个不同的值来记录连通性。还要有两个不同的值来表示第一种情况和第三种情况。我比较懒，所以直接用一个八进制数去表示，然后每次二分找编号。   考虑转移，分一堆情况进行讨论。默认从左上朝右下走。   首先是要走当前格子的情况。   如果左边和上面都有插头，那么看它们是否连通。如果不连通则把它们连通，如果已经连通，看是否还有其它插头。没有就更新答案，否则忽略。   如果只有左边有插头，再分类。如果它是第二种，那么这个格子可以新建一个第三种插头，或者把左边格子的插头接过来。如果它是第三种那么它必需把左边格子接过来。   如果只有上面有插头，那么必需把上面的插头接上来。   如果左边和上面都没有插头，那么可以新建一个第三种插头。   然后如果不走这个格子的话，要求上面没有插头，且左边不是第三种插头。   按mhy的话说，插头dp就是写起来很麻烦。的确。不过写出来也还是挺高兴的。   然后代码丑到不能看了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 109; const int maxm = 9; const int maxst = 50009; const int inf = 0x3f3f3f3f; #define pow8(x) (1<<(x)<<(x)<<(x)) #define mbit(x,y) ((x)<<(y)<<(y)<<(y)) #define gbit(x,y) (((x)>>(y)>>(y)>>(y))&7) int f[2][maxst], n, m, a[maxn][maxm], ans; int slst[maxst], tots;...

<div class="post_brief"><p> 我以为是最大权闭合子图来着。然后好像就直接最小割就行了吧。突然觉得我的网络流好弱。</p>   建源汇，分别连每个作物。对于每个组合建两个点分别边源汇，然后中间像源汇一样连它的成员。如果全在一边，那么会有一条边不用割。这也是一个集合都选对答案有贡献的建图方式。   然后就完了。建图和dinic都写得有些丑，所以调了半天。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, c; edge *next, *rv; }; const int maxn = 3009; const int inf = 0x3f3f3f3f; int n, m, c, d[maxn], t, st, te; edge *head[maxn]; inline edge* newEdge(int u, int v, int c) { edge* e(new edge); e-> t = v; e-> c = c; e-> next = head[u]; return head[u] = e; } inline void addEdge(int u, int v, int c) { edge *a(newEdge(u, v, c)), *b(newEdge(v, u, 0)); a-> rv = b; b-> rv = a; }...

<div class="post_brief"><p> usaco的银组都开始考这种题了么。其实还是挺水的，不过题号比较好。</p>   就按y排序，挨个把时间轴上的东西扔掉就完了。写离散可能还没有直接写smt快呢。   然后线段有一边要减1有点坑。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) struct cow { int y; int ta, tb; }; struct node { int l, r, w; node ls, rs; }; typedef pair <node, node > npr; const int maxn = 50009; inline bool operator <(const cow& a, const cow& b) { return a....

<div class="post_brief"><p> 左偏树+并查集的一眼题嘛。然后合并的时候搞忘了如果两个人已经在同一个团里要跳过，于是左偏树自交去了。</p>   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define szof(p) ((p)?(p->sz):0) struct node { int sz, vl, id; node *ls, rs; node() {} node(int v, int i) { vl = v; id = i; sz = 1; ls = rs = 0; } inline void update() { if (szof(ls) < szof(rs)) swap(ls, rs); } }; node merge(node p, node q) { if (!p) return q; else if (!...

<div class="post_brief"><p> 多老的省选题了。</p>   就处理一下任意两个格子之间最少要经过几个1，如果小于等于t就更新答案。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; #define mkword(x,y) (((x)<<16)|(y)) #define hiword(x) ((x)>>16) #define loword(x) ((x)&0x0000ffff) const int maxn = 33; const int maxnd = 909; const int movx[4] = {0, 0, 1, -1}; const int movy[4] = {1, -1, 0, 0}; typedef pair <int, int> dpr; inline int sqr(int x) { return x * x; } int n, m, t, d[maxn][maxn], ans; int mp[maxn][maxn]; dpr hp[maxnd << 2];...

<div class="post_brief"><p> 今天晚上的效率比白天高啊。</p>   树上莫队的另一道题。比糖果公园好写到哪里去了。   然后手写链表丑掉了导致调试半天+RE了一发。我还是太年轻了。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef struct node { int t; node *next; } edge; const int maxn = 50009; const int maxm = 100009; const int maxl = 17; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { if (a....