题目链接：

http://poj.org/problem?id=3040

https://www.lydsy.com/JudgeOnline/problem.php?id=1685

某普及模拟赛搬了这题，题解是贪心，我不会证还找不到证明。于是想了挺久然后证出来了。

贪心做法：

每次选出一个体积和 $\ge C$ 的物品集合，直到剩下物品体积和不足 $ < C $ 为止。

每次选择方法：

1.按 $v$ 从大到小枚举每个物品，在保证体积和 $< C $ 的情况下能选多少选多少。

2.将还存在的 $v$ 最小的物品加入选择的集合。显然加了之后体积和 $\ge C$ 。

证明：

假设 $v_{1..n}$ 递增。

首先，如果在第二步中选择的物品不是 $1$ ，设它为 $i$ 。

设第一步中选择的 $i..n$ 的物品的体积和为 $k v_i$ ， $1..i-1$ 的和为 $z$ 。

由第一步的定义得 $k v_i +z < C$ 。

因为第一步枚举到 $i$ 的时候没有多选一个 $i$ ，所以 $(k+1) v_i \ge C$ 。

因此体积和是否 $\ge C$ 跟物品 $1..i-1$ 无关，可以把他们都丢掉，即只考虑物品 $i..n$ 。

这样操作后第二步选择的物品就一定是 $1$ 了。

然后，将所有 $v_i$ 变成 $\displaystyle \frac{v_i}{v_1}$，并将 $C$ 变成 $\lceil \displaystyle \frac{C}{v_1} \rceil$ ，这样操作就使得 $v_1=1$ 。

于是可以发现，第一步选的物品体积和恰为 $C-1$ ，第二步之后物品体积和恰为 $C$ 。

用 $f_{1..n}$ 来描述一个物品集合，表示这个集合中物品 $i$ 有 $f_i$ 个。

假设贪心法得到的下一个选择为 $f$ ，但下一个选择为 $g$ 能得到更优的答案(称 $g$ 为反例)。

令 $p=\max\{i|f_i \not= g_i\}$ 。

情况 $1:$ $g_p < f_p$

因为 $\sum_{i=1}^{n} f_i v_i=C$,$\sum_{i=1}^{n} g_iv_i \ge C$ ，所以 $\sum_{i=1}^{n} g_iv_i \ge \sum_{i=1}^{n} f_iv_i$

所以 $\sum_{i=1}^{p} g_iv_i \ge \sum_{i=1}^{p} f_iv_i$ ，又因为 $g_p < f_p$ ，所以 $\sum_{i=1}^{p-1}g_iv_i \ge \sum_{i=1}^{p-1}f_iv_i+v_p$ 。

所以 $\sum_{i=1}^{p-1}g_iv_i \ge v_p$ 。

那么就一定能选出一个 $g_{1..p-1}$ 的子集 $s$ 满足和为 $v_p$ ，归纳一下就可以证明。

显然不选 $s$ 而多选一个 $p$ 肯定更优。

那么由 $g$ 为反例就可以推出 $g-s+\{p\}$ 为反例。归纳证明即可。

情况 $2:$ $g_p >f_p$

由第一步 $p$ 没有多选一个知 $\sum_{i=p}^{n} f_iv_i+v_p \ge C$

那么不妨令 $g_{1..p-1}=0,g_p=f_p+1$ ，因为由 $g$ 为反例可以推出这样操作后的 $g$ 为反例。

那么既然现在 $1..p-1$ 都不用，那么不妨令以后也都不用了，不然就会得到一个最小非零元素更小的反例，归纳证明即可。

那么只用 $p..n$ 的话 $f$ 显然优于 $g$ ，因为少用了一个 $p$ 。

因此就证完了。

我曾经在 uoj blog 问过，非常幸运的有两个大神给了解答，但当时我对于 pengyihao's blog 中答案式子(即 $f(n)$ )的推导搞不懂(他自己也忘了)。最近有学弟问，于是证了一下。

首先考虑证明贪心法每次的决策是唯一的，即每次能选的柱子只有 $0$ 或 $1$ 个。

定义 $h(x)=\min\{a | a^2 \ge 2x+1\}$ ，那么第一个能放在 $x$ 上面的数就是 $h(x)^2-x$ 。

显然，$h(x)^2-x$ 互不相同 $(x \in N^ * )$ 和原命题等价。

考虑单调性， $h(x)^2-x$ 并不单调。

但 $h(x)$ 是单调的，对于固定的 $h(x)$，对应的 $x$ 是一个区间，因此 $h(x)^2-x$ 也是一个区间，考虑证明这些区间单调，不相交。

也就是说第 $x$ 个区间的左端点 $>$ 第 $x-1$ 个区间的右端点，即 $x^2-\max\{ i_x | h(i_{x})=x \}>(x-1)^2-\min\{ i_{x-1} | h(i_{x-1})=x-1 \}$ 。

