2_01

辽宁师范大学 • 张大为@https://daweizh.github.io/noip/

2.1 基本算法之枚举(37)

Counterfeit Dollar，http://noi.openjudge.cn/ch0201/15/[+]

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

int n,f[30],t[30];
string l,r,p;

int main(){
//	freopen("15.in","r",stdin);
  
  cin >> n;
  while(n--){
    memset(f,0,sizeof(f));
    memset(t,0,sizeof(t));
    for(int it=1;it<=3;it++){
      cin >> l >> r >> p;
      if(p=="even"){
        int len=l.size();
        for(int i=0;i<len;i++) f[l[i]-'A']=1;
        for(int i=0;i<len;i++) f[r[i]-'A']=1;
      }
      if(p=="down"){
        int len=l.size();
        for(int i=0;i<len;i++) t[l[i]-'A']--;
        for(int i=0;i<len;i++) t[r[i]-'A']++;
      }		
      if(p=="up"){
        int len=l.size();
        for(int i=0;i<len;i++) t[l[i]-'A']++;
        for(int i=0;i<len;i++) t[r[i]-'A']--;
      }
    }
    for(int i=0;i<12;i++){
      if(f[i]==1) t[i]=0;
    }
    int mx = 0,pos=0;
    for(int i=0;i<12;i++){
      int val = abs(t[i]);
      if(val>mx){
        mx=val;
        pos = i;
      }
    }
    if(t[pos]<0)
      printf("%c is the counterfeit coin and it is light.\n",'A'+pos);
    else
      printf("%c is the counterfeit coin and it is heavy.\n",'A'+pos);
  }
  
  return 0;
}

Bomb Game，http://noi.openjudge.cn/ch0201/1661/[+]

#include <iostream>
#include <cstring>
using namespace std;

int row,col,k,x,y,p,t,a[105][105];

void bomb(int x,int y,int p,int t){
  int x1=max(1,x-p/2);
  int y1=max(1,y-p/2);
  int x2=min(row,x+p/2);
  int y2=min(col,y+p/2);
  if(t==0)
    for(int i=x1;i<=x2;i++)
      for(int j=y1;j<=y2;j++)
        a[i][j]=0;
  else
    for(int i=1;i<=row;i++)
      for(int j=1;j<=col;j++)
        if(i<x1||i>x2||j<y1||j>y2)
          a[i][j]=0;
}

int main(){
  memset(a,1,sizeof(a));
  cin >> row >> col >> k;
  for(int i=0;i<k;i++){
    cin >> x >> y >> p >> t;
    bomb(x,y,p,t);
  }
    
  int ans = 0;	
  for(int i=1;i<=row;i++){
    for(int j=1;j<=col;j++){
      if(a[i][j]) ans++;
    }
  }
  cout << ans << endl;
  
  return 0;
}

数字方格，http://noi.openjudge.cn/ch0201/1749/[+]

#include <iostream>
using namespace std;

int n,mx=0;

int main(){
  cin >> n;

  mx = 0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=n;k++){
        if((i+j)%2==0 && (j+k)%3==0 && (i+j+k)%5==0){
          if(i+j+k>mx)
            mx = i+j+k;			
        }
      }			
    }
  }

  cout << mx << endl;
  
  return 0;
}

鸡兔同笼，http://noi.openjudge.cn/ch0201/1752/[+]

#include <iostream>
using namespace std;

int main(){
  int a,maxl=-1,minl,flag=1;
  
  cin >> a;
  minl = a/2+1;
  //应考虑如22只脚这种情况 
  //有i只鸡，则有(a-i*2)/4只兔子
  //共有i+(a-i*2)/4=a/4+i/2动物
  //当i最大时，总数最大，当i最小时总数最小 
  for(int i=0;i<=a/2;i++){
    if((a-i*2)%4==0){
      if(i<minl)
        minl = i;
      if(i>maxl)
        maxl = i;
      flag = 0;
    }
  }	
  if(maxl==-1 && minl==a/2+1)
    cout << "0 0" << endl;
  else
    cout << int(a/4.00+minl/2.00) << " " << int(a/4.00 + maxl/2.00) << endl;
    
  return 0;
}

