首页 > 编程语言 >2023年第十四届蓝桥杯大赛软件类省赛Java大学B组真题

2023年第十四届蓝桥杯大赛软件类省赛Java大学B组真题

时间:2024-03-07 23:36:01浏览次数:36  
标签:组真题 Java int ll nullptr cin 蓝桥 const dp

2023年第十四届蓝桥杯大赛软件类省赛Java大学B组真题

C.数组分割

思路:因为最后要是分为2组偶数。由于偶数+偶数=偶数,奇数+奇数=偶数。那么我们的奇数个数一定要是偶数个。如果奇数个数为奇数个那直接就不行了,答案是0。如果奇数的个数是偶数的话,假设偶数n个,奇数m个。\(C_{n}^{0}+C_{n}^{1}+C_{n}^{2}...+C_{n}^{n} = 2^n\),\(C_{m}^{0}+C_{m}^{2}+C_{m}^{3}...+C_{m}^{m} = \dfrac{2^m}{2}(偶数次+奇数次=2^m,那么偶数次就是\dfrac{2^n}{2})\)。那么最后答案就是\(2^n*2^{m-1} = 2^{n+m-1}\)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;

        ll odd = 0,even = 0;
        for(int i = 1;i <= n; i++)
        {
            ll x; cin>>x;
            if(x % 2)odd++;
            else even++;
        }
        if(odd % 2)cout<<0<<"\n";
        else{
            ll ans = 1;
            if(odd)
                ans = qmi(2ll,odd-1,mod);
            ans %= mod;
            ans *= qmi(2ll,even,mod);
            ans %= mod;
            cout<<ans<<"\n";
        }
        
    }
    return 0;
}

D.矩形总面积

小模拟+容斥一下

对于重叠部分:

\(sx = max(x1,x3),sy = \max(y1,y3)\)左下角左边取max
\(ex = min(x2,x4),ey = \min(y2,y4)\)右上角左边取min

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll x1,y1,x2,y2,x3,y3,x4,y4;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    //(x1,y1) (x2,y2) (x3,y3) (x4,y4)
    ll s1 = (x2-x1)*(y2-y1);
    ll s2 = (x4-x3)*(y4-y3);

    ll sx = max(x1,x3),sy = max(y1,y3);
    ll ex = min(x2,x4),ey = min(y2,y4);

    if(sx < ex && sy < ey)
        cout<<s1+s2-(ex-sx)*(ey-sy)<<"\n";
    else cout<<s1+s2<<"\n";

    return 0;
}

E.蜗牛

是一个\(dp\),啊细节部分一开始写的有问题,debug好一会TAT.

思路:定义状态\(dp[i][0/1]\)。

\(dp[i][0]\)表示到第\(i\)个杆子是没有通过传送。

\(dp[i][1]\)表示到第\(i\)个杆子是通过传送到的。

注意,一开始我们在\((0,0)\),而起点到第一个杆子是没有传送的,初始化为:\(dp[1][0] = x[1],dp[1][1] = x[1]+\dfrac{a[1].h1}{0.7}\)。

由于第一个到第二个是特殊的。我们需要把第二个也手动初始化。

为什么第二个是特殊的呢?因为第一个到第二个的传送不需要代价,而对于别的比如第二个到第三个,需要先爬到传送点。

\(dp[2][0] = \min(dp[1][0]+(x[2]-x[1]),dp[1][1]+a[1].h1/1.3+(x[2]-x[1]))\)

$dp[2][1] = \min(dp[1][0]+a[1].h1/0.7,dp[1][1]) $

