只写了一道题,结果可想而知。
爆零。
1035. 粉刷匠 (Standard IO)
本题使用动态规划解决。
设sum[i][j]表示第i行中1~j的蓝色格子数,则j-sum[i][j]为红色格子数。
设g[i][j][k]表示i行中刷j次涂了1~k格的最大收益,则
考虑在q+1~k之间,
蓝色格子数为sum[i][k]-sum[i][q],
红色格子数为k-q-(sum[i][k]-sum[i][q]),
所以状态转移为:
g[i][j][k]=g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-(sum[i][k]-sum[i][q])),
则每行收益为g[i][j][m],k为粉刷次数。
所以可以转化成一个背包问题解决。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=55; 4 int n,m,t; 5 int sum[N][N],g[N][N*N][N],f[N][N*N]; 6 int main(){ 7 scanf("%d%d%d",&n,&m,&t); 8 char c[500]; 9 for(int i=1;i<=n;i++){ 10 cin>>c; 11 for(int j=1;j<=m;j++){ 12 if(c[j-1]=='1') sum[i][j]=sum[i][j-1]+1; 13 else sum[i][j]=sum[i][j-1]; 14 } 15 } 16 for(int i=1;i<=n;i++){ 17 for(int j=1;j<=m;j++){ 18 for(int k=1;k<=m;k++){ 19 for(int q=j-1;q<k;q++){ 20 int tm=max(sum[i][k]-sum[i][q],k-q-(sum[i][k]-sum[i][q])); 21 g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+tm); 22 } 23 } 24 } 25 } 26 for(int i=1;i<=n;i++){ 27 for(int j=1;j<=t;j++){ 28 for(int k=0;k<=min(j,m);k++){ 29 f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]); 30 } 31 } 32 } 33 int ans=0; 34 for(int i=1;i<=t;i++){ 35 ans=max(f[n][i],ans); 36 } 37 printf("%d",ans); 38 // for(int i=1;i<=n;i++){ 39 // for(int j=1;j<=m;j++){ 40 // printf("%d ",sum[i][j]); 41 // } 42 // cout<<endl; 43 // } 44 return 0; 45 }
送分题,对于一个点,我们可以将它拆成9个点,相应的矩阵变成9*n长度,对于一条边(u,v),我们可以先处理出u到u后面8个节点的路径,每当一条边连通,相当于将缺少的最后一条边补上,这条边才算真正连通,(设置中间那些节点对答案并无影响)接着就可以矩阵乘法了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100; 4 const int mod=2009; 5 int n,t; 6 int cnt,x; 7 struct matrix{ 8 int a[N][N]; 9 void Empty(){ 10 memset(a,0,sizeof(a)); 11 } 12 void One(){ 13 Empty(); 14 for(int i=1;i<=cnt;i++) a[i][i]=1; 15 } 16 matrix operator *(matrix b){ 17 matrix tmp; 18 tmp.Empty(); 19 for(int i=1;i<=cnt;i++){ 20 for(int j=1;j<=cnt;j++){ 21 for(int q=1;q<=cnt;q++){ 22 tmp.a[i][j]+=(a[i][q]*b.a[q][j])%mod; 23 tmp.a[i][j]%=mod; 24 } 25 } 26 } 27 return tmp; 28 } 29 void out(){ 30 for(int i=1;i<=cnt;i++){ 31 for(int j=1;j<=cnt;j++){ 32 printf("%d ",a[i][j]); 33 } 34 printf("\n"); 35 } 36 } 37 }res,ans; 38 void matrix_pow(int Q){ 39 ans.One(); 40 while(Q){ 41 if(Q&1){ 42 ans=ans*res; 43 } 44 res=res*res; 45 Q>>=1; 46 } 47 } 48 int pos(int a1,int a2){ 49 return a1+a2*n; 50 } 51 int main(){ 52 freopen("ans.txt","w",stdout); 53 scanf("%d%d",&n,&t); 54 res.Empty(); 55 cnt=n*9; 56 for(int i=1;i<=n;i++){ 57 for(int j=1;j<=8;j++){ 58 res.a[pos(i,j)][pos(i,j-1)]=1; 59 } 60 for(int j=1;j<=n;j++){ 61 scanf("%1d",&x); 62 res.a[i][pos(j,x-1)]=1; 63 } 64 } 65 res.out(); 66 matrix_pow(t); 67 printf("%d",ans.a[1][n]); 68 return 0; 69 }
这题需要一点点思考。
根据题意,我们发现给的变换中有“环”出现,比如1->2,2->3,3->1构成一个三元环,因此,排数就等于所有环的最小公倍数+1。
考虑到长度为1并不构成环,对题目没有影响,而出现两个含有倍数关系的环,实质可以拆成两个不同质数,但如果出现指数关系,公倍数就是大的那个,因此用背包模型来解决。
我们先筛出质数表,n为背包容量,每个质数及其指数倍为物品,数的大小为物品的体积,求方案数即可。
注意开长整型。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll N=1010; 5 bool check[N]; 6 ll cnt,p[N],n,ans; 7 ll f[N]; 8 void Eus(ll n){ 9 check[0]=check[1]=1; 10 for(int i=1;i<=n;i++){ 11 if(!check[i]) p[++cnt]=i; 12 for(int j=1;j<=cnt;j++){ 13 if(i*p[j]>n) break; 14 check[i*p[j]]=1; 15 if(i%p[j]==0) break; 16 } 17 } 18 19 } 20 int main(){ 21 scanf("%lld",&n); 22 Eus(n); 23 f[0]=1; 24 for(ll i=1;i<=cnt;i++){ 25 for(ll j=n;j>=p[i];j--){ 26 for(ll k=p[i];k<=j;k*=p[i]){ 27 f[j]+=f[j-k]; 28 } 29 } 30 } 31 ans=0; 32 for(int i=0;i<=n;i++) ans+=f[i]; 33 printf("%lld",ans); 34 return 0; 35 }
1039. windy数 (Standard IO)
数位dp板子,可惜我太辣鸡了,没学过。
学了之后发现好简单。
设f[i][j]表示第i位填j的windy数数量。
先递推出来,然后处理问题。
我们只要分别求出1~a与1~b的windy数数量再相减即可。
引用:
y2823774827y巨佬的题解
将数字分为三个部分,一个是长度不为len的部分,只要差大于等于2随便填,一个是有len位但是最高位不到len位数字的部分,一个是有len位且最高位为len的数字,但次位尽量往高位贴的部分,因为答案包括边界,所以是solve(r+1)-solve(l)。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll a,b; 5 ll f[15][10]; 6 ll num[20]; 7 ll solve(ll x){ 8 memset(num,0,sizeof(num)); 9 ll len=0,ans=0; 10 while(x){ 11 num[++len]=x%10; 12 x/=10; 13 } 14 for(ll i=1;i<len;i++){ 15 for(ll j=1;j<=9;j++){ 16 ans+=f[i][j]; 17 } 18 } 19 for(ll i=1;i<num[len];i++) ans+=f[len][i]; 20 for(ll i=len-1;i>=1;i--){ 21 for(ll j=0;j<num[i];j++){ 22 if(abs(j-num[i+1])>=2) ans+=f[i][j]; 23 } 24 if(abs(num[i]-num[i+1])<2) break; 25 } 26 return ans; 27 } 28 int main(){ 29 scanf("%lld%lld",&a,&b); 30 for(ll i=0;i<=9;i++) f[1][i]=1; 31 for(ll i=2;i<=10;i++){ 32 for(ll j=0;j<=9;j++){ 33 for(ll k=0;k<=9;k++){ 34 if(abs(j-k)>=2) f[i][j]+=f[i-1][k]; 35 } 36 } 37 } 38 printf("%lld",solve(b+1)-solve(a)); 39 return 0; 40 }
总结:知识要扎实的学习。