两倍，http://noi.openjudge.cn/ch0201/1809/[+]

#include <iostream>
using namespace std;

int a[100],p=0,x,cnt=0;

int main(){
  while(1){
    cin >> x;
    if(x!=0)
      a[p++] = x;
    else
      break;
  }
  for(int i=0;i<p;i++){
    for(int j=0;j<p;j++){
      if(a[i]*2==a[j]){
        cnt ++;
      }
    }
  }
  cout << cnt << endl;
  
  return 0;
}

完美立方，http://noi.openjudge.cn/ch0201/1812/[+]

#include <iostream>
#include <cmath>
using namespace std;

int n;

int main(){
  cin >> n;
  
  for(int a=2;a<=n;a++){
    for(int b=2;b<=n;b++){
      for(int c=b+1;c<=n;c++){
        for(int d=c+1;d<=n;d++){
          int t =  b*b*b + c*c*c+d*d*d;
          if(a*a*a==t){
            cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")" << endl;
          }
        }
      }
    }
  }

  return 0;
}

熄灯问题，http://noi.openjudge.cn/ch0201/1813/[+]

#include <iostream>
using namespace std;

int light[5][6],res[5][6],status[5][6];

int main(){
  for(int i=0;i<5;i++)
    for(int j=0;j<6;j++)
      cin >> light[i][j];
  //对第一行按开关的所有可能枚举共2^6=64种
  //看这64中的哪一种能让所有灯熄灭 
  for(int i=0;i<64;i++){
    //初始化status为初态 
    for(int x=0;x<5;x++)
      for(int y=0;y<6;y++)
        status[x][y]=light[x][y];
    //获得第一行在i时所在状态 
    for(int j=0;j<6;j++)
      res[0][j]=(i>>j)&1;
    //用第一行的i状态按开关 
    for(int j=0;j<6;j++)
      if(res[0][j]==1){
        status[0][j]=1-status[0][j];				//自己 
        if(j-1>=0) status[0][j-1]=1-status[0][j-1];	//左侧
        if(j+1<6) status[0][j+1]=1-status[0][j+1];	//右侧
        status[1][j]=1-status[1][j];				//下面 
      }
    //按剩下行开关产生的效果
    for(int x=1;x<5;x++){
      for(int y=0;y<6;y++)
        res[x][y]=status[x-1][y];
      for(int y=0;y<6;y++)
        if(res[x][y]==1){
          status[x-1][y]=1-status[x-1][y];			//上面 
          status[x][y]=1-status[x][y];				//自己 
          if(y-1>=0) status[x][y-1]=1-status[x][y-1];	//左侧
          if(y+1<6) status[x][y+1]=1-status[x][y+1];	//右侧
          if(x<4) status[x+1][y]=1-status[x+1][y];	//下面 
        }
    }
    //看看最后一行是不是全熄灭了
    bool flag = true;
    for(int j=0;j<6;j++)
      if(status[4][j]==1){
        flag = false;
        break;
      } 
    //如果全熄灭了就找到了
    if(flag){
      for(int x=0;x<5;x++){
        cout << res[x][0];
        for(int y=1;y<6;y++)
          cout << " " << res[x][y];
        cout << endl;
      }
      break;
    } 
  }

  return 0;
}

画家问题，http://noi.openjudge.cn/ch0201/1815/[+]

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

int n,Min=100000,wall[20][20],stat[20][20];
string s[20];