考虑完特殊的,其他的就很简单啦。具体的见代码。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int x[N];
struct node
{
    int h1,h2;
}a[N];
double dp[N][2];
int main()
{
    //ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>x[i];
    //up 0.7 ,down 1.3
    //第i个的h1高度传送门到达i+1的h2高度
    for(int i = 1;i < n; i++)
        cin>>a[i].h1>>a[i].h2;
    dp[1][0] = x[1],dp[1][1] = x[1]+a[1].h1/0.7;
    dp[2][0] = min(dp[1][0]+(x[2]-x[1]),dp[1][1]+a[1].h1/1.3+(x[2]-x[1]));
    dp[2][1] = min(dp[1][0]+a[1].h1/0.7,dp[1][1]);
    for(int i = 3;i <= n; i++)
    {
        dp[i][0] = min(dp[i-1][0]+(x[i]-x[i-1]),dp[i-1][1]+(a[i-2].h2)/1.3+(x[i]-x[i-1]));

        if(a[i-2].h2 < a[i-1].h1)
            dp[i][1] =dp[i-1][1]+(a[i-1].h1-a[i-2].h2)/0.7;
        else dp[i][1] = dp[i-1][1]+(a[i-2].h2-a[i-1].h1)/1.3;
        dp[i][1] = min(dp[i][1],dp[i-1][0]+a[i-1].h1/0.7);
    }

    printf("%.2lf",min(dp[n][0],dp[n][1]+a[n-1].h2/1.3));
    return 0;
}

F.合并区域

啊这个我一开始想简单了,以为只有一个地方可以进行合并,但发现可以有多个....写起来很恶心,要不断建图,然后dfs

G.买二赠一

贪心+单调队列

先排序,从大到小的买。当买了两个,较小的那个的价格的一半放入单调队列。每次买之前check一下能否使用免费,能用就用。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;

int a[N];

bool cmp(int a,int b)
{
    return a > b;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    sort(a+1,a+1+n,cmp);

    int l = 1;
    ll ans = 0;
    priority_queue<int>q;

    auto check_can_free = [&](){
        while(!q.empty() && l <= n)
        {
            int t = q.top();
            if(t >= a[l]){
                q.pop();
                l++;
            }else break;
            
        }
    };
    while(l <= n)
    {
        check_can_free();
        if(l<=n)
        {
            ans += a[l];
            l++;
        }
        check_can_free();
        if(l<=n)
        {
            ans += a[l];
            q.push(a[l]/2);
            l++;
        }
    }

    cout<<ans<<"\n";
    return 0;
}

I.最大开支

挺经典的一个题目,对于这类题,我们考虑,对于某一个项目,如果x个人参加价格就是\(cost1 = x*(kx+b)\),如果\(x+1\)个人参加就是\(cost2 = (x+1)*(k(x+1)+b)\)。

我们对二者做差就是\(cost2-cost1 = 2kx+k+b\)。这便是对于该项目多增加一人的价格的增量。

我们用priority_queue来实现(自定义排序),每次把增量最大的取出来,如果增量\(>0\)说明还可以往该项目加入,否则的话就结束。

自定义排序模板:

struct cmp{
   bool operator()(vector<int>&a,vector<int>&b){
       return a[0]>b[0]; 
   }
};
priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆

代码:

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll get(ll x,ll k,ll b)
{
    return x*max(0ll,k*x+b);
}

ll add(int x,int k,int b)
{
    //return get(x+1,k,b)-get(x,k,b);
    return 2ll*k*x+k+b;
}


struct Node
{
    int num,k,b;
    Node(int _num,int _k,int _b){num = _num;k = _k;b = _b;};
};


struct cmp{
   bool operator()(Node& a,Node& b){
       ll cost1 = get(a.num+1,a.k,a.b)-get(a.num,a.k,a.b);
       ll cost2 = get(b.num+1,b.k,b.b)-get(b.num,b.k,b.b);
       return cost1 < cost2;
   }
};
priority_queue<Node,vector<Node>,cmp> q;


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int n,m; cin>>n>>m;
    for(int i = 1;i <= m; i++)
    {
        ll k,b; cin>>k>>b;
        q.push(Node(0ll,k,b));
    }
    //max(0,kx+b)
    //need = x*(kx+b) = kx^2 + bx
    //mx = -(b/2*k) or -(b/k*k+1)

    //(k*(x+1)+b)*(x+1)-(kx+b)*x
    //2kx+k+b

    for(int i = 1;i <= n; i++)
    {
        Node t = q.top(); q.pop();
        int num = t.num,k = t.k,b = t.b;
        ll cost = add(num,k,b);
        //cout<<"num = "<<num<<"k = "<<k<<" b = "<<b<<" cost = "<<cost<<"\n";

        if(cost<=0)
        {
            q.push(t);
            break;
        }else{
            t.num++;
            q.push(t);
        }
    }    

    ll ans = 0;
    while(!q.empty())
    {
        Node t = q.top(); q.pop();
        int num = t.num,k = t.k,b = t.b;
        ans += get(num,k,b);
    }
    cout<<ans<<"\n";
    return 0;
}

