{"id":231,"date":"2010-04-23T19:27:00","date_gmt":"2010-04-23T11:27:00","guid":{"rendered":"http:\/\/localhost\/?p=231"},"modified":"2010-04-23T19:27:00","modified_gmt":"2010-04-23T11:27:00","slug":"bejing_icpc_2007_color_squares","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=231","title":{"rendered":"BeJing ICPC 2007 Color Squares"},"content":{"rendered":"

\u9898\u76ee\u5728UVA\u4e0a\u3002http:\/\/acm.uva.es\/archive\/nuevoportal\/<\/a>
\u4e00\u5f00\u59cb\u6211\u7684\u60f3\u6cd5\u662f\u641c\u7d22\u3002\u3002\u7136\u540e\u5199\u4e86N\u4e2a\u526a\u679d\u3002\u3002\u641e\u7684\u7d2f\u6b7b\u3002\u3002\u7ed3\u679c\u5374\u53d1\u73b0\u6839\u672c\u4e0d\u884c\u3002\u3002
\u6211\u6d4b\u4e86\u4e00\u4e0b\u53d1\u73b0\u4e00\u7ec4\u6570\u636e\u5dee\u4e0d\u591a0.2s\u3002\u3002\u4f46\u8fd9\u73a9\u610f\u6570\u636e\u591a\u7684\u5413\u4eba\u3002\u3002TLE\u3002\u3002\u3002
\u540e\u6765\u6211\u611f\u89c9\u5e94\u8be5\u4ece\u8fd9\u4e48\u591a\u6570\u636e\u4e2d\u627e\u5171\u540c\u70b9\u3002\u5c31\u662f\u9884\u5904\u7406\u4e00\u4e0b\u3002\u3002
\u7531\u4e8e\u68cb\u76d8\u662f\u4e00\u6837\u7684\uff0c\u6240\u4ee5\u80fd\u653e\u7684\u72b6\u6001\u662f\u6709\u9650\u7684\uff0c
\u6240\u6709\u72b6\u6001\u53ef\u4ee5\u7528\u5b83\u80fd\u5206\u522b\u653eB-Y\u7684\u4e2a\u6570\u548c\u5176\u9700\u8981\u7684\u5e03\u6570\u6765\u8868\u793a\uff0c
\u53ea\u6709\u6b65\u6570\u6700\u5c0f\u7684\u624d\u4e88\u4ee5\u8003\u8651\uff0c\u90a3\u4e48\u53ea\u8981\u5f00\u4e2a4\u7ef4\u6570\u7ec4\u8bb0\u5f55\u6240\u6709\u72b6\u6001\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u3001
\u7531\u4e8e\u6ca1\u6709\u526a\u679d\uff0c\u66b4\u529b\u641c\u51fa\u6240\u6709\u72b6\u6001\u9700\u89814s+\u3002\u3002\u4f46\u4e4b\u540e\u53ea\u8981\u679a\u4e3e4\u79cd\u989c\u8272\u7684\u4e2a\u6570\u5c31OK\u4e86\u3002\u3002
\u6240\u4ee5\u7a0b\u5e8f\u98de\u5feb\uff0cAC\u4e86(*^__^*) \u563b\u563b
Code\uff1a
#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1;using namespace std;int D[10][10][10][10]={0};int w[4],W,cnt=0;int a[4]={0};int M[3][3]={0};bool check[4];const int di[]={0,1,0,-1},dj[]={1,0,-1,0};inline bool Legal(int i,int j){ return i>=0&&i<3&&j>=0&&j<3;}void Fill(int p,int i,int j,int s){ \/\/cout<<p<<" "<<i<<" "<<j<<" "<<s<<endl; if(p==4) { int&x=D[a[0]][a[1]][a[2]][a[3]]; if(!x||x>s)x=s;cnt++; return; } if(i==3) { Fill(p+1,0,0,s); return; } int ii,jj; memset(check,0,sizeof(check)); rep(d,4) { ii=di[d]+i;jj=dj[d]+j; if(Legal(ii,jj)&&M[ii][jj]) check[M[ii][jj]-1]=true; } if(j==2)ii=i+1,jj=0; else ii=i,jj=j+1;bool c=true; rep(x,p)if(!check[x])c=false; Fill(p,ii,jj,s);if(!c)return; int om=M[i][j]; M[i][j]=p+1; a[p]++;if(om)a[om-1]–; Fill(p,ii,jj,s+1); a[p]–;if(om)a[om-1]++; M[i][j]=om;}int main(){ \/\/freopen("in","r",stdin); Fill(0,0,0,0); for(int num=1;;num++) { rep(i,4)cin>>w[i];if(!w[0])break; cin>>W; int ans=100,s=0; for(int a=0;a<=9;a++) { s+=a*w[0]; for(int b=0;a+b<=9;b++) { s+=b*w[1]; for(int c=0;a+b+c<=9;c++) { s+=c*w[2]; for(int d=0;a+b+c+d<=9;d++) { s+=d*w[3];int x=D[a][b][d]; \/\/cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<s<<" "<<x<<endl; if(x&&s>=W)ans<?=x; s-=d*w[3]; } s-=c*w[2]; } s-=b*w[1]; } s-=a*w[0]; } cout<<"Case "<<num<<": "; if(ans==100)cout<<"Impossible"<<endl; else cout<<ans<<endl; }} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u9898\u76ee\u5728UVA\u4e0a\u3002http:\/\/acm.uva.es\/archive\/nuevoportal\/\u4e00\u5f00\u59cb\u6211\u7684\u60f3\u6cd5\u662f\u641c\u7d22\u3002\u3002\u7136\u540e\u5199\u4e86N\u4e2a\u526a\u679d\u3002\u3002\u641e\u7684\u7d2f\u6b7b\u3002\u3002\u7ed3\u679c\u5374\u53d1\u73b0\u6839\u672c\u4e0d\u884c\u3002\u3002\u6211\u6d4b\u4e86\u4e00\u4e0b\u53d1\u73b0\u4e00\u7ec4\u6570\u636e\u5dee\u4e0d\u591a0.2s\u3002\u3002\u4f46\u8fd9\u73a9\u610f\u6570\u636e\u591a\u7684\u5413\u4eba\u3002\u3002TLE\u3002\u3002\u3002\u540e\u6765\u6211\u611f\u89c9\u5e94\u8be5\u4ece\u8fd9\u4e48\u591a\u6570\u636e\u4e2d\u627e\u5171\u540c\u70b9\u3002\u5c31\u662f\u9884\u5904\u7406\u4e00\u4e0b\u3002\u3002\u7531\u4e8e\u68cb\u76d8\u662f\u4e00\u6837\u7684\uff0c\u6240\u4ee5\u80fd\u653e\u7684\u72b6\u6001\u662f\u6709\u9650\u7684\uff0c\u6240\u6709\u72b6\u6001\u53ef\u4ee5\u7528\u5b83\u80fd\u5206\u522b\u653eB-Y\u7684\u4e2a\u6570\u548c\u5176\u9700\u8981\u7684\u5e03\u6570\u6765\u8868\u793a\uff0c\u53ea\u6709\u6b65\u6570\u6700\u5c0f\u7684\u624d\u4e88\u4ee5\u8003\u8651\uff0c\u90a3\u4e48\u53ea\u8981\u5f00\u4e2a4\u7ef4\u6570\u7ec4\u8bb0\u5f55\u6240\u6709\u72b6\u6001\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u3001\u7531\u4e8e\u6ca1\u6709\u526a\u679d\uff0c\u66b4\u529b\u641c\u51fa\u6240\u6709\u72b6\u6001\u9700\u89814s+\u3002\u3002\u4f46\u4e4b\u540e\u53ea\u8981\u679a\u4e3e4\u79cd\u989c\u8272\u7684\u4e2a\u6570\u5c31OK\u4e86\u3002\u3002\u6240\u4ee5\u7a0b\u5e8f\u98de\u5feb\uff0cAC\u4e86(*^__^*) \u563b\u563bCode\uff1a#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1;using namespace std;int D[10][10][10][10]={0};int w[4],W,cnt=0;int a[4]={0};int M[3][3]={0};bool check[4];const int di[]={0,1,0,-1},dj[]={1,0,-1,0};inline bool Legal(int i,int j){ return i>=0&&i<3&&j>=0&&j<3;}void Fill(int p,int i,int j,int s){ \/\/cout<<p<<" "<<i<<" "<<j<<" "<<s<<endl; if(p==4) { int&x=D[a[0]][a[1]][a[2]][a[3]]; if(!x||x>s)x=s;cnt++; return; } if(i==3) { Fill(p+1,0,0,s); return; } int ii,jj; memset(check,0,sizeof(check)); rep(d,4) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/231"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=231"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/231\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=231"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=231"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}