int main(){
  cin >> n;

  for(int i=0;i<n;i++){
    cin >> s[i];
    for(int j=0;j<n;j++)
      if(s[i][j]=='w') wall[i][j]=1;
      else wall[i][j]=0;	
  }

  while(stat[0][n]<1){
    int step=0,flag=1;
    for(int i=0;i<n-1;i++){
      for(int j=0;j<n;j++){
        stat[i+1][j]=(wall[i][j]+stat[i][j]+stat[i-1][j]+stat[i][j-1]+stat[i][j+1])%2;
      }
    }
    int t=n-1;
    for(int i=0;i<n;i++){
      if((stat[t][i]+stat[t-1][i]+stat[t][i+1]+stat[t][i-1])%2!=wall[t][i]){
        flag=0;
        break;
      }	
    }	
    if(flag){
      for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
          if(stat[i][j]) step++;
    }else
      step = 999999;

    if(step<Min) Min = step;
      
    stat[0][0]++;
    int d=0;
    while(stat[0][d]>1){
      stat[0][d]=0;
      stat[0][++d]++;
    }
  }
  
  if(Min>=100000)
    cout << "inf" << endl;
  else
    cout << Min << endl;
  
  return 0;
}

拨钟问题，http://noi.openjudge.cn/ch0201/1816/[+]

#include<cstdio>
int z[10],i[10],sum;
int main()
{
    for(int j=1;j<=9;j++)scanf("%d",&z[j]);
    for(i[1]=0;i[1]<4;i[1]++)
        for(i[2]=0;i[2]<4;i[2]++)
            for(i[3]=0;i[3]<4;i[3]++)
            {
                i[4]=(4-(z[1]+i[1]+i[2])%4)%4;
                i[5]=(4-(z[2]+i[1]+i[2]+i[3])%4)%4;
                i[6]=(4-(z[3]+i[2]+i[3])%4)%4;
                i[7]=(4-(z[4]+i[1]+i[4]+i[5])%4)%4;
                i[9]=(4-(z[6]+i[3]+i[5]+i[6])%4)%4; 
                i[8]=(4-(z[8]+i[5]+i[7]+i[9])%4)%4;
                sum=0;
                sum+=(z[1]+i[1]+i[2]+i[4])%4;
                sum+=(z[2]+i[1]+i[2]+i[3]+i[5])%4;
                sum+=(z[3]+i[2]+i[3]+i[6])%4;
                sum+=(z[4]+i[1]+i[4]+i[5]+i[7])%4;
                sum+=(z[5]+i[1]+i[3]+i[5]+i[7]+i[9])%4;
                sum+=(z[6]+i[3]+i[5]+i[6]+i[9])%4;
                sum+=(z[7]+i[4]+i[7]+i[8])%4;
                sum+=(z[8]+i[5]+i[7]+i[8]+i[9])%4;
                sum+=(z[9]+i[6]+i[8]+i[9])%4;
                if(sum==0){for(int j=1;j<=9;j++)while(i[j]--)printf("%d ",j);return 0;}
            }
}

满足条件的整数，http://noi.openjudge.cn/ch0201/1943/[+]

#include <iostream>
#include <cstdio>
using namespace std;

int a,b,c;

int main(){
  for(int i=2;i<=100;i++){
    a=i*i;
    for(int j=i;j<=100;j++){
      b=j*j;
      for(int k=j+1;k<=100;k++){
        c= k*k;
        if(a+b==c){
          printf("%d*%d + %d*%d = %d*%d\n",i,i,j,j,k,k);
        }
      }
    }
  }

  return 0;
}

确定进制，http://noi.openjudge.cn/ch0201/1973/[+]

#include <iostream>
using namespace std;

long long ten(int x,int r){
  long long ans=0,p=1;
  while(x){
    int t = x%10;
    if(t>=r){
      ans = 0;
      break;
    }
    ans += t*p;
    x/=10;
    p*=r;
  }
  return ans;
}

int p,q,r,i,flag;
long long a,b,c,d;

int main(){
  cin >> p >> q >> r;
  flag=1;
  for(i=2;i<=1000000;i++){
    a = ten(p,i);
    b = ten(q,i);
    c = ten(r,i);
    if(a>0 && b>0 && c>0 && a*b==c){
      flag=0;
      cout << i << endl;
      break;
    }
  }
  if(flag) cout << 0 << endl;

  return 0;
}

生理周期，http://noi.openjudge.cn/ch0201/1978/[+]

