前言

NOIp2018即将来临,ZhYic踏上了每天水水水的道路。没有作业没有文化课没有卷子,有的只是每天一两题的龟速和时常的爆零、垫底。ZhYic虽然文化课也不是特别差劲(反正之前没全校垫底过),但OI还是想好好搞的,还是很珍惜水水水的机会的。为了吸取教训防止持续的爆零,ZhYic新开一篇博文记录一下抄题解的经历和理解。

正文

以下进入正文部分

CF467C George and Job

题意

给出一组有n个整数的数列$p_1,p_2,...,p_n$,你需要挑出k组长度为m的数,要求这些数互不重叠 即$[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1\le l_{1}\le r_{1}

题解

具体怎么想到的我记不清了(我怕不是阿尔茨海默症了)。

首先我们可以想到以dp[i][j]来表示数列的前i个位置中选择了j个子区间且以i为第j个子区间结尾的最大子区间和,容易列出转移方程为:

dp[i][j]=max(dp[i][j],dp[k][j-1]+sum[i-l+1][i])($k\in [1,i-l]$),

然后最终答案为dp[n][m],复杂度为$O(n^3)$。

然后思考如何优化dp。我们首先发现sum数组只需要用前缀和维护以下就好了,然后对于dp转移的过程,我们移项发现其实就是找一个区间最大值(dp[i][j]=max(dp[k][j-1])+sum就是找到1~i-l内最大dp值转移过来),所以思考一下可以怎么维护区间最大值。

由于n,m都很小,我们可以直接使用数组记录:mx[i][j]表示形成j了个子区间的最大子区间和。

其实是个假的,我们只需要一个一维mx数组即可,每次扫到一个新的i时用i-l的dp值更新mx数组(i-l及之前的dp都可转移过来),然后对每个dp[i][j]$O(1)$转移即可。总复杂度$O(n^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5020;
int n,m,l,p[N];
long long s[N],dp[N][N],mx[N];
int main()
{
    scanf("%d%d%d",&n,&l,&m);
    for(int i=1;i<=n;i++)scanf("%d",p+i),s[i]=s[i-1]+p[i];
    for(int i=1;i<=n;i++)
    {
        long long sum=s[i]-s[i-l];
        for(int j=1;j<=m&&j*l<=(i-l);j++)
            mx[j]=max(mx[j],dp[i-l][j]);
        for(int j=1;j<=m&&j*l<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],mx[j-1]+sum);
        }
    }
    printf("%lld",dp[n][m]);
}	

有线电视网

题意

有一棵树,树上有给定的点权(部分为正整数部分为0)及边权,问一颗点权和>边权和的子树最大是多大。

题解

思路

看到最优化就有几个方向:dp,二分,贪心。首先贪心是不存在的。其次二分是不能直接check的。那么很明显就是一道树形DP了。

首先可以想到用dp[i]表示一个节点i的子树内最大的子树点集,然后会发现这样DP不能转移,我们还需要中间状态(非局部最优)。考虑加一维变成dp[i][j]表示节点i的子树内花费为j时最大子树点集,看上去可以转移了,但看数据范围,j会很大,时空复杂度不满足。考虑换个状态,发现我们可以计算i的子树中选j个点时的最小花费即最大收益,这样就是一个树形背包DP,并且如果dp值非负则此状态可以达到。即dp[i][j]表示i的子树中选j个点的最大收益,最后check所有dp[1][i]值中大于等于0的最大的i,即为答案。

此题巧妙之处在于转换状态,通过合法性确定最优答案。存在合法性条件的dp很多都是此类做法。

时间复杂度问题

之前某大佬@BoBvix
打了个假的$O(n^2)$dp,他的dfs是这么个结构:

void dfs(int now) {
    size[now]=1;
    for(edges) {
        dfs(v);
        size[now]+=size[v];
    }
    for(edges) {
        for(size[now])
        	for(size[v])
        	dp[now][j]=......;
    }
}

这个dp的时间复杂度是错的,每个节点的复杂度为$O(son\cdot size^2)$,由于数据过水没卡掉。。。

实际上dfs结构应为

void dfs(int now) {
    size[now]=1;
    for(edges) {
        dfs(v);
        size[now]+=size[v];
        for(size[now])
        	for(size[v])
        	dp[now][j]=......;
    }
}

即每次更新当前节点子树大小时dp,这样dp的时间复杂度相当于枚举点对的复杂度(数学证明我再想想),为严格$O(n^2)$。

代码

