比赛传送门：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