#include <iostream>
using namespace std;
int p,e,i,d,x,y,z,t;

int main(){
  cin >> p >> e >> i >> d;
  
  x = d-p;
  y = d-e;
  z = d-i;
  for(t=d;t<=21252;t++){
    x++;
    y++;
    z++;
    if(x%23==0 && y%28==0 && z%33==0 && t>=d)
      break;	
  }
  cout << t-d+1 << endl;

  return 0;
}

子串计算，http://noi.openjudge.cn/ch0201/2472/[+]

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

string s;
map<string,int> mp;
int finds(string x){
  int len = x.size(),ans=0,l=s.size();
  
  for(int i=0;i<=l-len;i++)
    if(s.substr(i,len)==x)
      ans++;
      
  return ans;	
}

int main(){
  cin >> s;
  int len=s.size();
  for(int i=0;i<len;i++){
    for(int j=1;j<=len-i;j++){
      string t = s.substr(i,j);
      int cnt = finds(t);
      if(cnt>1) mp[t]=cnt;
    }
  }
  for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++)
    cout << it->first << " " << it->second << endl;
  
  return 0;
}

Safecracker，http://noi.openjudge.cn/ch0201/250/[+]

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

int target;
string s;

string finds(string ss,int tt){
  vector<string> vv;
  int len = ss.size();
  for(int a=0;a<len;a++){
    for(int b=0;b<len;b++){
      for(int c=0;c<len;c++){
        for(int d=0;d<len;d++){
          for(int e=0;e<len;e++){
            int v=ss[a]-'A'+1;
            int w=ss[b]-'A'+1;
            int x=ss[c]-'A'+1;
            int y=ss[d]-'A'+1;
            int z=ss[e]-'A'+1;
            int ta = v-w*w+x*x*x-y*y*y*y+z*z*z*z*z;
            if(a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&d!=e&&ta==tt){
              string ts="";
              ts.append(1,ss[a]);
              ts.append(1,ss[b]);
              ts.append(1,ss[c]);
              ts.append(1,ss[d]);
              ts.append(1,ss[e]);
              vv.push_back(ts);
              //cout << ts << endl;
            }
          }
        }
      }
    }
  }
  if(vv.size()>0){
    sort(vv.begin(),vv.end());
    return vv[vv.size()-1];
  }
  return "";		
}

int main(){
  //freopen("250.in","r",stdin);
  
  cin >> target >> s;
  
  while(target!=0 && s!="END"){
    string t = finds(s,target);
    if(t.size()>0)
      cout << t << endl;
    else
      cout << "no solution" << endl;	
    cin >> target >> s;
  }
  
  return 0;
}

比赛排名，http://noi.openjudge.cn/ch0201/2673/[+]

#include <iostream>
using namespace std;
int a,b,c,d,e;

int main(){
  for(c=1;c<=5;c++){
    for(d=1;d<=5;d++){
      for(e=4;e<=5;e++)
        if(c!=d && c!=2 && d!=2){
          
        }
    }
  }
  
  b=2;
  for(a=2;a<=5;a++){
    //for(b=1;b<=5;b++){
      for(c=1;c<=5;c++){
        for(d=1;d<=5;d++){
          for(e=4;e<=5;e++){
            if((a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&d!=e)){
              if(	(c==1 && d!=1 && a==5)){
//								cout << "A " << a <<endl;
//								cout << "B " << b <<endl;
//								cout << "C " << c <<endl;
//								cout << "D " << d <<endl;
//								cout << "E " << e <<endl;
//								cout << endl;
                cout << a <<endl;
                cout << b <<endl;
                cout << c <<endl;
                cout << d <<endl;
                cout << e <<endl;
                cout << endl;
              }
            }
          }
        }
      }
    //}
  }

  return 0;
}

和数，http://noi.openjudge.cn/ch0201/2722/[+]

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

int n,a[105];
set<int> s;

