比赛传送门:https://ac.nowcoder.com/acm/contest/3674#question
B题 Xu1024's treasure chest
题意是给你一个数A,规定 -1e9<A<B<C<1e9,找到B,C满足 B^2^ - A^2^ = C^2^ - B^2^,找不到则输出"-1"。
虽然题目没说B,C一定是A的倍数,我们可以假设B,C是A的倍数,设 B=x*A,C=y*A,代入原方程得 2*x^2^*A^2^ - A^2^ = y^2^*A^2^,若 A^2^=0,则原方程为 2*B^2^=C^2^。
————————————————————以上是赛后补题————————————————————
E题 Days passing
我们很容易想到快速幂取模的解法。
这题关键就是求n^m^%7的值,但是n比较大,最大是10^10000^,不是1e4(我是怎么看成1e4的?),所以要注意是字符串输入,输入的时候对7取模。
#include <bits/stdc++.h>
using namespace std;
const int mod=7;
typedef long long ll;
string date,a;
string s[]={"Mon","Tue","Wed","Thu","Fri","Sat","Sun"};
ll i,n,m,k;
ll qpow(ll a,ll b)
{
ll s=1;
while(b)
{
if(b&1)s=s*a%mod;
b=b/2;
a=a*a%mod;
}
return s;
}
ll read(string a)
{
ll s=0;
for(int i=0;i<a.length();i++)
s=(s*10+a[i]-'0')%mod;
return s;
}
int main()
{
ios::sync_with_stdio(false);
cin>>date>>a>>m;
n=read(a);
k=qpow(n,m);//这里如果用欧拉降幂的公式是否可以更加简便运算呢?
for(i=0;i<6;i++)
if(s[i]==date)break;
int ans=(i+k)%mod;
printf("%s\n",s[ans].c_str());
return 0;
}
但是以上代码并不是最优的代码。
如果站在出题人的角度,我们可以悄咪咪地改一波数据,假装把这题出的毒瘤一点:把m的最大值变为10^1000000^,那么快速幂肯定是不行了,这个时候怎么做呢?
如果m很大则要用扩展欧拉定理进行欧拉降幂。
(欧拉定理/扩展欧拉定理传送门:洛谷 P5091 欧拉定理、洛谷 U55950 扩展欧拉定理)
由于欧拉定理的使用要考虑底数n与取模数p是否互质以及m与φ(p)的大小关系。首先p=7是质数则φ(p)=p-1=6,即φ(p)=6,根据题意可以确定m>=6并且m%6=0,那么下面我们再对底数n与取模数p是否互质进行分类讨论:
①如果n与7不互质,由于7是质数,则n必须含有7这个因子,那么n必定是7的倍数,所以 n^m^ % 7 = 0
②如果n与7互质,则 n^m^%7 = n^m%φ(p)^ % 7 = n^0^ % 7 = 1
于是我们找到了本题的规律:只要n%7==0则n^m^%7=0,否则n^m^%7=1,我们发现答案与m的大小没有任何关系! 如果我是出题人,我会把m的大小改到10^1000000^,可以更加迷惑你(出题人真是太友好了)
最终,我们可以改进之前的代码,不必再用快速幂,时间复杂度O(n)。(n=1e4)
#include <bits/stdc++.h>
using namespace std;
const int mod=7;
typedef long long ll;
string date,a;
string s[]={"Mon","Tue","Wed","Thu","Fri","Sat","Sun"};
ll i,n,m,k;
ll read(string a)
{
ll s=0;
for(int i=0;i<a.length();i++)
s=(s*10+a[i]-'0')%mod;
return s;
}
int main()
{
ios::sync_with_stdio(false);
cin>>date>>a>>m;
n=read(a);
if(n%7==0)k=0;
else k=1;
for(i=0;i<6;i++)
if(s[i]==date)break;
int ans=(i+k)%mod;
printf("%s\n",s[ans].c_str());
return 0;
}
J题 Fake Nim
这题是博弈,由于a[i]最大到2e18,sg函数打表是不可行的,只能思考找规律了。
虽然AC代码非常短,但是我想了挺长时间,下面说一下我的思考过程。
题意是两人取糖果,已知有n堆糖果以及每堆糖果数为a[i],假设先手是A,后手是B,规定A只能从任意一堆中取偶数个,B只能从任意一堆中取奇数个,并且如果轮到A取糖果的时候只要有任何一堆的糖果数量小于2(其实就是等于1),那么这个时候A就不能取,只能跳过。(其他情况下A不能跳过,必须取偶数个)。取走最后一个糖果的人获胜。
不难看出,B可以想方设法把任何一堆糖果数变为1,只要这堆数量为1的糖果存在,那么A就不能再取任何糖果,由于B能取奇数个,只要B一直留着这堆糖果不取,那么最后这堆糖果就只能被B取走。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>x;
if(n==1&&x%2==0)printf("DaDa\n");
else printf("TuTu\n");
return 0;
}
F题 Kuangyeye's Game
题意就是给你n个点,问你这n个点是否在同一直线上。
用向量的知识推导,假设A(x1,y1),B(x2,y2),现在要判断某个点C(xi,yi)是否在直线AB上。
向量AB=(x2-x1,y2-y1),向量AC=(xi-x1,yi-y1),若C在直线AB上,则存在非零实数k(注意k不一定是整数)满足AB=k*AC,那么
x2-x1=k(xi-x2),y2-y1=k(yi-y1),则k=(x2-x1)/(xi-x1)=(y2-y1)/(yi-y1)
公式推导到这里就要注意了,如果就这样求,则k是double类型,由于精度问题不好判断k值是否相等,这时需要把等式两边的除法形式转化为乘法形式,即 (x2-x1)/(xi-x1)=(y2-y1)/(yi-y1) 等价于 (x2-x1)*(yi-y1)=(y2-y1)*(xi-x1),这样都是整数就好判断是否相等了。
#include <bits/stdc++.h>
using namespace std;
int n;
struct node
{
int x,y;
}p[1010];
bool judge()//判断第i个点是否在前两个点构成的直线上
{
int dx=p[2].x-p[1].x;
int dy=p[2].y-p[1].y;
for(int i=3;i<=n;i++)
{
int nx=p[i].x-p[1].x;
int ny=p[i].y-p[1].y;
if(dx*ny!=dy*nx)return 0;
}
return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
if(n<=2)printf("Yes\n");
else
{
for(int i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
if(judge())printf("Yes\n");
else printf("No\n");
}
return 0;
}
C题 Binbin's treasure map
题意是求含 "\$" 最多的两个连通分量的 "\$" 之和,直接dfs即可。
#include <bits/stdc++.h>
using namespace std;
const int N=510;
char a[N][N];
int n,m,tmp,one,two,vis[N][N];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y)
{
if(a[x][y]=='$')tmp++;
vis[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]!='#')dfs(nx,ny);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
tmp=0;//tmp记录当前连通分量搜索到的"$"个数
if(!vis[i][j]&&a[i][j]!='#')dfs(i,j);
if(tmp>=one)two=one,one=tmp;//one表示最大的"$"个数,two表示第二大的"$"个数
else if(tmp>=two)two=tmp;
}
printf("%d\n",one+two);
return 0;
}
L题 Special number
题意是求[l,r]区间内有多少个数的因子数小于3,可以用唯一分解定理,也可以直接暴力。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5;
typedef long long ll;
int l,r,ans[N+10];
bool judge(int x)//判断x的因子个数是否小于3,小于3则返回True
{
ll s=1;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
int c=0;
while(x%i==0)
x=x/i,c++;
s=s*(1+c);
if(s>=3)return 0;
}
}
if(x>1)s=s*2;
if(s>=3)return 0;
return 1;
}
void get_ans()//预处理答案的前缀和
{
int cnt=0;
for(int i=1;i<=N;i++)
{
if(judge(i))ans[i]=++cnt;
else ans[i]=cnt;
}
}
int main()
{
ios::sync_with_stdio(false);
get_ans();
cin>>l>>r;
printf("%d\n",ans[r]-ans[l-1]);
return 0;
}
A题 The GCD of Fibonacci Numbers
任意两个Fibonacci数求gcd满足一个公式:gcd(F[n],F[m])=F(gcd(n,m))。
以下给出证明:
斐波那契数列的这个性质的本质是gcd(a,b)=gcd(a+nb,b),n>=0
令f(n)=a,f(n+1)=b,于是f(n+k)=f(k-1)a+f(k)b,gcd(f(n),f(n+k))=gcd(f(n),f(k)b),因为a和b互质,所以gcd(f(n),f(k)b)=gcd(f(n,f(k))。令m=n+k,于是gcd(f(n),f(m))=gcd(f(n),f(m-n))
如果不断重复gcd(f(n),f(m))=gcd(f(n),f(m-n))这个过程,那么n和m的变化其实就是更相减损术的过程
所以迭代的终点就是gcd(m,n)
可以去看看这篇文章关于斐波那契数列的性质,写得很好:https://blog.csdn.net/qq_30974369/article/details/78468788
#include <bits/stdc++.h>
using namespace std;
int a,b,t,f[50];
int main()
{
ios::sync_with_stdio(false);
f[0]=0,f[1]=1;
for(int i=2;;i++)
{
int x=f[i-1]+f[i-2];
if(x<0)break;
f[i]=x;
}
cin>>t;
while(t--)
{
cin>>a>>b;
printf("%d\n",f[__gcd(a,b)]);
}
return 0;
}
M题 XOR sum
这题找规律,先找[1,x]区间异或和sum(x)的规律,sum(r)^sum(l-1)即为[l,r]区间异或和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum(ll x)//求出[1,x]的异或和
{
if(x%4==1)return 1;
else if(x%4==2)return x+1;
else if(x%4==3)return 0;
else return x;
}
int main()
{
ll l,r;
cin>>l>>r;
printf("%lld\n",sum(r)^sum(l-1));
return 0;
}
G题 Buying Keys
暴力枚举,贪心,尽量多买10元3个的,少买3元1个的,这样总个数最小。
#include <bits/stdc++.h>
using namespace std;
long long n,x,y,ans;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
int flag=0;
for(x=n/10;x>=0;x--)
{
if((n-10*x)%3==0)
{y=(n-10*x)/3;flag=1;break;}
}
if(flag==0)printf("orz\n");
else printf("%lld\n",3*x+y);
return 0;
}
H题 Dice
签到题。
#include <bits/stdc++.h>
using namespace std;
int t,n;
double tmp=1,ans[22];
int main()
{
ios::sync_with_stdio(false);
for(int i=1;i<=20;i++)
{
tmp=tmp*0.5;
ans[i]=ans[i-1]+tmp;
}
cin>>t;
while(t--)
{
cin>>n;
printf("%.4lf\n",ans[n]);
}
return 0;
}
Comments | NOTHING