ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

博客营比赛题解

posted on 2019-08-06 15:48:55 | under 比赛题解 |

翻币问题

这是一道傻题,绵羊竟然去宽搜,真搞不懂他在干什么,我的代码很简单。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==6){
        cout<<6;//可恶的绵羊告诉我,翻5次的时候必须翻不同的棋子,于是就只能这样做了
        return 0;
    }
    switch(n%5){
        case 0:cout<<n/5;break;
        case 1:cout<<n/5+1;break;
        case 2:cout<<n/5+2;break;
        case 3:cout<<n/5+3;break;
        case 4:cout<<n/5+2;break;
    }
    return 0;
}

ZHK的忧伤

数学题

列出公式: $2n\times 3^n$

代码自然也很简单了

#include<bits/stdc++.h>
using namespace std;
const int mod=10079833;
long long Pow(long k){
    long long s=1,tot=3;
    while(k){
        if(k%2==1)s=s*tot%mod;
        tot=tot*tot%mod;
        k=k>>1;
    }return s;
}
int main(){
    long long k;
    cin>>k;
    cout<<Pow(k)*k*2%mod;
    return 0;
}

ZHK的国家

太水了!

直接晾晒代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"Peace is what everyone wants.";
    return 0;
}

ZHK国王

显然,大正方形的边长等于小正方形的斜边长度。

同时,小正方形的面积是

$10\times10=100$

正方形还有一种计算面积的公式:

斜边 $\times$ 斜边 $\div2 $

所以斜边是

$ \sqrt {100\times2} $

所以,正方形的面积是

$\sqrt{100\times2}\times\sqrt{100\times2}$

那么

正方形的面积就出来了是

$100\times2$

也就是

$200$

所以代码就出来了

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

很优秀的拆分

美妙的二进制的极致应用

例如:

1248163264128

互相加可以加出1~255之间所有的数

所以,代码也简单了

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int s=0;
    while(n!=0){
        n/=2;
        s++;
    }cout<<s;
    return 0;
}

就这么短,没问题

ZHK的反击

是否有人当成守灵者的逃亡来做?

我可以告诉你们有

为什么不要像守灵者的逃亡那样去dp,原因是,等待8秒后再开15分钟的F1模式车相当于23秒开了450米,可普通模式23可以跑460

$460>450$

所以吗,可以得到一个结论,不要去等待F1模式,这样就好办了,代码也很简单了

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int x,y;
        cin>>x>>y;
        if(x<=15){
            x*=30;
            if(x>=y)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }else{
            x-=15;
            int n=x*20+450;
            if(n>=y)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

简单数论

让大家接触提前接触一下数论

$$ [ (\sum_{i=1}^n \sum_{j=1}^n i^2 j^2 ) \times 36 ]mod \ p $$

这道题的意思是什么呢?

我相信我打一个暴力大家也懂了

#include<bits/stdc++.h>
using namespace std;
int n,s=0,x;
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            s+=i*i+j*j;
    s*=36;
    s%=x;
    cout<<s;
   return 0;
}

这样写,大概能得30

这不就是平方和吗,每个数的平方算了2n次 $$ [ (\sum_{i=1}^n i^2 \times 2n ) \times 36 ]mod \ p $$

#include<bits/stdc++.h>
using namespace std;
int n,s=0,x;
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)s+=i*i*n*2;
    s%=x;
    s*=36;
    s%=x;
    cout<<s;
   return 0;
}

这样写大概能得50

最后在给一个AC代码,具体为什么,其实我也不知道,详情请问StephaneZ

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,p;
    cin>>n>>p;
    long long ans=n;
    ans*=n+1;
    ans%=p;
    ans*=2*n+1;
    ans%=p;
    ans*=ans;
    ans%=p;
    cout<<ans;
    return 0;
}

二叉树上的程序猿

水题!

dp

其实就很像导弹拦截

#include <bits/stdc++.h>
using namespace std;
int a[55],b[55],f[55];
int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
            if(a[j]>=a[i])f[i]=max(f[i],f[j]);
        f[i]+=b[i];
        ans=max(ans,f[i]);
    }cout<<ans;
    return 0;
}

鸭王

最难的题目

二分+贪心