#include<bits/stdc++.h>
#define Side(x) for(int i=p[x];i;i=nt[i])
using namespace std;
const int N=3020;
int n,m,ans,tot,e[N<<1],nt[N<<1],w[N<<1],p[N],tsize[N],a[N];
void add(int x,int y,int z){e[++tot]=y,nt[tot]=p[x],w[tot]=z,p[x]=tot;}
long long dp[N][N];
void dfs(int x)
{
    tsize[x]=1,dp[x][0]=0,dp[x][1]=a[x];
    Side(x)
    {
        dfs(e[i]);
        tsize[x]+=tsize[e[i]];
        for(int j=tsize[x];j;j--)
        {
            for(int k=min(tsize[e[i]],j);k;k--)
                dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[e[i]][k]-w[i]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(dp,-0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)a[i]=-INFINITY;
    for(int i=1,k;i<=n-m;i++)
    {
        scanf("%d",&k);
        for(int j=1,ai,ci;j<=k;j++)
            scanf("%d%d",&ai,&ci),add(i,ai,ci);
    }
    for(int i=n-m+1;i<=n;i++)scanf("%d",&a[i]);
    dfs(1);
    for(int i=1;i<=n;i++)if(dp[1][i]>=0)ans=i;
    printf("%d",ans);
}

 

CF5C Longest Regular Bracket Sequence

题意

给出一个括号序列,求出最长合法子串和它的数量。 合法的定义:这个序列中左右括号匹配。

题解

首先对于括号序列常用的一种括号匹配方法为:设'('=1,')'=-1,维护一个前缀和,相邻的前缀和相等的位置的括号匹配。因此此题基本思路由此而来。我们记录每个前缀和值上一次出现的位置,如果遇到相等的即更新答案。

但如何保证中间的括号合法(即不会出现刑如”)(())(“的子串)?

我们形象画图理解,以位置为x轴,前缀和为y轴,描点做出折线图,发现类似一种山峰状图形,当我们截取的左端点在”下坡“上(左端点为')')或右端点在”上坡“上(右端点为'(')一定不合法。还有若左端点及右端点间有低于左右端点的点也不合法(前缀和做差得到子串的前缀和,其中有的项<0)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000020;
char str[N];
int ans,cnt=1,s[N],lstt[N*2];
int *lst=&lstt[N];
int main()
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    for(int i=-n;i<=n;i++)lst[i]=INFINITY;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+(str[i]=='('?1:-1);
        if(s[i]>s[i-1])lst[s[i]]=min(i,lst[s[i]]);
        else
        {
            if(ans<(i-lst[s[i]+1]+1))ans=i-lst[s[i]+1]+1,cnt=1;
            else if(ans==i-lst[s[i]+1]+1)cnt++;
            lst[s[i]+2]=INFINITY;
        }
    }
    printf("%d %d",ans,cnt);
}

CF8C Looking for Order

一道老题,但也是一道好题。

题意

太长了,略。洛谷上有翻译,点上面标题就是了。

题解

乍看觉得需要dp[S][i][0/1]表示当前状态为S,当前选择的是i,包里还有0/1个空位,但这样不好写。

遂抄题解,发现题没看全。。。结合题面分析,每一趟若捡拾i、j花费为$dist_{0,i}+dist_{i,j}+dist_{j,0}$,若只捡了i花费为$dist_{0,i}+dist_{i,0}=dist_{0,i}+dist_{i,i}+dist_{i,0}$,这样我们发现捡1件物品和捡2件物品的花费其实是有通式的,因此可以全部当做捡2件物品来进行处理。

所以用dp[S]表示当前捡物品集合为S的最小花费,每次枚举两件未捡拾的物品(两物品可相同,捡未捡拾的物品一定比重复经过已经捡了的更优,因为两点之间线段最短不可能比两件物品相同更优),转移至dp[S|s1|s2],最后答案即为dp[U](U为全集符号)。

细节上,初始化dp数组为较大值,dp[0]=0,从0状态开始枚举(因为是顺推下一个状态转移,逆推上一个状态转移需要枚举子集,复杂度大了)。

最后复杂度为$O(2^n)$。

代码

