lemonoil


OI__nothing is impossible


dp专题

220分,加上long long 成320分。。。无语,果真需要更加细致地分析数据啊!!!

天平(balance.in/balance.out)

这里写图片描述 物理老师YJ有一个长杆天平,天平的两臂长均为15,将长杆看作x轴,则平衡点在0位置处,负数位置在左臂上,正数位置在右臂上。长杆上有n个位置有挂钩可以挂秤砣。YJ有m个秤砣,质量分别为gi,每个挂钩可以不挂也可以挂任意个秤砣。YJ想要知道,在使用所有秤砣的条件下,有多少种不同的挂秤砣的方案,可以使得天平平衡?问题太过复杂,仅凭物理知识难以解决,所以请你来帮助他。 天平的平衡条件是所有秤砣的位置质量之和为0。例如有质量为2,3,4的秤砣分别挂在-3,-2,3位置处,则2(-3) + 3*(-2) + 4*3 == 0,天平是平衡的。 【输入格式】 第一行两个数n,m。表示挂钩的数目和秤砣的数目。 第二行n个不同且递增的数,第i个数表示第i个挂钩的位置,数的范围在[-15,15]内。 第三行m个不同且递增的数,第i个数表示第i个秤砣的质量,数的范围在[1,25]内。 【输出格式】 一个整数,代表能使得天平平衡的方案数。

【输入样例】 2 4 -2 3 3 4 5 8 【输出样例】 2

【样例解释】 方案1: (-2)*(3+4+5) + 3 8 = 0 方案2: (-2) (4+8) + 3 *(3+5) = 0 【数据规模】 10% 数据满足2≤n,m≤4。 100% 数据满足2≤n,m≤20。

题解