// luogu-judger-enable-o2
#pragma GCC optimize(1)
#include <bits/stdc++.h>
using namespace std;
bool a[18010];
vector<int>q;
int n,k;
int find(int x){
    for(int i=max(x-k,1);i<=n;i++)
        if(a[i]){
            a[i]=false;
            return i;
        }
    return -1;
}
bool check(int x){
    memset(a,1,sizeof(a));
    q.clear();
    q.push_back(x);
    a[x]=0;
    int beg=1;
    while(beg<n)
        for(int j=0;j<q.size();j++){
            beg++;
            x=find(q[j]);
            if(x==-1)return false;
            q.insert(j+q.begin()+1,x);
            j++;
        }
    return true;
}
int main(){
    cin>>n>>k; 
    int left=1,right=n+1;
    while(left+1<right){
        int mid=(left+right)/2;
        if(check(mid))left=mid;
        else right=mid;
    }cout<<left;
    return 0;
}
// luogu-judger-enable-o2
#pragma GCC optimize(1)

这个是个好东西,让我最后一个点的时间,减少了一半,从TLE变成AC

洛谷神鸭竟然用了并查集

我仔细想了一下,确实是一个好方法,在这也放一下代码

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF)
{
    int RR=1;FF=0;char CH=getchar();
    while(!isdigit(CH)&&CH!='-') CH=getchar();
    if(CH=='-') RR=-1;else FF=CH^48;CH=getchar();
    while(isdigit(CH)) FF=(FF<<1)+(FF<<3)+(CH^48),CH=getchar(); FF*=RR;
}
int n,k,ans;
int fa[100010];
int bcj(int xi)
{
    if(xi==-1) return xi;
    if(fa[xi]==xi) return xi;
    return fa[xi]=bcj(fa[xi]);
}
bool work(int i)
{
    for(int l=1;l<=n;l++)
        fa[l]=l;
    fa[n+1]=-1;
    fa[i]=(i==n)?-1:i+1;
    deque<int> qi; int o=1;
    qi.push_front(i);
    while(o<n)
    {
        int stp=qi.back();
        while(qi.front()!=stp)
        {
            o++;
            int pi=qi.front(); qi.pop_front(); qi.push_back(pi);
            int Ty=bcj(max(pi-k,1));
            if(Ty==-1) return false;
            qi.push_back(Ty),fa[Ty]=bcj(Ty+1);
        }
        o++;
        int pi=qi.front(); qi.pop_front(); qi.push_back(pi);
        int Ty=bcj(max(pi-k,1));
        if(Ty==-1) return false;
        qi.push_back(Ty),fa[Ty]=bcj(Ty+1);
    }
    return true;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n),read(k);
    int l=1,r=n;
    while(l<=r)
    {
        //memset(flag,0,sizeof(flag));
        int mid=(l+r)>>1;
        if(work(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}

并查集真强大,我开O(1)+O(2)用时还是他的代码的20倍左右

斗地主

这题显然是dp

数组

f[i][j]

表示的是,翻到的数字和为i,现在数值为j的那一面朝上

题意有一个坑点

你可以随便选择一面朝上开始翻

状态有了,现在要来考虑转移状态的方程该怎么写了

#include <bits/stdc++.h>
using namespace std;
long long f[10010][11];//状态表示:f[i][j]表示,翻完的值为i,此时色子j面朝上,所花费的步数最小值(算j)
int main(){//由于数据个数很多,所以需要直接在外面初始化 
    memset(f,0x3f3f3f,sizeof(f));//先将f的值设定为无穷大 
    f[0][1]=0;//边界条件。显然的。 
    for(int i=2;i<=10000;i++)//一直算到最大值 
        for(int j=1;j<=6&&j<=i;j++)//从哪个地方过来的 
            for(int k=1;k<=6;k++)//从那个地方过来的之前在哪个点能是f[i][j]最小(它是怎么来的) 
                if(j+k!=7&&j!=k)f[i][j]=min(f[i][j],f[i-j][k]+1);//不能跟j对面,也不能与j相同,我看过了陈书扬的代码,状态转移方程竟然是推未来,很玄学,我觉得还是我的代码更加简洁易懂。 
    long long T;
    cin>>T;
    while(T--){
        long long x;
        cin>>x;
        long long ans=0x3f3f3f;
        for(int i=1;i<=6;i++)ans=min(ans,f[x][i]);//判断最后到那个格子翻的次数最少 
        if(x<=6)cout<<1<<endl;
        else if(ans==0x3f3f3f)cout<<-1<<endl;//如果对于赋的初值,显然是没有办法翻到了 
            else cout<<ans<<endl;//否责,当然是输出最优解了 
    }
    return 0;
}