[UOJ 110][APIO2015]Bali Sculptures

第一次做subtask题= =其实这题也没啥难度吧

其实就是两个subtask……

对于第一个subtask,就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\),于是乎可以贪心,从高位枚举到低位,看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话,可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件,枚举断点\(O(n)\)转移。

第二个subtask,虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小,所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段,这样的话第二维就可以省掉了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
  bool d[105][105];
  bool dp(int bi) {
    memset(d, 0, sizeof(d));
    d[0][0] = true;
    for(int i = 1; i <= n; i ++) {
      for(int k = 1; k <= b; k ++) {
        for(int j = 0; j < i; j ++) {
          ll sum = S[i] - S[j];
          if((sum & (st | (1LL << bi))) == 0LL) {
            d[i][k] = (d[i][k] || d[j][k - 1]);
          }
        }
      }
    }
    for(int k = a; k <= b; k ++) {
      if(d[n][k]) return true;
    }
    return false;
  }
};
namespace Task2 {
  int d[maxn];
  bool dp(int bi) {
    d[0] = 0;
    for(int i = 1; i <= n; i ++) {
      d[i] = 0x3f3f3f3f;
      for(int j = 0; j < i; j ++) {
        ll sum = S[i] - S[j];
        if(!(sum & (st | (1LL << bi)))) {
          d[i] = std::min(d[i], d[j] + 1);
        }
      }
    }
    return (d[n] <= b);
  }
};

ll solve() {
  ll ans = 0;
  for(int i = maxb; i >= 0; i --) {
    bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
    if(flag) {
      st |= (1LL << i);
    } else {
      ans |= (1LL << i);
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &a, &b);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &Y[i]);
    S[i] = S[i - 1] + Y[i];
  }
  printf("%lld\n", solve());
  return 0;
}

[BZOJ 1009][HNOI2008]GT考试

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[UVa 10635]Prince and Princess

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到[tex][1,p+1][/tex],然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

[LA 3942]Remember the Word

Trie第一题……

首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~

代码:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int n;
vector<int> AnsList;
namespace Trie{
	const int maxnode=400005;
	const int sigma_siz=26;
	int Tree[maxnode][sigma_siz];
	int val[maxnode];
	int siz;
	inline int idx(char c){
		return c-'a';
	}
	inline void InitTrie(){
		siz=0;
		val[0]=0;
		CL_ARR(Tree[0],0);
	}
	void Insert(char *s,int v){
		register int u=0,n=strlen(s);
		register int i,c;
		REP(i,n){
			c=idx(s[i]);
			if(!Tree[u][c]){
				siz++;
				Tree[u][c]=siz;
				val[siz]=0;
				CL_ARR(Tree[siz],0);
			}
			u=Tree[u][c];
		}
		val[u]=v;
	}
	void Query(char *s,int len){
		register int i,c,u=0;
		AnsList.clear();
		REP(i,len){
			if(!s[i])
				break;
			c=idx(s[i]);
			if(!Tree[u][c])
				break;
			u=Tree[u][c];
			if(val[u])
				AnsList.push_back(val[u]);
		}
	}
};

char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}

[CF 710E]Generate a String

很不错的题。

很容易想到大爆搜:每搜索一个点,预处理只插入的深度,然后限制之。之后再加一些其他的剪枝。不过估计会炸。

然后有同学就想:那个删除操作真特么棘手啊……因为这个就用不了DP了……哎

不过,删除的目的是什么?下一步干啥?再插入?那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程(i11r的TeX插件好像不能排版多行公式,所以分两部分写吧):

[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]

[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]

然后问题就迎刃而解了。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
    ll n,x,y;
    cin>>n>>x>>y;
    register ll i;
    d[0]=0;
    REP(i,n+1)
        d[i]=x*i;
    REP(i,n){
        if(1&i){
            d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
        }else{
            d[i]=min(d[i-1]+x,d[i>>1]+y);
        }
    }
    cout<<d[n]<<endl;
    return 0;
}

[VIJOS P1037]搭建双塔

很不错的题啊……

很容易想到构造三维的状态,但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态,表示用前[tex]i[/tex]块水晶,搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。

转移的时候,要考虑放到高塔上还是低塔上,以及是否会导致高低塔地位对调。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
	int n,maxj=0;
	register int i,j,now,pre;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&V[i]);
		maxj+=V[i];
	}
	memset(d,-1,sizeof(d));
	d[0][0]=0;
	for(i=1;i<=n;i++){
		now=i%2;
		pre=1-now;
		for(j=0;j<=maxj;j++){
			if(d[pre][j]>=0)
				d[now][j]=d[pre][j];
			if(V[i]<=j){
				if(d[pre][j-V[i]]>=0){
					d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
				}
			}
			if(V[i]>j && d[pre][V[i]-j]>=0){
				d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
			}
			if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
				d[now][j]=max(d[now][j],d[pre][j+V[i]]);
		}
	}
	if(d[1&n][0]<=0)
		puts("Impossible");
	else
		printf("%d\n",d[1&n][0]);
	return 0;
}

[CodeVS 3269]混合背包

哎……现在才敢说真正会背包DP……

这个题可以分成三类问题分别处理,然后用一个一维数组一起递推。

0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高,可以考虑单调队列优化……然而窝太弱……不过还是用了

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && x>D.back())
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
int d[maxv];
int v;
void pack(int V,int W,int c){
	register int i,j,m;
	if(c==1){
		for(i=v;i>=V;i--)
			d[i]=max(d[i],d[i-V]+W);
	}else{
		if(c==-1){
			for(i=V;i<=v;i++)
				d[i]=max(d[i],d[i-V]+W);
		}else{
			c=min(c,v/V);
			for(i=0;i<V;i++){
				m=(v-i)/V;
				DQueue Q;
				for(j=0;j<=m;j++){
					if(Q.size()==c+1)
						Q.pop();
					Q.push(d[j*V+i]-j*W);
					d[j*V+i]=Q.top()+j*W;
				}
			}
		}
	}
}
int main(){
	register int i;
	int n,x,y,z;
	scanf("%d%d",&n,&v);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		pack(x,y,z);
	}
	printf("%d\n",d[v]);
	return 0;
}

[CodeVS 1044]拦截导弹

第一问很显然是最长不升子序列,直接DP即可。

第二问咋整?暴力?网络流?

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

[BZOJ 3831]Little Bird

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划,然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可,递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响,也不过是1,这样撑死也不会使答案更差

但凡是单调队列的题,都会有神秘细节,这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码:

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}

[洛谷 P2679]子串

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}