比较神奇的dp题.其实也不能算dp辣ovo 有一个神奇的事情是,塔的高度与底层的宽度是负相关的. 所以就变成了问塔底最窄的时候塔有多高. 用f[i]来表示用从第i个砖块到第n个砖块搭起来的塔的最窄底层宽度.用s[i]来表示宽度的前缀和,然后得到一个式子: f[i] = min(s[j-1]) - s[i - 1] (f[j] ≤ s[j - 1] - s[i - 1], j > i) s是单调的.看上去很像是dp呢. 然后就变成了求s[j - 1] - f[j] ≥ s[i - 1]时的最大的s[j - 1].于是开单调队列搞吧ovo
#include #include #include using namespace std; const int maxn = 100009; int n, a[maxn], sm[maxn], ans; int f[maxn], g[maxn], q[maxn], hd, tl; int main() { #ifndef ONLINE_JUDGE //freopen(".in", “r”, stdin); #endif scanf("%d", &n); sm[0] = 0; for (int i = 0; i < n; ++ i) { scanf("%d", a + i); sm[i + 1] = sm[i] + a[i]; } hd = 0, tl = 1, q[hd] = n; f[n] = 0, g[n] = 0; for (int i = n - 1; i >= 0; -- i) { while (hd + 1 < tl && sm[q[hd + 1]] - f[q[hd + 1]] >= sm[i]) ++ hd; f[i] = sm[q[hd]] - sm[i]; g[i] = g[q[hd]] + 1; while (hd < tl && sm[i] - f[i] >= sm[q[tl - 1]] - f[q[tl - 1]]) -- tl; q[tl ++] = i; } printf("%d\n", g[0]); }
好像是省选前最后一天在学校考试了ovo 第一题构造水. 第二题我以为是出题人丧心病狂卡常数,然后发现我比std多一个log.然后就和朴素一个分了不开心啊. 第三题神搜索ovo 然后不知不觉自己也站到最后一次省选的面前了.这么多年,感觉积累了好多东西,要在接下来的也许是几天也许是几个月里爆发. 当初年少无知的我以及现在虽然不年少但是还是无知的我.站在茫茫的时间轴上不知所措.心里想着远方,却没有找到脚下的路. 最初开始搞oi的时候并没有想过那些功利的东西.只是一种热爱罢了.但是经历了这么多之后,人总是会变的.于是也有了些背水一站的悲壮.其实如果不是为了做自己喜欢的事情,为什么要付出这么些东西? 未来是未知的.也许几天也不能再改变些什么了.要相信世界是科学的.然后淡定地去迎接挑战. 唉,我还是太弱了.
#include #include #include using namespace std; const int maxn = 200009; int n, tn, tr[maxn][26], ed[maxn], fl[maxn]; int m, pi[maxn], dl[maxn], r[maxn]; char a[maxn], g[maxn]; void trieIns(char* i) { int p(1), l(0); for (; *i; ++ i, ++ l) { int t(*i - 97); if (!tr[p][t]) { tr[p][t] = ++ tn; ed[tn] = 0; memset(tr[tn], 0, sizeof(tr[tn])); } p = tr[p][t]; } ed[p] = l; } void acaBuild() { static int q[maxn]; int hd(0), tl(1); q[0] = 1; while (hd < tl) { int u(q[hd ++]); for (int i = 0; i < 26; ++ i) if (tr[u][i]) { int v(tr[u][i]), w; for (w = fl[u]; w && !...
自从会了sam,似乎已经不知道acam该怎么写了ovo 这个题就是强行用ac自动机记录匹配到某个位置的时候的状态.然后如果走到一个终态的话就可以强行删掉一段,然后把当前状态变为上一个状态. 最初没有想到有可能会连续删除,于是挂了很久.最后用官网上的数据还是过不了第9个点,然后交bzoj居然过了.好神奇.我猜想是迅雷挂了hhh毕竟usaco的数据用wget根本搞不下来好伤心. 所以我还是太弱ovo
好奇怪的题ovo他们说难度太低ovo 第一题原来构造这么简单.我还是只会朴素+乱随机ovo遇构造题必出事的节奏啊不爽啊. 第二题居然是这么水的树剖. 第三题正解居然就是朴素ovo然后我乱写了个随机化缩小范围的玩意.如果在非windows下就能过ovo然后发现是windows随机数的范围问题.当时想到了然后想物品的范围是2k肯定没有问题.卧类个擦. 所以我还是太弱啊.马上都要省选了.怎么办啊ovo
idy居然会开1d-1d这个坑ovo之前听讲的时候也只是觉得很神奇,没有真正手写过,所以不明觉厉. 这个东西需要实际问题实际分析.总的思路就是利用决策的单调性. 对于这题,设f(x)=sqrt(x-j)+a[j].那么显然它是凸的.然后若干个它还可以拼成一个奇怪的凸壳状的分段函数.然后我们要取每段的极值.怎么有种半平面交的变形的感觉. 然后发现每次插入的函数的j单增,既x单增.于是只需要开一个双端出的队列就好了.然后每次二分一下两个函数的交的x坐标.其它时候可以完全单调性搞定. 然后算的时候用double会方便很多. 似乎很有意思啊hhh
#include #include #include #include using namespace std; const int maxn = 500009; int n, a[maxn], z[maxn], ans, sa[maxn], sr[maxn]; double sqa[maxn]; void pre(int n) { for (int i = 0, j = 0; j <= n; ++ i) for (; j <= i * i && j <= n; ++ j) z[j] = i; for (int i = 0; i <= n; ++ i) sqa[i] = sqrt(i); } inline double fi(int j, int i) { return a[j] + sqa[i - j]; } inline int fii(int j, int i) { return a[j] + z[i - j]; }...
明明就是usaco的水题嘛有啥好写的ovo只是想mark一下刚自己想出来的非递归的正常版的tarjan. 这题思路灰常简单.就tarjan缩scc然后在dag上找一下最长路就完了. 然后就是非递归的tarjan.考虑平时用栈建树的dfs序的方法,既把一个点的所有儿子扔进栈再递归.然而这个方法不能直接套进tarjan的dfs.因为它的一个儿子可能会对另一个儿子造成影响,有可能甚至直接改变dfs的顺序. 所以如果更新的时候一个点连出去的点还没有被访问,那么不管它是否已经在栈里,都再把它扔进去一次.这样就保证了访问的顺序.而在再次访问的时候只要判断一下是否已经访问就行了. 然后对于两个更新,首先如果直接low[p]=dfn[p]的话是不需要专门去用dfn来取min的.然后考虑倒着更新.每个点被退visit栈的时候去更新它的父亲就好.因为它的父亲一定还没有出栈.然后如果是只更新不递归那就直接访问. 这样的话空间复杂度会变成O(n+m),不过妈妈再也不用担心我暴栈了.而这个方法也比强行模拟系统栈要方便一些. 开心ovo
#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 200009; const int maxe = 300009; int n, m, vis[maxn], tscc, fs[maxn], cs[maxn], f[2][maxn]; int tpo[maxn], ind[maxn]; edge ebuf_arr[maxe], *ebuf(ebuf_arr), *head[maxn], *hg[maxn]; inline void addEdge(edge** head, int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } void tarjanDFS(int po) { static int stc[maxn], stv[maxn], stj[maxn], fr[maxn], d[maxn]; static int dfb[maxn], low[maxn]; int tst(1), dfn(0), tsv(0), tsj(0); vis[stc[tst] = po] = 1; fr[po] = 0; d[po] = 1; while (tst) { int p(stc[tst –]); if (dfb[p]) continue; for (; tsv && d[stv[tsv]] >= d[p]; – tsv) { int q(stv[tsv]); low[fr[q]] = min(low[fr[q]], low[q]); if (dfb[q] == low[q]) { cs[++ tscc] = 0; do { ++ cs[tscc]; fs[stj[tsj]] = tscc; vis[stj[tsj]] = 2; } while (stj[tsj –] !...