dp

<div class="post_brief"><p> 比较神奇的数学题。首先你要知道这个函数的意思是把它的二进制flip。至于怎么来的我也是听说的。然后推一下发现的确是这么回事。</p>   于是就变成数位dp了。然后我发现数位dp常常可以用奇奇怪怪的方法水过去。然后又发现数组从0开始标号也会造成麻烦。+1-1啥的最讨厌了。   于是这题就变成高精度练习题了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 409; struct BigInt { int l, a[maxn], base; BigInt(int b = 10) { l = 0; base = b; } void push() { for (int i = 0; i < l - 1; ++ i) { a[i + 1] += a[i] / base; a[i] %= base; } for (; a[l - 1] >= base; ++ l) { a[l] = a[l - 1] / base; a[l - 1] %= base; } } void pull() { for (; l && !...

<div class="post_brief"><p> 第六百道题一定要不水！虽然离第一页还有几十道题的距离。</p>   很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦，更不要说这个了。   现在想想还行，因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的，那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来，其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量，写起来也比较明了。虽然还是比mhy长。   然后因为我在最后一步dp的时候写了一个static的f数组，所以光荣了。debug了好久。晕。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, av; edge *next, *rv; }; struct ball { int l, *a, h; }; const int maxn = 50009; const int maxm = 200009; const int maxarr = 400009; int n, m, cb, fb[maxn], d[maxn]; int f[maxn], ans, fd[maxn], fe[maxn]; int stc[maxn], tst; int ibuf_arr[maxarr], *ibuf(ibuf_arr); bool vis[maxn]; edge elst[maxm], *ep(elst), *head[maxn]; ball b[maxm];...

<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> 我的第二道插头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>   这题很久之前看过。当时以为是高消就没管。然后开坑之神idy做了之后仔细一想才知道不是。   这题的做法是dp。首先因为边数少所以不用floyd，直接bfs预处理出所有t[i][j]表狼在i，兔子在j的时候狼下一步去哪。然后有一个结论是每一步两个玩意的距离至少缩短1，所以状态是不会有环的，这也是为啥可以不用高消。然后坑点是不能直接开状态队列，因为那不是拓补序。要先把每个点的入度算出来再跑dp。结局是我的代码超长。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; #define mkword(x,y) (((x)<<16)|(y)) #define hiword(x) ((x)>>16) #define loword(x) ((x)&0x0000ffff) const int maxn = 1009; const int maxst = 1000009; const int inf = 0x3f3f3f3f; int n, m, st, te, deg[maxn], d[maxn], t[maxn][maxn], ind[maxn][maxn]; edge elst[maxn << 1], *ep(elst), *head[maxn]; double f[maxn][maxn], g[maxn][maxn], c[maxn], ans;...

<div class="post_brief"><p> 多少年前的坑了。</p>   用mac写的第一篇题解呢。   环套树DP。先把树上的情况处理了，然后枚举取不取环上的第一个。   要注意会有重边的情况，比较恶心。   #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4000; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; }...

<div class="post_brief"><p> 数据水。填坑。语文阅读题，看到都不想做。</p>   就一树形dp。f[i][j][k]表示第i个物品，上供j个，花k块钱的代价。背包转移是O(m2)的，因为是一棵树所以转移次数是O(n)的，但是还要考虑j最大为100。一个技巧是合并完所有的东西之后再考虑把上供的烧掉。虽然这样的复杂度还是有点高。   毕竟我还是太弱啊，居然又花了一个上午。（虽然睡到十点）   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; const int maxm = 2009; const int maxn = 53; const int maxa = 103; int n, m, f[maxn][maxa][maxm], ans[maxm], vl[maxn], vmax[maxn]; bool lf[maxn], ir[maxn]; edge elst[maxn], *ep(elst), *head[maxn]; inline void addEdge(int u, int v, int w) { ep-> t = v; ep-> v = w; ep-> next = head[u]; head[u] = ep ++; }...

<div class="post_brief"><p> 插头DP的基础题。想插头DP都是将军没走的时候给我讲的了，距今有大半年了吧。mhy已经写了无数道了，我才开始写。唉，还是效率太低。</p>   插头DP的意思是把已经处理的部分的轮廓线上对后面状态有影响的东西状压下来，然后挨着处理每个格子的状态（比如方向，或者这里的地板怎么铺之类的）。   具体到这道题来说，考虑一个相邻格子之前的边，那么它可能没有连接两个相同的磁砖，有可能连接了两个还没有拐过弯的磁砖，有可能连接了两个已经拐过弯的磁砖，一共是3种情况，所以用一个三进制数把它压下来。然后直接一路转移过去就行了。要注意的是每行都处理完了之后要把最边上的那一条从右移动到左，所以还需要把所有的状态都改一下。   今天效率比较低，心不在焉，然后在最后一个转移的地方wa了大半天。插头DP的调试也比较麻烦。所以我还是naive。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 13; const int maxa = 109; const int maxs = 200009; const int mod = 20110520; bool mp[maxa][maxa]; int n, m, a[maxn], b[maxn], f[2][maxs]; #define fc f[cur] #define fp f[prv] #define doNothing ; inline void mInc(int& a, int b) { a += b; if (a >= mod) a %= mod; }...