title: ACM-NEFU-2020大一寒假培训三（暴力）
tags:

  • ACM
  • NEFUOJ
  • 暴力
    abbrlink: eac8bff4
    date: 2020-12-24 16:39:28

A.二倍的问题

Description

  1. 给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。

Input

  1. 输入包括n组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。

Output

  1. 对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。

Sample Input

  1. 3
  2. 1 4 3 2 9 7 18 22 0
  3. 2 4 8 10 0
  4. 7 5 11 13 1 3 0

Sample Output

  1. 3
  2. 2
  3. 0

Code

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int main()
  6. {
  7.     int vis[25],a[25];
  8.     int t,x,p,ans;
  9.     cin>>t;
  10.     while(t--)
  11.     {
  12.         memset(vis,0,sizeof(vis));
  13.         p=ans=0;
  14.         while(cin>>x&&x)
  15.         {
  16.             p++;
  17.             a[p]=x;
  18.         }
  19.         sort(a+1,a+p+1);
  20.         for(int i=1;i<=p;i++)
  21.         {
  22.             if(vis[a[i]]==1)    ans++;
  23.             vis[2*a[i]]=1;
  24.         }
  25.         cout<<ans<<endl;
  26.     }
  27.     return 0;
  28. }

B.大乐透

Description

  1. 在小明曾经玩过的一种对号码的纸牌游戏(乐透)里,玩家必须从{1,2,……，49}中选择6个数。玩Lotto的一个流行策略是（虽然它并不增加你赢的机会）：就是从这49个数中，选出k（k&gt;6）个数组成一个子集S，然后只从S里拿出牌来玩几局游戏。例如，k=8，s={1,2,3,5,8,13,21,34}，那么有28场可能的游戏：[1,2,3,5,8,13],[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,13,21],……,[3,5,8,13,21,24]。
  2. 读取数字k和一组数S，输出由S中的数组成的所有可能的游戏。

Input

  1. 输入数据有多组，每组一行，每行有多个整数，其中第一个整数为数字k，接下来有k个整数，即子集S。当k为0，输入结束。

Output

  1. 输出由S中的数组成的所有可能的游戏。每种游戏一行。

Sample Input

  1. 7 1 2 3 4 5 6 7
  2. 0

