第十四届蓝桥杯（C/C++ 大学B组）

2024-03-22 12:50:03
开发
18

试题 A：日期统计

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

const int numbers[100] = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5,
                          8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5,
                          1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2,
                          8, 5, 0, 2, 5, 3, 3};
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() { //235
    int ans = 0;
    char ss[10];
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= days[i]; j++) {
            string str = "2023";
            if (i < 10)str += "0";
            sprintf(ss,"%d",i);
            str += ss;
            if (j < 10)str += "0";
            sprintf(ss,"%d",j);
            str += ss;
            int k = 0;
            for (int l = 0; l < 100 && k < 8; l++) {
                if (numbers[l] == str[k] - '0') k++;
            }
            if (k >= 8) ans++;
        }
    }
    cout << ans << endl;
    
    return 0;
}

试题 B：01 串的熵

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

int n = 23333333;
double d = 11625907.5798;

int main()
{
	for(int i = 1,j = n - 1;i <= n;i++,j--)
	{
		double p1 = -1 * 1.0 * i * i / n * log2(1.0 * i / n);
		double p2 = -1 * 1.0 * j * j / n * log2(1.0 * j / n);
		if(fabs(p1 + p2 - d) < 1e-4) cout<<i<<endl;
	}
	
	return 0;
}

试题 C：冶炼金属

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

typedef long long ll;
ll N,A,B,most=1e9,least=0;

int main()
{
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	
	cin>>N;
	for(int i = 0;i < N;i++)
	{
		cin>>A>>B;
		most = min(most,A / B);
		least = max(least, A / (B + 1) + 1);
	}
	cout<<least<<" "<<most<<endl;
	return 0;
}

试题 D：飞机降落

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

struct plane
{
	//到达时间，可持续时间，降落所需时间，最晚降落时间 
	int reach;
	int sustain;
	int need;
	int latest;
};

const int N = 1e5;
struct plane data[N];
int timeline = 0;
int flag;

//所有飞机按顺序降落，能否安全降落 
bool isSafe(int n)
{
	timeline = 0;
	for(int i = 0;i < n;i++)
	{
		//当前飞机最晚降落时间已过，无法成功降落 
		if(data[i].latest < timeline) return false;
		//每一辆飞机降落所需要的时间 
		else timeline += data[i].need;
	}
	flag = 1;
	return true;
}
//全排列
void allCase(int n,int len)
{
	if(n == 1) isSafe(len);
	else
	{
		for(int i = 0;i < n;i++)
		{
			swap(data[i],data[n-1]);
			allCase(n-1,len);
			swap(data[i],data[n-1]);
		}	
	}	
} 

