1.A-B数对
二分法
将A-B=C转化成A=B+C,然后遍历数组,让数组的每个元素加C,再查找原数组中是否存在对应数组元素+C之后的值。(数据量比较大,所以我们就用二分在查找过程中提高效率,这里就用到了二分模板)。
因为原数组不一定是有序的,所以我们先使用C++STL库中的sort()函数进行升序排序,这样的数组就是有序的。我们查找每个元素+C第一次出现的下标和最后一次出现的下标,再让最后一次出现的下标-第一次出现的下标+1(用sum不断累加这个值),最后sum的值就是A-B数对的个数。
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
long long a[200001],n,c,cnt;
map<long long, long long>m;
void find(int l,int r,int num);
int main() {
int i;
cin>>n>>c;
for (i=0;i<n;i++) {
cin>>a[i];
m[a[i]]++;
}
sort(a,a+n);
//分查找
for (i=0;i<n;i++) {
find(0,n-1,a[i]);
}
cout<<cnt;
return 0;
}
void find(int l,int r,int num)
{
int mid;
mid=(l+r)/2;
if(l>r) return;
if(num-a[mid]==c)
{
cnt+=m[a[mid]];
return;
}
//如果差值比C大往右找
else if (num-a[mid]>c) find(mid+1,r,num);
//如果差值比C小往左找
else find(l,mid-1,num);
}
2.Good Kid
题意:有一个由n个数字组成的数组a,可以将其中任意一个数加一,求操作之后的最大乘积。
思路:加在最小的数上可以是乘积最大化。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,i,min,j,p=1,a[100];
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
if(i==0||a[i]<min)
{
min=a[i];
j=i;
}
}
a[j]++;
for(i=0;i<n;i++) p=p*a[i];
cout<<p<<endl;
}
return 0;
}
3.Short Sort
三个字母只要确保有一个在正确的位置上就行。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i;
char a[4];
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a;
if(a[0]=='a'||a[1]=='b'||a[2]=='c')
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
4.Target Practice
此题是一道几何题,图从外到里依次为1-5分,X为射中了这个点,求总分。设某点坐标x,y,则该点分值为 { x,y,10-x+1,10-y+1 } 取其中的最小值,对所有射中点求和即可
5个正方形的环,越内圈分数越高。那给出一个坐标我们判断它属于那个环就行。
#include<stdio.h>
int main()
{
int t;
scanf("%d", &t);
char c;
scanf("%c", &c);
for (int i = 0; i < t; i++)
{
int s = 0;
for (int j = 0; j < 10; j++)
{
for (int k = 0; k < 10; k++)
{
scanf("%c", &c);
if (c == 'X')
{
int a = 5;
if (j + 1 < a)
{
a = j + 1;
}
if (10 - j < a)
{
a = 10 - j;
}
if (k + 1 < a)
{
a = k + 1;
}
if (10 - k < a)
{
a = 10 - k;
}
s += a;
}
}
scanf("%c", &c);
}
printf("%d\n", s);
}
return 0;
}
5.Round Down the Price
一道数学题,找到最接近某个数的10的幂,可以通过遍历每次乘以10,然后再求出差值。
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,t,m,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>t;
m=1;
while(m<=t) m=m*10;
m=m/10;
cout<<t-m<<endl;
}
return 0;
}
6.最大公约数和最小公倍数问题
经典的gcd以及lcm的题(其实就是最大公约数和最小公倍数)
gcd一个很重要的定理:gcd(x,y)*lcm(x,y)=x*y
依靠这个定理,只需要进行枚举,便可AC
一层for循环,i初始值为1,终止值为x*y
如果x*y%i==0(意思看上方定理理解)以及gcd(i,x*y/i)==x(检测两数gcd是否为x)
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b);
int main()
{
int m,n,num,ans,i;
cin>>m>>n;
num=m*n;
if(m==n) ans--;
for(i=1;i<=sqrt(num);i++)
{
if(num%i==0&&gcd(i,num/i)==m)
{
ans=ans+2;
}
}
cout<<ans;
return 0;
}
//辗转相除
int gcd(int a,int b)
{
if(a%b==0) return b;
else return gcd(b,a%b);
}
7.Odd One Out
三个数中两个数一样,找出另一个数,水题,直接比较即可。
结合异或
可以用异或的性质来做,异或有以下两个性质:
1.两个相同的数异或等于0
2.0异或一个数等于这个数本身
发现这两个性质完美契合这道题,那我们直接输出三个数异或后的结果即可
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b,c;
cin>>a>>b>>c;
int s;
s=a^b^c;
cout<<s<<endl;
}
return 0;
}
8.Not Quite Latin Square
数学题,要求A,B,C每行每列都只出现一次,其实换个思路就知道整个3X3矩阵中A,B,C每个字母出现次数是固定的3次,于是求和直接判断就行了,剩下的那个字母就是要找出的值。
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
getchar();
while(t--)
{
int sum=0;
int i,j;
char line[4];
for(i=0;i<3;i++)
{
scanf("%s",line);
for(j=0;j<3;j++)
{
if(line[j]>='A') sum=sum+line[j]-'A';
}
}
printf("%c\n",'A'+9-sum);
}
return 0;
}
9.Can I Square?
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long long num,ret=0,input;
cin>>num;
int i;
for(i=0;i<num;i++)
{
cin>>input;
ret=ret+input;
}
num=sqrt(ret);
if(num*num==ret) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
10.Unnatural Language Processing
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
char q[300000];
int n = 0;
cin >> n;
cin >> q;
for (int j = 0; j < n; j++)
{
if ((j+2<n)&&(q[j] == 'a' || q[j] == 'e') && (q[j + 2] == 'a' || q[j + 2] == 'e'))
cout << q[j] << '.';
else if ((j + 2 < n) && (q[j] == 'b' || q[j] == 'c' || q[j] == 'd') && (q[j + 2] == 'a' || q[j + 2] == 'e'))
cout << q[j] << '.';
else cout << q[j];
}
cout << endl;
}
return 0;
}