Contest地址(VJ) 点击打开链接
好气啊啊啊！！！C题简直神TM坑！！！
Problem A (HDU 1050)
区间覆盖最小,也叫最小工人问题. 需要注意的是门牌号需要处理一下(对门归为一个门牌号)
参见 区间调度问题详解
AC代码 View Source On GitHub
Problem B (POJ 1125)
做过。Floyd算法的题目。题解 POJ 1125 Floyd最短路入门
Problem C (POJ 1176)
沃日啊！我最后做的这道题！我TM以为这道题非常困难呢，一直在找规律，6个分一组然后判断一共有8种状态！然而，这是一道DFS就能过的题！
AC代码 View Source On GitHub
来来来，贴一下累得半死的找规律...(俩小时) 最关键的是居然WA !
/// POJ 1176 #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <string> #include <algorithm> using namespace std; #define MAXN 150 /// 按照6个一组进行分组,每一组只能有以下8种状态 /** A 000000 B 101010 (1) C 010101 (1) D 010010 (1) E 111111 (B^C) (2) F 111000 (B^D) (2) G 000111 (C^D) (2) H 101101 (B^C^D) (3) */ int abit[MAXN]; int c_abit=0; int bbit[MAXN]; int c_bbit=0; int status_map[8][6] { { 1,1,1,1,1,1 ///A 0 }, { 0,1,0,1,0,1 ///B 1 }, { 1,0,1,0,1,0 ///C 1 }, { 0,1,1,0,1,1 ///D 1 }, { 1,0,0,1,0,0 ///E 2 }, { 0,0,1,1,1,0 ///F 2 }, { 1,1,0,0,0,1 ///G 2 }, { 0,0,0,0,0,0 ///H 3 } }; int exclude_lable[8]; int bit_bucket[6]; int main() { /// Input Start int N; scanf("%d",&N); int C; scanf("%d",&C); C=C%3; int tmp; while(scanf("%d",&tmp)==1&&tmp!=-1) abit[c_abit++]=tmp%6; while(scanf("%d",&tmp)==1&&tmp!=-1) abit[c_bbit++]=tmp%6; /// Input Finish. for(int i=0;i<8;i++)/// Search in 8 Status { for(int j=0;j<c_abit;j++) { if(status_map[i][abit[j]]!=1) /// Must Be ON { exclude_lable[i]=1; } } for(int j=0;j<c_bbit;j++) { if(status_map[i][bbit[j]]!=0) /// Must Be OFF { exclude_lable[i]=1; } } } /// Now status not excluded might be answers. /// Check C and confirm them for(int i=0;i<8;i++) { if(!exclude_lable[i]) { /// Not excluded. switch(i) { /// case 0 is not checked. case 1:case 2:case 3: {if(C!=1) exclude_lable[i]=1;}break; case 4:case 5:case 6: {if(C!=2) exclude_lable[i]=1;}break; } } } /// Now status are confirmed. /// But if N%6 != 0 then you should check if repetitions exist. /// But N >= 10 > 6 , so check is needn't. vector<string> ans; /// Output for(int i=0;i<8;i++) { if(!exclude_lable[i]) { string t; switch(i) { case 0: { char p[]="111111"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } case 1: { char p[]="010101"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 2: { char p[]="101010"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 3: { char p[]="011011"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 4: { char p[]="100100"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 5: { char p[]="001110"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 6: { char p[]="110001"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; case 7: { char p[]="000000"; for(int c=0;c<N/6;c++) t+=p; p[N%6]=0; t+=p; } break; } ans.push_back(t); } } sort(ans.begin(),ans.end()); for(size_t i=0;i<ans.size();i++) { printf("%s\n",ans.at(i).c_str()); } return 0; }Problem D (POJ 3667)
线段树。写了份新的模板。
AC代码 View Source On GitHub
线段树模板集合(持续更新)
ACM模板——各种各样的线段树
SegmentTree Template On GitHub
