19年第十届蓝桥杯国赛C/C++ B组

蓝桥杯 3 Minutes

我怎么这么菜啊？我到底在干啥啊？
题都没读清楚啊！能做的写炸了啊！

A

题意

求满足2019 < x < y且2019^2,x^2,y^2构成等差数列的x,y，使得x+y最小，输出最小的x+y。

思路

从小到大枚举x，计算y并检验。
答案：7020

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n=2019;
    for (int x=n+1;;x++) {
        int y=(int)sqrt(2*x*x-n*n+0.5);
        if (y*y==2*x*x+-n*n) {
            cout<<x+y<<endl;
            break;
        }
    }
    return 0;
}

B

题意

把2019分解成若干个不重复的质数之和，求方案数。

思路

预处理2019以内的质数，01背包求方案数。
答案：55965365465060

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int MAXN=(int)3e3+10;
int prime[MAXN],vis[MAXN];
ll dp[MAXN];

void init(int n);
ll solve(int n,int v);

int main()
{
    int n=2019;
    init(n);
    ll ans=solve(prime[0],n);
    cout<<ans<<endl;
    return 0;
}

void init(int n)
{
    int m=0;
    for (int i=2;i<=n;i++) {
        if (vis[i]==0) {
            prime[++m]=i;
        }
        for (int j=i;i*j<=n;j++) {
            vis[i*j]=1;
        }
    }
    prime[0]=m;
}

ll solve(int n,int v)
{
    dp[0]=1;
    for (int i=1;i<=n;i++) {
        for (int j=v;j>=prime[i];j--) {
            dp[j]+=dp[j-prime[i]];
        }
    }
    return dp[v];
}

C

D

题意

求约数个数为100的最正整数n。

思路

枚举n，暴力计算约数个数并检验。
答案：45360

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    for (int n=2;;n++) {
        int sum=0;
        for (int d=1;d*d<=n;d++) {
            if (n%d==0) {
                if (d==n/d) {
                    sum++;
                } else {
                    sum+=2;
                }
            }
        }
        if (sum==100) {
            cout<<n<<endl;
            break;
        }
    }
    return 0;
}

E

题意

6*6的网格图，问满足下列要求的路径有多少条（路线相同但访问顺序不同算作不同的路径）：
1、从左上角出发，最终回到左上角。
2、除起点外，任意一点最多经过一次。
3、路径长度不大于12。

思路

dfs暴搜，注意起点会访问两次，需要特别处理。
答案：206

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=10;
const int DIR[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int vis[MAXN][MAXN];
int n=6,cnt=0;

void dfs(int x,int y,int step);
bool chk(int x,int y);

int main()
{
    dfs(0,0,0);
    cout<<cnt<<endl;
    return 0;
}

void dfs(int x,int y,int step)
{
    if (step>12) {
        return;
    }
    if (x==0 && y==0) {
        //step=0,the start
        //step=2,into the beside and back right now
        if (step!=0) {
            if (step!=2) {
                cnt++;
            }
            return;
        }
    }

    for (int d=0;d<4;d++) {
        int xt=x+DIR[d][0],yt=y+DIR[d][1];
        if (chk(xt,yt) && vis[xt][yt]==0) {
            vis[xt][yt]=1;
            dfs(xt,yt,step+1);
            vis[xt][yt]=0;
        }
    }
}

bool chk(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<n;
}

I

题意

长度为n的序列A，初始值均为0。有m次操作，分为以下两种：
1、C p x：把A[p]的值改为x.
2、Q l r： 询问区间[l,r] 的第8大的数，不存在输出0。

思路

经典的带修改区间第k小（大）问题，可以用树状数组＋主席树（可持久化权值线段树）来做。
但此题k为给定值8，非常小 ，所以可以考虑直接用线段树维护区间内最大的8个数。

代码

#include<bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
const int MAXN=(int)1e5+10;
struct SegmentTree {
    int l,r;
    int val[8];
} t[MAXN*4];
int temp[20],add[20];

void build(int p,int l,int r);
void update(int p);
void change(int p,int x,int v);
VI query(int p,int l,int r);


int main()
{
    int n,m;
    cin>>n>>m;
    build(1,1,n);
    while (m--) {
        char opt[4];
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if (opt[0]=='C') {
            change(1,x,y);
        } else {
            if (y-x+1<8) {
                printf("0\n");
            } else {
                VI ans=query(1,x,y);
                printf("%d\n",ans[7]);
            }
        }
    }
    return 0;
}

void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if (l==r) {
        return;
    }

    int mid=(l+r)/2,ls=p*2,rs=ls+1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

void update(int p)
{
    int ls=p*2,rs=ls+1;
    for (int i=0;i<8;i++) {
        temp[i]=t[ls].val[i];
        temp[i+8]=t[rs].val[i];
    }
    sort(temp,temp+16,greater<int>());
    for (int i=0;i<8;i++) {
        t[p].val[i]=temp[i];
    }
}

void change(int p,int x,int v)
{
    if (t[p].l==t[p].r) {
        t[p].val[0]=v;
        return;
    }

    int mid=(t[p].l+t[p].r)/2,ls=p*2,rs=ls+1;
    if (x<=mid) {
        change(ls,x,v);
    } else {
        change(rs,x,v);
    }
    update(p);
}

VI query(int p,int l,int r)
{
    if (l<=t[p].l && t[p].r<=r) {
        VI ans(8);
        for (int i=0;i<8;i++) {
            ans[i]=t[p].val[i];
        }
        return ans;
    }

    
    int mid=(t[p].l+t[p].r)/2,ls=p*2,rs=ls+1,len=0;
    if (l<=mid) {
        VI lv=query(ls,l,r);
        for (int i=0;i<8;i++) {
            add[len+i]=lv[i];
        }
        len+=8;
    }
    if (mid<r) {
        VI rv=query(rs,l,r);
        for (int i=0;i<8;i++) {
            add[len+i]=rv[i];
        }
        len+=8;
    }

    sort(add,add+len,greater<int>());
    VI ans(8);
    for (int i=0;i<8;i++) {
        ans[i]=add[i];
    }
    return ans;
}
未知 的头像

发布者：风竹曦

已发布

留下评论