首页 > 代码库 > Topcoder SRM 146

Topcoder SRM 146

Div1 300 RectangularGrid

题意:给定一个长方形,问包含有多少不是正方形的小长方形

题解:枚举小长方形的长宽即可

#line 2 "RectangularGrid.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;class RectangularGrid{    public:    long long countRectangles(int width, int height)    {        LL ans=0;        for (int i=1;i<=width;++i)        {            for (int j=1;j<=height;++j)            {                if (i==j) continue;                int w=width-i+1;                int h=height-j+1;                ans+=w*h;            }        }        return ans;    }};#ifdef exint main(){    #ifdef ex1    freopen ("in.txt","r",stdin);    #endif}#endif

 

Div1 600 Masterbrain

题意:略

题解:主要是卡题意,以及“No digit in either a guess or a secret combination may be involved in giving more than one peg”这个条件的处理

#line 2 "Masterbrain.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;int ans;int A[5];int cnt[15];int ok[5];vector<vector<int> > G;vector<int> v;vector<int> B;vector<int> W;bool check(){    int wa=0;    for (int i=0;i<G.size();++i)    {        memset(ok,0,sizeof(ok));        vector<int>& v=G[i];        int b=0;        int w=0;        for (int j=0;j<v.size();++j)        {            if (A[j]==v[j])            {                ++b;                ok[j]=1;            }        }        for (int j=0;j<v.size();++j)        {            if (A[j]!=v[j] && cnt[v[j]]!=0)            {                for (int jj=0;jj<v.size();++jj)                {                    if (A[jj]==v[j] && ok[jj]==0)                    {                        ok[jj]=1;                        ++w;                        break;                    }                }            }        }        if (b!=B[i] || w!=W[i]) ++wa;    }    if (wa!=1) return false;    else return true;}void dfs(int k){    if (k==4)    {        if (check()) ++ans;        return;    }    for (int i=1;i<=7;++i)    {        A[k]=i;        ++cnt[i];        dfs(k+1);        --cnt[i];    }    return ;}class Masterbrain{    public:    int possibleSecrets(vector <string> guesses, vector <string> results)    {        for (int i=0;i<guesses.size();++i)        {            string& tmp=guesses[i];            v.clear();            for (int j=0;j<tmp.length();++j)            {                int t=tmp[j]-0;                v.push_back(t);            }            G.push_back(v);        }        for (int i=0;i<results.size();++i)        {            string& tmp=results[i];            B.push_back(tmp[0]-0);            W.push_back(tmp[3]-0);        }        ans=0;        memset(cnt,0,sizeof(cnt));        dfs(0);        return ans;    }};#ifdef exint main(){    #ifdef ex1    freopen ("in.txt","r",stdin);    #endif}#endif

 

Div2 1000 BridgeCrossing

题意:略

题解:状压DP

#line 2 "BridgeCrossing.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1<<8;int dp[maxn+5];int sz;vector<int> T;int DP(int x){    if (dp[x]!=-1) return dp[x];    vector<int> v1,v2;    for (int i=0;i<=sz-1;++i)    {        if (x>>i & 1) v1.push_back(i);        else v2.push_back(i);    }    if (v1.size()==0) return dp[x]=0;    else if (v1.size()==1) return dp[x]=T[v1[0]];    else if (v1.size()==2) return dp[x]=max(T[v1[0]],T[v1[1]]);    int q=0;    int val=1e8;    for (int i=0;i<v2.size();++i)    {        int& e=v2[i];        if (T[e]<val)        {            val=T[e];            q=e;        }    }    dp[x]=1e8;    for (int i=0;i<v1.size();++i)    {        for (int j=i+1;j<v1.size();++j)        {            int& e1=v1[i];            int& e2=v1[j];            int S=x&~(1<<e1);            S=S&~(1<<e2);            int t=T[e1]<T[e2]?e1:e2;            int p=val<T[t]?q:t;            S=S|(1<<p);            dp[x]=min(dp[x],DP(S)+max(T[e1],T[e2])+T[p]);            //printf("%d %d %d\n",x,S,q);            //printf("%d %d %d %d\n",x,v1.size(),i,j);        }    }    return dp[x];}class BridgeCrossing{    public:    int minTime(vector <int> times)    {        sz=times.size();        for (int i=0;i<=sz-1;++i) T.push_back(times[i]);        memset(dp,-1,sizeof(dp));        int ans=DP((1<<sz)-1);        /*        for (int i=0;i<=((1<<sz)-1);++i)        {            printf("%d %d\n",i,DP(i));        }        */        return ans;    }};#ifdef exint main(){    #ifdef ex1    freopen ("in.txt","r",stdin);    #endif}#endif

 

Topcoder SRM 146