广东工业大学校赛

因为两人在进密室前可以商量,因此有策略保证可以必胜

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"1.00"<<endl<<"1.00"<<endl<<"1.00"<<endl<<"1.00"<<endl;
    return 0;
}


一开始没想到,但是看到斐波那契数列的时候就知道是什么意思了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e5)+100
using namespace std;
int mod;
ll f[maxn];
ll a[maxn];
ll ff[maxn];
int main(){
    int T;
    mod=192600817;
    f[1]=1;f[2]=1;
    a[1]=1;a[2]=1;
    ff[1]=1;ff[2]=2;
    ff[0]=0;
    for(int i=3;i<=maxn-100;++i){
        f[i]=(f[i-1]+f[i-2])%mod;
        a[i]=(f[i]*f[i])%mod;
        ff[i]=(ff[i-1]+a[i])%mod;
    }
    while(~sc(T)){
        while(T--){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            int aa=a*4+b+1;
            int bb=c*4+d+1;
            if(bb<aa)
                swap(aa,bb);
            ll ans=0;
            ans=(ff[bb]-ff[aa-1]+mod)%mod;
            printf("%lld\n",ans);
        }
    }
}

 


对于任意的一个数,在处理一次之后肯定会转化成一个不超过600的数,因此我们可以按照题意先打表预处理前面600个鸽子数,如果k比600大就先处理一次,然后直接o(1)输出就可以了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e6)+100
using namespace std;
int ans[1000];
ll work(ll x){
    ll ans=0;
    while(x){
        ans+=(x%10)*(x%10);
        x/=10;
    }
    return ans;
}
int an[10000000];
int main(){
    int T;
    vector<int> v;
    mst(an,0);
    for(int k=1;k<=6000;k++){
        int ans=work(k);
        int cnt=0;
        int tot=0;
        while(ans!=1){
            ans=work(ans);
            cnt++;
            if(cnt>int(1e3))
                break;
        }
        if(ans==1){
            an[k]=1;
        }
    }
    for(int k=1;k<=int(1e7);++k){
        int aa=work(k);
        if(an[aa])
            v.pb(k);
    }
    sc(T);
    while(T--){
        int k;
        sc(k);
        cout<<v[k-1]<<endl;
    }
    return 0;
}


待补


十叉树深搜

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e2)+100
#define mod 123456789
using namespace std;
int n,k,ans;
void dfs(int pre){
    if(k==0)
        ans=pre;
    rep(i,0,9){
        if(pre==0&&i==0)
            continue;
        if(pre*10+i<=n){
            k--;
            dfs(pre*10+i);
        }
        else
            return;
    }
}
int main(){
    int T;sc(T);
    while(T--){
        sc2(n,k);
        dfs(0);
        printf("%d\n",ans);
    }
}

 


公式我就不推了,是找规律做的,头很铁

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e5)+100
using namespace std;
int mod;
ll quick_power(ll base, ll n){
    ll res = 1;
    while (n > 0){
        if (n & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    mod=1000000007;
    ll n;
    while(~scanf("%lld",&n)){
        printf("%lld\n",((((n-1)%mod)*quick_power(2,n)%mod)%mod+mod+1)%mod);
    }
}

 


矩阵快速幂,几乎是模版题,可惜没时间做了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e2)+100
#define mod 123456789
using namespace std;
int z[7]={0,2,1,27,37,24,6};
struct mtix{
    ll a[10][10];
    mtix(){mst(a,0);}
}f;
mtix mul(mtix a,mtix b){
    mtix c;
    for (int i=1;i<=6;i++)
        for (int j=1;j<=6;j++)
            for (int k=1;k<=6;k++)
            {c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;c.a[i][j]%=mod;}
    return c;
}
mtix mpow(ll y){
    mtix ans;
    mtix tem=f;
    for (int i=1;i<=6;i++)
        ans.a[i][i]=1;
    for (;y;tem=mul(tem,tem),y>>=1)
        if (y&1) ans=mul(ans,tem);
    ll sum=0;
    for (int i=1;i<=6;i++)
        sum+=(ans.a[1][i]*z[i])%mod;
    cout<<sum%mod<<endl;
    return ans;
}
int main(){
    f.a[1][1]=1;f.a[1][2]=2;f.a[1][3]=1;f.a[1][4]=0;f.a[1][5]=0;f.a[1][6]=0;
    f.a[2][1]=1;f.a[2][2]=0;f.a[2][3]=0;f.a[2][4]=0;f.a[2][5]=0;f.a[2][6]=0;
    f.a[3][1]=0;f.a[3][2]=0;f.a[3][3]=1;f.a[3][4]=1;f.a[3][5]=0;f.a[3][6]=0;
    f.a[4][1]=0;f.a[4][2]=0;f.a[4][3]=0;f.a[4][4]=1;f.a[4][5]=1;f.a[4][6]=0;
    f.a[5][1]=0;f.a[5][2]=0;f.a[5][3]=0;f.a[5][4]=0;f.a[5][5]=1;f.a[5][6]=1;
    f.a[6][1]=0;f.a[6][2]=0;f.a[6][3]=0;f.a[6][4]=0;f.a[6][5]=0;f.a[6][6]=1;
    int T;
    sc(T);
    while(T--){
        ll x;scanf("%lld",&x);
        mpow(x-2);
    }
}



待补


发表评论,支持MarkDown语法