第一题：神秘大门 大意：
两个字符串A,B，按字典序最大的顺序输出B 的每个字符在A 中的位置，如果B不全在A中，输出No，否则Yes。
解：
这道题就是一遍的扫描，因为要按字典序最大的输出，所以从后面向前面扫描。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1000005 6 using namespace std; 7 string s1,s2; 8 int xi,yi,ans[maxn],head; 9 int main() 10 { 11 freopen("door.in","r",stdin); 12 freopen("door.out","w",stdout); 13 cin>>s1;cin>>s2; 14 xi=s1.size();yi=head=s2.size(); 15 if (xi!=0&&yi==0){ 16 cout<<"No"; 17 return 0; 18 } 19 while (yi!=0&&xi!=0) 20 { 21 if (s1[xi-1]==s2[yi-1]) { 22 ans[yi]=xi; 23 yi--; 24 } 25 xi--; 26 } 27 if (xi==0&&yi!=0) { 28 cout<<"No"; 29 return 0; 30 } 31 cout<<"Yes"<<endl; 32 for (int i=1;i<=head;i++) 33 printf("%d ",ans[i]); 34 return 0; 35 }
第二题 集结蚂蚁 大意：
给一个矩阵，1表示不通，0表示可走。奇数行是路径，偶数行的连续的0是蚁巢。从第一行开始往下走，问走到最后一行时经过的蚁巢的总大小。蚁巢的大小为连续的0的个数。如果不能到最后一行，则输出-1。
样例：
10 10
1111101111
1100001011 4
1101111111
1100000101 5
1110110111
1000110001 3
1101111011
1101000011 4
1101011111
1101010001 1
17
解：
自己画完图后，想的是这道题肯定是动规 ，但是我还是用搜索吧。其实当时也想过用图做，把每一个蚁巢看做节点，然后把奇数行的路径看做边，把蚁巢的大小当做边的权值（如果有多个蚁巢，则取最大的），再搜一条最长路径就可以了。本以为是一棵树，但是觉得路径不一定只有一个0，可能有传递性，就又冒出来一个想法，可以对每一个蚁巢记录三个：bool in，out；表示有没有路径穿过它，否则这个蚁巢也没用；一个sum，记录走到这个蚁巢最大的ans大小。然后注意到当前蚁巢只会由上一个蚁巢推得，就用一个滚动数组。
还有一个问题，就是判断能不能走到最后一行。先开始因为我用的滚动，所以相当于只判断了最后一行有没有连路径，但有可能这条路径不是与第一行联通的，所以 in 这个判断要从第一行向下传递，而不只是从上一行的路径传递下来。
写动规的话，好像比我的代码少了好多行。。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #define maxn 5005 7 #define maxm 2005 8 using namespace std; 9 struct pp{ 10 bool in,out; 11 int sum; 12 }; 13 pp ant_home[5][maxm]; 14 bool isroad[maxm]; 15 int n,m,cnt,road[maxm],home[maxm],cur=1,suf,last_cnt,ans; 16 char c[maxm]; 17 void clr_suf() 18 { 19 //cnt=0; 20 for(int i=1;i<=last_cnt;i++) 21 { 22 ant_home[suf][i].in=false; 23 ant_home[suf][i].out=false; 24 ant_home[suf][i].sum=0; 25 } 26 } 27 void worki()//处理路径 28 { 29 memset(road,0,sizeof(road)); 30 memset(isroad,0,sizeof(isroad)); 31 for (int i=1;i<=m;i++)//更新可走蚁巢和标记 32 if (c[i]=='0'){ 33 isroad[i]=true; 34 if (home[i]!=0){//上一行 35 road[i]=home[i]; 36 ant_home[suf][home[i]].out=true; 37 } 38 int st=i; 39 while(c[st]=='0'){//它相连的左边的路 更新 40 if (road[st]){ 41 if (!road[i]) road[i]=road[st]; 42 else{ 43 if (ant_home[suf][road[st]].sum>ant_home[suf][road[i]].sum) 44 road[i]=road[st]; 45 else road[st]=road[i]; 46 } 47 }else if (road[i]) road[st]=road[i]; 48 st--; 49 } 50 } 51 } 52 void workj()//处理蚁巢 53 { 54 int i=1; 55 memset(home,0,sizeof(home)); 56 while (i<=m){ 57 if (c[i]=='0') { 58 int st=i; 59 cnt++; 60 while (c[i]=='0') { 61 if(isroad[i]) { 62 ant_home[cur][cnt].in=true; 63 int _last=road[i]; 64 if (ant_home[suf][_last].in&&ant_home[suf][_last].out) 65 ant_home[cur][cnt].sum=max(ant_home[cur][cnt].sum,ant_home[suf][_last].sum); 66 } 67 home[i]=cnt; 68 i++; 69 } 70 ant_home[cur][cnt].sum+=i-st; 71 } 72 else i++; 73 } 74 clr_suf();//滚动数组清零 75 last_cnt=cnt; 76 cnt=0; 77 swap(cur,suf); 78 } 79 int main() 80 { 81 freopen("ant.in","r",stdin); 82 freopen("ant.out","w",stdout); 83 scanf("%d%d",&n,&m); 84 for (int i=1;i<=n;i++) 85 { 86 scanf("%s",c+1); 87 if (i%2) worki(); 88 else workj(); 89 } 90 swap(cur,suf);//****** 91 for (int i=1;i<=last_cnt;i++) 92 if(ant_home[cur][i].in&&ant_home[cur][i].sum>ans) 93 ans=ant_home[cur][i].sum; 94 if(ans) cout<<ans; 95 else cout<<-1; 96 return 0; 97 }
第三题 计数 大意：
长n宽m的矩阵点之间连线，问长度为 wi 的线有多少条。
解：
做到这道题，已经只有半个小时了，又没有把题读清楚，以为只有横边 和竖边，觉得好简单，到最后才发现，还有斜边，已经没有时间了。
然后，这道题的正解是数论，各种转换，我也还没弄懂，就先不写了，昨天把脚扭了，现在还痛的不行。