#include<bits/stdc++.h>
#define pow(x) ((x)*(x))
using namespace std;
int n,x[30],y[30],dis[30][30],dp[1<<24],pre[1<<24],ans[2];
int dist(int a,int b)
{
    return dis[a][b]?dis[a][b]:(dis[a][b]=pow(x[a]-x[b])+pow(y[a]-y[b]));
}
int main()
{
    memset(dp,0x3f,sizeof(dp));
    scanf("%d%d%d",&x[0],&y[0],&n);
    int S=(1<<n)-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    dp[0]=0;
    for(int i=0;i<=S;i++)
    {
        if(dp[i]>=0x3f3f3f3f)continue;
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<(j-1)))continue;
            for(int k=j,now,nowval;k<=n;k++)
            {
                if(i&(1<<(k-1)))continue;
                now=(1<<(j-1))|(1<<(k-1)),nowval=dp[i]+dist(j,0)+dist(k,0)+dist(j,k);
                if(dp[i|now]>nowval)
                {
                    dp[i|now]=nowval,pre[i|now]=i;
                }
            }
            break;
        }
    }
    printf("%d\n",dp[S]);
    for(int i=S;i;i=pre[i])
    {
        int k=i^pre[i],pos=1,cnt=-1;
        while(k)
        {
            if(k&1)ans[++cnt]=pos;
            pos++,k>>=1;
        }
        if(!cnt)printf("%d %d ",0,ans[0]);
        else printf("%d %d %d ",0,ans[0],ans[1]);
    }
    putchar('0');
}

[SHOI2015]超能粒子炮·改

题解

$$\sum\limits_{i=0}^{i\le k}\binom{n}{i}\pmod{233}=\sum\limits_{i=0}^{i\le k}\binom{n\%p}{i\%p}\binom{n/p}{i/p}=\sum\limits_{i=0}^{i\le p-1}\binom{n\%p}{i}\cdot \sum\limits_{i=0}^{i\le \lfloor k/p\rfloor -1}\binom{n/p}{i}+\binom{n/p}{k/p}\cdot\sum\limits_{i=0}^{i\le k\%p}\binom{n\%p}{i}$$

(抄ViXbob.jpg)

然后我们定义$f_{k,n}=\sum\limits_{i=0}^{i\le k}C^i_n\pmod{2333}$,则上式可以变形为:$$f_{k,n}=f_{p-1,~n\%p}\cdot f_{\lfloor k/p\rfloor-1,~n/p}+\binom{n/p}{k/p}\cdot f_{k\%p,~n\%p}$$

根据Lucas定理简单地递推计算即可经过复杂计算即可。

前面i,j小于p的部分直接暴力计算,后面的利用上面推出的式子递归处理即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2336;
const long long p=2333;
int cmod[N][N],f[N][N];
long long Lucas(long long n,long long m)
{
    return !m?1:((long long)cmod[n%p][m%p]*Lucas(n/p,m/p))%p;
}
int F(long long n,long long k)
{
    if(k<0)return 0;
    if(k<p&&n<p)return f[n][k];
    return ((long long)F(n/p,k/p-1)*f[n%p][p-1]%p+(long long)f[n%p][k%p]*Lucas(n/p,k/p)%p)%p;
}
int main()
{
    int T;
    long long n,k;
    scanf("%d",&T);
    cmod[0][0]=1;
    for(int i=1;i<=p;i++)
    {
        cmod[i][0]=1;
        for(int j=1;j<=i;j++)
            cmod[i][j]=(cmod[i-1][j]+cmod[i-1][j-1])%p;
    }
    f[0][0]=1;
    for(int i=0;i<=p;i++)
    {
        f[i][0]=1;
        for(int j=1;j<=p;j++)
            f[i][j]=(f[i][j-1]+cmod[i][j])%p;
    }
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        printf("%d\n",F(n,k));
    }
}

[SDOI2010]地精部落

题意

求值域为[1,n]每个元素只出现一次的摇摆序列方案数(即每连续三个数中,相邻两数变化趋势相反)。

题解

不完全懂,待填坑

代码

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=4520;
int n,p,dp[2][N][2],ans;//dp[i][j][0] -> down dp[i][j][1] ->up
long long pls(int x,int y){return (int)((long long)x+y)%p;}
int main()
{
    scanf("%d%d",&n,&p);
    //p=1e9;
    //for(int i=1;i<=n;i++)dp[0][i][1]=1,dp[0][i][0]=1;
    //dp[0][0][0] = dp[0][0][1] = 1;
    dp[1][1][0] = dp[1][1][1] = 1;
    for(int i=2;i<=n;i++)
    {
        int t = i & 1, t0 = t ^ 1;
        memset(dp[t], 0, sizeof(dp[t]));
        /*for(int j=1;j<=i;j++)
        {
            dp[i][j][1]=pls(dp[i][j-1][1],dp[i-1][j-1][0]);
        }
        for(int j=i;j;j--)
        {
            dp[i][j][0]=pls(dp[i][j+1][0],dp[i-1][j+1][1]);
        }*/

        /*for(register int j = 1; j <= i; j++)
            for(register int k = 1; k < j; k++)
              f[t][j] = pls(f[t][j], f[t0][i - k]);
                                     g[t0][k]
                                     f[i][j] = g[i][i + 1 - k];
                                     */

        for(register int j = 1; j <= i; j++) {
            //for(register int k = 1; k < j; k++)
                dp[t][j][1] = pls(dp[t][j - 1][1], dp[t0][j - 1][0]);
        }
        for(register int j = 1; j <= i; j++) {
            dp[t][j][0] = dp[t][i + 1 - j][1];
        }
    }
    for(int i=1;i<=n;i++)
        ans=pls(ans,dp[n & 1][i][0]),ans=pls(ans,dp[n & 1][i][1]);
    cout<<ans;
}