bool comp(int a,int b){
  return a>b;	
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    cin >>a[i];
  }
  sort(a,a+n,comp);
  for(int i=0;i<n-2;i++){
    int flag = 1;
    for(int j=i+1;flag && j<n-1;j++){
      for(int k=j+1;flag && k<n;k++){
        if(a[i]==a[j]+a[k]){
          s.insert(a[i]);
          flag = 0;	
        }
      }
    }
  }
  cout << s.size() << endl;	
  
  return 0;
}

因子问题，http://noi.openjudge.cn/ch0201/2723/[+]

#include <iostream>
using namespace std;
int n,m,a,b;

int main(){
  cin >> n >> m;
  for(a=1;a<m;a++){
    b = m-a;
    if(n%a==0 && n%b==0){
      cout << a << endl;
      break;
    }
  }
  if(a==m) cout << -1 << endl;

  return 0;
}

谁是你的潜在朋友，http://noi.openjudge.cn/ch0201/2983/[+]

#include <iostream>
#include <map>
using namespace std;

int n,m,a[205],b;
map<int,int> mp;

int main(){
  cin >> n >> m;
  for(int i=1;i<=n;i++){
    cin >> a[i];
    mp[a[i]]++;		
  }
  for(int i=1;i<=n;i++)
    if(mp[a[i]]>1)
      cout << mp[a[i]]-1<< endl;
    else
      cout << "BeiJu" << endl;
      
  return 0;
}

最简真分数，http://noi.openjudge.cn/ch0201/3526/[+]

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

int n,a[605],ans=0;

int gcd(int x,int y){
  int r = x%y;
  while(r){
    x=y;
    y=r;
    r=x%y;
  }
  return y;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> a[i];
  sort(a,a+n);
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(gcd(a[i],a[j])==1)
        ans++;
    } 
  }	
  cout << ans << endl;
  
  return 0;
}

找和为K的两个元素，http://noi.openjudge.cn/ch0201/6184/[+]

#include <iostream>
using namespace std;

int n,a[1005],k;

int main(){
  cin >> n >> k;
  for(int i=0;i<n;i++)
    cin >> a[i];
  int flag = 0;
  for(int i=0;!flag && i<n-1;i++)
    for(int j=i+1;!flag && j<n;j++)
      if(a[i]+a[j]==k){
        flag =1;
      }
  if(flag) cout << "yes" << endl;
  else cout << "no" << endl;
  
  return 0;
}

称体重，http://noi.openjudge.cn/ch0201/6187/[+]

#include <iostream>
#include <algorithm>
using namespace std;
struct zqsl{
  char c;
  int w;
} p[4];

bool comp(zqsl a,zqsl b){
  return a.w < b.w;
}

int main(){
  for(int z=10;z<=50;z=z+10){
    for(int q=10;q<=50;q=q+10){
      for(int s=10;s<=50;s+=10){
        for(int l=10;l<=50;l+=10){
          if(z!=q && q!=s && s!=l)
          if(z+q==s+l && z+l>s+q && z+s<q){
            p[0].c='z';
            p[0].w=z; 
            p[1].c='q';
            p[1].w=q; 
            p[2].c='s';
            p[2].w=s; 
            p[3].c='l';
            p[3].w=l; 
          }
        }
      }
    }
  }
  sort(p,p+4,comp);
  for(int i=0;i<4;i++)
    cout << p[i].c << " " << p[i].w << endl;
    
  return 0;
}

比饭量，http://noi.openjudge.cn/ch0201/6188/[+]

#include <iostream>
using namespace std;

int a,b,c;

int main(){
  
  for(a=1;a<=3;a++){
    for(b=1;b<=3;b++){
      for(c=1;c<=3;c++){
        if(a!=b&&a!=c&&b!=c){
          int as = (b>a) + (a==c);
          int bs = (a>b) + (a>c);
          int cs = (c>b) + (b>a);
          if(a+as==b+bs && a+as==c+cs && b+bs==c+cs){
            //cout << a << b << c << endl;
            if(as>bs && as>cs){
              cout << "A";
              if(bs>cs)
                cout << "BC" << endl;
              else
                cout << "CB" << endl;
            }else{
              if(bs>cs){
                cout << "B";
                if(as>cs)
                  cout << "AC" << endl;
                else
                  cout << "CA" << endl;
              }else{
                cout << "C";
                if(as>bs)
                  cout << "AB" << endl;
                else
                  cout << "BA" << endl;	
              }
            }	
          }
        }
      }
    }
  }
  
  return 0;
}

