比赛传送门: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;
}