int main()
{
	int n,m;
	cin>>n;
	for(int i = 0;i < n;i++)
	{
		cin>>m;
		flag = 0;
		for(int j = 0;j < m;j++)
		{
			//到达时间，可持续时间，降落所需时间，最晚降落时间 
			cin>>data[j].reach>>data[j].sustain>>data[j].need;
			data[j].latest = data[j].reach + data[j].sustain; 
		}
		allCase(m,m);
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	return 0;
}

试题 E：接龙数列

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

const int d = 1e5+5;

int dp[d];

int main()
{
	int n,m=0;
	string s;
	cin>>n;
	
	for(int i = 0;i < n;i++)
	{
		cin>>s;
		int front = s[0];
		int rear = s[s.length() - 1];
		//dp[rear]:以rear数字结尾的长度
		//dp[front]:以front数字结尾的长度
		//dp[front] + 1:当前数字以front开头，所以长度+1 
		dp[rear] = max(dp[rear],dp[front] + 1);
		m = max(m,dp[rear]);
	}
	cout<<n-m<<endl;
	return 0;
}

试题 F：岛屿个数

【输出格式】

对于每组数据，输出一行，包含一个整数表示答案。

【样例输入】

【样例输出】

1
3

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

const int N = 60;
int plat[N][N];
bool visited[N][N];
int m,n,res;
int dx[] = {-1,1,0,0},
    dy[] = {0,0,-1,1};

void dfs_land(int u,int v)
{
	//某个陆地上下左右4个方位内有陆地才算是连通 
	visited[u][v] = true;
	int x,y;
	for(int i = 0;i < 4;i++)
	{
	 	x = u + dx[i];
	 	y = v + dy[i];
	 	if(visited[x][y] || plat[x][y] == 0) continue;
	 	dfs_land(x,y);
	}
}

void dfs_sea(int u,int v)
{
	//某个海水顶点的8个方向内有海水算是连通,8个方位 
	visited[u][v] = true;
	int x,y;
	for(int i = -1;i <= 1;i++)
	{
		for(int j = -1;j <= 1;j++)
		{
			x = u + i;
			y = v + j;
			if(visited[x][y] || x < 0 || x > m + 1 || y < 0 || y > n + 1) continue;
			if(plat[x][y] == 0) dfs_sea(x,y);
			else 
			{
				dfs_land(x,y);
				res++;
			}
		}
	}
}

int main()
{
	int t;
	cin>>t;
	char c;
	for(int i = 0;i < t;i++)
	{
		memset(plat, 0, sizeof plat);
		memset(visited, false, sizeof visited);
		cin>>m>>n;
		res = 0;
		//地图外的方格全部视为海， 
		//与地图外的海连通的海都视为外海，接触到了外海的岛屿， 就一定不是其它岛屿的子岛。
		for(int j = 1;j <= m;j++)
		{
			for(int k = 1;k <= n;k++)
			{
				cin>>c;
				plat[j][k] = c - '0';
			}
		}
		//dfs遍历外海每一个方格， 
		//若与外海方格相邻的岛屿未被遍历过，那么这就是一个新的岛屿， 再用一个dfs去遍历这个岛。
		dfs_sea(0,0);
		cout<<res<<endl;
	}
	return 0;
}

试题 G：子串简写

【样例输入】

4
abababdb a b

【样例输出】

【方法一】

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

int main()
{
	int K,res=0;
	string s;
	char a,b;
	cin>>K>>s>>a>>b;
	int len = s.length();
	for(int i = 0;i < len;i++)
	{
		if(s[i] == a)
			for(int j = i + K - 1;j < len;j++)
				if(s[j] == b) res++;
	}
	cout<<res<<endl;
	return 0;
}

【方法二】

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

const int n = 5 * 1e5 + 10;
int dp[n];

int main()
{
	int K,res=0;
	string s;
	char a,b;
	cin>>K>>s>>a>>b;
	int len = s.length();
	int i;
	for(i = 1;i <= len;i++)
	{
		if(s[i-1] == a) dp[i] = 1;
		dp[i] += dp[i - 1];
	}
	while(--i >= K)
	{
		if(s[i-1] == b) res += dp[i - K + 1];
	}
	cout<<res<<endl;
	return 0;
}

试题 H：整数删除

【样例输入】

5 3
1 4 2 8 7

【样例输出】

17 7

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

typedef long long ll;
const int n = 5 * 1e5 + 10;
int arr[n],l[n],r[n];

void del(int i)
{
	//左元素的右指针，指向当前元素的右指针 
	r[l[i]] = r[i];
	//右元素的左指针，指向当前元素的左指针
	l[r[i]] = l[i];
	//更新左右元素的值
	arr[l[i]] += arr[i];
	arr[r[i]] += arr[i]; 
}

int main()
{
	int N,K;
	//小顶堆 
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
	pair<ll, int> p;
	cin>>N>>K;
	l[0] = 1;
	r[n+1] = n;
	for(int i = 1;i <= N;i++)
	{
		cin>>arr[i];
		l[i] = i - 1;
		r[i] = i + 1;
		q.push({arr[i],i});
	}
	while(K--)
	{
		p = q.top();
		q.pop();
		//小顶堆的数据跟实际值不一致，需要更新小顶堆 
		if(p.first != arr[p.second]) 
		{
			q.push({arr[p.second], p.second});
			K++;
		}
		else del(p.second);
	}
	int head = r[0];
	while(head != N + 1)
	{
		cout<<arr[head]<<" ";
		head = r[head];
	}
	
	return 0;
}

试题 I：景区导游（超时）

【样例输入】

【样例输出】

10 7 13 14

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

const int MAX = 1e5 + 5;
//邻接点 
vector<pair<int, int> > adj[MAX];
//x到y的距离
map<pair<int, int>, int> st; 
int a[MAX];

bool dfs(int start,int current,int father,int end, int sum)
{
	//cout<<start<<"   "<<end<<endl;
	//当前结点就是终点 
	if(current == end)
	{
		st[{start,end}] = sum;
		st[{end,start}] = sum;
		return true;
	}
	//接着找邻接点 
	for(int i = 0;i < adj[current].size();i++)
	{
		int son = adj[current][i].first;
		//如果这个邻接点是当前结点的父节点，就会陷入循环 
		if(son == father) continue;
		//当前结点到下一个临界点的距离 
		int w = adj[current][i].second;
		//注意这里的参数 当前结点已是父节点，邻接点是当前结点 
		if(dfs(start,son,current,end,sum + w)) return true;
	}
	return false;
}

int main()
{
	int N, K;
    cin >> N >> K;
    
    for(int i = 0;i < N - 1;i++)
    {
    	int u,v,t; 
    	cin>>u>>v>>t;
    	adj[u].push_back({v,t});
    	adj[v].push_back({u,t});
	}
    
    for(int i = 0;i < K;i++)
    	cin>>a[i];
    	
    int ans = 0;
    //求出完整路线的时间
	for(int i = 0;i < K - 1;i++)
	{
		dfs(a[i],a[i],-1,a[i+1],0);
		ans += st[{a[i],a[i+1]}];
		//cout<<ans<<endl;
	} 
	//依次去除每个顶点
	for(int i = 0;i < K;i++)
	{
		int tem = ans;
		if(i == 0) tem -= st[{a[i],a[i+1]}];
		else if(i == K - 1) tem -= st[{a[i - 1],a[i]}];
		else
		{
			tem -= st[{a[i-1],a[i]}];
			tem -= st[{a[i],a[i+1]}];
			dfs(a[i-1],a[i-1],-1,a[i+1],0);
			tem += st[{a[i-1],a[i+1]}];
		}
		cout<<tem<<" ";
	 } 
    
    return 0;
}

试题 J: 砍树（LCA，不会做）

原文地址:https://blog.csdn.net/lishifu_/article/details/136769759 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1771036592534851584.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部