垃圾炸弹，http://noi.openjudge.cn/ch0201/7213/[+]

#include <iostream>
#include <vector>
using namespace std;
struct pos{
  int x,y,v;
  pos(){};
  pos(int a,int b,int c){x=a;y=b;v=c;}
};

int d,n,x,y,w,bomb,maxb=-1;
vector<pos> p;

int main(){
  cin >> d >> n;
  for(int i=0;i<n;i++){
    cin >> x >> y >> w;
    p.push_back(pos(x,y,w));
  }
  
  bomb = 0;
  for(int i=0;i<=1024;i++){
    for(int j=0;j<=1024;j++){
      int gb=0;
      for(int k=0;k<p.size();k++){
        pos pp = p[k];
        if(pp.x>=(i-d)&&pp.x<=(i+d)&&pp.y>=(j-d)&&pp.y<=(j+d)){
          gb+=pp.v;
        }			
      }
      if(gb>maxb){
        bomb = 1;
        maxb=gb;
      }else if(gb==maxb){
        bomb++;
      }
    }
  }
  cout << bomb << " " << maxb << endl;
  
  return 0;
}

Minecraft，http://noi.openjudge.cn/ch0201/7216/[+]

#include <iostream>
using namespace std;

int n,h,ans,mn=1000000000,t;

int main(){
  cin >> n;
  t=n/3;
  if(t==0) t=1;
  for(int l=1;l<=t;l++){
    for(int w=1;w<=t;w++){
      if(n%(l*w)==0){
        h=n/(l*w);
        ans = (l*w+w*h+l*h)*2;
        if(ans<mn) mn=ans;
      }
    }
  }
  cout << mn << endl;
  
  return 0;
}

猴子吃桃，http://noi.openjudge.cn/ch0201/7217/[+]

#include <iostream>
using namespace std;

long long n,a,flag,t;

int main(){
  cin >> n;
  if(n==0){
    cout << 0 << endl;
    return 0;
  }
  if(n==1){
    cout << 2 << endl;
    return 0;
  }
  int p=1;
  while(1){
    t=p;
    flag=1;
    for(int i=1;i<n;i++){
      a=t*n+1;
      t = a/(n-1);
      if(a%(n-1)!=0){
        flag=0;
        break;
      }
    }
    if(flag){
      cout << a*n/(n-1)+1 << endl;
      break;
    }
    p++;
  }
  
  return 0;
}

Flip Game，http://noi.openjudge.cn/ch0201/755/[+]

#include <iostream>
#include <string>
using namespace std;
string map[4];
int d[5][2]={{-1,0},{1,0},{0,0},{0,-1},{0,1}};
int flag = 0,ans,s;

bool done(){
  for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
      if(map[i][j]!=map[0][0])
        return false;
  return true;
}

void flip(int cx,int cy){
  for(int i=0;i<5;i++){
    int x = cx + d[i][0];
    int y = cy + d[i][1];
    if(x>=0 && y>=0 && x<4 && y<4)
      if(map[x][y]=='b')
        map[x][y]='w';
      else
        map[x][y]='b';
  }
}

void dfs(int x,int y,int step){
  //cout << "x="<< x << ",y=" << y << ",step=" << step << endl;
  if(s==step){
    flag = done();
    ans = step;
    //cout << "ans = " << ans << endl;
    return;
  }
  if(flag || x==4) return;
  flip(x,y);
  if(y<3) dfs(x,y+1,step+1);
  else dfs(x+1,0,step+1);
  flip(x,y);
  if(y<3) dfs(x,y+1,step);
  else dfs(x+1,0,step);
} 