Sample Output

  1. 1 2 3 4 5 6
  2. 1 2 3 4 5 7
  3. 1 2 3 4 6 7
  4. 1 2 3 5 6 7
  5. 1 2 4 5 6 7
  6. 1 3 4 5 6 7
  7. 2 3 4 5 6 7

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int k,num[1000];
  7.     while(1)
  8.     {
  9.         cin>>k;
  10.         if(k==0)break;
  11.         for(int i=0;i<k;i++)
  12.         {
  13.             cin>>num[i];
  14.         }
  15.         for(int i=0;i<k;i++)
  16.         {
  17.             for(int j=i+1;j<k;j++)
  18.             {
  19.                 for(int l=j+1;l<k;l++)
  20.                 {
  21.                     for(int m=l+1;m<k;m++)
  22.                     {
  23.                         for(int n=m+1;n<k;n++)
  24.                         {
  25.                             for(int o=n+1;o<k;o++)
  26.                             {
  27.                                 printf("%d %d %d %d %d %d\n",num[i],num[j],num[l],num[m],num[n],num[o]);
  28.                             }
  29.                         }
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.     }
  35.     return 0;
  36. }

C.密码箱

Description

  1. 小明的密码箱打不开了，小明的密码箱是传统的3位滚轮密码。小明完全不记得他的密码了，所以他从 000开始以升序开始尝试，他已经试到第abc位密码了，可是箱子还是没有打开，他希望你将之后所有可能尝试的密码输出，这样他就可以完全不去思考，让他波动密码盘更有效率

Input

  1. 每行输入一个整数n(0 &lt; n &lt; 1000);n没有前缀0。

Output

  1. n之后所有可能尝试的密码;输出有前缀0的。

Sample Input

  1. 989

Sample Output

  1. 990
  2. 991
  3. 992
  4. 993
  5. 994
  6. 995
  7. 996
  8. 997
  9. 998
  10. 999

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n;
  7.     while(cin>>n)
  8.     {
  9.         for(int i=n+1;i<1000;i++)
  10.         {
  11.             if(i<10)    cout<<"0";
  12.             if(i<100)    cout<<"0";
  13.             cout<<i<<endl;
  14.         }
  15.     }
  16.     return 0;
  17. }

D.字符串统计

Description

  1. 对于给定的一个字符串，统计其中数字字符出现的次数。

Input

  1. 输入数据有多组，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一个由字母和数字组成的字符串。

Output

  1. 对于每个测试实例，输出该串中数值的个数，每个输出占一行。

Sample Input

  1. 2
  2. asdfasdf123123asdfasdf
  3. asdf111111111asdfasdfasdf

Sample Output

  1. 6
  2. 9

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,ans;
  7.     string s;
  8.     cin>>n;
  9.     while(n--)
  10.     {
  11.         ans=0;
  12.         cin>>s;
  13.         for(int i=0;i<s.size();i++)
  14.         {
  15.             if(s[i]>='0'&&s[i]<='9')    ans++;
  16.         }
  17.         cout<<ans<<endl;
  18.     }
  19.     return 0;
  20. }

E.丑数

Description

  1. 只有质数2,3,5,7这几个作为因子的数叫做,丑数,比如前20个丑数是(从小到大来说) 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24和25.

Input

  1. 我们给你个n（1&lt;=m&lt;=5842）当输入n为0结束。

Output

  1. 输出第n个丑数。每个数一行。

Sample Input

  1. 1
  2. 2
  3. 3
  4. 4
  5. 11

Sample Output

  1. 1
  2. 2
  3. 3
  4. 4
  5. 12

Code

这题打表过的，就不出了…

F.矩形

Description

  1. 在测试超大规模集成电路时，对给定的一个设计，专家要检测元件是否相互遮盖。一个元件可视为一个矩形，假设每个矩形都是水平排列的（边与x轴或y轴平行），所以长方形由最小的和最大的x，y坐标表示。
  2. 编程计算完全被覆盖的矩形个数。

Input

  1. 输入有多组长方形实例。对每组长方形，第一个数字是长方形的数量，然后是长方形的最小和最大x，y坐标（最小x，最大x，最小y，最大y）。

Output

  1. 对每组输入数据，输出一行，是被完全覆盖的长方形数量。

Sample Input

  1. 3
  2. 100 101 100 101
  3. 0 3 0 101
  4. 20 40 10 400
  5. 4
  6. 10 20 10 20
  7. 10 20 10 20
  8. 10 20 10 20
  9. 10 20 10 20

Sample Output

  1. 0
  2. 4

Code

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. struct node
  6. {
  7.     int minx,maxx;
  8.     int miny,maxy;
  9. }s[10010];
  11. int main()
  12. {
  13.     int n,ans,a[10010]={0};
  14.     while(cin>>n)
  15.     {
  16.         ans=0;
  17.         memset(a, 0, sizeof(a));
  18.         for(int i=0;i<n;i++)
  19.         {
  20.             cin>>s[i].minx>>s[i].maxx>>s[i].miny>>s[i].maxy;
  21.         }
  22.         for(int i=0;i<n;i++)
  23.         {
  24.             for(int j=0;j<n;j++)
  25.             {
  26.                 if(i==j)continue;
  27.                 if(!a[j] && s[i].minx <= s[j].minx && s[i].maxx >= s[j].maxx && s[i].miny <= s[j].miny && s[i].maxy >= s[j].maxy)
  28.                 {
  29.                     ans++;
  30.                     a[j]=1;
  31.                 }
  32.                 if(!a[i] && s[j].minx <= s[i].minx && s[j].maxx >= s[i].maxx && s[j].miny <= s[i].miny && s[j].maxy >= s[i].maxy)
  33.                 {
  34.                     ans++;
  35.                     a[i]=1;
  36.                 }
  37.             }
  38.         }
  39.         cout<<ans<<endl;
  40.     }
  41.     return 0;
  42. }

G.抽奖

Description

  1. 公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码 num，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中的是第几个号码；如果没有中奖，请输出 0。

Input

  1. 第一行一个正整数 n，表示有 n 个获奖号码，2&lt;n≤100。
  2. 第二行包含 n 个正整数，之间用一个空格隔开，表示依次公布的 n 个获奖号码。
  3. 第三行一个正整数 num，表示小谢抽奖券上的号码。
  4. 1≤获奖号码，num&lt;10000。

Output

  1. 一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为 0。

Sample Input

  1. 7
  2. 17 2 3 4 9555 6 1
  3. 3

Sample Output

  1. 3

Hint

  1. 暴力
  2. 单组输入

Code

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int main()
  6. {
  7.     int n,num[110],lotto,flag=0;
  8.     int i;
  9.     cin>>n;
  10.     for(i=0;i<n;i++)
  11.     {
  12.         cin>>num[i];
  13.     }
  14.     cin >> lotto;
  15.     for(i=0;i<n;i++)
  16.     {
  17.         if(num[i] == lotto)
  18.         {
  19.             cout<<i+1;
  20.             break;
  21.         }
  22.     }
  23.     if(i==n)    cout<<0;
  24.     return 0;
  25. }

H.比身高

Description

  1. 有 N 个人排成一排，假设他们的身高均为正整数，请找出其中符合以下条件的人：排在他前面且比他高的人数与排在他后面且比他高的人数相等。

Input

  1. 第一行为一个正整数 N，1&lt;N&lt;1000，表示有多少个人。
  2. 下面 N 行，每行一个正整数，表示从前往后每个人的身高，假设每个人的身高≤10000。

Output

  1. 一行一个整数，表示满足这个条件的人数。

Sample Input

  1. 4
  2. 1
  3. 2
  4. 1
  5. 3

Sample Output

  1. 2

Hint

  1. 第 3、第 4 个人满足条件。
  2. 单组输入

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,num[1010],l,r,ans=0;
  7.     cin>>n;
  8.     for(int i=0;i<n;i++)
  9.     {
  10.         cin>>num[i];
  11.     }
  12.     for(int i=0;i<n;i++)
  13.     {
  14.         l=r=0;
  15.         for(int j=i-1;j>=0;j--)
  16.         {
  17.             if(num[j]>num[i])    l++;
  18.         }
  19.         for(int j=i+1;j<n;j++)
  20.         {
  21.             if(num[j]>num[i])    r++;
  22.         }
  23.         if(l==r)    ans++;
  24.     }
  25.     cout<<ans;
  26.     return 0;
  27. }

