枚举及优化（二）
-
基础题
第1题 找比我大的数 查看测评数据信息
若某元素在一组数中比它大元素越多，则说明这个数在这组数的值就越小。
现请你统计出数组中的每个元素，数一数该数组有多少个元素比它大。
输入格式
第一行：N （N<=1000)
第二行：N个整数
输出格式
N个整数，各数这之间有空格
输入/输出例子1
输入：
5
4 6 12 16 8
输出：
4 3 1 0 2
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
int s=0;
for(int j=0;j<n;j++){
if(a[i]<a[j]){
s++;
}
}
cout<<s<<" ";
}
return 0;
}第2题 找比我大的数2 查看测评数据信息
给出n（n<=100000）个数，每个数不超过100。按输入的顺序统计并输出每一个数前有多少个比它大的数。
输入格式
第一行：N
第二行：N个整数
输出格式
N个整数，各数这之间有空格
输入/输出例子1
输入：
5
3 1 4 2 5输出：
0 1 0 2 0#include<bits/stdc++.h>
using namespace std;
long long a,n,s,b[1005];
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
s=0;
scanf("%lld",&a);
b[a]++;
for(int j=a+1;j<=100;j++){
s+=b[j];
}
printf("%lld ",s);
}
return 0;
}第3题 与7无关的数 查看测评数据信息
一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7,则称其为与7相关的数.现求所有小于等于n(n<100)的与7无关的正整数的平方和。
输入格式
输入为一行,正整数n,(n<100)
输出格式
输出小于等于n的与7无关的正整数的平方和
输入/输出例子1
输入：
21
输出：
2336
#include<bits/stdc++.h>
using namespace std;
int n,s=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
if((i/1%10!=7&&i/10%10!=7&&i/100%10!=7)&&(i%7!=0)){
s=s+i*i;
}
}
cout<<s;
return 0;
}第4题 幸运数序列 查看测评数据信息
作为信息学高手，桐桐和晶晶数学也相当厉害，他们非常喜欢研究数列。一次桐桐写下一个数列，每个数都是正整数。晶晶想把它们都变成“幸运数”。晶晶认为的“幸运数”是指能被 4 或 7 整除的数（注意 0 也是“幸运数”）。对于桐桐写的数X，如果X是“幸运数”，则不变化；否则晶晶用一个与X相差最小的“幸运数”Y代替它（Y不必是正整数），如果有两个Y都是 | X-Y|最小的，则选择小的数。（说明：| X-Y|叫做绝对值，当X>Y时，| X-Y|=X-Y,当X<Y时，| X-Y|=Y-X)
输入格式
第一行：一个整数 N ( N<= 100 )，表示数列有N个整数。
第二行：N个正整数，每个整数在 [ 1 , 1,000,000,000 ] 范围内。
输出格式
只一行，有N个整数，晶晶变化后的数列。答案可能为0。
输入/输出例子1
输入：
7
1 2 3 4 5 6 7
输出：
0 0 4 4 4 7 7
样例解释
幸运数是0、4、7、8、12、14、16......，第一个数1不是幸运数，与1最接近的幸运数是0；第二个数2不是幸运数，与2最接近的幸运数是0和4，但取小的0；第3个数3不是幸运数，与3最接近的幸运数是4；第4个数是4，是幸运数，直接输出......
#include<bits/stdc++.h>
using namespace std;
long long n,x,s1,s2;
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&x);
if(x%4==0||x%7==0){
printf("%lld ",x);
}
else{
s1=0,s2=0;
for(int j=x-1;;j--){
if(j%4==0||j%7==0){
s1=j;
break;
}
}
for(int j=x+1;;j++){
if(j%4==0||j%7==0){
s2=j;
break;
}
}
if(x-s1<=s2-x){
printf("%lld ",s1);
}
else {
printf("%lld ",s2);
}
}
}
return 0;
}第5题 猜数字游戏 查看测评数据信息
小明设计了一个猜数字游戏。它是一个正整数，并且小明给你三个提示：
提示的格式为 x y：
提示1，表示这个多位数A的范围是：x<=A<=y。
提示2，表示这个多位数中最少有x个数字y。
提示3，表示这个多位数中最多有x个数字y。
你能推算有多少个符合提示的正整数吗？
这个正整数不超过六位数。
数据保证有解。
输入格式
输入数据的数据有三行，每行都有一个 x y格式的数据，分别表示小明给出的三个提示。
输出格式
输出你推算出的符合提示条件的数的个数。
输入/输出例子1
输入：
15231 15521
2 2
1 9
输出：
9
样例解释
符合三个提示的有以下9个数：
15232 15242 15252 15262 15272 15282 15292 15322 15422
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,x1,y_1,t,s1,s2,s;
int main(){
cin>>n>>m;
cin>>x>>y;
cin>>x1>>y_1;
for(int i=n;i<=m;i++){
t=i;
while(t>0){
if(t%10==y)s1++;
else if(t%10==y_1)s2++;
t/=10;
}
if(s1>=x&&s2<=x1){
s++;
}
s1=0,s2=0;
}
cout<<s;
return 0;
}第6题 珠心算测验 查看测评数据信息
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练， 既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正 整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另 外两个（不同的）数之和？
最近老师出了一些测验题，请你帮忙求出答案。
输入格式
输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
输出格式
输出共一行，包含一个整数，表示测验题答案。
输入/输出例子1
输入：
4
1 2 3 4
输出：
2
样例解释
【样例说明】：
由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的两个不同的数。
【数据说明】：
对于 100%的数据，3 ≤ n ≤ 10000，测验题给出的正整数大小不超过 10,000。
#include<bits/stdc++.h>
using namespace std;
int n,a[10005],s,b[1000005],c[1000005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
c[a[i]]=1;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
b[a[i]+a[j]]++;
}
}
for(int i=1;i<=200002;i++){
if(b[i]>0&&c[i]){
s++;
}
}
cout<<s;
return 0;
}-
附加题
第1题 猫和兔子 查看测评数据信息
一只猫和一只兔子玩简单的猜谜游戏。猫选择了两个不同的正整数 X 和 Y，然后他告诉兔子 N 个正整数，这 N 个正整数当中，有一个是 X + Y，还有一个是 X - Y， 剩余的 N-2 个是任意给的。兔子喜欢大整数，输出 X * Y 的最大可能值。
输入格式
多组测试数据。
第一行，一个整数 G，表示有 G 组测试数据。1 <= G <= 5。每组测试数据格式如下：
第 1 行，一个正整数 N。 2 <= N <= 50。
第 2 行，N 个正整数，空格分开，就是猫给出的那 N 个正整数，范围都是【1,100】, 数据保证这 N 个正整数都是不同的，而且一定有解。
输出格式
共 G 行，每行一个正整数。
输入/输出例子1
输入：
5
3
1 4 5
4
1 4 5 8
9
9 8 7 6 5 4 3 2 1
2
2 100
5
50 58 47 57 40
输出：
6
12
20
2499
441
样例解释
对于第 2 组测试数据的解释：
当 X=3 且 Y=2 是可行的，此时 X * Y = 6。但 X=6 且 Y=2 也是可行，此时 X *Y=12。可以发现，后者更优。
#include<bits/stdc++.h>
using namespace std;
int n,m,t,x,s,a[10005],b;
int main() {
cin>>t;
for(int k=1;k<=t;k++){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
m=-1;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x=a[i]*a[i];
s=a[j]*a[j];
if((x-s)%4==0&&i!=j){
b=(x-s)/4;
m=max(b,m);
}
}
}
cout<<m<<'\n';
}
return 0;
}第2题 回文日期 查看测评数据信息
在日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 8 位数字表示一个日期,其中,前 4 位代表年份,接下来 2 位代表月份,最后 2 位代表日期。显然：一个日期只有一种表示方法,而两个不同的日期的表示方法不会相同。
牛牛认为,一个日期是回文的,当且仅当表示这个日期的 8 位数字是回文的。现在,牛牛想知道：在他指定的两个日期之间（包含这两个日期本身）,有多少个真实存在的日期是回文的。
【提示】
一个8位数字是回文的,当且仅当对于所有的 i （ 1 ≤ i ≤ 8 ）从左向右数的第 i 个数字和第 9 − i 个数字（即从右向左数的第 i 个数字）是相同的。
例如：
• 对于 2016 年 11 月 19 日,用8位数字 20161119 表示,它不是回文的。
• 对于 2010 年 1 月 2 日,用 8 位数字 20100102 表示,它是回文的。
• 对于 2010 年 10 月 2 日,用 8 位数字 20101002 表示,它不是回文的。
每一年中都有 12 个月份：
其中, 1 、 3 、 5 、 7 、 8 、 10 、 12 月每个月有 31 天; 4 、 6 、 9 、 11 月每个月有 30 天;而对于 2 月,闰年时有 29 天,平年时有 28 天。
一个年份是闰年当且仅当它满足下列两种情况其中的一种：
1. 这个年份是 4 的整数倍,但不是 100 的整数倍;
2. 这个年份是 400 的整数倍。
例如：
• 以下几个年份都是闰年： 2000 、 2012 、 2016 。
• 以下几个年份是平年： 1900 、 2011 、 2014 。
输入格式
输入包括两行,每行包括一个 8 位数字。第一行表示牛牛指定的起始日期 date1 。第二行表示牛牛指定的终止日期 date2 。
保证 date1 和 date2 都是真实存在的日期,且年份部分一定为 4 位数字,且首位数字不为 0 。
保证 date1 一定不晚于 date2 。
输出格式
输出一行,包含一个整数,表示在 date1 和 date2 之间,有多少个日期是回文的。
输入/输出例子1
输入：
20110101
20111231
输出：
1
输入/输出例子2
输入：
20000101
20101231
输出：
2
样例解释
【样例说明】：
对于样例1,符合条件的日期是 20111102 。
对于样例2,符合条件的日期是 20011002 和 20100102 。
【数据范围】：
对于 60% 的数据,满足 date1 = date2
#include<bits/stdc++.h>
using namespace std;
int s1,t,s,x,y,m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main(){
cin>>x>>y;
for(int i=1;i<=12;i++){
for(int j=1;j<=m[i];j++){
s1=j%10*1000+j/10*100+i%10*10+i/10;
t=s1*10000+i*100+j;
if(t>=x&&t<=y){
s++;
}
}
}
cout<<s;
return 0;
}