第七维度2020复赛题解

复赛题解

出题人:A星际穿越

因为初赛大家表现得实在是太好了,所以我一度想要砍掉复赛的时间。。。
不过我也如之前在群里说过的,复赛没有数据结构的题

A

看上去挺唬人的,实际上挺简单的
对于n>2,分n为奇数和偶数讨论
若n为奇数,因为2和n一定互质,所以显然f(n)=f(2)+1=2
若n为偶数,那么偶数和偶数是不会互质的,所以f(n)=f(某个不为1的奇数)+1=3
所以。。。就这样咯,答案很显然了

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll unsigned long long
#define mod 19260817
ll n,T;
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n)return 0*putchar('0');if(n<0){putchar('-');write(-n);return n;}
    if(n>=10)write(n/10);putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
int main(){
    read(T);
    while(T--){
        read(n);
        writeln((n^1)?(((n/2%mod-1)*5%mod+((n&1)?3:1))%mod):0);
    }
    return 0;
}

B

参考视频
12
讲道理当时我正在思考到底要出啥题,看到了3b1b的这个视频,就愉快地决定出一道汉明码的题目
注意到输出格式中有一句“注意,此坐标从第一行第一列开始计算”,这句话给了提示,就是说计算过程中我们可以从第0行第0列开始计算
视频里讲的很清楚了,所以这里就简单讲讲
行和列编号0~n-1,然后二维转一维,对于每个1的格子ans异或上该格子的编号,然后一维转二维得到答案

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
#define N 1100
int n,T;
int ans,x,y;
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n)return 0*putchar('0');if(n<0){putchar('-');write(-n);return n;}
    if(n>=10)write(n/10);putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
char red(){
    char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar());
    return ch-'0';
}
int main(){
    read(T);
    while(T--){
        read(n);ans=0;
        fui(i,0,n-1,1)fui(j,0,n-1,1)if(red())ans^=(n*i+j);
        x=ans/n,y=ans%n;
        x++,y++;
        write(x),putchar(' '),writeln(y);
    }
    return 0;
}

C

这道题目是一道博弈论的题目。如果你构造了一些数据,就会发现在随机数据下,基本上先手必赢(但是我怎么可能给你们全部都是随机数据呢23333)
首先先看暴力做法
博弈论中,我们将某个选手必赢的状态称为必胜态,必输的状态称为必败态。如果A的一个状态能转移到B的必败态,那么该状态就是A的必胜态;若A的这个状态只能转移到B的必胜态,那该状态就是A的必败态
所以构造深搜dfs(i,j,k,S),S表示剩余可选数集合,i表示当前Alice已经选了的数的异或和,j表示Bob已经选的数的异或和,k取0表示当前轮到Alice取数,取1表示Bob取数
很显然这个做法严重超时,所以我们需要优化它
考虑所有数的二进制表示,我们发现如果某一个二进制位是1的数的总数是偶数,那么这个二进制位对答案无影响(因为不管两人怎么取,最终两个人的数的这个二进制位一定是一样的);而对于某个二进制位,若该位是1的数的总数是奇数,而且这个位是满足上面条件下最高的位,那这个位就是决定答案的一位(因为Alice和Bob在这一位的取数异或和一定不会相同,而更低的位即使有不同也不会超过这一位的大小)
所以我们可以很快得到,两人平局当且仅当所有数的异或和为0;而若所有数的异或和不为0,那么答案取决于异或和的非零最高位
不妨假设这一位上是1的数个数是p,0的个数是q,显然p和q都是奇数且p+q=n,于是我们可以写一个新的深搜
dfs(i,j,k),i取0表示当前Alice取了偶数个1,1表示取了奇数个1,j表示还剩下j个1,k表示还剩下k个0,j+k为偶数表示当前为Alice回合,奇数表示Bob回合
这个深搜可以写成记忆化搜索,f[i][j][k],值为1表示必胜态,为0表示必败态,递推式如下(^表示异或)
f[i][j][k]=!(f[i][j-1][k]&f[i][j][k-1])
=!(!(f[i^1][j-2][k]&f[i][j-1][k-1])& !(f[i^1][j-1][k-1]&f[i][j][k-2]))
=f[i^ 1][j-2][k]&f[i][j-1][k-1]|f[i^1][j-1][k-1]&f[i][j][k-2]
但是这个还是会超时,那怎么办呢?
注意到f[i][1][奇数]=1,且不难证f[i][奇数][1]=1(只需要分类讨论然后用归纳法处理即可),而f[i][0][偶数]=i,f[i][j(j为偶数)][0]=i^(j/2%2),
也就是说k为偶数时,f[i][0][k]和f[i^ 1][0][k]至少有一个1,f[i][k][0]和f[i^ 1][k][0]也至少有一个1,于是利用递推式在二维自然数空间中运用数学归纳法,得到f[i][奇数][奇数]必为1,j,k为偶数时f[i][j][k]和f[i^1][j][k]中至少有一个1
在非平局条件下我们要求的是f[0][p][q],而p,q都是奇数,故答案一定是1

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
int n,x,y,T;
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n){putchar('0');return 0;}
    if(n<0){putchar('-');write(-n);}else if(n>=10)write(n/10);
    putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
