IF's ACM Journey: 2009-03

Sunday, 22 March 2009

The 9th Zhejiang University Programming Contest B

题目在这里：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3207

我还只能化简到这个程度：

uint F(int n){
    uint r=0;
    for(int i=2;i<=n;++i){
        r+=n/i;
    }
    return r;
}

O(n)时间复杂度显然是不够的——所以如你所料，我还没做出来。

The 9th Zhejiang University Programming Contest I

题目在这里：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3214


#include <iostream>
using namespace std;
unsigned int gray2dec(unsigned int x) {
 unsigned int y = x; while(x>>=1) y ^= x; return y;
}
int main() {
 int N,n;
 for(cin>>N;N;--N){
     cin>>n; cout<<gray2dec((1<<n)-1)<<endl;
 }
 return 0;
}

The 9th Zhejiang University Programming Contest F

题目在这里 http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3211


#include <iostream>
#include <memory.h>
using namespace std;
typedef unsigned int uint;
int p10(int n){
  switch(n){
      case 0: return 1;
      case 1: return 10;
      case 2: return 100;
      case 3: return 1000;
      case 4: return 10000;
      case 5: return 100000;
      case 6: return 1000000;
  }
}
bool fail(int n){
  for(;n;--n)
      cin.ignore(8,'\n');
  return false;
}
bool check(uint n){
  char tmp[8];
  bool should_move[6]={false};
  int i,remained;
  cin.getline(tmp,8);
  for(i=0;i<6;++i)
      should_move[i]=(n/p10(i))%10>=5;
  for(i=0;i<6;++i)
      if((tmp[i]=='o')==should_move[5-i]) return fail(7);
  cin.getline(tmp,8);
  cin.getline(tmp,8); //---
  cin.getline(tmp,8);
  cin.getline(tmp,8);
  for(i=0;i<6;++i)
      should_move[i]=(n/p10(i))%10%5==1;
  for(i=0;i<6;++i)
      if((tmp[i]=='o')==should_move[5-i]) return fail(3);
  cin.getline(tmp,8);
  for(i=0;i<6;++i)
      should_move[i]=(n/p10(i))%10%5==2;
  for(i=0;i<6;++i)
      if((tmp[i]=='o')==should_move[5-i]) return fail(2);
  cin.getline(tmp,8);
  for(i=0;i<6;++i)
      should_move[i]=(n/p10(i))%10%5==3;
  for(i=0;i<6;++i)
      if((tmp[i]=='o')==should_move[5-i]) return fail(1);
  cin.getline(tmp,8);
  for(i=0;i<6;++i)
      should_move[i]=(n/p10(i))%10%5==4;
  for(i=0;i<6;++i)
      if((tmp[i]=='o')==should_move[5-i]) return false;
  return true;
}
int main() {
  int N,a,b;
  for(cin>>N;N;--N) {
      cin>>a>>b; cin.get();
      cout<<(check((a+b)*(b-a+1)/2)?"No mistake":"Mistake")<<endl;
  }
  return 0;
}

The 9th Zhejiang University Programming Contest A

题目如下：

The 9th Zhejiang University Programming Contest - A

Square Root Day

Time Limit: 1 Second Memory Limit: 32768 KB

Square Root Day is an unofficial holiday celebrated on days when both the day of

the month and the month are the square root of either the last two or three

digits of the year. For example, the last Square Root Day was March 3, 2009

(3/3/09), and the next Square Root Day will be April 4, 2016 (4/4/16).

Input

The first line of the input contains an integer T (T <= 10), indicating the

number of cases.

Then T lines follows, each has two integers x and y (1 <= x <= y <= 2009).

Output

Output the number of Square Root Days from year x to year y, both inclusive.

Sample Input

2009 2009

81 100

Sample Output


#include <iostream>
#include <cmath>
using namespace std;
int calc(int from,int to){
  int n=0;
  for(;from<=to;++from) {
      int x3=from%1000,x2=from%100;
      if(x3==144) ++n;
      if(x3==121) ++n;
      if(x3==100) ++n;
      if(x2==81) ++n;
      if(x2==64) ++n;
      if(x2==49) ++n;
      if(x2==36) ++n;
      if(x2==25) ++n;
      if(x2==16) ++n;
      if(x2==9) ++n;
      if(x2==4) ++n;
      if(x2==1) ++n;
  }
  return n;
}
int main() {
  int n,f,t;
  for(cin>>n;n&&cin>>f>>t;--n)
      cout<<calc(f,t)<<endl;
  return 0;
}

Saturday, 21 March 2009

POJ ( acm.pku.edu.cn ) 3673


