首页 > 代码库 > 某些题的做法。。。

某些题的做法。。。

B一个大神的做法。。。更普遍的做法是打表。。

有一个3*3的机场,里面有一些飞机,飞机的颜色有B和G两种,飞机只能在(0,0)处起飞,飞机可以往上下左右的空白处移动。

问这些飞机一共可以组成多少种不同的起飞颜色序列。

。。。。

如果不考虑30000组case,那么可以直接O(n!)枚举起飞顺序,然后判定可不可行,最后再计算有多少种不同的颜色序列。

现在预处理这个:can[sta][x][y]表示当前地图状态为sta(2进制串,0表示没有飞机,1表示有飞机)时那些地方和(0,0)联通。

那么判定的时候就可以直接判断了。

但是交上去还是TLE。

于是又把可行的起飞顺序给暴力预处理出来了,arr[sta][]表示当前初始状态为sta的时候的所有起飞顺序(最坏情况只有1344种)。

然后就可以降到O(cas*1344)了。

交上去果然还是TLE。

没辙,再预处理一下当前初始状态为sta,且每辆飞机的颜色状态为col的时候有多少种不同答案。

预处理大概2^8*3*3+2^8*2^8*1344*8这么多。

每组数据可以做到O(1)。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int step[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};bool can[256][3][3];char g[3][3];void DFS(int sta,int x,int y){    can[sta][x][y] = true;    for (int i = 0; i < 4; i++)    {        int tx = x+step[i][0];        int ty = y+step[i][1];        if (tx < 0 || tx > 2 || ty < 0 || ty > 2)   continue;        if (g[tx][ty] == #)            can[sta][tx][ty] = true;        else        {            if (can[sta][tx][ty] == false)                DFS(sta,tx,ty);        }    }}int arr[2000][10],arrlen[2000],arrtot;int tmp[10];void DFS2(int ful,int sta,int tot){    if (sta == 0)    {        int id = arrtot;        arrlen[id] = tot;        for (int i = 0; i < tot; i++)            arr[id][i] = tmp[i];        arrtot++;        return;    }    for (int i = 0; i < 3; i++)        for (int j = 0; j < 3; j++)            if (((sta>>(i*3+j-1))&1) == 1)                if (can[sta][i][j] == true)                {                    tmp[tot] = i*3+j-1;                    DFS2(ful,sta-(1<<(i*3+j-1)),tot+1);                }}bool flag[256];int res[256][256];int tid[8];void Gao(){    memset(can,false,sizeof(can));    for (int i = 0; i < (1<<8); i++)    {        g[0][0] = .;        for (int x = 0; x < 3; x++)            for (int y = 0; y < 3; y++)                if (x != 0 || y != 0)                {                    if (((i>>(x*3+y-1))&1) == 1)                        g[x][y] = #;                    else                        g[x][y] = .;                }        DFS(i,0,0);    }    memset(res,0,sizeof(res));    for (int i = 0; i < (1<<8); i++)    {        arrtot = 0;        DFS2(i,i,0);        int ttid = 0;        for (int x = 0; x < 3; x++)            for (int y = 0; y < 3; y++)                if (x != 0 || y != 0)                    if (((i>>(x*3+y-1))&1) == 1)                        tid[x*3+y-1] = ttid++;        int len = arrlen[0];        for (int j = 0; j < (1<<len); j++)        {            memset(flag,false,sizeof(flag));            for (int k = 0; k < arrtot; k++)            {                int v = 0;                for (int q = 0; q < len; q++)                    if (((j>>tid[arr[k][q]])&1) == 1)                        v = (v<<1)|1;                    else                        v = v<<1;                if (flag[v] == false)                    res[i][j]++;                flag[v] = true;            }            /*if (j == 0 || j == (1<<len)-1)                printf("%d %d %d\n",i,j,res[i][j]);*/        }    }    //printf("%d\n",res[255][254]);    //printf("%d\n",arrtot[255]);}char mp[3][4];    int main()    {        Gao();        int cas = 0;        while (scanf("%s",mp[0]) != EOF)        {            for (int i = 1; i < 3; i++)            scanf("%s",mp[i]);            int sta = 0;            for (int x = 2; x >= 0; x--)            for (int y = 2; y >= 0; y--)                if (x != 0 || y != 0)                    {                        if (mp[x][y] == *)                        sta = sta<<1;                        else                        sta = (sta<<1)|1;                    }            int col = 0;            for (int x = 2; x >= 0; x--)            for (int y = 2; y >= 0; y--)                if (x != 0 || y != 0)                    {                        if (mp[x][y] == G)                        col = col<<1;                        else if (mp[x][y] == B)                        col = (col<<1)|1;                    }            printf("Case %d: %d\n",++cas,res[sta][col]);        }        return 0;    }
View Code

还有一种。。定义一个状态s,表示飞机场上对应的格子有无飞机(不管颜色),总共有2^9种状态,如果对与s,我们选择一个和起飞点直接连通的有飞机的格子,并把其置0,得到状态ss,那么s和ss连一条有向边。然后就可以利用这个状态转移图直接dfs了。

#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;struct edge{    int v,p;    edge(){}    edge(int v,int p):v(v),p(p){}};vector<edge> G[256];int dx[]={0,1,0,-1},    dy[]={1,0,-1,0};int mat[5][5],vis[5][5],flag[1<<8],ans;void predfs(int s,int x,int y){    vis[x][y]=1;    if(mat[x][y]==2){        int v=s,p=(x-1)*3+y-1;        v^=(1<<(8-p));        G[s].push_back(edge(v,p));        return;    }    for(int i=0;i<4;i++){        int tx=x+dx[i],ty=y+dy[i];        if(mat[tx][ty]&&!vis[tx][ty])            predfs(s,tx,ty);    }}void dfs(int s,int color){    if(!s){if(!flag[color]) flag[color]=1,ans++;return;}    for(int i=0;i<G[s].size();i++){        int ts=G[s][i].v,p=G[s][i].p;        int tmp=mat[p/3+1][p%3+1];        mat[p/3+1][p%3+1]=1;        dfs(ts,color*2+tmp-2);        mat[p/3+1][p%3+1]=tmp;    }        }int main(){        for(int s=1;s<256;s++)    {        for(int t=s,i=3;i;i--)            for(int j=3;j;j--)                mat[i][j]=(t&1)+1,t>>=1;        memset(vis,0,sizeof(vis));        predfs(s,1,1);    }    int cas=0;    char str[3][5];    while(scanf("%s%s%s",str[0],str[1],str[2])+1){        int s=0;        for(int i=0;i<3;i++)            for(int j=0;j<3;j++){                mat[i+1][j+1]=(str[i][j]==*?1:(str[i][j]==B?2:3));                s=s*2+(str[i][j]!=*);            }        ans=0;        memset(flag,0,sizeof(flag));        dfs(s,0);        printf("Case %d: %d\n",++cas,ans);    }        return 0;}

 

D

给定n种颜色的石头,每种颜色有si颗,同种颜色的石头不区分。问能构成多少种不同的石头序列(不同的序列是指:1.石头数不同;2.石头数相同,至少一个位置的石头颜色不同)  dp[ i ][ j ]表示:考虑前i种石头构成的长度为j的序列的个数。  转台转移方程:    dp[ i ][ j ] = dp[ i-1 ][ j ];   //未放入第i种颜色的石头    for  k := 1 ~ min( j , s[ i ] ) //放入k个第i种颜色的石头      dp[ i ][ j ] += dp[ i-1 ][ j - k ] * C[ j ][ k ];    其中C[ n ][ m ]表示组合数。
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#define ll  long long#define mod  1000000007using namespace std;long long dp[110][10010],s[110],c[10010][110],n;void init(long long n,long long m){    long long i,j;    memset(c,0,sizeof(c));    for(i=0;i<=m;i++)c[0][i]=c[1][i]=1;    for(i=0;i<=m;i++)c[i][i]=1;    for(i=0;i<=n;i++)c[i][0]=1;    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++)        {            if(i!=j)            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;        }    }}void DP(){    memset(dp,0,sizeof(dp)); long long t=s[1],m; for(int i=1; i<=n; i++)   dp[i][0]=1; for(int j=1; j<=s[1]; j++)      dp[1][j]=1; for(int i=2; i<=n; i++){    t+=s[i]; for(int j=1; j<=t; j++){     m=min((ll)j,s[i]);     dp[i][j]=dp[i-1][j]; for(int k=1; k<=m; k++){    dp[i][j]+=dp[i-1][j-k]*c[j][k];     dp[i][j]%=mod;   }  } }}int main(){    init(10000,100);    long long l=0,i,j,k,len,h,ans;    while(scanf("%lld",&n)!=EOF)    {        l++;        h=0;        for(i=1;i<=n;i++){scanf("%lld",&s[i]);h+=s[i];};         DP();        ans=0;        for(j=1;j<=h;j++)        {            ans+=dp[n][j];            ans%=mod;        }        printf("Case %lld: %lld\n",l,ans);        //cout<<ans<<endl;    }}

E 数位dp吧,只不过写起来有点繁琐,先预处理一下会好很多。把每一位都预处理出min和max,表示这一位的数只能从min到max,比如问号就是0-9。并且对于位数不够字符串,把高位补成0。然后dp[i][j]表示从低到高至第i位并进位为j的时候的方案数。最后答案为dp[n][0]。

#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<algorithm>#define ll long longusing namespace std;int n;int d[3][20],u[3][20];ll dp[20][2];void init(string s){    string a,b,c;    int i,j;    memset(d,0,sizeof(d));    memset(u,0,sizeof(u));    for(i=0;s[i]!=+;i++);    for(j=0;s[j]!==;j++);    a=s.substr(0,i);    b=s.substr(i+1,j-i-1);    c=s.substr(j+1,s.size()-j-1);    reverse(a.begin(),a.end());    reverse(b.begin(),b.end());    reverse(c.begin(),c.end());        n=max(a.size(),max(b.size(),c.size()));        for(i=0;i<a.size();i++){        if(a[i]==?) d[0][i]=0,u[0][i]=9;        else d[0][i]=u[0][i]=a[i]-0;                    }    if(a.size()>1&&a[a.size()-1]==?) d[0][a.size()-1]=1;    for(i=0;i<b.size();i++){        if(b[i]==?) d[1][i]=0,u[1][i]=9;        else d[1][i]=u[1][i]=b[i]-0;            }    if(b.size()>1&&b[b.size()-1]==?) d[1][b.size()-1]=1;    for(i=0;i<c.size();i++){        if(c[i]==?) d[2][i]=0,u[2][i]=9;        else d[2][i]=u[2][i]=c[i]-0;            }    if(c.size()>1&&c[c.size()-1]==?) d[2][c.size()-1]=1;}void gao(){    memset(dp,0,sizeof(dp));    dp[0][0]=1;    for(int i=0;i<n;i++)        for(int j=0;j<2;j++){            if(!dp[i][j]) continue;            for(int x=d[0][i];x<=u[0][i];x++)                for(int y=d[1][i];y<=u[1][i];y++){                    int t=(x+y+j)%10,tt=(x+y+j)/10;                    if(t>=d[2][i]&&t<=u[2][i]) dp[i+1][tt]+=dp[i][j];                }                            }}int main(){        int cas=0;    string s;    while(cin>>s){        init(s);        gao();        printf("Case %d: %lld\n",++cas,dp[n][0]);            }    return 0;}

F和I都可以用神题形容了。。

F:7k+:

首先看奇度点个数。

如果有4个,那么两条边必然四个端点为这四个点。枚举判断即可。

如果有2个,令这两个点为left和right。

对于所有存在边(x, left)和(x, right)的x,删掉这两条边。

在删除后的图中,对于所有在原图中存在边(x, left)和(x, right)的x,如果

(1) x与left连通   或

(2) x与right连通  或

(3) x与某个点y连通,且原图中存在边(y, left)和(y, right)

那么如果存在一个z,使得原图中删除(z, left)和(z, right)是合法的,那么,原图中删除(x, left)和(x, right)也是合法的,且合法的x只有这三种情况。

取最小的边对((x, left), (x, right)),判断是否可行即可。

 

如果奇点个数是其他情况,都无解。

#include<cstdio>#include<iostream>#include<cstring>#include<vector>#include<algorithm>#define N 200009using namespace std;int n,m;int a[N],b[N],d[N];int tf[N],vis[N],fa[N];typedef pair<int,int > PII;typedef pair<pair<int,int>,int > PPI;int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}bool union_set(int a,int b){    a=find(a),b=find(b);    if(a==b) return false;    fa[a]=b;    return true;}bool check(){        int c=n-1;    for(int i=1;i<=n;i++) fa[i]=i;    for(int i=m;i;i--)        if(!tf[i])            c-=union_set(a[i],b[i]);    return !c;}int main(){    int cas=0;        while(scanf("%d%d",&n,&m)+1){        printf("Case %d: ",++cas);        memset(tf,0,sizeof(tf));        memset(d,0,sizeof(d));        memset(vis,0,sizeof(vis));        for(int i=1;i<=m;i++){            scanf("%d%d",a+i,b+i);            d[a[i]]^=1;            d[b[i]]^=1;        }        if(!check()){puts("NO");continue;}        vector<int> odd;        for(int i=1;i<=n;i++)            if(d[i])                odd.push_back(i);        if(!odd.size()||odd.size()>4){puts("NO");continue;}        if(odd.size()==2)        {            int u=odd[0],v=odd[1];            for(int i=1;i<=m;i++){                if(a[i]==u) vis[b[i]]=i;                else if(b[i]==u) vis[a[i]]=i;            }            vector<PPI> del;            for(int i=1;i<=m;i++){                if(a[i]==v&&vis[b[i]]){                    tf[i]=tf[vis[b[i]]]=1;                    del.push_back(PPI(PII(min(i,vis[b[i]]),max(i,vis[b[i]])),b[i]));                }                                    else if(b[i]==v&&vis[a[i]]){                    tf[i]=tf[vis[a[i]]]=1;                    del.push_back(PPI(PII(min(i,vis[a[i]]),max(i,vis[a[i]])),a[i]));                }                                }            check();            sort(del.begin(),del.end());                        memset(vis,0,sizeof(vis));            for(int i=0;i<del.size();i++)                                vis[find(del[i].second)]=del[i].second;            PPI ans;            int ok=0;                        for(int i=0;i<del.size();i++){                int t=find(del[i].second);                if(t==find(u)||t==find(v)||vis[t]!=del[i].second){                    ok=1;                    ans=del[i];                    break;                }            }            if(ok){                memset(tf,0,sizeof(tf));                tf[ans.first.first]=tf[ans.first.second]=1;                if(!check()) ok=0;            }            if(ok) printf("YES\n%d %d\n",ans.first.first,ans.first.second);            else puts("NO");        }        else        {            vector<int> v;            for(int i=1;i<=m;i++)                if(d[a[i]]&&d[b[i]])                    v.push_back(i);            sort(v.begin(),v.end());            int ok=0,e1,e2;            for(int i=0;!ok&&i<v.size();i++)                for(int j=i+1;!ok&&j<v.size();j++){                    e1=v[i],e2=v[j];                    d[a[e1]]^=1,d[b[e1]]^=1;                    d[a[e2]]^=1,d[b[e2]]^=1;                    if(!d[odd[0]]&&!d[odd[1]]&&!d[odd[2]]&&!d[odd[3]]){                        tf[e1]=1,tf[e2]=1;                        if(check()) ok=1;                        tf[e1]=0,tf[e2]=0;                    }                    d[a[e1]]^=1,d[b[e1]]^=1;                    d[a[e2]]^=1,d[b[e2]]^=1;                }            if(ok) printf("YES\n%d %d\n",e1,e2);            else puts("NO");        }    }    }

I:clj的题,丧心病狂。。http://oj.tsinsen.com/resources/Train2012-test-clj-tree.pdf

#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;int n,m,K;struct edge{    int a,b,c,x;    }E[100009];int fa[50009];bool cmp(const edge &a,const edge &b){if(a.c==b.c) return a.x<b.x;return a.c<b.c;}int find(int a){return a==fa[a]?a:fa[a]=find(fa[a]);}bool union_set(int a,int b){a=find(a),b=find(b);if(a==b) return false;fa[a]=b;return true;}int cal(int &cnt,int x){    int ret=0;    cnt=0;    for(int i=0;i<m;i++) if(!E[i].x) E[i].c+=x;    for(int i=0;i<n;i++) fa[i]=i;    sort(E,E+m,cmp);        for(int i=0,c=n-1;c;i++)        if(union_set(E[i].a,E[i].b))            c--,ret+=E[i].c,cnt+=!E[i].x;    for(int i=0;i<m;i++) if(!E[i].x) E[i].c-=x;    return ret;}int main(){        int cas=0;        while(scanf("%d%d%d",&n,&m,&K)+1)    {                   for(int i=0;i<m;i++)                    scanf("%d%d%d%d",&E[i].a,&E[i].b,&E[i].c,&E[i].x);        int cnt,s=-100,e=100,mid,res;        while(s<=e){            mid=(s+e)/2;            cal(cnt,mid);            if(cnt>=K) res=mid,s=mid+1;            else e=mid-1;        }        printf("Case %d: %d\n",++cas,cal(cnt,res)-K*res);    }}

J题