寒假学习计划

比赛地址

牛客

官方题解

[A] 模板

题意

给出两个字符串,有三种操作,第一种是在某个字符串后面加上一个字符,第二种是删去某个字符串的最后一个字符.最后一种是将某个字符串的某个字符改为另一个.求最少几次操作后可以让两个字符串相等.

题解

贪心.

答案为两个字符串相同下标中不同的字符对数加上长度之差.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i;
char c[N],C[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    scanf("%s",&c);
    scanf("%s",&C);
    int Ans=0;
    for (i=0;i<Min(n,m);i++)
        if (c[i]!=C[i]) Ans++;
    Ans+=Abs(n-m);
    cout<<Ans<<endl;
    return 0;
}

[B] 牛牛战队的比赛地

题意

给出平面上的n个点,要求在x轴上找到一点,使得其到这些点的最远距离最小.求这个最小值,

题解

二分答案.

每个点会对应一段x轴上的区间,判断这n个区间是否相交即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define EPS 1e-6
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

inline double Min(double a,double b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}
inline double Fabs(double x){return (x<-EPS)?-x:(x>EPS)?x:0;}
inline bool Equ(double x,double y){return (Fabs(x-y)<EPS);}

struct Vector{
    double x,y;
    void Clean(void){x=y=0;}
    void Write(void){printf("%.3lf %.3lf\n",x,y);}
    Vector operator +(Vector p){return (Vector){x+p.x,y+p.y};}
    Vector operator -(Vector p){return (Vector){x-p.x,y-p.y};}
    double operator *(Vector p){return x*p.y-y*p.x;}
    double operator &(Vector p){return x*p.x+y*p.y;}
};
typedef Vector V;

struct Point{
    double x,y;
    void Clean(void){x=y=0.0;}
    void Write(void){printf("%.3lf %.3lf\n",x,y);}
    bool operator ==(Point a){return (x==a.x && y==a.y);}
    Point operator +(Point p){return (Point){x+p.x,y+p.y};}
    Point operator /(double l){return (Point){x/l,y/l};}
    Vector operator -(Point p){return (Vector){x-p.x,y-p.y};}
};
typedef Point P;

inline void SW(P &a,P &b){P t=a;    a=b;    b=t;}
inline double Dis2(P a,P b){return pow(a.x-b.x,2)+pow(a.y-b.y,2);}
inline double Dis(P a,P b){return pow(pow(a.x-b.x,2)+pow(a.y-b.y,2),0.5);}

int n,i,tot;
double low,high,mid,Ans;
P a[N];

struct Data{
    double x;
    int y;
}b[N*2];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL bool cmp(const Data &a,const Data &b){
    return a.x<b.x;
}

IL bool Check(double x){
    reg int i=0,sum=0,top=0;
    reg double y=0,l=0,t=0;
    for (i=1;i<=n;i++){
        if (Equ(a[i].y,0)){
            b[++top].x=a[i].x-x;    b[top].y=1;
            b[++top].x=a[i].x+x;    b[top].y=-1;
            continue;
        }
        l=sqrt(x*x-a[i].y*a[i].y);
        b[++top].x=a[i].x-l;    b[top].y=1;
        b[++top].x=a[i].x+l;    b[top].y=-1;
    }
    sort(b+1,b+1+top,cmp);
    for (i=1;i<=top;i++){
        sum+=b[i].y;
        if (sum >= n)   return 1;
    }
    return 0;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d",&n);
    for (i=1;i<=n;i++)  scanf("%lf%lf",&a[i].x,&a[i].y);
    low=0;  high=40000;
    while (Fabs(low-high)!=0){
        tot++;
        mid=(low+high)/2;
        if (Check(mid)) Ans=mid,high=mid;
        else low=mid;
    }
    //cout<<tot<<endl;
    printf("%.8lf\n",Ans);
    return 0;
}

[C] C语言IDE

题意

大模拟

题解

有点毒瘤,懒得补

代码

NULL

[D] 牛牛与牛妹的约会

题意

给出x轴上的起点和终点,一个人站在起点处.他可以以1m/s的速度前进,或者花费1s,从x瞬移到x^{\frac{1}{3}}.求最快几秒到达终点.

题解

贪心暴力都行.瞬移用的次数一定不多,直接枚举更方便.

注:pow(x,y)当x是负数,y是小数的时候会出错.被这个坑到自闭.

代码

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define IL inline
#define EPS 1e-8
using namespace std;

int T,i;
double a,b,Ans,l,t,u=1.0/3.0;

IL double Abs(double x){return (x<0)?-x:x;}
IL double Min(double a,double b){return (a<b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        scanf("%lf%lf",&a,&b);
        Ans=Abs(a-b);
        for (i=1;i<=10;i++){
            a=cbrt(a);
            Ans=Min(Ans,(double)i+Abs(a-b));
        }
        printf("%.9lf",Ans);
        if (T)  puts("");
    }
    return 0;
}

[E] Enjoy the game

题意

两个人轮流从牌堆里拿牌,第一次不能全部拿完,之后的每一次拿的数量不能超过上一次.谁没牌可拿谁就输.给出初始牌堆数量,求先手是否必胜.

题解

博弈论.

当数量是2^{n}时先手必输,否则必胜.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL n,i;

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%lld",&n);
    for (i=1;i<=60;i++)
        if (((LL)1<<i) == n){
            puts("Alice");
            return 0;
        }
    puts("Bob");
    return 0;
}

[F] 碎碎念

题意