#include <iostream>
using namespace std;
unsigned __int64 mul(char* a,char*b){
   unsigned __int64 r=0;
   for(;*a;++a) {
       if(*a=='0')continue;
       for(char* c=b;*c;++c) {
           r+=(*a-'0')*(*c-'0');
       }
   }
   return r;
}
int main()
{
   for(char a[16],b[16];cin>>a>>b;cout<<mul(a,b)<<endl);
   return 0;
}

POJ ( acm.pku.edu.cn ) 3650

我爱STL


#include <iostream>
#include <string>
using namespace std;
#define CR(c,n) case c: str.replace(b,1,"%" #n); b+=2; break
string replace_all(string& str){
  size_t b;
  for(b=0;b<str.length();++b) {
      switch ( str[b] ){
          CR(' ',20);CR('!',21);CR('$',24);CR('%',25);
          CR('(',28);CR(')',29);CR('*',2a);
          default:break;
      }
  }
  return str;
}

int main()
{
  for(string str; getline(cin,str)&&str!="#"; cout<<replace_all(str)<<endl);
  return 0;
}

POJ ( acm.pku.edu.cn ) 3589

水啊水啊


#include <iostream>
using namespace std;
int main() {
  int N;
  for(cin>>N;N;--N){
      int digit[10]={0},A=0,B=0;
      char x[5],y[5],*i,*j;
      cin>>x>>y;
      for(i=x,j=y;*i;++digit[*i-'0'],++i,++j) if(*i==*j) ++A;
      for(i=x,j=y;*i;++i,++j) if(digit[*j-'0']&&*i!=*j) ++B;
      cout<<A<<'A'<<B<<'B'<<endl;
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 3518

我挺自我欣赏那二分查找的算法


#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
typedef unsigned int uint;
uint primes[100001];
struct init {
 init() {
     primes[0]=2;
     bool ok=true;
     int n=1;
     uint p;
     for (uint i=3;n<=100000;i+=2) {
         ok=true;
         uint sq=sqrt(double(i))+1;
         for (uint j=1;j<n;++j) {
             p=primes[j];
             if (p>sq)   {
                 ok=true;
                 break;
             }
             if (i%p==0) {
                 ok=false;
                 break;
             }
         }
         if (ok) {
             primes[n]=i;
             ++n;
         }
     }
 }
}initer;

template <class T>
size_t bin_search(T* array, size_t len, T const& n) {
 size_t a=0,b=len,m1,m2=-1;
 for (m1=(a+b)>>1;m1!=m2;) {
     m2=m1;
     if     (array[m1]==n) return m1;
     else if (array[m1]<n)  a=m1;
     else /*(array[m1]>n)*/b=m1;
     m1=(a+b)>>1;
 }
 if (array[m1]<n) return m1;
 else /*(array[m1]>n)*/ return m1-1;
}

int main() {
 for(int n;cin>>n&&n;){
     int p=bin_search<uint>(primes,100000,n);
     if (primes[p]==n) cout<<0<<endl;
     else cout<<primes[p+1]-primes[p]<<endl;
 }
 return 0;
}

POJ ( acm.pku.edu.cn ) 3100

本以为用 floor(pow(b,1./n)) 可以直接算出来——谁知道错了。


#include <iostream>
#include <cmath>
using namespace std;
inline int p(int a,int b){
for(int x=a;--b>0;a*=x);
return a;
}
int main() {
for(int b,n,i;cin>>b>>n&&b&&n;cout<<endl){
   double x=floor(pow(b,1./n));
   for(i=x;p(i,n)<b;++i);
   if(p(i,n)-b>b-p(i-1,n))
       cout<<i-1;
   else
       cout<<i;
}
return 0;
}

POJ ( acm.pku.edu.cn ) 3094

我爱水题我爱水题


#include <iostream>
#include <string>
using namespace std;
int main(){
  for(string str;getline(cin,str)&&str!="#";){
      int crc=0;
      for(int i=0;i<str.length();++i){
          char c=str[i];
          if(c<='Z'&&c>='A')
              crc+=(i+1)*(c-'A'+1);
      }
      cout<<crc<<endl;
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 3085

水题，贪心，我喜欢


#include <iostream>
using namespace std;
int main(){
 int N;cin>>N;
 for(int i=1;i<=N;++i){
     int cents,q=0,d=0,n=0,p=0;
     cin>>cents;
     for(;cents-25>=0;cents-=25) ++q;
     for(;cents-10>=0;cents-=10) ++d;
     for(;cents- 5>=0;cents-= 5) ++n;
     for(;cents>0;  --cents    ) ++p;
     cout<<i<<' '
         <<q<<" QUARTER(S), "<<d<<" DIME(S), "
         <<n<<" NICKEL(S), "<<p<<" PENNY(S)"
         <<endl;
 }
 return 0;
}

POJ ( acm.pku.edu.cn ) 3077

我小学时还真以为“应该”这样舍入呢


#include <iostream>
using namespace std;
//int xround(int n){
//    double dn=n;
//    int d=floor(log10(dn))+1;
//    int pow10=1;
//    for (int i=1;i<d;++i) pow10*=10;
//    return int(dn/pow10+0.5)*pow10;
//}
char* xround(char n[]){
  static char ret[16]={0};
  char *a=n,*b=ret+15;
  for(;*a;++a);
  for(--a,--b;a!=n;--a,--b){
      if(*a-'0'>=5)
          ++*(a-1);
      *b=*a='0';
  }
  if(*a-'0'>=10){
      *b='0';
      *--b='1';
  } else {
      *b=*a;
  }
  return b;
}
int main(){
  int N;
  for(cin>>N;N;--N){
      char n[16];
      cin>>n;
      cout<<xround(n)<<endl;
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 3062

考胆量的


#include <iostream>
#include <string>
using namespace std;
int main(){
  for(string str;getline(cin,str);cout<<str<<endl);
  return 0;
}

POJ ( acm.pku.edu.cn ) 3030

水得一塌糊涂


#include <iostream>
using namespace std;
int main(){
  int n,r,e,c,x;
  for(cin>>n;n;--n){
      cin>>r>>e>>c;
      x=e-r;
      if(x>c)cout<<"advertise\n";
      else if(x<c)cout<<"do not advertise\n";
      else cout<<"does not matter\n";
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 2105

早年写的


#include <iostream>
using namespace std;

int main()
{
  int i,j,k,n;
  int a[4];
  char **cIp;
  cin>>n;
  cIp=new char* [n];
  for(i=0;i<n;i++) cIp[i]=new char[36];
  for(i=0;i<n;i++) cin>>cIp[i];
  for(i=0;i<n;i++)
  {
      a[0]=a[1]=a[2]=a[3]=0;
      for(k=0;k<4;k++)
      {
          for(j=k*8;j<k*8+8;j++)
          {
              a[k]<<=1;
              a[k]+=cIp[i][j]=='0'?0:1;
          }
          cout<<a[k]<<(k==3?'\n':'.');
      }
  }
  for(i=0;i<n;++i) delete[] cIp[i];
  delete[] cIp;
  return 0;
}

POJ ( acm.pku.edu.cn ) 1915

以前写过求马的周游路线的算法——相对而言这道题就没啥难度了。


#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[304][304];

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() {
  int N;
  for(cin>>N;N;--N){
      int size; cin>>size;
      int xf,yf,xt,yt; cin>>xf>>yf>>xt>>yt;
      board b={OUT};
      for(int i=2;i<size+2;++i)
          for(int j=2;j<size+2;++j)
              b[i][j]=OK;
      b[xf+2][yf+2]=VISITED;
      b[xt+2][yt+2]=TARGET;
      cout<<go(b,xf+2,yf+2)<<endl;
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 1458

经典DP，做过一次以后再做就觉得简单了。


#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

size_t cs(string const& a, string const& b) {
  size_t table[256][256]={0};
  for(size_t ia=1;ia<=a.length();++ia)
      for(size_t ib=1;ib<=b.length();++ib)
          table[ia][ib]=a[ia-1]==b[ib-1]?table[ia-1][ib-1]+1:max(table[ia-1][ib],table[ia][ib-1]);
  return table[a.length()][b.length()];
}

int main() {
  for(string a,b;cin>>a>>b;cout<<cs(a,b)<<endl);
  return 0;
}

POJ ( acm.pku.edu.cn ) 1050

把二维的拍扁成一维的，然后谁都会做了。


#include <iostream>
using namespace std;
__int64 max_sum(int* array, size_t len){
__int64 m=-0x7fffffff, mx=-0x7fffffff;
for ( size_t i=0;i<len;++i) {
   if ( mx>=0 ) mx+=array[i];
   else if (mx<array[i]) mx=array[i];
   if(mx>m) m=mx;
}
return m;
}
template <class T>
__int64 max_sum_2d(T matrix, size_t len){
__int64 m=-0x7fffffff,t;
for(int i=0;i<len;++i){
   int tmparr[100]={0};
   for(int j=i;j<len;++j){
       for(int k=0;k<len;++k)
           tmparr[k]+=matrix[j][k];
       t=max_sum(tmparr,len);
       if(t>m) m=t;
   }
}
return m;
}

int main() {
int matrix[100][100];
for(int n;cin>>n;){
   for(int i=0;i<n;++i)
       for(int j=0;j<n;++j)
           cin>>matrix[i][j];
   cout<<max_sum_2d(matrix,n)<<endl;
}
return 0;
}

对了还有神奇的事情就是把函数头改了改之后他算出来的答案就很无厘头了：

有人知道为什么吗？


template <class T,int len>
__int64 max_sum_2d(T (&matrix)[len][len]){
  __int64 m=-0x7fffffff,t;
  for(int i=0;i<len;++i){
      int tmparr[len]={0};
      for(int j=i;j<len;++j){
          for(int k=0;k<len;++k)
              tmparr[k]+=matrix[j][k];
          t=max_sum(tmparr,len);
          if(t>m) m=t;
      }
  }
  return m;
}

POJ ( acm.pku.edu.cn ) 1049

之前由于使用 char 而非 unsighed char 数据类型吃了苦头。


#include <iostream>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cstdarg>
using namespace std;
#if 0
void dbg_print(char* fmt, ...){
    va_list vl;
    va_start(vl,fmt);
    vfprintf(stderr,fmt,vl);
    va_end(vl);
}
#else
#define dbg_print(...) /*nothing*/
#endif
inline unsigned char to_int(char c){
  if(c>='A'){
      c-=('A'-10);
  } else {
      c-='0';
  }
  return c;
}
inline unsigned char to_hex(char c){
  if(c>=10){
      c+='A'-10;
  } else {
      c+='0';
  }
  return c;
}
inline unsigned char to_address(char high,char low){
  return (to_int(high)<<4|to_int(low));
}
void operate(char* mem){
  unsigned char A=0,B=0,address,tmp;
  for(char* m=mem;*m&&*m!='8';++m){
      switch(*m){
          case '0':
              address=to_address(m[1],m[2]);
              m+=2;
              A=to_int(mem[address]);
              dbg_print("    [debug]  %c%c%c\t read  A ( %01X ) from mem ( %02X )\n",*(m-2),*(m-1),*m,A,address);
              break;
          case '1':
              address=to_address(m[1],m[2]);
              m+=2;
              mem[address]=to_hex(A);
              dbg_print("    [debug]  %c%c%c\t write A ( %01X ) to mem ( %02X )\n",*(m-2),*(m-1),*m,A,address);
              break;
          case '2':
              tmp=A;A=B;B=tmp;
              dbg_print("    [debug]  %c\t\t swap A and B, got: A ( %01X ) B ( %01X )\n",*m,A,B);
              break;
          case '3':
              tmp=A+B;
              A=tmp&0xf;
              B=tmp>>4;
              dbg_print("    [debug]  %c\t\t add A and B, got: A ( %01X ) B( %01X )\n",*m,A,B);
              break;
          case '4':
              ++A; if(A>=16) A=0;
              dbg_print("    [debug]  %c\t\t inc A, got: A ( %01X )\n",*m,A);
              break;
          case '5':
              --A; if(A<0) A=0xf;
              dbg_print("    [debug]  %c\t\t dec A, got: A ( %01X )\n",*m,A);
              break;
          case '6':
              address=to_address(m[1],m[2]);
              m+=2;
              if(A==0){
                  m=mem+address-1;
                  dbg_print("    [debug]  %c%c%c\t bz, go to address %02X\n",*(m-2),*(m-1),*m,address);
                  break;
              }
              dbg_print("    [debug]  %c%c%c\t bz, go on\n",*(m-2),*(m-1),*m);
              break;
          case '7':
              address=to_address(m[1],m[2]);
              m+=2;
              m=mem+address-1;
              dbg_print("    [debug]  %c%c%c\t jump to address %02X\n",*(m-2),*(m-1),*m,address);
              break;
          case '8':
              break;
      }
  }
}
void print(char* mem){
  puts(mem);
}
int main() {
  for(char mem[257];gets(mem);){
      if(mem[0]=='8')break;
      operate(mem); print(mem);
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 1032


#include <iostream>
using namespace std;
int main(){
   for(int n;cin>>n;){
       int i,j,s;
       for(s=0,i=2;s<n;s+=i,++i);
       if (s==n) {
           for(j=2;j<i;++j)
               cout<<j<<" ";
       } else if (s-n==1) {
           for(j=2;j<i-2;)
               cout<<++j<<" ";
           cout<<j+2<<" ";
       } else {
           for(j=2;j<s-n;++j)
               cout<<j<<" ";
           for(;j<i-1;)
               cout<<++j<<" ";
       }
       cout<<endl;
   }
   return 0;
}

POJ ( acm.pku.edu.cn ) 1028


#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main()
{
   char instu[16]; string url;
   deque<string> b,f;
   b.push_back("http://www.acm.org/");
   while(cin>>instu){
       switch(*instu){
           case 'V':
               f.clear(); if(url!="") b.push_back(url);
               cin>>url;
               cout<<url<<endl;
               break;
           case 'B':
               if(b.empty())
                   cout<<"Ignored"<<endl;
               else {
                   f.push_back(url);
                   url=b.back();
                   b.pop_back();
                   cout<<url<<endl;
               }
               break;
           case 'F':
               if(f.empty())
                   cout<<"Ignored"<<endl;
               else {
                   b.push_back(url);
                   url=f.back();
                   f.pop_back();
                   cout<<url<<endl;
               }
               break;
           default:
               return 0;
       }
   }
   return 0;
}

POJ ( acm.pku.edu.cn ) 1026


#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
//void encode ( char* in, char* out, int* key, int len, int k) {
//    for (;k;--k){
//        for (int i=0;i<len;++i) {
//            out[key[i]]=in[i];
//        }
//        swap(in,out);
//    }
//    swap(in,out);
//}

char* encode(char* in, char* out, int* key, int len, int k) {
for (int i=0;i<len;++i){
   int n,c,a;
   for(n=1,c=key[i];c!=i;c=key[c])++n;
   for(c=i,a=k%n;a;--a)c=key[c];
   out[c]=in[i];
}
return out;
}

int main() {
for (int N;cin>>N&&N;){
   int key[256];
   for(int i=0;i<N;++i) {
       cin>>key[i];
       --key[i];
   }
   for(int k;cin>>k&&k>0;){
       cin.get();//space
       char msg[256],enmsg[256]={0}; cin.getline(msg,256);
       int l=strlen(msg);
       for(;l<N;++l)msg[l]=' ';
       msg[l]=0;
       encode(msg,enmsg,key,N,k);
       cout<<enmsg<<endl;
   }
   cout<<endl;
}
return 0;
}

之后，为了避免重复计算，我这么改进了：


#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

class encoder {
 int* key;
 int len;
 int circle_len[256];
 encoder();
 encoder(encoder const&);
public:
 encoder(int *key, int len):key(key),len(len){calc_circle();}
 ~encoder(){delete[] circle_len;}
 void calc_circle() {
     for (int i=0;i<len;++i){
         int n,c;
         for(n=1,c=key[i];c!=i;c=key[c])++n;
         circle_len[i]=n;
     }
 }
 char* operator()(char* in, char* out, int k){
     for (int i=0;i<len;++i){
         int c,a;
         for(c=i,a=k%circle_len[i];a;--a)c=key[c];
         out[c]=in[i];
     }
     return out;
 }
};


int main() {
 for (int N;cin>>N&&N;){
     int key[256];
     for(int i=0;i<N;++i) {
         cin>>key[i];
         --key[i];
     }
     encoder encode(key, N);
     for(int k;cin>>k&&k>0;){
         cin.get();//space
         char msg[256],enmsg[256]; cin.getline(msg,256);
         int l=strlen(msg);
         for(;l<N;++l)msg[l]=' ';
         msg[l]=enmsg[l]=0;
         encode(msg,enmsg,k);
         cout<<enmsg<<endl;
     }
     cout<<endl;
 }
 return 0;
}

——结果是戏剧性的 Runtime Error

POJ ( acm.pku.edu.cn ) 1019

之前使用 int 数据类型导致了3 次无辜的 WA~


#include <iostream>
using namespace std;
typedef unsigned int uint;
uint len[31300];
inline uint dig(uint n) {
 if     (n<10) return 1;
 else if(n<100) return 2;
 else if(n<1000) return 3;
 else if(n<10000) return 4;
 else if(n<100000) return 5;
 else if(n<1000000) return 6;
 else return -1;
}
inline uint pow10(uint n){
 switch (n){
     case 0: return 1;
     case 1: return 10;
     case 2: return 100;
     case 3: return 1000;
     case 4: return 10000;
     case 5: return 100000;
     case 6: return 1000000;
     default:return -1;
 }
 return -1;
}
struct init {
 init() {
     len[0]=0;
     for (uint i=1; i<31300; i++) {
         len[i]=len[i-1]+dig(i);
     }
 }
} initer;

uint f(uint n) {
 uint digits=0;
 uint i=0,j;
 for(;digits<n;digits+=len[i]) ++i;//这里可以考虑用二分查找
 if (digits==n) return i%10;
 uint front=digits-len[i]+1;
 for(j=1;front<n;front+=dig(j)) ++j;
 if (front==n) return j%10;
 return (j/pow10(front-n))%10;
}

int main(uint argc, char *argv[]) {
 uint N;
 uint n;
 for(cin>>N;N;--N){
     cin>>n; cout<<f(n)<<endl;
 }
 return 0;
}

POJ ( acm.pku.edu.cn ) 1014


#include<iostream>
#include<cstdlib>
using namespace std;
#define A_SIZE 60001
bool can[A_SIZE];
bool can_div(int marbles[6])
{
  int mid=0,i,j,k,t,back=0;
  for(i=0;i<6;++i)mid+=marbles[i]*(i+1);
  if (mid&1) return false;
  mid>>=1;
//  cerr<<"    [debug]   mid="<<mid<<endl;
  memset(can,0,A_SIZE);
  can[0]=1;
  for(i=1;i<=6;++i)
  {
      if(marbles[i-1])
      {
          for(j=back;j>=0;--j)
          {
              if(can[j])
              {
                  if (can[mid]) return true;
                  for(k=1;k<=marbles[i-1];++k)
                  {
                      t=i*k+j;
                      if(t>mid)break;
                      if(can[t])break;
                      can[t]=1;
//  cerr<<"    [debug]   t="<<t<<"\ti="<<i<<"\tj="<<j<<"\tk="<<k<<endl;
                  }
              }
          }
          back+=i*marbles[i-1];
          if (back>mid) back=mid;
      }
  }
  if(can[mid])return true;
  return false;
}

int main()
{
  int marbles[6];
  int q=0,t=0;
  for(;;)
  {
      q=0;++t;
      for(int i=0;i<6;++i)
      {
          cin>>marbles[i];
          q+=marbles[i];
      }
      if(q==0)break;
      cout<<"Collection #"<<t<<":\n"<<(can_div(marbles)?"Can":"Can\'t")<<" be divided.\n\n";
  }
  return 0;
}

POJ ( acm.pku.edu.cn ) 1011

剪枝，深搜，that's it.


#include <memory.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int  g_sticks[65];
bool g_used[65];
int  g_length;
int  g_sum;
int  g_max;
int  g_min;
int  g_target;

bool dfs(int target, int remained, int begin) {
 if( target<g_min||begin>=g_length )
     return false;
 if (target==g_target) { //第一根
     for (int i=begin;i<g_length;++i) {
         if (g_used[i])
             continue;
         g_used[i]=true;
         if(g_sticks[i]==target){ // 最后一根
             if(remained==1)
                 return true;
             if(dfs(g_target , remained-1, 1))
                 return true;
             g_used[i]=false;
             return false;
         } else if (dfs(target-g_sticks[i],remained,i+1))
             return true;
         g_used[i]=false;
         return false;
     }
 } else {
     for (int i=begin;i<g_length;++i) {
         if (g_used[i])
             continue;
         if (g_sticks[i]>target)
             continue;
         g_used[i]=true;
         if(g_sticks[i]==target){ // 最后一根
             if(remained==1)
                 return true;
             if(dfs(g_target , remained-1, 1))
                 return true;
             g_used[i]=false;
             return false;
         }
         if (dfs(target-g_sticks[i],remained,i+1))
             return true;
         g_used[i]=false;
         for(;g_sticks[i]==g_sticks[i+1];++i);
     }
 }
 return false;
}

//#include <fstream>
int main() {
//    ifstream fin("test.txt");
 istream& xin=cin;
 for (;xin>>g_length&&g_length;) {
     int x;
     bool succeed=false;
     g_max=g_sum=0;
     g_min=1000;
     for (int i=0;i<g_length;++i) {
         xin>>x;
         g_sticks[i]=x;
         g_sum+=x;
         if (x>g_max) g_max=x;
         if (x<g_min) g_min=x;
         g_used[i]=false;
     }
     sort(g_sticks,g_sticks+g_length,greater<int>());
     g_sticks[g_length]=0;
     g_used[g_length]=true;
     for (int j=g_max;j<=g_sum/2;++j) {
         if (g_sum%j==0) {
             g_target=j;
             if ( dfs(j,g_sum/j,0) ) {
                 cout<<j<<endl;
                 succeed=true;
                 break;
             }
         }
     }
     if (!succeed)
         cout<<g_sum<<endl;
 }
 return 0;
}

看完整版本就知道我下了多大功夫了：


#if 1 // includes
#include <memory.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#endif   //  for folding

#define POJ_IS_STUPID 0
#if     POJ_IS_STUPID
#if 0

struct state { //里面这些东西不一定都用得着倒是了
    int sticks[51];  // 长度为 i 的木棍有 sticks[i] 个。
    int figures[51]; // 各种长度
    int nfigures;
    int length;
    int target;
    int remained;
    int max;
    int min;
    int sum;
};
template <class T>
size_t inv_bin_search(T* array, size_t len, T const& n) {
    size_t a=0,b=len,m1,m2=-1;
    for (m1=(a+b)>>1;m1!=m2;) {
        m2=m1;
        if     (array[m1]==n) return m1;
        else if (array[m1]>n)  a=m1;
        else b=m1;
        m1=(a+b)>>1;
    }
    if (array[m1]<n) return m1;
    else return m1-1;
}

bool match(state& st, int target) {
    bool first=(target==st.target);
    int i,*j;
    if (target>st.max) {
        //for(i=st.max;i>=st.min;--i){
        for (j=st.figures;i=*j;++j) {
            if (st.sticks[i]) {
                --st.sticks[i];
                st.sum-=i;
                if (match(st,target-i))
                    return true;
                st.sum+=i;
                ++st.sticks[i];
                if (first)
                    return false;
            }
        }
        return false;
    } else if (target<st.min) {
        return false;
    } else if (target>st.sum) {
        return false;
    } else if (target==st.sum) {
        return true;
    }
    if (st.sticks[target]) {
        --st.sticks[target];
        st.sum-=target;
        if (--st.remained==0) return true;
        if (match(st,st.target))
            return true;
        ++st.remained;
        st.sum+=target;
        ++st.sticks[target];
        return false;
    }
    for (j=st.figures+inv_bin_search<int>(st.figures,st.nfigures,target);
        *j>=target&&*j;++j);
    for (;i=*j;++j) {
        if (st.sticks[i]) {
            --st.sticks[i];
            st.sum-=i;
            if (match(st,target-i))
                return true;
            st.sum+=i;
            ++st.sticks[i];
            if (first)
                return false;
        }
    }
    return false;
}

int main() {
    for (state s={{0},{0},0,0};cin>>s.length&&s.length;) {
        s.sum=0;
        s.max=0;
        s.min=100;
        int x,i,j,n=0;
        bool succeed=false;
        for (i=0;i<=50;++i)
            s.sticks[i]=0;
        for (i=0;i<s.length;++i) {
            cin>>x;
            if (!s.sticks[x]) {
                s.figures[n]=x;
                ++n;
            }
            ++s.sticks[x];
            s.sum+=x;
            if (x>s.max) s.max=x;
            if (x<s.min) s.min=x;
        }
        s.figures[n]=0;
        s.nfigures=n;
        sort(s.figures,s.figures+n,greater<int>());
        for (j=s.max;j<=s.sum/2;++j) {
            if (s.sum%j==0) {
                s.target=j;
                s.remained=s.sum/j;
                if ( match(s,j) ) {
                    cout<<j<<endl;
                    succeed=true;
                    break;
                }
            }
        }
        if (!succeed)
            cout<<s.sum<<endl;
    }
    return 0;
}

#else

struct state { //里面这些东西不一定都用得着倒是了
  int sticks[51];  // 长度为 i 的木棍有 sticks[i] 个。
  int figures[51]; // 各种长度
  int nfigures;
  int length;
  int target;
  int remained;
  int max;
  int min;
  int sum;
};
template <class T>
size_t inv_bin_search(T* array, size_t len, T const& n) {
  size_t a=0,b=len,m1,m2=-1;
  for (m1=(a+b)>>1;m1!=m2;) {
      m2=m1;
      if     (array[m1]==n) return m1;
      else if (array[m1]>n)  a=m1;
      else b=m1;
      m1=(a+b)>>1;
  }
  if (array[m1]<n) return m1;
  else return m1-1;
}

bool match(state& st, int target) {
  int (&sticks)[51]=st.sticks;
  int (&figures)[51]=st.figures;
  int &sum=st.sum;
  int &remained=st.remained;
  bool first=(target==st.target);
  int i,*j;
  if (target>st.max) {
      //for(i=st.max;i>=st.min;--i){
      for (j=figures;i=*j;++j) {
          if (sticks[i]) {
              --sticks[i];
              sum-=i;
              if (match(st,target-i))
                  return true;
              sum+=i;
              ++sticks[i];
              if (first)
                  return false;
          }
      }
      return false;
  } else if (target<st.min) {
      return false;
  } else if (target>st.sum) {
      return false;
  } else if (target==st.sum) {
      return true;
  }
  if (sticks[target]) {
      --sticks[target];
      sum-=target;
      if (--remained==0) return true;
      if (match(st,st.target))
          return true;
      ++remained;
      sum+=target;
      ++sticks[target];
      return false;
  }
  for (j=figures+inv_bin_search<int>(figures,st.nfigures,target);
      *j>=target&&*j;++j);
  for (;i=*j;++j) {
      if (sticks[i]) {
          --sticks[i];
          sum-=i;
          if (match(st,target-i))
              return true;
          sum+=i;
          ++sticks[i];
          if (first)
              return false;
      }
  }
  return false;
}

int main() {
  for (state s={{0},{0},0,0};cin>>s.length&&s.length;) {
      s.sum=0;
      s.max=0;
      s.min=100;
      int x,i,j,n=0;
      bool succeed=false;
      for (i=0;i<=50;++i)
          s.sticks[i]=0;
      for (i=0;i<s.length;++i) {
          cin>>x;
          if (!s.sticks[x]) {
              s.figures[n]=x;
              ++n;
          }
          ++s.sticks[x];
          s.sum+=x;
          if (x>s.max) s.max=x;
          if (x<s.min) s.min=x;
      }
      s.figures[n]=0;
      s.nfigures=n;
      sort(s.figures,s.figures+n,greater<int>());
      for (j=s.max;j<=s.sum/2;++j) {
          if (s.sum%j==0) {
              s.target=j;
              s.remained=s.sum/j;
              if ( match(s,j) ) {
                  cout<<j<<endl;
                  succeed=true;
                  break;
              }
          }
      }
      if (!succeed)
          cout<<s.sum<<endl;
  }
  return 0;
}

#endif
#else
#if 0 //以前的

struct state { //不想用全局变量, 又不应该在递归的函数中使用太多参数, so...
    int  sticks[65];
    bool thereis[65];
    int  length;
    int  sum;
    int  max;
    int  target;
};

bool dfs(state& st, int target, int nremained, int begin=0) {
    if ( target==0 ) {
        if ( nremained==1 )
            return true;
        else
            return dfs(st,st.target,nremained-1,1);
    } else {
        if (begin>=st.length)
            return false;
        bool first=(target==st.target),last=false;
        for (int i=begin;i<st.length;++i) {
            if (!st.thereis[i])
                continue;
            if (st.sticks[i]>target) {
                // if(first){return false;}//impossible
                continue;
            }
            st.thereis[i]=false;
            last=(st.sticks[i]==target);
            if (dfs(st,target-st.sticks[i],nremained,i+1)) {
                return true;
            } else {
                st.thereis[i]=true;
                if ( first||last ) return false;
                for (;st.sticks[i]==st.sticks[++i];);
                --i;
            }
        }
    }
    return false;
}

int main() {
    for (state s;cin>>s.length&&s.length;) {
        s.max=s.sum=0;
        int x;
        bool succeed=false;
        for (int i=0;i<s.length;++i) {
            cin>>x;
            s.sticks[i]=x;
            s.sum+=x;
            if (x>s.max) s.max=x;
            s.thereis[i]=true;
        }
        sort(s.sticks,s.sticks+s.length,greater<int>());
        s.sticks[s.length]=0;
        s.thereis[s.length]=false;
        for (int j=s.max;j<=s.sum/2;++j) {
            if (s.sum%j==0) {
                s.target=j;
                if ( dfs(s,j,s.sum/j) ) {
                    cout<<j<<endl;
                    succeed=true;
                    break;
                }
            }
        }
        if (!succeed)
            cout<<s.sum<<endl;
    }
    return 0;
}

#else

int  g_sticks[65];
bool g_used[65];
int  g_length;
int  g_sum;
int  g_max;
int  g_min;
int  g_target;

bool dfs(int target, int remained, int begin) {
  if( target<g_min||begin>=g_length )
      return false;
  if (target==g_target) { //第一根
      for (int i=begin;i<g_length;++i) {
          if (g_used[i])
              continue;
          g_used[i]=true;
          if(g_sticks[i]==target){ // 最后一根
              if(remained==1)
                  return true;
              if(dfs(g_target , remained-1, 1))
                  return true;
              g_used[i]=false;
              return false;
          } else if (dfs(target-g_sticks[i],remained,i+1))
              return true;
          g_used[i]=false;
          return false;
      }
  } else {
      for (int i=begin;i<g_length;++i) {
          if (g_used[i])
              continue;
          if (g_sticks[i]>target)
              continue;
          g_used[i]=true;
          if(g_sticks[i]==target){ // 最后一根
              if(remained==1)
                  return true;
              if(dfs(g_target , remained-1, 1))
                  return true;
              g_used[i]=false;
              return false;
          }
          if (dfs(target-g_sticks[i],remained,i+1))
              return true;
          g_used[i]=false;
          for(;g_sticks[i]==g_sticks[i+1];++i);
      }
  }
  return false;
}

#include <fstream>
int main() {
  ifstream fin("test.txt");
  istream& xin=fin;
  for (;xin>>g_length&&g_length;) {
      int x;
      bool succeed=false;
      g_max=g_sum=0;
      g_min=1000;
      for (int i=0;i<g_length;++i) {
          xin>>x;
          g_sticks[i]=x;
          g_sum+=x;
          if (x>g_max) g_max=x;
          if (x<g_min) g_min=x;
          g_used[i]=false;
      }
      sort(g_sticks,g_sticks+g_length,greater<int>());
      g_sticks[g_length]=0;
      g_used[g_length]=true;
      for (int j=g_max;j<=g_sum/2;++j) {
          if (g_sum%j==0) {
              g_target=j;
              if ( dfs(j,g_sum/j,0) ) {
                  cout<<j<<endl;
                  succeed=true;
                  break;
              }
          }
      }
      if (!succeed)
          cout<<g_sum<<endl;
  }
  return 0;
}

#endif
#endif

IF's ACM Journey