int main(){
    read(T);
    while(T--){
        read(n);x=0;
        fui(i,1,n,1)x^=read(y);
        writeln(x?1:0);
    }
    return 0;
}

D

题目数据出锅了,而且强度不够。。。
这道题是我高中时候出的(制造数据的那个标程也是高中写的),本来我是模仿hdu6395,结果比赛了才发现数据不对,再一看AC了的选手的程序,发现因为a和b太小了,这种解法被完全绕过了。。。
那就这道题目而言,在i<a+b的时候fi和Sumi暴力求出,i>a+b的时候我们发现(a+b)/i一定是0,所以就直接用矩阵乘法快速幂解决

//这个标程常数有点大
#include<bits/stdc++.h>
using namespace std;
#define N 100
#define M 20010
#define mod 1000000007
#define ll long long
struct Matrix{
    int n,m;
    ll a[N][N];
    Matrix(){n=m=0;memset(a,0,sizeof(a));}
    Matrix operator *(Matrix x){
        Matrix y;y.n=n;y.m=x.m;
        for(int i=1;i<=n;i++)for(int j=1;j<=x.m;j++){
            for(int k=1;k<=m;k++)(y.a[i][j]+=a[i][k]*x.a[k][j]%mod)%=mod;
        }
        return y;
    }
    void clear(){n=m=0;memset(a,0,sizeof(a));}
}a1,a2,a3,a4;
ll f[M],sum[M];
ll t,n,k,a,b,q;
Matrix power(Matrix x,ll y){
    Matrix ans;
    ans.m=ans.n=x.n;
    for(int i=1;i<=ans.n;i++)ans.a[i][i]=1;
    while(y){
        if(y&1)ans=ans*x;
        x=x*x;y>>=1;
    }
    return ans;
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&k,&a,&b);
        scanf("%lld",&q);
        memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));
        f[1]=1;f[2]=k;f[3]=k*(a+b)%mod;
        for(int i=1;i<=3;i++)sum[i]=(sum[i-1]+f[i])%mod;
        for(int i=4;i<=a+b;i++){
            f[i]=(a*f[i-3]%mod+b*f[i-1]%mod+(a+b)/i)%mod;
            sum[i]=(sum[i-1]+f[i])%mod;
        }
        a1.clear();a2.clear();
        a1.m=a1.n=4;a1.a[1][2]=a1.a[2][3]=a1.a[4][4]=1;
        a1.a[3][1]=a1.a[4][1]=a;a1.a[3][3]=a1.a[4][3]=b;
        a2.n=4,a2.m=1;
        a2.a[1][1]=f[a+b-2];a2.a[2][1]=f[a+b-1];a2.a[3][1]=f[a+b];a2.a[4][1]=sum[a+b];
        while(q--){
            scanf("%lld",&n);
            if(n<=a+b)printf("%lld %lld\n",f[n],sum[n]);
            a3=power(a1,n-a-b);a4=a3*a2;
            printf("%lld %lld\n",a4.a[3][1],a4.a[4][1]);
        }
    }
    return 0;
}

