ZJT's Blog

Keep your determination.

集训队作业之ARC083-E

2017-11-2 11:422017-11-2 11:42
集训队作业AtCoder背包DP树形DP

传送门

显然在一种颜色权值和确定的情况下,另一种的权值和要尽可能小才最优。所以直接DP一下,$f_i$表示$i$的子树里面和$i$颜色不同的权值和最小是多少,转移的时候直接背包一下就行了。如果哪一步背包装不下了,就可以直接判无解了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1010
#define MAXM 5010
using namespace std;

int n;
int p[MAXN],a[MAXN],b[MAXN],f[MAXN][MAXM];

bool gao(int x){
    int temp=-1;
    for(int i=0;i<=a[x];i++)
        if(f[x][i]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[x][i]);
    if(temp==-1) return 0;
    b[x]=temp;
    return 1;
}

void trans(int x){
    int y=p[x];
    for(int i=a[y];i>=0;i--){
        int temp=-1;
        if(i>=a[x] && f[y][i-a[x]]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[y][i-a[x]]+b[x]);
        if(i>=b[x] && f[y][i-b[x]]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[y][i-b[x]]+a[x]);
        f[y][i]=temp;
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",p+i);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=n;i>=1;i--){
        if(!gao(i)){
            puts("IMPOSSIBLE");
            return 0;
        }
        if(i>1) trans(i);
    }
    puts("POSSIBLE");
    return 0;
}

查看详细内容

17.10.10 NOIP模拟赛

2017-10-10 15:142017-10-13 12:56
背包DP后缀自动机

最近校内开始打联赛模拟题了。感觉一直做散题可能会找不到打比赛的感觉,于是就随便打了一场。

比较正常的联赛难度,花了1.5h AK(加上各种对拍接近2h)。感觉状态还是在的,就怕真的到了场上又是另外一个样子了。。。


T1

题意是给$n$个数,$n\leq500$,让你用这些值排出一个序列,使得满足斐波那契序列的性质($f_n=f_{n-1}+f_{n-2}$)。

没啥难度,直接枚举前两个数,由于fib序列的值是指数级的,所以这个序列会比较短,直接暴力一个个往后找就行了。


T2

让你构造一个$n$个字母的排列($n\leq26$),使得这个排列的第$k$小子串为给定串。

由于是个排列,所以子串的顺序比较好确定。转化模型之后就变成了一个背包,直接枚举给定子串出现位置后$O(n^4)$瞎DP就行了,总复杂度$O(n^5)$。


T3

给一个字符串(长度$2\times10^5$内),让你统计有多少个本质不同的子串,满足这个子串循环左移一位后依然是该字符串的子串。

SAM裸题,跑出SAM之后直接考虑每个状态的可行转移,根据字符左端点在不在该状态内,分两种情况统计一下就行了(一种是左端字符还在该状态内,另一种是怼到parent树中的别的儿子的状态里面去了,需要另外统计一下)。

查看详细内容