定义 $g(x)=\lfloor \frac{x^2-1}{2} \rfloor$ ，即 $\max\{y|h(y)=x\}$ 。

则上式等价于 $x^2-g(x)>(x-1)^2-(g(x-2)+1)$ 。

化简得 $0>-2$ 。

注意到这里用到了 $g(x-2)$ ，所以 $x=2$ 要特判：$3>0$。

所以得证。

同时可以发现每两个区间之间恰好隔着一个数，所以所有没柱子可选的数为 $\{x^2-g(x)-1 | x \ge 2 \} \bigcup \{1\}$ 。

因此 $f(n)$ 就是第 $n+1$ 个没柱子可选的数$ -1=((n+1)^2-g(n+1)-1)-1$，化简得 $\lfloor \frac{n^2+1}{2} \rfloor+n-1$ 。

求出 $f(n)$ 以后需要证明 $f(n)+1$ 是不可行的，注意到最大的 $n+1$ 个数两两无法得到完全平方数即可。

这是$jhr$优化得到的.

首先把求方差转化为求$E(x)$和$E(x^2)$($x$表示某个方案经过的不同位置数,$E$表示期望)

定义$f(i,x,y)$表示第$i$天第一次到达$(x,y)$的概率,$g(i,x,y)$表示第$i$天到达$(x,y)$的概率.

$g$很好算,$f$用$g$容斥一下就可以算了.

$E(x)$只用对$f$求和就好了.

$x^2=2{x \choose 2}+x$,所以$E(x^2)$转化为求$E({x \choose 2})$,然后就转化为$\sum_{x,y} x,y$都被经过的概率.

定义$h(i,x,y)$表示第$i$天第一次到达了一个点$(a,b)$,且之前经过了$(a-x,b-y)$的所有情况的概率和.

答案就是对$h$求和.

怎么计算$h(i,x,y)$呢?

先考虑$\sum_{j < i,a,b} f(j,a,b) \times f(i-j,x,y)$

它多算的情况就是,在经过$(a,b)$之前就已经经过了$(a+x,b+y)$

再减去$\sum_{j < i} h(j,-x,-y) \times f(i-j,x,y)$就好了.

时间$O(n^4)$

代码http://uoj.ac/submission/265113

令$s_{r}(i)$表示题面中的$s(i,r)$

注意到,对于一个$r$,$s_{r}(i)$不会超过$\sqrt m$种

从左到右枚举$r$,线段树维护$s_{r}$,然后再在线段树上$dfs$计算以$r$右端点的答案,就是当一个区间的$s_{r}(i)$一样时直接$check$一下区间左端点然后返回.

具体怎么维护线段树,就是枚举到$i$的时候

先令$s_{i}=s_{i-1}$,然后对于每个$j$,$s_{i}(1..j)$都对$abs(a_{i}-a_{j})$取$min$

但实际上有可能更新的$j$只有$log(m)$个

因为考虑$a_{j}>a_{i}$的情况,假设所有可能的$j$从大到小是$j_{1..m}$,则有$2 (a_{j_{k+1}}-a_{i}) < a_{j_{k}}-a_{i}$.

时间$O(nlog^2)+O(n \sqrt m log \frac{n}{\sqrt m} ))$

后面这个东西虽然带$log$但常数比较小(把线段树换成平衡树好像就不带$log$了)

代码:http://uoj.ac/submission/264123

http://uoj.ac/contest/36

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1825

好久之前的坑.今天想了一下,忽然发现了一个简单做法.

记两个串为$a,b$,长度为$n,m$

设$dp[i][j]$表示$a_{1..i}$和$b_{1..j}$的$lcs$

考虑从$1$到$m$枚举$h$,动态维护无视$b_{1..h}$的$dp$数组(也就是$dp[i][j]$表示$a_{1..i}$和$b_{h+1..j}$的$lcs$)

假如现在枚举到$h$,对于$h$这一列,第一个变化的$dp[i][h]$必定满足$a[i]==b[h]$,并且$dp[i..n][h]$全部会减$1$.

再依次考虑列$h+1,..m$的变化,可以发现每一列变化的都是一个后缀,并且不长于前一列.

所以枚举每一列,维护后缀长度即可.

现在唯一的问题就是判断一个点可以从哪里转移过来.

每次变化的转移边只有轮廓上那些,所以可以轻松维护.

时间$O(n^2)$

(然而被卡常了...不是很懂为什么$n^2$要出成$5000$)

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T&x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc

const int N=5000+5,D=998244353;
bool fr[N][N][3];
char s1[N],s2[N];
int dp[N][N],dpn[N];