一个队伍在做题.当他们A了一道题后,一个人会大声呼喊1次.当出现Rejected Submit时大声呼喊k次.已知这支队伍在RJ的下一次提交的结果一定是AC,且他们呼喊次数的区间为[l,r].求他们提交序列的可能数.

题解

根据题意,把RJ和AC进行绑定,视为两次提交共呼喊了k+1次.最后一次提交是RJ的情况单独考虑.

设f[i]表示呼喊次数为i的提交序列可能总数.有如下转移方程:

f[i]=f[i-1]+f[i-k-1]

表示在i-1次提交的最后多了一次AC,或是在i-k-1次提交后多了一次RJ+AC.最后一次提交为RJ的情况显然可以用f[n-k]来表示.[l,r]长度的呼喊次数可以拆分成前缀和的性质.预处理完成后就可以O(1)回答了.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
#define N 100010
#define MOD 1000000007
using namespace std;

LL T,i,l,r,k;
LL c[N],f[N],s[N],inv[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

IL void Ready(){
    reg LL i=0,j=0,t=1,p=0,cnt=0;
/*  c[0]=c[1]=1;
    for (i=2;i<=100000;i++) c[i]=(c[i-1]*i)%MOD;
    f[0]=1; f[1]=1; inv[1]=1;
    for (i=2;i<=100000;i++) inv[i]=Mi(i,MOD-2);
    for (i=2;i<=100000;i++){
        t=(t*(i-1+p))%MOD;
        t=(t*inv[i])%MOD;
        f[i]=(f[i-1]*t)%MOD;
        f[i]=(f[i]*Mi(i,p)%MOD);
        if ((i%(k+1)) == 0){
            p++;    f[i]++;
        }
    }
    for (i=1;i<=10;i++) cout<<f[i]<<endl;
    for (i=1;i<=100000;i++) s[i]=(s[i-1]+f[i])%MOD;*/
    f[0]=1;
    for (i=1;i<=100000;i++){
        f[i]=f[i-1];
        if (i>=k+1) f[i]=(f[i]+f[i-k-1])%MOD;
    }
    for (i=0;i<=100000;i++) s[i]=(s[i-1]+f[i])%MOD;
}

IL LL Cal(LL x){
    LL sum=0;
    if (x<0)    return 0;
    sum=s[x];
    if (x>=k)   sum=(sum+s[x-k])%MOD;
    return sum%MOD;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    k=read();   T=read();
    Ready();
    while (T--){
        l=read();   r=read();
        printf("%lld\n",(Cal(r)-Cal(l-1)+MOD)%MOD);
    }
    return 0;
}

[G] 街机争霸

题意

毒瘤模拟

题解

坑

代码

坑

[H] hash

题意

给出一个哈希函数:

const int LEN = 6;
int mod;
int Hash(char str[])
{
    int res = 0;
    for (int i = 0; i < LEN; i++)
    {
        res = (res * 26 + str[i] - 'a') % mod; 
    }
    return res;
}

给出一个长度为6的字符串和mod,求hash值和这个字符串相等的长度也为6的字符串.要求这个字符串的字典序比给出的大,且尽可能的小.

题解

把字符串视为26进制的数.转化为数之后加上mod再转化回去即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL i,mod;
char c[10];
LL s[10];

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    while (~scanf("%s",c+1)){
        scanf("%lld",&mod);
        s[0]=0;
        for (i=1;i<=6;i++)  s[i]=c[i]-'a';
        s[6]+=mod;
        for (i=6;i;i--)
            if (s[i]>=26)   s[i-1]+=s[i]/26,s[i]%=26;
        if (s[0]>0) puts("-1");
        else {
            for (i=1;i<=6;i++)  putchar(s[i]+'a');
            puts("");
        }
    }
    return 0;
}

[I] I题是个签到题

题意

给出一些题目以及这些题目的通过人数.判断I题的通过人数是否超过了总人数的80\%或者是通过人数第三多的题目.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 10010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,sum;
double s,s2;
int a[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)  scanf("%d",&a[i]);
    for (i=1;i<=n;i++)  sum+=a[i];
    s=(double)m*0.8;
    if (a[9]>=s-0.0001) {
        puts("Yes");
        return 0;
    }
    sum=0;
    for (i=1;i<=n;i++)  
        if (a[i]>a[9])  sum++;
    if (sum<=2) puts("Yes");
    else puts("No");
    return 0;
}

[J] 牛牛战队的秀场

题意

给出半径为r的圆上的一个正n边形,两个人分别站在两个顶点上.每次移动只能沿着多边形的边走.求两个人要相遇所走过的路程.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define PI 3.14159265358979323846
#define INF 0x3f3f3f3f
using namespace std;

int i,x,y,n;
double r,l,Ans;

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d%lf",&n,&r);
    scanf("%d%d",&x,&y);
    if (x==y){
        puts("0.0000");
        return 0;
    }
    x=Min(Abs(x-y),n-Abs(x-y));
    l=cos(2*PI/(double)n);
    l=2*r*r*(1-l);
    l=sqrt(l);
    Ans=l*(double)x;
    printf("%.10lf\n",Ans);
    return 0;
}

总结

寒假基础训练第五场.

感觉是这个系列比赛中质量最低的一场了.

出题人好像很偏爱浮点数,出了n多道浮点数计算相关的问题,卡常,卡一些做法,题目描述各种不清晰,比赛途中疯狂改题面,还有所谓的不大不小的模拟,简直无力吐槽了.

唯一的收获可能是学了个cbrt函数吧.

希望下一场能够正常一些.