河南理工大学算法协会暑期集训积分赛（一）
Nth power of n
Descripition:
求 nn 的个位数。
输入格式
多组输入，处理到文件结束。
每组数据输入一个 n。(1≤n≤1e9)
输出格式
输出 nn 的个位数。
样例
input
1
2
3
output
1
4
7
Problem solving:
快速幂的板子题，对10取模即可。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll poww(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1) ans=ans*x%10;
x=x*x%10;
y/=2;
}
return ans;
}
int main()
{
ll n;
while(~scanf("%lld",&n))
{
cout<<poww(n,n)<<endl;
}
return 0;
}复读机的力量
Descripition:
Codancer: “我好菜啊！”
Dicer: “我好菜啊！”
Todest: “我好菜啊！”
CaprYang: “我好菜啊！”
…
大佬们又开始装弱了，真正的菜鸡瑟瑟发抖不敢说话。
我们规定一个人是复读机当且仅当他说的每一句话都是复读前一个人说的话。
我们规定一个人是复读机当且仅当他说的每一句话都是复读前一个人说的话。
我们规定一个人是复读机当且仅当他说的每一句话都是复读前一个人说的话。
规定一个复读机的熟练度为复读数量的多少。现在给你一段聊天记录，请你找出其中的复读机们。
规定一个复读机的熟练度为复读数量的多少。现在给你一段聊天记录，请你找出其中的复读机们。
规定一个复读机的熟练度为复读数量的多少。现在给你一段聊天记录，请你找出其中的复读机们。
输入格式
输入T组,(1≤T≤10)
每组第一行输入一个正整数N,表示聊天记录的长度（1≤N≤10000）。
接下来N行，每行两个字符串，前一个字符串为姓名，后一个字符为聊天记录。
保证所有字符串长度不超过50，保证所有字符串只包含小写字母.
输出格式
如果没有复读机，输出 “Unbelievable!”(不包含引号）
否则按照熟练度从大到小输出所有的复读机，如果熟练度相同，按照字典序从小到大输出。
样例
input
1
4
codancer iamsovegetable
dicer iamsovegetable
todest iamsovegetable
capryang iamsovegetable
output
capryang
dicer
todest
提示
数据保证上面大佬们说的话都是瞎话。
Problem solving:
不难，但是是一道送命题。需要注意的是当一个人说的每一句话都是复读的上一个人说的话的时候他才能算得上是复读机。然后就是map，结构体，set之类的使用。具体可以看代码
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
string x,y;
}p[10005];
struct nod{
string na;
int fo;
}pp[10005];
bool cmp(nod m,nod n)
{
if(m.fo==n.fo) return m.na<n.na;
return m.fo>n.fo;
}
int main()
{
int t,n;
cin>>t;
string x,y;
while(t--)
{
cin>>n;
set<string> se;
map<string,int> ma;
map<string,int> mp;
for(int i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y;
se.insert(p[i].x);
ma[p[i].x]=1;
}
ma[p[0].x]=0;
for(int i=1;i<n;i++)
{
if(p[i].y==p[i-1].y)
mp[p[i].x]++;
if(p[i].y!=p[i-1].y)
ma[p[i].x]=0;
}
int pos=0;
for(set<string>::iterator it=se.begin();it!=se.end();it++)
{
if(ma[*it])
{
pp[pos].na=*it;
pp[pos].fo=mp[*it];
pos++;
}
}
if(pos==0) puts("Unbelievable!");
else
{
sort(pp,pp+pos,cmp);
for(int i=0;i<pos;i++)
{
cout<<pp[i].na<<endl;
}
}
}
}无穷的小数
Descripition:
在十进制下，我们能够很轻易地判断一个小数的位数是有穷的或无穷的，但是把这个小数用二进制表示出的情况下其有穷性和无穷性就会发生改变，比如
十进制下的 0.5 ,在二进制下的值为 0.1 ；
十进制下的 0.75 ,在二进制下的值为 0.11 ；
十进制下的 0.6 ,在二进制下的值为 0.1001100......
给你一个十进制的小数，判断其在二进制表示下小数位数是否无穷。
输入格式
多组输入，处理到文件结束
每组数据输入一个六位的小数 n.(0≤n<1)
输出格式
如果在二进制下小数位数是有穷的，输出”YES”,否则输出”NO”.
样例
input
0.500000
0.600000
0.750000
output
YES
NO
YES
Problem solving:
我拿了一血，主要是一开始大佬们没有注意到这个水题233.
模拟就行了，小数转换成二进制就是每次乘以2直到等于1.如果一个小数在二进制表示下小数位数是无穷的，意思就是无论它承几次2，都不会正好等于1。我们只需要乘以2一定的次数，如果出现1，就不是无穷的，反之即无穷的。这个次数我写的时候用的100，后来结束后各种测试发现最小改成6也能过Orz。
官方题解里面说会有精度问题，但是我没遇到哈，double过了。
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
double s;
while(~scanf("%lf",&s))
{
int i=0,flag=0;
while(i<=6)
{
s*=2;
if(s==int(s)) flag=1;
i++;
}
if(!flag) cout<<"NO"<<endl;
else puts("YES");
}
return 0;
}Special String
Descripition:
我们定义一个字符串S为Special String只要这个字符串满足下面这些条件:
1.这个串是回文的，即把这个字符串正着读和反着读相同，如abba和aca，而ba和abca则不是。
2.26个小写字母必须全部出现
3.这个串的长度为偶数。
对于给定的S,判断它是否是Special String.
输入格式
输入一个只由小写字母组成的字符串S。(1≤|S|≤1e5)
输出格式
如果这个字符串是Special String，输出”YE5”,否则输出”N0”
样例
input
aaaa
output
N0
input
abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba
output
YE5
Problem solving:
这道题，很厉害，很难！
三个条件的判断：
回文串的判断可以通过可以翻转之后比较或者比较对称位置上的字符是否相等来实现
26个字母都必须出现的判断，因为保证输入是小写字母，用一个set就行，最后看set的大小是否为26.
长度为偶数这个就不用说了。
最难的地方来了，<font color="red">是'YE5'和'N0'，不是'YES'和'NO'。。。学长tql。</font>
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s,mid;
cin>>s;
set<char> se;
int flag=0,len=s.size();
if(len%2==0) flag++;
for(int i=0;i<len;i++) se.insert(s[i]);
if(se.size()==26) flag++;
mid=s;
reverse(s.begin(),s.end());
if(mid==s) flag++;
if(flag==3) puts("YE5");
else puts("N0");
return 0;
}Max Gcd
Descripition:
一个数组a，现在你需要删除某一项使得它们的gcd最大，求出这个最大值。
输入格式
第一行输入一个正整数n，表示数组的大小，接下来一行n个数，第i个数为ai。(2≤n≤1e5,1≤ai≤1e9)
输出格式
输出删除掉某个数以后的gcd的最大值。
样例
input
4
2 4 8 1
output
2
input
4
1 2 3 4
output
1
提示
样例一：删除第四个元素后，2,4,8的最大公因子为2。
样例二：无论删除哪一个，最大公因子都为1。
Problem solving:
比赛的时候这题毫无思路，，，
完了之后了解到，是使用了一个前缀gcd数组和一个后缀gcd数组来实现求去掉第I位数字之后剩余所有数字的gcd。
b为前缀gcd数组，c为后缀gcd数组
那么去点第I位的数字之后剩余所有数字的gcd就是
gcd（b[i-1],c[i+1]）
这种思想是真的巧妙。
我师父还想到了一种贪心的解法，但是我没听太懂233，总之很强就对了。
Code:
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
int c[200005];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
b[0]=a[0];
for(int i=1;i<n;i++)
{
b[i]=__gcd(b[i-1],a[i]);
// cout<<b[i]<<endl;
}
c[0]=a[n-1];
for(int i=n-1;i>=0;i--)
{
c[i]=__gcd(c[i+1],a[i]);
}
int ans=0;
for(int i=0;i<n;i++)
{
if(i==0) ans=max(ans,c[1]);
else if(i==n-1) ans=max(ans,b[n-2]);
else ans=max(ans,__gcd(b[i-1],c[i+1]));
}
cout<<ans<<endl;
} Count Prime Pairs
Descripition:
对于数组a，如果i≠j并且ai+aj是一个质数，那么我们就称(i,j)为质数对，计算数组中质数对的个数。
输入格式
第一行输入一个n，表示数组的长度,接下来n个整数，第i个数代表ai。
(1≤n≤100000,0≤ai≤100)
输出格式
输出数组中质数对的个数。
样例
input
3
1 2 3
output
4
提示
样例说明：a1+a2,a2+a1,a2+a3,a3+a2都为质数，总共有四对。
Problem solving:
其实比赛的时候想到了这样去暴力，但是没实现。
题目中最大的素数是199，每个素数对所有出现过的数进行判断看差值是否出现过，就行了。
先来个素数打表，还有就是用map统计每个数出现的次数。
假设1出现了2次，2出现了2次，那么和为3的次数就是2*2=4次
假设1出现了4次，那么和为2出现的次数就是4*（4-1）/2=6次
按照这上面两种进行统计输出就行。
Code:
#include<bits/stdc++.h>
using namespace std;
int t[205];
int p[205];
int main()
{
p[0]=p[1]=1;
for(int i=2;i<=205;i++)
{
for(int j=i*2;j<=205;j+=i)
p[j]=1;
}
int n,a;
cin>>n;
while(n--)
{
cin>>a;
t[a]++;
}
int ans=0;
for(int i=0;i<=100;i++)
{
for(int j=i+1;j<=100;j++)
{
if(i==j) continue;
if(!p[i+j])
{
ans+=t[i]*t[j];
}
}
}
cout<<ans*2+t[1]*(t[1]-1)<<endl;
}平行线
Descripition:
“大猩猩为什么不喜欢平行线？”“因为平行线没有相交”
哈哈哈哈哈哈哈哈哈
为了管理动物园不听话的大猩猩们，动物管理员Boctorio 决定去远方的ACM之城找一些平行线，当他逛到一个神奇的店铺时，他发现了一副黑色的图，上面依稀可见一些白色的点。Boctorio 询问店铺老板这幅画是什么，老板说：“天机不可泄露”。等Boctorio仔细端详了一会这幅画后，他惊讶的发现其中所蕴含的奥秘。向店铺老板道谢后，他拿着刚买的这幅画，就连忙赶回动物园。
输入格式
输入一个数 n(1≤n≤1000)，表示点的个数。
接下来n行，每行两个整数 xi,yi(1≤xi,yi≤1e9),表示第i个点。
数据保证没有重复的点
输出格式
输出用这些点所能表示出来的平行线段的对数。（两条不同的线段重合也算为平行）
样例
input
6
0 0
1 0
1 1
3 1
3 3
5 4
output
10
Problem solving:
两线平行的条件就是斜率相等（也可以用向量做）统计每个斜率出现的次数即可
斜率不能直接用double存，会爆精度，可以用一个pair来存，但是注意，分数要进行约分，同时除以它们的gcd就行了
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int x[maxn],y[maxn];
int main()
{
int n;
cin>>n;
set<pair<int,int> > se;
map<pair<int,int> ,int> ma;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int dx=x[j]-x[i];
int dy=y[j]-y[i];
int mid=__gcd(dx,dy);
dx/=mid;
dy/=mid;
ma[{dx,dy}]++;
se.insert({dx,dy});
}
}
int ans=0;
for(set<pair<int,int> >::iterator it=se.begin();it!=se.end();it++)
{
ans+=(ma[*it]*(ma[*it]-1))/2;
}
cout<<ans<<endl;
}Area of polygons
Descripition:
现在有a个边长为1的正方形，b个半径为1的圆，c个边长为1的等边三角形，现在你随机拿出一个图形，求这个图形面积的期望。
输入格式
第一行输入一个T,代表输入的组数。(1≤T≤100)
接下来T行，每行三个数字a,b,c(1≤a,b,c≤1000)。
输出格式
输出T行，对于每一组输入，输出面积的期望，小数点后保留三位小数。
样例
input
3
1 2 3
4 5 6
7 8 9
output
1.430
1.487
1.501
提示
圆周率为3.1415926535897
Problem solving:
简单数学题
期望即平均值
Code:
#include<bits/stdc++.h>
using namespace std;
#define PI 3.1415926535897
int main()
{
double t,a,b,c;
cin>>t;
while(t--)
{
double sum=0;
cin>>a>>b>>c;
sum+=a+PI*b+sqrt(3)*c/4;
printf("%.3lf\n",sum/(a+b+c));
}
}双色球
Descripition:
双色球投注区分为红色球号码区和蓝色球号码区，红色球号码区由1-33共三十三个号码组成，蓝色球号码区由1-16共十六个号码组成。投注时选择6个红色球号码和1个蓝色球号码组成一注进行单式投注。其中奖规则为：
一等奖（6+1）
二等奖（6+0）
三等奖（5+1）
四等奖（5+0、4+1）
五等奖（4+0、3+1）
六等奖（2+1、1+1、0+1）
其中(a+b)即为有a个红色球，b个蓝色球与开奖某个数字相同（只与数字有关，与位置无关）。
现在你有 n 张双色球彩票，以及本场彩票开奖结果，请你求出这 n 张彩票获得的最高奖。
输入格式
第一行输入一个 n ，表示 n 张彩票
接下来 n 行，每行 7 个数字，表示每张彩票的选号，其中前六个位红色球，后一个为蓝色球。
接下来一行，输入 7 个数字，表示开奖结果，其中前六个为红色球，后一个为蓝色球。
输出格式
输出所有彩票中能获得的最高等级奖，若无，则输出”0”。
样例
input
5
2 17 21 28 30 32 10
2 12 17 29 30 31 15
9 10 19 25 26 30 12
6 8 18 29 30 31 10
13 14 21 22 27 32 8
6 7 12 19 27 28 12
output
6
input
3
2 17 21 28 30 32 10
2 12 17 29 30 31 15
9 10 19 25 26 30 12
6 8 18 29 30 31 10
output
6
提示
彩票六个红色球数字均为从小到大排列
Problem solving:
看懂题意后直接暴力模拟就行
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int ball[10];
}p[100];
int re[10];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<7;j++)
cin>>p[i].ball[j];
}
for(int i=0;i<7;i++) cin>>re[i];
int ans,mmp=7,mmm=7;
for(int i=0;i<n;i++)
{
ans=0;
int flag=0;
for(int j=0;j<6;j++)
{
if(binary_search(re,re+6,p[i].ball[j]))
ans++;
}
if(p[i].ball[6]==re[6]) flag=1;
if(ans==1&flag) mmm=6;
else if(ans==0&&flag) mmm=6;
else if(ans==2&&flag) mmm=6;
else if(ans==3&&flag==1) mmm=5;
else if(ans==4)
{
if(!flag) mmm=5;
else mmm=4;
}
else if(ans==5)
{
if(!flag) mmm=4;
else mmm=3;
}
else if(ans==6)
{
if(!flag) mmm=2;
else mmm=1;
}
mmp=min(mmm,mmp);
}
cout<<mmp%7<<endl;
}
Remainder Minimization 2019
Descripition:
给你一个区间[L,R],在这个区间内找到两个不同的数字i,j，使得(i∗j)%2019的值最小。
输入格式
输入两个数 L,R,(1≤L<R≤1e9）
输出格式
如题
样例
input
4 5
output
20
input
2020 2040
output
2
Problem solving:
区间内只要出现2019的倍数，那么答案就是0。
所以我们只需要判断区间大小与2019的关系，如果大于2019，直接输出0就行，反之直接两个for循环就行，因为这时区间长度小于2019，时间复杂度也不高。注意要用long long。
Code:
a,b=input().split()
a=eval(a)
b=eval(b)
ans=1111111111111
for i in range(a,b):
for j in range(a+1,b+1):
mid = i*j % 2019
ans = min(ans,mid)
if ans==0:
break
if ans==0:
break
print(ans)今天的题确实不算太难吧，就过了6题，还罚时巨高，主要还是自己的原因。STL和结构体的使用能力还有点欠缺，另外用map统计出现次数这个真的是很有用的东西，set去重，这些都知道的东西用不到平常写题的过程中太亏了。继续加油，Fighting！！！
