首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。