I.楼层编号

Description

  1. 小林在 NOIP 比赛期间住在“新世界”酒店。和其他酒店不一样的是，这个酒店每天都有一个高能的数字 t，这个数字在楼层中是不会出现的，以 t=3 为例，则 3、13、31、33 等楼层是不存在的，楼层编号为 1，2，4，5，…所以实际上的 4 楼才是 3 楼。
  2. 已知小林预订了编号为 m 层的房间，并且当天高能数字是 t，现在他想知道房间所在的真实楼层是多少。

Input

  1. 一行两个整数 m 和 t，1≤m≤100000，0≤t≤9，保证 m 对 t 合法。

Output

  1. 一行一个整数，表示真实楼层。

Sample Input

  1. 14 3

Sample Output

  1. 12

Hint

  1. 单组输入

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int t,b;
  6. bool judge(int n)
  7. {
  8.     while(n>0)
  9.     {
  10.         b=n%10;
  11.         n/=10;
  12.         if(b==t)return 0;
  13.     }
  14.     return 1;
  15. }
  17. int main()
  18. {
  19.     int m;
  20.     int now=0;
  21.     cin >> m >> t;
  22.     for(int i=1; i <= m; i++)
  23.     {
  24.         if(judge(i))    now++;
  25.     }
  26.     cout<<now;
  27.     return 0;
  28. }