标签:组真题,Java,int,ll,nullptr,cin,蓝桥,const,dp
From: https://www.cnblogs.com/nannandbk/p/18060022

相关文章

  • 卡码java基础课 | 11.句子缩写
    学习内容:字符大小的比较、字符运算、字符拼接ASCII码和Unicode码字符大小写转换字符串trim()方法StringBuilder的使用重点归纳:字符编码:Ascii码和Unicode编码。Ascii早,用7位就能表示128个字符;Unicode包含几乎所有世界上的字符,utf-8、utf-16、utf-32等用不同的字节来表示(8、1......
  • JavaWeb之Java Servlet学习笔记
    JavaWeb学习笔记,主要是讲JavaServle,很适合Java开发网站的入门学习。(以课程进度为目录)第四周Web课.jsp中删除共性代码(html、body)————.java文件能相对的简洁taglib指令(标签库)动作元素action——element:包含include动态包含:在运行时才引入文件,代码也会动态引入,时间和......
  • Java基础 语法笔记
    大二学习Java语法时,上课写的部分笔记,可能并不完整,仅用以作纪念。数组、集合、字符串(第六课)目录数组、集合、字符串(第六课)数组集合类Collection接口:泛型:List:ArrayList:LinkedList类SetHashSet类TreeSet类MapLterator接口Vector类Collections类查找、替换操作复制StringtoString()......
  • Day 2 java
    类是变量的蓝图对象本身已知的事物称为实例变量,对象可以执行的动作称为方法;两种变量:primitive主数据和引用1.事实上没有对象变量这样的东西,只有引用(reference)到对象的变量;2.对象引用变量保存的是存取对象的方法;3.这种变量是一种类似指针的东西(引用变量是一个遥控器);4.数组......
  • 每天一道蓝桥杯Day1 分考场(dfs+结论)
    题意:这道题第一眼咋看以为是图论,但是要抽象成图论的话就会变成:给定一个无向图,要求对点染色,使得任意相邻点之间颜色不能相同,试问最少的颜色数是多少?发现转化成图论后好像也没有什么图论算法可以解决,这个转化不是很有效。往往不知道怎么下手时可以试着考虑极端情况,比如考虑上界......
  • java jndi
    JNDI(JavaNamingandDirectoryInterface,Java命名和目录接口)是SUN公司提供的一种标准的Java命名系统接口,JNDI提供统一的客户端API,通过不同的访问提供者接口JNDI服务供应接口(SPI)的实现,由管理者将JNDIAPI映射为特定的命名服务和目录系统,使得Java应用程序可以和这些命名服务和......
  • Java 日期和时间 API:实用技巧与示例 - 轻松处理日期和时间
    Java用户输入(Scanner)简介Scanner类用于获取用户输入,它位于java.util包中。使用Scanner类要使用Scanner类,请执行以下步骤:导入java.util.Scanner包。创建一个Scanner对象,并将其初始化为System.in。使用Scanner对象的方法读取用户输入。示例importjava.ut......
  • P8686 [蓝桥杯 2019 省 A] 修改数组
    备赛蓝桥杯和icpc的习题:一道并查集的题目>#include<iostream>>#include<vector>>#include<algorithm>>#include<math.h>>#include<string>>#include<string.h>>#include<iomanip>>#include<map>&g......
  • java基础 韩顺平老师的 面向对象(基础) 自己记的部分笔记
    194,对象内存布局基本数据类型放在堆里面,字符串类型放在方法区。栈:一般存放基本数据类型(局部变量)堆:存放对象(Catcat,数组等)方法区:常量池(常量,比如字符串),类加载信息 196,属性注意细节1,属性可以是基本数据类型,也可以是引用类型(对象,数组)2,属性的定义语法同变量,示例:访问修饰符属......
  • Java基础 --- 方法
    方法什么是方法方法(method)是程序中最小的执行单元。实际应用当中,将重复的方法打包提高代码的复用性提高代码可维持性总结:什么是方法?方法是程序中最小的执行单元。实际开发中,什么时候用到方法?重复的代码、具有独立功能的代码可以抽取到方法中。实际开发......