简单的DP。 考虑天平的状态可以用秤砣质量距离来表示,而题目情况下,天平的全部秤砣质量距离在(-7500,7500)(20* 2515 = 7500)以内。故可以以此状态来dp。 类似背包问题,把每一个秤砣挂在不同地方,对应成nm个物品,转移方程f[i][j]+=f[i-1][j-dis[k]*mg[i]] (i=1..n,j=0..15000,k=1..m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cstdio>
#define NAME "balance"
using namespace std;
int n,m,c[100],w[100];
long long dp[30][15001];
inline void readin(int &resez) {
static char ch;int flag=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ ch-48;resez*=flag;
}
int main(){
freopen(NAME".in","r",stdin);
freopen(NAME".out","w",stdout);
readin(n),readin(m);
for(register int i=1;i<=n;i++)readin(c[i]);
for(register int i=1;i<=m;i++)readin(w[i]);
dp[0][7500]=1;
for(register int i=1;i<=m;i++)
for(register int j=0;j<=15000;j++)
if(dp[i-1][j])for(register int k=1;k<=n;k++)
dp[i][j+w[i]*c[k]]+=dp[i-1][j];
cout<<dp[m][7500]<<endl;
return 0;
}

山峰数(hill.in/hill.out)

这里写图片描述 山峰数是指数字排列中不存在山谷(先降后升)的数,例如0,5,13,12321都是山峰数,101,1110000111都不是山峰数。 现给出n个数,请依次判断它们是否为山峰数,如果不是,输出-1。如果是,求出比它小的数中有多少个山峰数。 【输入格式】 第一行一个数n,表示询问数目。 接下来n行,每一行一个数x,表示询问的数。 【输出格式】 输出有n行,x如果不是山峰数,输出-1。x如果是山峰数,则输出有多少个比它小的山峰数。

【输入样例】 5 10 55 101 1000 1234321 【输出样例】 10 55 -1 715 94708

【数据规模】 20% 数据满足x ≤ 10^6。 100% 数据满足n ≤ 10, x ≤ 10^60

题解

数位DP 在数位dp的模板基础上,加入参数nu和isdown,nu表示上一个数填的多少,isdown表示当前是在上升期还是在下降期,然后使用模板记忆化搜索即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define NAME "hill"
using namespace std;
int T;
ll dp[77][11][2];
char s[77];
inline void readin(int &resez) {
static char ch;int flag=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ ch-48;resez*=flag;
}
ll dfs(int pos,int pre,int state,int fp){
if(pos<0)return 1;
if(!fp&&dp[pos][pre][state]!=-1)return dp[pos][pre][state];
ll ans=0;
int fpmax=fp?s[pos]-'0':9;
if(state){
for(register int i=0;i<=min(fpmax,pre-1);i++)
ans+=dfs(pos-1,i,0,fp&&i==fpmax);
for(register int i=pre;i<=fpmax;i++)
ans+=dfs(pos-1,i,1,fp&&i==fpmax);
}
else{
for(register int i=0;i<=min(fpmax,pre);i++)
ans+=dfs(pos-1,i,0,fp&&i==fpmax);
}
if(!fp)dp[pos][pre][state]=ans;
return ans;
}
int main(){
freopen(NAME".in","r",stdin);
freopen(NAME".out","w",stdout);
memset(dp,-1,sizeof(dp));
readin(T);
while(T--){
scanf("%s",s);
int len=strlen(s),flag=0,gg=0;
for(register int i=0,j=len-1;i<j;i++,j--)swap(s[i],s[j]);
for(register int i=0;i<len-1;i++){
if(s[i]<s[i+1]&&flag){
gg=1;
break;
}
if(s[i]>s[i+1])flag=1;
}
if(gg)printf("-1\n");
else printf("%I64d\n",dfs(len-1,0,1,1)-1);
}
return 0;
}

粉刷匠2(draw.in/draw.out)

这里写图片描述 有一个4*N的木板需要粉刷,第i行j列的颜色记为A(i, j)。 有256种颜色,记为0..255,为了使得粉刷比较好看,粉刷需要满足如下要求:

  1. A(x,y) >= A(x,y-1)
  2. 有一些指定的(x1, y1)和(x2, y2),要求A(x1, y1) = A(x2, y2) 请问有多少种满足要求的粉刷方式?输出答案的最后5位即可。 【输入格式】 第一行两个数n, m,表示木板的长度,和指定规则的条目个数。 接下来m行,每行四个数x1,y1,x2,y1,此规则表示A(x1, y1) 需要等于 A(x2, y2) 。 【输出格式】 一个整数,表示答案的末5位。

【输入样例1】 1 0 【输出样例1】 67296 【输入样例2】 1 3 1 1 2 1 1 1 3 1 4 1 3 1 【输出样例2】 00256

【提示】 5 输出可以使用%05d输出。 【数据规模】 30% 数据满足 n ≤ 3,m = 0。 100% 数据满足1 ≤ n ≤ 15,0 ≤ M ≤ 100,X1,X2≤4,Y1,Y2≤n

题解

30分的做法:dp[i][c1][c2][c3]表示第i行,第一列填到c1,第二列填到c2,,第三列填到c3的方法总数。转移时如果暴力枚举转移仍然会TLE,需要使用完全背包的降低维度思想,列出转移方程:dp[i][c1][c2][c3]= dp[i-1][c1][c2][c3] + dp[i] [c1-1][c2][c3] + dp[i] [c1][c2-1][c3] + dp[i][c1][c2][c3-1]。这样才不会TLE。 100分的做法:换一种dp思路,我们不按照常规思维枚举行列,而是从小到大枚举颜色。若当前枚举到的颜色为i,我们使用dp[l1][l2][l3][l4]表示每一行使用当前颜色涂到哪一个位置。 假设有一行现在是123344556,现在涂7,显然涂7只能涂序列的后缀,比如涂成123777777,或者123344577才能符合条件。所以考虑枚举当前颜色涂到哪个后缀来转移,转移时同样需要使用完全背包的降维思想优化。 对于限制条件,我们需要把不符合限制条件的去掉,什么样的方案符合限制条件呢?对于限制条件A(x1, y1) = A(x2, y2),和当前枚举到的颜色i,要么x1行和x2行,当前颜色都涂到了y1,y2位置,要么都没有涂到y1,y2位置。除此之外的都是不合法的方案,我们事先处理好一个vis数组,vis[l1][l2][l3][l4]表示四行分别涂到l1,l2,l3,l4,是否可行,在dp时如果遇到标记不可行的vis,这dp值设为0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<iostream>
#define res(i,x) for(register int i=1;i<=x;i++)
#define rek(i,x) for(register int i=0;i<=x;i++)
#define rez(i,x) for(i=0;i<=x;i++)
#define ll long long
using namespace std;
int f[16][16][16][16];
bool vis[16][16][16][16];
int x1[105],x2[105],y1[105],y2[105];
int n,m,c[4];
inline void readin(int &resez) {
static char ch;
while ((ch = getchar()) < '0' || ch > '9');resez = ch - 48;
while ((ch = getchar()) >= '0' && ch <= '9')resez = resez * 10 + ch - 48;
}
int main(){
freopen("draw.in","r",stdin);
freopen("draw.out","w",stdout);
readin(n),readin(m);
res(i,m){
readin(x1[i]),readin(y1[i]),readin(x2[i]),readin(y2[i]);
x1[i]--;x2[i]--;
}
res(i,m)rez(c[0],n)rez(c[1],n)rez(c[2],n)rez(c[3],n){
if(c[x1[i]]>=y1[i] ^ c[x2[i]]>=y2[i])
vis[c[0]][c[1]][c[2]][c[3]]=1;
}
f[0][0][0][0]=1;
rek(color,255){
rek(col,3)rez(c[0],n)rez(c[1],n)rez(c[2],n)rez(c[3],n)
if(c[col]<n){
int tmp=f[c[0]][c[1]][c[2]][c[3]];
c[col]++;
f[c[0]][c[1]][c[2]][c[3]]=(f[c[0]][c[1]][c[2]][c[3]]+tmp)%100000;
c[col]--;
}
rez(c[0],n)rez(c[1],n)rez(c[2],n)rez(c[3],n)
if(vis[c[0]][c[1]][c[2]][c[3]])
f[c[0]][c[1]][c[2]][c[3]]=0;
}
printf("%05d\n",f[n][n][n][n]);
return 0;
}

棋盘(knight.in/knight.out)

这里写图片描述 有一个N*M的棋盘,要在上面摆上knight,每个格子可以放至多一个knight。 knight的攻击范围如下图: 这里写图片描述 所有knight不能互相攻击,请问总共有多少可行的摆法?答案对1000000007取模。 【输入格式】 第一行个数t,表示测试的组数。 接下来t组,每组两个整数,n和m。 【输出格式】 一共t行,第i行表示第i组的答案。

【输入样例】 4 1 2 2 2 3 2 3 31415926 【输出样例】 4 16 36 933912086

【数据规模】 70% 数据满足m≤100。 100% 数据满足t≤10, n≤3, m≤10^9。

题解

n非常小,所以考虑状态压缩动态规划,每一行使用一个二级制串表示当前行的摆knight情况。用f[i][j][k]表示第i行,前一行为j,前一行的前一行为k时的方法总数,转移时枚举三行的状态,判断合法情况转移即可。 如果枚举每一行转移,可以得70分。如果将状态转移矩阵化,使用矩阵快速幂,可以通过全部测试数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstring>
#include<cstdio>
#define NAME "knight"
#define MOD 1000000007
#define ll long long
using namespace std;
#define maxn 256
#define mod 1000000007ll
struct Matrix{
int Matrix[maxn][maxn];//矩阵
int row,col;//矩阵行列数
};
Matrix mod_mul(Matrix a,Matrix b,ll p){//矩阵乘法
Matrix ans;
ans.row=a.row;
ans.col=b.col;
memset(ans.Matrix,0,sizeof(ans.Matrix));
for(int i=0;i<ans.row;i++)
for(int k=0;k<a.col;k++)
if(a.Matrix[i][k])
for(int j=0;j<ans.col;j++)
{
ans.Matrix[i][j]+=1ll*a.Matrix[i][k]*b.Matrix[k][j]%p;
ans.Matrix[i][j]%=p;
}
return ans;
}
Matrix mod_pow(Matrix a,int k,ll p){//矩阵快速幂 昨天才打的。。。。
Matrix ans;
ans.row=a.row;
ans.col=a.col;
for(int i=0;i<a.row;i++)
for(int j=0;j<a.col;j++)
ans.Matrix[i][j]=(i==j);
while(k){
if(k&1)ans=mod_mul(ans,a,p);
a=mod_mul(a,a,p);
k>>=1;
}
return ans;
}
int T,n,m,a[5][5];
void deal(int x){
for(int i=0;i<3*m;i++)
if(x&(1<<i))a[i/m][i%m]=1;
else a[i/m][i%m]=0;
}
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={-1,1,-2,2,-2,2,-1,1};
bool check(){
for(register int i=0;i<3;i++)
for(register int j=0;j<m;j++)
if(a[i][j])for(register int k=0;k<8;k++){
int ii=i+dx[k],jj=j+dy[k];
if(ii<0||ii>=3||jj<0||jj>=m)continue;
if(a[ii][jj])return 0;
}
return 1;
}
Matrix A,B;
inline void readin(int &resez) {
static char ch;
while ((ch = getchar()) < '0' || ch > '9');resez = ch - 48;
while ((ch = getchar()) >= '0' && ch <= '9')resez = resez * 10 + ch - 48;
}
int main(){
freopen(NAME".in","r",stdin);
freopen(NAME".out","w",stdout);
readin(T);
while(T--){
readin(m),readin(n);
if(n==1){
printf("%d\n",1<<m);
continue;
}
int M=1<<(m<<1),N=1<<(3*m);
B.row=M,B.col=1;
for(register int i=0;i<M;i++){
deal(i);
B.Matrix[i][0]=check();
}
A.row=A.col=M;
memset(A.Matrix,0,sizeof(A.Matrix));
for(register int i=0;i<N;i++){
int x=i>>m,y=i&(M-1);
deal(i);
if(check())A.Matrix[x][y]=1;
}
A=mod_pow(A,n-2,mod);
A=mod_mul(A,B,mod);
ll ans=0;
for(register int i=0;i<M;i++)ans=(ans+A.Matrix[i][0])%mod;
printf("%I64d\n",ans);
}
return 0;
}

click it and link me

Launch CodeCogs Equation Editor