Frost_Delay 的博客

Frost_Delay 的博客

day 9

posted on 2019-08-09 15:18:32 | under 未分类 |

四道SCOI2009原题,三道DP一道矩乘,我又不会,难受;

才87.5分;

8.11:终于把4道题都A了

T1P4158 [SCOI2009]粉刷匠

改完AC了

处理f数组时k只需枚举到m,因为一块木板最多用m桶油漆XD

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t,ans=-1;
int sum[51][51][2];
int f[51][51][51];
int g[51][2501];
int main()
{
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char c=getchar();
        while(c!='0'&&c!='1')c=getchar();
        sum[i][j][1]=sum[i][j-1][1];
        sum[i][j][0]=sum[i][j-1][0];
        sum[i][j][c-48]++;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=1;k<=m;k++)
    for(int h=0;h<j;h++)
    {
        f[i][j][k]=max(f[i][j][k],f[i][h][k-1]+max(sum[i][j][1]-sum[i][h][1],sum[i][j][0]-sum[i][h][0]));
    }
    for(int i=1;i<=n;i++)
    for(int j=t;j>=1;j--)
    for(int k=1;k<=min(j,m);k++)
    {
        g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][m][k]);
    }
    cout<<g[n][t]<<endl;
    return 0;
}

T2P4159 [SCOI2009]迷路

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=2009;
char c;
ll n,t,rd;
struct node{
    ll a[101][101];
}ans,p;
void X()
{
    node tot;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    tot.a[i][j]=0;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    for(int k=1;k<=n*9;k++)
    tot.a[i][j]=(tot.a[i][j]+p.a[i][k]*p.a[k][j]%mod)%mod;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    p.a[i][j]=tot.a[i][j];
    return;
}
void anss()
{
    node tot;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    tot.a[i][j]=0;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    for(int k=1;k<=n*9;k++)
    tot.a[i][j]=(tot.a[i][j]+ans.a[i][k]*p.a[k][j]%mod)%mod;
    for(int i=1;i<=n*9;i++)
    for(int j=1;j<=n*9;j++)
    ans.a[i][j]=tot.a[i][j];
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=8;j++)
    p.a[i*9-9+j][i*9-8+j]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>c;
        rd=c^48;
        if(rd)
            p.a[i*9-9+rd][j*9-8]=1;
    }
    for(int i=1;i<=9*n;i++)
        ans.a[i][i]=1;
    while(t)
    {
        if(t&1)
        {
            anss();
            t--;
        }
        X();
        t>>=1;
    }
    cout<<ans.a[1][n*9-8]<<endl;
    return 0;
}

T3P4161 [SCOI2009]游戏

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int su[1000]={0,2},tmp,n,k=1;
long long f[1010];
int main()
{
    cin>>n;
    if(n==1)
    {
        cout<<"1"<<endl;
        return 0;
    }
    for(int i=3;i<=n;i+=2)
    {
        su[++k]=i;
        for(int j=2;j<k;j++)
        if(i%su[j]==0){
        k--;break;
        }
    }
    f[0]=1;
    for(int i=1;i<=k;i++)
    for(int j=n;j>=su[i];j--)
    {
        tmp=su[i];
        while(tmp<=j)
        {
            f[j]+=f[j-tmp];
            tmp*=su[i];
        }
    }
    long long ans=1;
    for(int i=1;i<=n;i++)ans+=f[i];
    cout<<ans<<endl;
    return 0;
}

T4P2657 [SCOI2009]windy数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int f[20][20],a,b;
int main()
{
    cin>>a>>b;
    for(int i=0;i<=9;i++)
    f[1][i]=1;
    for(int i=2;i<=15;i++)
    for(int j=0;j<=9;j++)
    for(int k=0;k<=9;k++)
    if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
    int s[15]={},cnt=0,tot=0,s1[15]={},cntt=0,tot1=0;
    while(a){
        cnt++;
        s[cnt]=a%10;
        a/=10;
    }
    for(int i=1;i<cnt;i++)
    for(int j=1;j<=9;j++)
    tot+=f[i][j];
    for(int i=1;i<s[cnt];i++)tot+=f[cnt][i];
    for(int i=cnt-1;i>=1;i--)
    {
        for(int j=0;j<s[i];j++)
        {
            if(abs(s[i+1]-j)>=2)tot+=f[i][j];
        }
        if(abs(s[i+1]-s[i])<2)break;
    }

    b++;
    while(b){
        cntt++;
        s1[cntt]=b%10;
        b/=10;
    }
    for(int i=1;i<cntt;i++)
    for(int j=1;j<=9;j++)
    tot1+=f[i][j];
    for(int i=1;i<s1[cntt];i++)tot1+=f[cntt][i];
    for(int i=cntt-1;i>=1;i--)
    {
        for(int j=0;j<s1[i];j++)
        {
            if(abs(s1[i+1]-j)>=2)tot1+=f[i][j];
        }
        if(abs(s1[i+1]-s1[i])<2)break;
    }

    cout<<tot1-tot<<endl;
    return 0;
}