int main(){
  for(int i=0;i<4;i++)
    cin >> map[i];
  for(s=0;s<=16;s++){
    dfs(0,0,0);
    if(flag) break;
  }
  if(flag)
    cout << ans << endl;
  else
    cout << "Impossible" << endl;
  return 0;
}

硬币面值组合，http://noi.openjudge.cn/ch0201/7621/[+]

#include <iostream>
#include <cstdio>
using namespace std;

int n,a,b,c,i;

int main(){
  cin >> n;
  i=1;
  for(c=0;c<=n/5;c++){
    for(b=0;b<=n/2;b++){
      for(a=0;a<=n;a++){
        if(c*5+b*2+a==n){
          printf("%03d%12d%12d%12d\n",i++,a,b,c);	
        }
      }
    }
  }
  return 0;
}

五户共井问题，http://noi.openjudge.cn/ch0201/7623/[+]

#include <iostream>
#include <cstdio>
using namespace std;
int k,n1,n2,n3,n4,n5;
int a,b,c,d,e,len;

int main(){
  cin >> k >> n1 >> n2 >> n3 >> n4 >> n5;
  for(len=1;len<=k*100;len++){
    for(a=1;a<=len;a++){
      b = len - a * n1;
      c = len - b * n2;
      d = len - c * n3;
      e = len - d * n4;
      if(a==b||a==c||a==d||a==e||b==c||b==d||b==e||c==d||c==e||d==e)
        continue;
      if(e*n5+a==len){
        printf("%d %d %d %d %d %d\n",len,a,b,c,d,e);
        return 0;
      }
    }
  }
  printf("not found\n");
  
  return 0;
}

余数相同问题，http://noi.openjudge.cn/ch0201/7647/[+]

#include <iostream>
using namespace std;

int a[3],mx;

int main(){
  for(int i=0;i<3;i++){
    cin >> a[i];
    if(a[i]>mx) mx = a[i];
  }
  
  for(int i=2;i<=mx;i++){
    int t = a[0]%i;
    if(a[1]%i==t && a[2]%i==t){
      cout << i << endl;
      break;
    }
  }

  return 0;
}

我家的门牌号，http://noi.openjudge.cn/ch0201/7649/[+]

#include <iostream>
using namespace std;

int n,x,i=1,s=0,flag=1;

int main(){
  cin >> n;
  while(flag){
    s+=i;
    for(int j=1;j<=i;j++){
      if(s-2*j==n){
        x = j;
        flag = 0;
        break;	
      }
    }
    i++;
  }
  cout << x << " " << i-1 << endl;
  
  return 0;
}

不定方程求解，http://noi.openjudge.cn/ch0201/7650/[+]

#include <iostream>
using namespace std;

int a,b,c,ans;

int main(){
  
  cin >> a >> b >> c;
  for(int i=0;i<=c;i++){
    for(int j=0;j<=c;j++){
      int t = a*i + b*j;
      if(t==c) ans ++;
    }
  }
  cout << ans << endl;
  
  return 0;
}

质数的和与积，http://noi.openjudge.cn/ch0201/7827/[+]

#include <iostream>
#include <cmath>
using namespace std;

int s;

bool isprime(int x){
  int t=sqrt(x);
  for(int i=2;i<=t;i++)
    if(x%i==0) return 0;
  return 1;	
}

int main(){
  
  cin >> s;
  int t=s/2;
  for(int i=t;i<=s;i++){
    if(isprime(i)&&isprime(s-i)){
      cout << i * (s-i) << endl;
      break;
    }
  }

  return 0;
}

最接近的分数，http://noi.openjudge.cn/ch0201/7832/[+]

#include <iostream>
using namespace std;

int n,x,y;
double a,b,mn=10000;

int gcd(int a,int b){
  int r = a%b;
  while(r){
    a=b;
    b=r;
    r=a%b;
  }	
  return b;
}

int main(){
  cin >> n >> a >> b;
  double t = a/b;
  for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
      if(gcd(i,j)==1){
        double tt = double(j)/double(i);
        if(tt<t && (t-tt)<mn){
          mn=t-tt;
          x = j;
          y = i;
        }
      }
    }
  }
  cout << x << " " << y << endl;
  
  return 0;
}

