第十五届蓝桥杯JavaB组省赛题解

第十五届蓝桥杯JavaB组省赛题解

蓝桥杯2024年第十五届省赛真题-分布式队列 - C语言网 (dotcpp.com)

阅读理解＋模拟

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n;
cin >> n;
vector<int> list[n];
string cz;
int element, follower_id;
while (cin >> cz) {
    if (cz == "add") {
        cin >> element;
        list[0].push_back(element);
    } else if (cz == "sync") {
        cin >> follower_id;
        if (list[0].size() != list[follower_id].size()) {
            list[follower_id].push_back(list[0][list[follower_id].size()]);
        }
    } else if (cz == "query") {
        int min_size = list[0].size();
        for (int i = 1; i < n; i++) {
            min_size = min(min_size, (int)list[i].size());
        }
        cout << min_size << endl;
    }
}

return 0;
}

蓝桥杯2024年第十五届省赛真题-食堂 - C语言网 (dotcpp.com)

分类讨论+贪心

因为有3人寝室，而桌子有4和6人桌，如果让3人寝室上4人桌的话这样就会空出一个位置，而其他4人2人寝室都可以凑满。

所以我们这只要讨论3人寝室，能先放6人桌就先放6人桌。剩下的2人寝和4人寝室，先放满6人桌，再放4人桌。（不过这个分类讨论情况真的太多了，写了2小时都没写出来脑子晕了就不贴代码了）

蓝桥杯2024年第十五届省赛真题-最优分组 - C语言网 (dotcpp.com)

思路很简单，我们只要枚举每个组有多少宠物就行了。

假设每个组有$x$个宠物。一开始让一个组内所有宠物共同使用一个试剂，也就是需要$n/x$个试剂

再假设每个组里患病的宠物是$x\ast p$，而总的患病数量是$n\ast x\ast p$，检测这些患病的宠物也需要$n\ast x\ast p$个试剂

再加起来就是按照$x$分组所需要的试剂，答案只用取个$min$即可

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=210000,INF=0x3f3f3f3f;
typedef pair<int,int>pii;
int a[100];

void solve()
{
   int n;
   double p;
   cin>>n>>p;
   double res=0x3f3f3f3f;
   int ans=0;
   for(int i=1;i<=n;i++)
   {
   	   if(n%i==0)
   	   {
   	   	 double t=n*p*i+n/i;
   	   	 if(res>=t)
   	   	 {
   	   	 	ans=i;
   	   	 	res=t;
   	   	 }
   	   }
   }
   cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

蓝桥杯2024年第十五届省赛真题-星际旅行 - C语言网 (dotcpp.com)

这题需要先分析看到边和点很小，询问很大，第一反应是需要预处理。答案是要求$x$走$y$步最多能走几个星球，所以我们可以贪心的想，我们对每个点都走最短路，那么走的星球数量肯定是最多的，所以这时候我们可以把$dis{t}_{i,j}$定义为从$i$开始走到$j$的最短距离，类似于多源汇最短路，第一时间想到的是$Floyd$不过时间复杂度是$O(n^3)$会tle，这时候我们就需要用$dijkstra$跑完任意点时间复杂度是$O(n^{2}log(m)+qn)$

这里的$n$很小所以能过。我们预处理完$dist$数组我们遍历所有以$x$为起点权值小于等于$y$的有几个累加起来就是答案

int m,n,q;
vector<int>e[N];
vector<int>d[N];
bool st[N];

vector<int> dij(int u)
{
	memset(st,0,sizeof st);
    vector<int>dist(n+10,0x3f3f3f3f);
	priority_queue<pii,vector<pii>,greater<pii>>q;
	q.push({0,u});
	dist[u]=0;
	while(q.size())
	{
		auto t=q.top();
		q.pop();
		if(st[t.y])continue;
		st[t.y]=1;
		for(auto v:e[t.y])
		{
		    if(dist[v]>t.x+1)
		    {
		    	dist[v]=t.x+1;
		    	q.push({dist[v],v});
		    }
		}
	}

	return dist;
}

void solve()
{
	memset(st,0,sizeof st);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
	    e[x].push_back(y);
	    e[y].push_back(x);
	}
    for(int i=1;i<=n;i++)
    {
    	  d[i]=dij(i);
    }
    int res=0;
    for(int i=1;i<=q;i++)
    {
    	int x,y;
    	cin>>x>>y;
        for(int j=1;j<=n;j++)
          if(d[x][j]<=y)
          {
          	res++;
          }
       // cout<<res<<endl;
    }
    double ans=(res*1.0)/q;
    printf("%.2lf\n",ans);
}