int main()
{
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    scanf("%s%s",s1+1,s2+1);
    int n=strlen(s1+1),m=strlen(s2+1);
    rep(i,1,n)
    rep(j,1,m)
    {
        int a=dp[i][j-1],b=dp[i-1][j-1]+(s1[i]==s2[j]),c=dp[i-1][j];
        dp[i][j]=max(max(a,b),c);
        fr[i][j][0]=a==dp[i][j];
        fr[i][j][1]=b==dp[i][j];
        fr[i][j][2]=c==dp[i][j];
    }
    rep(j,1,m)dpn[j]=dp[n][j];
    s64 ans=0;
    rep(h,1,m)
    {
        rep(j,h,m)ans=(ans*233+dpn[j])%D;
        int i=1;
        while(fr[i][h][0]||fr[i][h][2])++i;
        if(i>n)continue;
        rep(j,h+1,m)
        {
            if(!fr[i][j][1]&&!fr[i][j][2])fr[i][j][1]=fr[i][j][2]=1;
            else
            {
                fr[i][j][0]=0;
                while(++i,fr[i][j][2])fr[i][j][0]=fr[i][j][1]=0;
                if(i>n)break;
                fr[i][j][2]=1;
            }
            --dpn[j];
        }
    }
    cout<<ans;
}

令$ans_{l}(r)$表示$[l,r]$的答案,$dy(l)$表示$\min r$满足$[l+1,r-1]$可以消除

当$dy(l)$不存在时,$ans_{l}(r)=ans_{l+1}(r)$

否则,当$r < dy(l)$时,$ans_{l}(r)=ans_{l+1}(r)$;当$r \ge dy(l)$时,$ans_{l}(r)=ans_{dy(l)+1}(r)+ r-l+1$

可持久化线段树即可.

时间$O((n+q)log_{2}n)$

代码:http://uoj.ac/submission/261655

可能是省选退役前的最后一次$51nod$了

前两题水的吧

后面四题我貌似都跟题解不一样。。

$C$

首先让点$x$为随便一个端点

让点$y$使$x,y$将多边形长度分成两半

然后一直旋转，每次让距离下一个端点比较近的点移动到下一个端点

令$S$为指定的某一侧的面积

感觉它说不定可以二分

如果一次移动使$S$从小于一半变成大于一半就二分找出答案。

如果能做到两边$S$都会大于一半，但中间$S$小于一半我就错了。不知道能不能卡

复杂度$O(n+log)$

$D$

特判$2$

剩下的质数都是奇数

枚举右端点，枚举区间长度，发现左端点是隔着一个的连续的

就是说把点按奇偶分类后左端点是一个连续的区间

维护前缀和$O(1)$算

$O(n^2/logn)$

卡卡常就过了

$E$

考虑询问时枚举比较小的集合，在大的集合里$O(1)$找到前驱后继

那么如果对大于根号的集合两两求出答案，询问就是根号的

对于合并集合操作

如果合并后大于根号的话是要更新跟所有大于根号的集合的答案的

此时如果原来就大于根号的话是可以直接用原来信息的

如果原来小于根号的话就暴力枚举，$O(1)$找前驱后继

复杂度还是$n$根号

现在问题就是支持合并两个集合，$O(1)$询问某个集合中某个数的前驱后继

考虑用类似线段树合并的方法合并值域分块

就是把分块看成三层线段树的话，第二层暴力合并，叶子只有在两个都非空的时候合并

复杂度$n$根号

可能因为常数比标算大，卡常后才能过。

$F$

后缀数组水题

假如是一个字符串的话

枚举每个后缀

设长度为$len$,跟所有未枚举后缀的$lcp$长度为$mx$

它的贡献就是长度在$[mx+1,len]$的前缀

小于$k$的暴力

大于$k$的是一个区间，$O(1)$算

多个串是类似的

复杂度为$O(构建后缀数组)+O(n*k)$

$upd$

$C$正解性好像能证。。

其实就是跟题解一个证法

就是存在$f(x1)>0,f(x2)<0$的话，一定存在$f(x+1)>0,f(x)<0$

($f(x)$只是表达个大概的意思)

最后的盒子一定是前面一段没贡献，中间一段有贡献，后面一段没贡献。

那么$b_{i}=0$的$a_{i}$的作用就是放在前面一段，$dp$求出哪些前缀是可以被他们摆出，然后就可以丢掉他们了。

设将$b_{i}=1$的$a_{i}$排序后为$na_{1},..na_{nn}$

设中间有贡献的那一段为$v_{1},v_{2},..v_{m}$

可以发现，$v_{1},v_{2}..v_{m-1}$一定是$na_{1},na_{2},..na_{m-1}$,而$v_{m}$只要是$na_{m},..na_{nn}$中的一个就可以了。

因为如果有一个是更大的，换成更小的一定不会变劣。

那么我们就从后往前$dp$,$dp_{i,0/1,j}$表示到了第$i$个，是否有$na$没选，能否摆出长度为$j$的前缀。

用$bitset$优化，复杂度$O(n^{2}/32)$

官方题解好像说能$O(n \sqrt{n})$，我不知道怎么做。

(而且我还没看见$O(n \sqrt{n})$的代码，不然我也不能拿下时间$rank1$了)

代码:http://codeforces.com/contest/956/submission/36681265