[SDOI2009]学校食堂

题解

暴力的dp很好想到,直接状压表示所有人的吃饭状态,然后每次check状态合法性转移。

但,,,好吧出题人给了大概30?还是很良心的。

正解其实就是一种”trick of the trade“,由于存在Bi的限制,对于一个合法的状态,它的二进制表示必然是一段连续的1和一段长度不超过2×Bi的01序列,形如111...1110110001。这时我们会发现这个状态有一些特殊,我们发现转移时只会用到最后几位01交错的序列,而与前面许多连续1无关。于是考虑直接将前面的连续1用一维代替掉,计算一下复杂度,单点大约是$O(n\cdot2^{2Bi})$级别的,也许可以过?

考虑状态表示细节,我们每次由当前状态转移到下一个状态需要知道的是当前状态谁最后吃的,下一个状态该谁吃(因为这个dp是顺序相关的),所以还得再加一维记录每个状态最后进餐的人。因为最后进餐的人的可能位置只有Bi个,所以只需要表示出最后进餐人的相对位置就可以。最后得到的dp状态表示为dp[前面连续的已经用餐的人数i][从第i个人起2×Bi个人的用餐状态][当前用餐人员分布状态下最后一个用餐的人的相对(第i个人)位置]

解释一下第三维为什么是2×Bi:因为可能当前状态为111...1100...0,这时候的状态可能是由111...10111110...0转移而来的,即上一个状态的用餐者的相对位置为负值。

我们再考虑一个转移细节(这题细节真的多)。当前状态向下一个状态转移时有个双层循环枚举当前和下一个用餐者的过程,下一个用餐者不仅受到当前用餐者的限制,也受到中间的人的限制(中间的人也不允许后面某一距离外的人先进餐),因此我们需要在枚举下一个用餐者的过程中动态更新枚举范围,具体到代码上就是

for(k:-8...7)
	lim=7;
	for(j:0...lim)
	{
        if(not eaten)
        {
            dp[i][next state][j]=chkmin(dp[i][state now][k]+cal(...),...);
            lim=min(lim,j+B[i+j]);
        }
	}

所以最后时间复杂度为$O(n\cdot 2^{2Bi}\cdot Bi^2)$,空间复杂度为$O(n\cdot2^{Bi}\cdot 2Bi)$。

代码

#include<bits/stdc++.h>
#define pls(x,y) ((x)+(y)+P)%P
const int N=1020,P=12345678;
using namespace std;
int n,a[N],b[N],dp[N][1<<8][16];
int cal(int x,int y)
{
    return x<=0?0:(a[x]^a[y]);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&b[i]),b[i]=min(b[i],n-i);
        // dp[ status compress][status detail][cur eat]
        int U=(1<<8)-1;
        memset(dp,0x3f,sizeof(dp));
        dp[1][0][7]=0;
        for(int i=1;i<=n;i++)// status 1...i-1 1
        {
            for(int s=0;s<=U;s++)
            {
                for(int k=-8;k<=7;k++)
                {
                    if(dp[i][s][k+8]>1e9)continue;// status illegal
                    if(s&1)// can directly compress status
                    {
                        int &t=dp[i+1][s>>1][k+7];
                        t=min(t,dp[i][s][k+8]);
                    }
                    else for(int j=0,lim=7;j<=lim;j++)
                    {
                        if(!(s&(1<<j)))
                        {
                            int &t=dp[i][s|(1<<j)][j+8];
                            t=min(t,dp[i][s][k+8]+cal(i+k,i+j));
                        lim=min(lim,j+b[i+j]);// ?
                        }
                    }
                }
            }
        }
        int ans=INFINITY;
        for(int i=0;i<=7;i++)ans=min(ans,dp[n+1][0][i]);
        printf("%d\n",ans);
    }
}