POJ 1051

水题。

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
char Mcode[30][5]={
   /*A-G:*/".-","-...","-.-.","-..",".","..-.","--.",
   /*H-N:*/"....","..",".---","-.-",".-..","--","-.",
   /*O-U:*/"---",".--.","--.-",".-.","...","-","..-",
   /*V-Z:*/"...-",".--","-..-","-.--","--..",
   /*_.,?*/"..--","---.",".-.-","----"
};
int len[30]={
2, 4, 4, 3, 1, 4, 3,4, 2, 4, 3, 4, 2, 2,
3, 4, 4, 3, 3, 1, 3,4, 3, 4, 4, 4,
4, 4, 4, 4
};
int index(char ch){
   if(ch<='Z'&&ch>='A')
       return ch-'A';
   switch(ch){
       case '_':return 26;
       case '.':return 27;
       case ',':return 28;
       case '?':return 29;
   }
   return -1;
}
char* encode(char c,int& n){
   int i=index(c);
   n=len[i];
   return Mcode[i];
}
char decode(char* m,int n){
   for(int i=0;i<30;++i){
       if(n!=len[i]||strncmp(Mcode[i],m,n))
           continue;
       if(i<26)
           return i+'A';
       switch(i){
           case 26: return '_';
           case 27: return '.';
           case 28: return ',';
           case 29: return '?';
       }
   }
   return 0;
}
int main(){
   int N,n;cin>>N;
   for(n=1;n<=N;++n){
       char msg[128],crypt[128*4]={0},*p,*q;
       vector<int> codelen;
       int tmp;
       cin>>msg;
       for(p=msg,q=crypt;*p;++p){
           strcpy(q,encode(*p,tmp));
           codelen.push_back(tmp);
           q+=tmp;
       }
       q=crypt;
       cout<<n<<": ";
       for(int i=codelen.size()-1;i>=0;--i){
           cout<<decode(q,codelen[i]);
           q+=codelen[i];
       }
       cout<<endl;
   }
   return 0;
}

POJ 2390

水

#include <iostream>
using namespace std;
typedef unsigned int uint;
uint suck(int R,int M,int Y){
   double g=M,r=1.+R/100.;
   for(;Y--;g*=r);
   return g;
}
int main(){
   for(int R,M,Y;cin>>R>>M>>Y;cout<<suck(R,M,Y)<<endl);
   return 0;
}

POJ 1056

#include <iostream>
#include <string.h>
using namespace std;
bool sub(char const* a,char const* b){
   for(;*a==*b&&*a&&*b;++a,++b);
   return *a==0||*b==0;
}
bool ok(char vs[1024][11],int n){
   for(int i=0;i<n-1;++i)
       for(int j=i+1;j<n;++j)
           if(sub(vs[i],vs[j]))
               return false;
   return true;
}
int main(){
   int N=0;
   for(char buf[1024][11];;){
       int n=0;
       for(;cin>>buf[n]&&0[buf[n++]]!='9';);
       if(cin.eof())break;
       --n;
       cout<<"Set "<<++N<<(ok(buf,n)?" is":" is not")<<" immediately decodable"<<endl;
   }
   return 0;
}

POJ 1207

由于 f 可以比 t 小，卡住了无数次——而且就算改过来了还是不对——直到说出了粗口，它就突然 AC 了。

#include <iostream>
using namespace std;
typedef unsigned int uint;
uint fuck(int f,int t){
   uint b,x,n;
   if(f>t)f^=t^=f^=t;
   for(b=0;f<=t;++f){
       for(x=1,n=f;n-1;n=n&1?3*n+1:n>>1)++x;
       if(x>b)b=x;
   }
   return b;
}
int main(){
   for(uint f,t,b,x;cin>>f>>t;){
       if(f>10000||t>10000||f==0||t==0)break;
       cout<<f<<" "<<t<<" "<<fuck(f,t)<<endl;
   }
   return 0;
}

POJ 1046

水。

#include <iostream>
#include <cstdio>
using namespace std;
inline int p(int n){
   return n*n;
}
int main() {
   int R[16],G[16],B[16],r,g,b,i,j,min,tmp;
   for(i=0;i<16;++i)
       cin>>R[i]>>G[i]>>B[i];
   for(;cin>>r>>g>>b&&r+1;){
       min=0x7fffffff;
       for(i=0;i<16;++i) {
           tmp=p(R[i]-r)+p(G[i]-g)+p(B[i]-b);
           if(tmp<min){
               min=tmp;
               j=i;
           }
       }
       printf("(%d,%d,%d) maps to (%d,%d,%d)\n",r,g,b,R[j],G[j],B[j]);
   }
   return 0;
}

POJ 1068

笨方法

#include <iostream>
using namespace std;
enum bracket{
 LEFT=0,
 RIGHT=1,
 VISITED=2
};
int main() {
 int N;
 for(cin>>N;N;--N){
     int n,i,a[32];
     bracket b[64]={LEFT};
     cin>>n;
     for(i=0;i<n;++i) {
         cin>>a[i];
         b[a[i]+i]=RIGHT;
     }
     for(i=0;i<n<<1;++i){
         if(b[i]==RIGHT){
             int t=0;
             for(int j=i;j>=0;--j){
                 if(b[j]==RIGHT) ++t;
                 else if(b[j]==LEFT){
                     b[j]=VISITED;
                     break;
                 }
             }
             cout<<t<<" ";
         }
     }
     cout<<endl;
 }
 return 0;
}