这是原来的有问题的标程(各位大佬可以一起来抓bug)
(当然我也很奇怪hdu的那道题目当年我是AC的,这个代码我也是按照那个代码打的,为啥这个会WA的这么惨QAQ)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ME 0x7f
#define FO(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define fel(i,a) for(register int i=h[a];i;i=ne[i])
#define ll long long
#define MEM(a,b) memset(a,b,sizeof(a))
#define mod 1000000007ll
int T,q;ll n,a,b,k,xx;
ll jz[10],zy[10][10],pre[10][10];
ll f[100000+10],sum[100000+10];
template<class T>
inline T read(T &n){
    n=0;int t=1;double x=10;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());(ch=='-')?t=-1:n=ch-'0';
    for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-'0';
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=(ch-'0')/x,x*=10;
    return (n*=t);
}
template<class T>void write(T n){if(n>=10) write(n/10);putchar(n%10+'0');}
template<class T>void print(T x,T y){write(x);putchar(' ');write(y);puts("");}
void jzc(){
    ll aaa[10][10];MEM(aaa,0);
    fui(i,1,5,1)fui(j,1,5,1)fui(k,1,5,1)
        aaa[i][j]=(aaa[i][j]+pre[i][k]*pre[k][j]%mod)%mod;
    fui(i,1,5,1)fui(j,1,5,1)pre[i][j]=aaa[i][j];
}
void power(int x){
    if(x<=1) return;power(x/2);jzc();if(!(x&1)) return;
    ll aaa[10][10];MEM(aaa,0);
    fui(i,1,5,1)fui(j,1,5,1)fui(k,1,5,1)
        aaa[i][j]=(aaa[i][j]+pre[i][k]*zy[k][j]%mod)%mod;
    fui(i,1,5,1)fui(j,1,5,1)pre[i][j]=aaa[i][j];
}
int main(){
    read(T);zy[2][1]=zy[3][2]=zy[4][4]=zy[5][3]=zy[5][4]=zy[5][5]=1;
    while(T--){read(k);read(a);read(b);read(q);
        zy[1][3]=zy[1][4]=a;zy[3][3]=zy[3][4]=b;ll fj=sqrt((xx=a+b));
        f[1]=1;f[2]=k;f[3]=k*(xx%mod)%mod;fui(i,1,3,1) sum[i]=sum[i-1]+f[i];
        fui(i,4,fj,1) f[i]=((a*f[i-3]%mod+b*f[i-1]%mod)%mod+xx/i)%mod,sum[i]=(sum[i-1]+f[i])%mod;
        if(xx<=3){fui(i,1,3,1) jz[i]=f[i];jz[4]=sum[3];jz[5]=0;
            fui(zzz,1,q,1){read(n);if(n<=3){print(f[n],sum[n]);continue;}
                fui(i,1,5,1)fui(j,1,5,1) pre[i][j]=zy[i][j];
                power(n-3);ll aaa[10];MEM(aaa,0);
                fui(i,1,5,1)fui(j,1,5,1)aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
                print(aaa[3],aaa[4]);
            }
            continue;
        }
        if(fj<=3){
            fui(i,4,xx,1)f[i]=((a*f[i-3]%mod+b*f[i-1]%mod)%mod+xx/i)%mod,sum[i]=(sum[i-1]+f[i])%mod;
            jz[1]=f[xx-2],jz[2]=f[xx-1],jz[3]=f[xx],jz[4]=sum[xx];jz[5]=0;
            fui(zzz,1,q,1){read(n);if(n<=xx){print(f[n],sum[n]);continue;}
                fui(i,1,5,1)fui(j,1,5,1) pre[i][j]=zy[i][j];
                power(n-xx);ll aaa[10];MEM(aaa,0);
                fui(i,1,5,1)fui(j,1,5,1)aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
                print(aaa[3],aaa[4]);
            }
            continue;
        }
        ll fj0=fj;
        fui(zzz,1,q,1){read(n);fj=fj0;if(n<=fj){print(f[n],sum[n]);continue;}
            ll fj1=xx/(fj+1);fui(i,1,5,1)fui(j,1,5,1) pre[i][j]=zy[i][j];
            fui(i,1,3,1)jz[i]=f[fj-3+i];jz[4]=sum[fj];jz[5]=fj1;
            if(n<xx/fj1){power(n-fj);ll aaa[10];MEM(aaa,0);
                fui(i,1,5,1)fui(j,1,5,1)aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
                fui(i,1,5,1)jz[i]=aaa[i];print(jz[3],jz[4]);continue;
            }
            power(xx/fj1-fj);ll aaa[10];MEM(aaa,0);
            fui(i,1,5,1)fui(j,1,5,1)aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
            fui(i,1,5,1)jz[i]=aaa[i];fj=fj1;fj1--;
            while(fj1>0&&xx/fj1<=n){
                jz[5]=fj1;fui(i,1,5,1)fui(j,1,5,1)pre[i][j]=zy[i][j];
                power(xx/fj1-xx/fj);MEM(aaa,0);
                fui(i,1,5,1)fui(j,1,5,1) aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
                fui(i,1,5,1)jz[i]=aaa[i];fj=fj1;fj1--;
            }
            if(xx/fj<n){jz[5]=fj1;fui(i,1,5,1)fui(j,1,5,1)pre[i][j]=zy[i][j];
                power(n-xx/fj);MEM(aaa,0);
                fui(i,1,5,1)fui(j,1,5,1) aaa[i]=(aaa[i]+jz[j]*pre[j][i]%mod)%mod;
                fui(i,1,5,1)jz[i]=aaa[i];
            }
            print(jz[3],jz[4]);
        }
    }
    return 0;
}

相关推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

微信扫一扫,分享到朋友圈

第七维度2020复赛题解
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close