大一寒假训练三（暴力枚举）【更新完成】
本次训练共12 题，本文附AC代码和题目链接。
本次训练中稍有难度的题：nefu 574 丑数 和 nefu 1644 奶牛碑文
（这两题代码都很短，但是思维过程并不简单）
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,j,t,n,ans,a[20];
while(cin>>t)
{
while(t--)
{
n=ans=0;
while(cin>>a[n]&&a[n])n++;//输入数据a[0]~a[n-1]
sort(a,a+n);
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{if(a[j]==a[i]*2)ans++;}
}
printf("%d\n",ans);
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,s,a,i;
while(scanf("%d",&n)!=-1)
{
s=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a);
if(a<60)s++;
}
printf("%d\n",s);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n,s;
char a[101];
while(scanf("%d",&n)!=-1)
{
for(i=1;i<=n;i++)
{
scanf("%s",&a);
s=0;
for(j=0;j<strlen(a);j++)
{
if(a[j]>='0'&&a[j]<='9')
s++;
}
printf("%d\n",s);
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i;
while(scanf("%d",&n)!=-1)
{
for(i=n+1;i<=999;i++)
printf("%.3d\n",i);//%.3d输出007,012等含前缀0的三位数
}
return 0;
}
nefu 573 大乐透
写了6层循环，时间复杂度很大，这题数据小不超时，数据大就别想着用暴力枚举了
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[50],k,i1,i2,i3,i4,i5,i6;
while(scanf("%d",&k)!=-1)
{
if(k==0)break;
for(i1=1;i1<=k;i1++)
scanf("%d",&a[i1]);
for(i1=1;i1<=k;i1++)
{
for(i2=i1+1;i2<=k;i2++)
{
for(i3=i2+1;i3<=k;i3++)
{
for(i4=i3+1;i4<=k;i4++)
{
for(i5=i4+1;i5<=k;i5++)
{
for(i6=i5+1;i6<=k;i6++)
printf("%d %d %d %d %d %d\n",a[i1],a[i2],a[i3],a[i4],a[i5],a[i6]);
}
}
}
}
}
}
return 0;
}
nefu 574 丑数
这题难点在于丑数的排序，即由最先4个最小的丑数乘以2、3、5、7产生之后的丑数，
关键是怎么产生之后的丑数，并且让之后产生的所有丑数按升序排列，详见注释。
#include <bits/stdc++.h>
#define min4(a,b,c,d) min(min(a,b),min(c,d))
using namespace std;
int n,p2,p3,p5,p7,a[5850];//定义min4(a,b,c,d)，找四个数中的最小值
int main()
{
a[1]=1;p2=p3=p5=p7=1;
for(int i=2;i<=5842;i++)//打表5842个丑数
{
a[i]=min4(a[p2]*2,a[p3]*3,a[p5]*5,a[p7]*7);//a[p2]、a[p3]、a[p5]、a[p7]分别为*2、*3、*5、*7的次数
if(a[i]%2==0)p2++;//如果选择的最小值a[i]是乘以了2，则*2的丑数下标位置后移一位
if(a[i]%3==0)p3++;
if(a[i]%5==0)p5++;
if(a[i]%7==0)p7++;
}
while(cin>>n&&n)
printf("%d\n",a[n]);
return 0;
}
nefu 575 矩形
完全被覆盖的矩形，是指被其他所有矩形覆盖的矩形。
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x1,x2,y1,y2;
}p[1001];
int main()
{
int i,j,n;
while(scanf("%d",&n)!=-1)
{
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&p[i].x1,&p[i].x2,&p[i].y1,&p[i].y2);
int sum=0;
for(i=1;i<=n;i++)
{
int s=0;
for(j=1;j<=n;j++)
{
if(p[i].x1>=p[j].x1&&p[i].x2<=p[j].x2&&p[i].y1>=p[j].y1&&p[i].y2<=p[j].y2)
s++;
}
if(s==n)
sum++;
}
printf("%d\n",sum);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[10010],i,x,n,s;
while(scanf("%d",&n)!=-1)
{
int flag=0;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&x);
for(i=1;i<=n;i++)
{
if(a[i]==x)
{
flag=1;
printf("%d\n",i);
break;
}
}
if(flag==0)printf("0\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[1001],i,j,n,s,lsum,rsum;
while(scanf("%d",&n)!=-1)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
s=0;
for(i=1;i<=n;i++)
{
lsum=rsum=0;
for(j=i-1;j>=1;j--)
{
if(a[j]>a[i])
lsum++;
}
for(j=i+1;j<=n;j++)
{
if(a[j]>a[i])
rsum++;
}
if(lsum==rsum)
s++;
}
printf("%d\n",s);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int m,t,i,ans;
bool judge(int n)//若这个房间存在，即这个房间编号不包含数字t，为true
{
int d;
while(n)
{
d=n%10;
n=n/10;
if(d==t)return 0;
}
return 1;
}
int main()
{
cin>>m>>t;
ans=0;
for(i=1;i<=m;i++)
{if(judge(i))ans++;}
printf("%d\n",ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
int a,b,i,j,l,ans1,ans2;
double s1,s2,d,min;
while(cin>>a>>b>>l)
{
min=10000;
for(i=l;i>=1;i--)
{
for(j=l;j>=1;j--)
{
if(gcd(i,j)==1)
{
s1=1.0*i/j;
s2=1.0*a/b;
if(s1>=s2)
{
d=s1-s2;
if(d<min)
{
min=d;
ans1=i;
ans2=j;
}
}
}
}
}
printf("%d %d\n",ans1,ans2);
}
return 0;
}
nefu 1644 奶牛碑文
这题实际上是要你统计每个O字母左边有多少个C字母（假设有c[i]个）以及右边有多少个W字母（假设有w[i]个），则这个O字母可以组成c[i]*w[i]个cow单词，把所有O字母左右两边的c[i]*w[i]累加即可。
#include <bits/stdc++.h>
using namespace std;
long long n,i,k1,k2,ans,c[100010],w[100010];
char str[100010];
int main()
{
scanf("%lld%s",&n,str);
k1=k2=ans=0;//k1，k2为临时计数变量
for(i=0;i<n;i++)
{
if(str[i]=='C') k1++;
c[i]=k1;
}
for(i=n-1;i>=0;i--)
{
if(str[i]=='W') k2++;
w[i]=k2;
}
for(i=0;i<n;i++)
{
if(str[i]=='O')
ans=ans+c[i]*w[i];
}
printf("%lld\n",ans);
return 0;
}