J.比例简化

Description

  1. 在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某观点表示支持的有 1498 人，反对的有 902 人，那么其比例可以简单地记为1498∶902。
  2. 因该比例的数值太大，难以一眼看出它们的关系。若把比例记为 5∶3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
  3. 现给出支持人数 A 和反对人数 B，以及一个上限 L，请将 A 比 B 化简为 A′ 比 B′，要求在 A′和 B′ 均不大于 L，且 A′ 和 B′ 互质（两个整数的最大公约数为 1）的前提下，A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。

Input

  1. 一行三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。

Output

  1. 一行两个整数 A′ 和 B′，中间用一个空格隔开，表示化简后的比例。

Sample Input

  1. 1498 902 10

Sample Output

  1. 5 3

Hint

  1. 单组输入,1&lt;=A,B&lt;=1000000,1&lt;=L&lt;=100,A/B&lt;=L

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int a,b,l,tmp,a1,a2,t;
  7.     double fs,minnum=10000000,r;
  8.     cin>>a>>b>>l;
  9.     tmp=__gcd(a,b);
  10.     a/=tmp;
  11.     b/=tmp;
  12.     r= (double)a / b;
  13.     if(a<l&&b<l)cout<<a<<" "<<b;
  14.     else
  15.     {
  16.         a1=a;
  17.         a2=b;
  18.         for(int i=1;i<=l;i++)
  19.         {
  20.             for(int j=1;j<=l;j++)
  21.             {
  22.                 if(__gcd(i,j)!=1)continue;
  23.                 fs=(double)i/j;
  24.                 if(fs < r)continue;
  25.                 if(fabs(fs - r) < minnum)
  26.                 {
  27.                     minnum=fabs(fs - r);
  28.                     a1=i;
  29.                     a2=j;
  30.                 }
  31.             }
  32.         }
  33.         cout << a1 << " " << a2;
  34.     }
  35.     return 0;
  36. }

K.奶牛碑文

Description

  1. 小伟暑假期间到大草原旅游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C、O 和 W。尽管小伟看不懂，但是令他高兴的是，C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在，他想知道有多少次 COW 出现在文本中。
  2. 如果 COW 内穿插了其他字符，只要 COW 字符出现在正确的顺序，小伟也不介意。甚至，他也不介意出现不同的 COW 共享一些字母。例如，CWOW 出现了 1 次 COW，CCOW 算出现了2 次 COW，CCOOWW 算出现了 8 次 COW。

Input

  1. 第 1 行为 1 个整数 N。
  2. 第 2 行为 N 个字符的字符串，每个字符是一个 C、O 或 W。

Output

  1. 输出 COW 作为输入字符串的字串出现的次数（不一定是连续的）。
  2. 提示：答案会很大，建议用 64 位整数（long long）。

Sample Input

  1. 6
  2. COOWWW

Sample Output

  1. 6

Hint

  1. 对于 50% 的数据满足：N≤60。
  2. 对于 100% 的数据满足：N≤100000。
  3. 单组输入

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n;
  7.     long long c=0,co=0,cow=0;
  8.     string s;
  9.     cin >> n >> s;
  10.     for(int i=0;i<n;i++)
  11.     {
  12.         if(s[i] == 'C')c++;
  13.         if(s[i] == 'O')co+=c;
  14.         if(s[i] == 'W')cow+=co;
  15.     }
  16.     cout<<cow<<endl;
  17.     return 0;
  18. }