砝码称重，http://noi.openjudge.cn/ch0201/8755/[+]

#include <iostream>
using namespace std;

int n[6],w[1005],ans;

int main(){
  for(int i=0;i<6;i++) cin >> n[i];

  for(int a=0;a<=n[0];a++){
    for(int b=0;b<=n[1];b++){
      for(int c=0;c<=n[2];c++){
        for(int d=0;d<=n[3];d++){
          for(int e=0;e<=n[4];e++){
            for(int f=0;f<=n[5];f++){
              w[a*1+b*2+c*3+d*5+e*10+f*20]++;
            }
          }
        }
      }
    }
  }
  ans = 0;
  for(int i=1;i<=1000;i++)
    if(w[i]>0) ans++;
  cout << "Total=" << ans << endl;
  
  return 0;
}

三个三位数，http://noi.openjudge.cn/ch0201/8757/[+]

#include <iostream>
using namespace std;
int a,b,c;
bool judge(int src,int dst){
  int x1 = src / 100;
  int y1 = src / 10 % 10;
  int z1 = src % 10;
  int x2 = dst / 100;
  int y2 = dst / 10 % 10;
  int z2 = dst % 10;
  if(x1==x2||x1==y2||x1==z2) return false;
  if(y1==x2||y1==y2||y1==z2) return false;
  if(z1==x2||z1==y2||z1==z2) return false;
  if(x1==y1||x1==z1||y1==z1) return false;
  if(x2==y2||x2==z2||y2==z2) return false;
  if(x1==0||0==z1||y1==0) return false;
  if(x2==0||0==z2||y2==0) return false;
  
  return true;
}
int main(){
  for(int i=1;i<=9;i++){
    for(int j=1;j<=9;j++){
      for(int k=1;k<=9;k++){
        if(i!=j && j!=k && i!=k){
          a = i*100+j*10+k;
          b = a*2;
          c = a*3;
          if(c<1000&&judge(a,b)&&judge(b,c)&&judge(a,c))
            cout << a << " " << b << " " << c << endl;		
        }
      }
    }
  }

  return 0;
}

火车上的人数，http://noi.openjudge.cn/ch0201/8759/[+]

#include <iostream>
using namespace std;
int a,n,m,x,up;
struct station{
  int haveA,haveX;
  int upA,upX;
}s[10000];

int main(){
  cin >> a >> n >> m >> x;
  s[1].haveA=0;
  s[1].haveX=0;
  s[1].upA=1;
  s[1].upX=0;
  s[2].haveA=1;
  s[2].haveX=0;
  s[2].upA=0;
  s[2].upX=1;
  for(int i=3;i<n;i++){
    s[i].upA = s[i-1].upA+s[i-2].upA;
    s[i].upX = s[i-1].upX+s[i-2].upX;
    s[i].haveA = s[i-1].haveA+s[i].upA-s[i-1].upA;
    s[i].haveX = s[i-1].haveX+s[i].upX-s[i-1].upX;
  }	
  up = (m-s[n-1].haveA*a)/s[n-1].haveX;
  cout << s[x].haveA*a+s[x].haveX*up << endl;
    
  return 0;
}

Cantor表，http://noi.openjudge.cn/ch0201/8760/[+]

#include <iostream>
using namespace std;
int n,x;

int main(){
  cin >> n;
  for(x=1;x*(x+1)<=2*n;x++);
  int t = n*2-x*(x+1);
  if(t<0){
    x--;
    t = n-x*(x+1)/2;
  }
  if(t==0){
    if(x%2==1){
      cout << 1 << "/" << x << endl;			
    }else{
      cout << x << "/" << 1 << endl;
    }
  }else{
    x++;
    if(x%2==1){
      cout << (x+1-t )<< "/" << t << endl;
    }else{
      cout << t << "/" << (x+1-t) << endl;
    }
    
  }

  return 0;
}

参考网址

http://noi.openjudge.cn