POJ 1159

注意这个的最长公共子序列算法的空间复杂度

#include <stdio.h>
#include <string.h>
typedef unsigned int uint;
uint max(uint a,uint b){
  return a>b?a:b;
}
uint LCS(char* a,char*b){
  static uint matrix[2][5*1024]={{0},{0}};
  int i,j,k;
  for(i=0;a[i];++i) matrix[0][i]=0;
  for(i=1;a[i-1];++i){
      k=i%2;
      for(j=1;b[j-1];++j){
          if(a[i-1]==b[j-1])
              matrix[k][j]=matrix[!k][j-1]+1;
          else
              matrix[k][j]=max(matrix[k][j-1],matrix[!k][j]);
      }
  }
  return matrix[k][j-1];
}
int main() {
  char str[5001],s[5001];
  for(int n;scanf("%d%s",&n,str)+1;){
      strcpy(s,str);
      printf("%d\n",n-LCS(s,strrev(str)));
  }
  return 0;
}

POJ 1057

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct dir {
   string name;
   vector<dir>    subdir;
   vector<string> files;
   bool operator<(dir const& other) const {
       return this->name<other.name;
   }
};
void input(dir& d, string & str){
   switch(str[0]){
       case 'f':{
           d.files.push_back(str);
           cin>>str;
           input(d,str);
       } break;
       case 'd':{
           dir subdir;
           subdir.name=str;
           cin>>str;
           input(subdir,str);
           d.subdir.push_back(subdir);
       } break;
       default:
         return;
   }
}
ostream& spacer(int n){
   for(;n;--n) cout<<"|     ";
   return cout;
}
void output(dir & d,int level){
   if(!d.subdir.empty()){
       spacer(level+1)<<d.name<<endl;
//        sort(d.subdir.begin(),d.subdir.end());
       for(vector<dir>::iterator i=d.subdir.begin();i!=d.subdir.end();++i)
           output(*i,level+2);
   }
   sort(d.files.begin(),d.files.end());
   for(vector<string>::const_iterator i=d.files.begin();i!=d.files.end();++i)
       spacer(level)<<*i<<endl;
}
int main() {
   int N=0;
   for(string str;cin>>str;){
       if(str[0]=='#')break;
       else if(str[0]=='*')continue;
       dir d;
       input(d,str);
       cout<<"DATA SET "<<++N<<":"<<endl;
       output(d,0);
       cout<<endl;
   }
   return 0;
}

POJ 1936

混乱版：main(){char s[100001],t[100001],*p,*q;for(;scanf("%s%s",s,t)+1;puts(*p?"No":"Yes"))for(p=s,q=t;*p&&*q;*p==*q++&&++p);}

#include <iostream>
using namespace std;
bool isin(char* s,char *t){
  for(;*t;++t) if (*s==*t&&*++s==0) return true;
  return false;
}
int main() {
  for(char s[100001],t[100001];cin>>s>>t;cout<<(isin(s,t)?"Yes\n":"No\n"));
  return 0;
}

POJ 2243

#include <algorithm>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
typedef std::pair<int,int> move;
enum state {OUT=0, OK=1, VISITED=2, TARGET=-1};
typedef state board[12][12];
const int MOVES[8][2]={
   {-1,-2}, {-2,-1}, {-1,2}, {-2,1}, {1,-2}, {2,-1}, {1,2}, {2,1}
};
int go(board b,int x,int y){ //BFS
   if(b[x][y]==TARGET)
       return 0;
   deque<int> stepx[2];
   deque<int> stepy[2];
   stepx[0].push_back(x);
   stepy[0].push_back(y);
   int level=0;
   int l1=0,l2=1;
   while(true){
       ++level;
       if(stepx[l1].empty()) return -1;
       while(!stepx[l1].empty()){
           x=stepx[l1].front();
           stepx[l1].pop_front();
           y=stepy[l1].front();
           stepy[l1].pop_front();
           for(int i=0;i<8;++i){
               int tx=x+MOVES[i][0],ty=y+MOVES[i][1];
               if (b[tx][ty]==OUT) continue;
               if (b[tx][ty]==VISITED) continue;
               if (b[tx][ty]==TARGET) return level;
               b[tx][ty]=VISITED;
               stepx[l2].push_back(tx);
               stepy[l2].push_back(ty);
           }
       }
       l1^=l2^=l1^=l2;
   }
   return -1;
}

int main() {
   for(char f[3],t[3];cin>>f>>t;){
       const int xf=f[0]-'a',yf=f[1]-'1',xt=t[0]-'a',yt=t[1]-'1';
       board b={OUT};
       for(int i=2;i<10;++i)
           for(int j=2;j<10;++j)
               b[i][j]=OK;
       b[xf+2][yf+2]=VISITED;
       b[xt+2][yt+2]=TARGET;
       cout<<"To get from "<<f<<" to "<<t<<" takes "<<go(b,xf+2,yf+2)
           <<" knight moves."<<endl;
       //cout<<go(b,xf+2,yf+2)<<endl;
   }
   return 0;
}