蓝桥杯 2023 C++ B组 (个人代码，可能有小错误)

Henry_WYH 2023-04-17 原文

A题直接枚举即可，枚举日期，暴力匹配

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool check(string t){
	if(t.substr(0, 4)!="2023") return false;
	string mon = t.substr(4, 2);
	string day = t.substr(6, 2);
	int m = (mon[0]-'0')*10+(mon[1]-'0');
	int d = (day[0]-'0')*10+(day[1]-'0');
	if(m==1||m==3||m==5||m==7||m==8||m==10||m==12){
		if(d>=1&&d<=31) return true;
	}else if(m==2){
		if(d>=1&&d<=28) return true;
	}else if(m==4||m==6||m==9||m==11){
		if(d>=1&&d<=30) return true;
	}
	return false;
};

string p="",s="";
int ans = 0, n;

string mon[]={"01","02","03","04","05","06","07","08","09","10","11","12"};
string day[]={"01","02","03","04","05","06","07","08","09","10",
"11","12","13","14","15","16","17","18","19","20",
"21","22","23","24","25","26","27","28","29","30","31"};
int md[]={31,28,31,30,31,30,31,31,30,31,30,31};

bool check(string t,string s){
	int j=0;
	for(int i=0;i<t.size();++i){
		if(j==s.size()) return true;
		if(t[i]==s[j]) j++;
	}
	return j==s.size();
}

void solve(){
	while(cin >> s){
		p += s;
	}
	// cout << p << endl;
	n=p.size();
	string t = "2023";
	for(int i=0;i<12;++i){
		for(int j=0;j<md[i];++j){
			string N = t + mon[i] + day[j];
			if(check(p, N)) {
				ans ++;
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
	solve();
	return 0;
}

答案：

可以看出香浓信息熵有单调性(在0不超过1这个前提下)
因此直接二分即可，顺便输出一下结果对应的函数值

#include<bits/stdc++.h>
using namespace std;
#define int long long
double p(int x,int y){ //x 0 y 1
	double P0 = 1.0*x/(x+y);
	double P1 = 1.0*y/(x+y);
	return -1.0*x*x/(x+y)*log2(P0)-1.0*y*y/(x+y)*log2(P1);
}

void solve(){
	int n = 23333333;
	int l=1, r=(n-1)/2;
	double PP = 11625907.5798;
	while(l<r){
		int mid = (l+r)>>1;
		double t = p(mid, n-mid);
		if(t<PP) l=mid+1;
		else r=mid;
	}
	cout << l << endl;
	
	l=11027421;
	printf("%.5lf", p(l, n-l));
}

signed main(){
	solve();
	return 0;
}

貌似可以直接O(1)算，但是我选择直接二分

二分的正确性在保证有解的前提下成立

#include<iostream>
#include<vector>
using namespace std;
//V:normal -> 1:X
void solve(){
	int n;
	cin >> n;
	long long x,y,X=1e9,Y=0;
	vector<pair<int,int>> vec;
	for(int i=0;i<n;++i){
		cin >> x >> y;
		vec.push_back({x,y});
	}
	auto check=[&](long long x)->bool{
		for(auto u:vec){
			if(u.first/x < u.second) return false;
		}
		return true;
	};
	long long l=1,r=1e9;
	while(l<r){
		long long mid=(l+r+1)>>1;
		if(check(mid)) l=mid; // x/mid >= y
		else r=mid-1;
	}
	Y=l;
	auto find=[&](long long x)->bool{
		for(auto u:vec){
			if(u.first/x > u.second) return false;
		}
		return true;
	};
	l=1,r=1e9;
	while(l<r){
		long long mid=(l+r)>>1;
		if(find(mid)) r=mid;
		else l=mid+1;
	}
	X=l;
	cout<<X<<" " << Y<<endl;
}

int main(){
	solve();
	return 0;
}

顺便跑了几组对拍：

N $\le$ 10 直接搜，不要想什么贪心

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

bool vis[20];
int n;

bool dfs(int num,int now, vector<array<int,3>>& vec){
	if(num==n){
		return true;
	}
	int flag = 0;
	for(int i=0;i<n;++i){
		if(!vis[i]){
			if(now>vec[i][0]+vec[i][1]) return false;
			vis[i] = true;
			flag |= dfs(num+1, now+vec[i][2], vec);
			vis[i]=false;
		}
	}
	return flag;
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;++i) vis[i] = 0;

	vector<array<int,3>> vec;
	for(int i=0;i<n;++i){
		int x,y,z;
		cin >> x >> y >> z;
		vec.push_back({x,y,z});
	}
	bool res = dfs(0, 0, vec);
	cout<<(res?"YES":"NO")<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; cin >>_;
	while(_--) solve();
	return 0;
}
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/

删最少数使得他是接龙序列，即求原序列的最大接龙子序列，然后用n减去。
最大接龙子序列求法：DP
但是我们发现转移类型一共只有9种1~9结尾的数字
因此我们可以开一个数组f[i]表示前i个数字，以第i个结尾的最大接龙子序列。
再开一个数组bac[1~9]表示以1~9结尾的最大接龙子序列
每次用第i个数组开头的字母对应的数组更新f[i]，然后再用f[i]反过来更新bac即可
细节看代码

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

int n;

void solve(){
	cin >> n;
	vector<string> vec;
	for(int i=0;i<n;++i){
		string t;
		cin >> t;
		vec.push_back(t); 
	}
	vector<int> bac(10); //1,2,3....
	vector<int> f(n+1, 0);
	int ans = 0 ;
	for(int i=0;i<n;++i){
		f[i]=max(1, bac[vec[i][0]-'0']+1);
		ans=max(ans, f[i]);
		bac[vec[i].back()-'0'] = 
		  	max(bac[vec[i].back()-'0'], f[i]);
	}
	cout << n-ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

先用边缘的海水进行bfs求出"真的海水"，然后再对所有岛屿进行BFS,此时BFS的时候非真的海水可以直接识别为陆地然后入队。
两遍BFS得到答案。

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;

int n,m;
char G[60][60];
int vis[60][60], g[60][60], water[60][60];

int d[][2]={1,0,0,1,-1,0,0,-1};
int mov[][2]={{1,0},{-1,0},{0,1},{0,-1},{1,-1},
				{1,1},{-1,-1},{-1,1}};

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[i][j] = g[i][j] = water[i][j] = 0;
		}
	}

	for(int i=1;i<=n;++i){
		cin >> (G[i]+1);
		for(int j=1;j<=m;++j){
			g[i][j] = G[i][j]-'0';
		}
	}

	queue<pair<int,int>> q;
	for(int i=1;i<=n;++i){
		if(g[i][1] == 0){
			water[i][1] = true;
			q.push({i, 1});
		}
		if(g[i][m] == 0){
			water[i][m] = true;
			q.push({i, m});
		}
	}

	for(int i=1;i<=m;++i){
		if(g[1][i] == 0){
			if(!water[1][i]){
				water[1][i] = true;
				q.push({1, i});
			}
		}
		if(g[n][i] == 0){
			if(!water[n][i]){
				water[n][i] = true;
				q.push({n, i});
			}
		}
	}

	while(q.size()){
		auto u=q.front(); q.pop();
		int x=u.x,y=u.y;
		for(int i=0;i<8;++i){
			int xx=x+mov[i][0], yy=y+mov[i][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!water[xx][yy]&&!g[xx][yy]){
				q.push({xx, yy});
				water[xx][yy] = true;
			}
		}
	}

	while(q.size()) q.pop();
	
	int idx = 0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!water[i][j]&&g[i][j]&&!vis[i][j]){
				q.push({i, j});
				vis[i][j]=++idx;
				while(q.size()){
					auto u=q.front(); q.pop();
					int x=u.x,y=u.y;
					for(int i=0;i<4;++i){
						int xx=x+d[i][0], yy=y+d[i][1];
						if(xx>=1&&xx<=n&&yy>=1&&yy<=m
						&&!vis[xx][yy]&&!water[xx][yy]){
							vis[xx][yy]=idx;
							q.push({xx,yy});
						}
					}
				}
			}
		}
	}
	cout << idx << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	cin >>_;
	while(_--) solve();
	return 0;
}

/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/

二分/双指针都行
先按照位置处理出来两个数组
然后枚举开头的位置，二分出结尾在另一个数组的合法位置，直接累加答案

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;

int k;
char st,ed;
string p;

void solve(){
	cin >> k;
	cin >> p >> st >> ed;
	vector<int> ps,pe;
	for(int i=0;i<p.size();++i){
		if(p[i]==st) ps.push_back(i);
		if(p[i]==ed) pe.push_back(i);
	}

	long long ans = 0;
	for(int i=0;i<ps.size();++i){
		int x = ps[i];
		int X = x + k - 1;
		int l=0,r=pe.size()-1;
		while(l<r){
			int mid=(l+r)>>1;
			if(pe[mid] >= X) r=mid;
			else l=mid+1;
		}
		if(pe[l] >= X){
			ans += pe.size() - l;
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

双链表维护每个数左边和右边分别是什么数
set维护每个位置的值和要删的最小值
本题考察STL的用法

#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
#include<string>
#include<queue>
#include<set>
#define x first
#define y second
using namespace std;

int n,k;

void solve(){
	cin >> n >> k;
	vector<int> a(n+1),pre(n+1),nxt(n+1);
	set<pair<int,int>> ds;

	for(int i=1;i<=n;++i){
		pre[i] = i-1;
		nxt[i] = i+1;
	}

	for(int i=1;i<=n;++i){
		cin >> a[i];
		ds.insert({a[i], i});
	}

	for(int t=1;t<=k;++t){
		auto pos=ds.begin();
		int x=pos->first, y=pos->second;
		int l = pre[y], r = nxt[y];

		ds.erase(pos);
		pre[nxt[y]]=pre[y];
		nxt[pre[y]]=nxt[y];
		pre[y]=-1, nxt[y]=-1;
		
		if(l>0){
			ds.erase(ds.find({a[l], l}));
			a[l] += x;
			ds.insert({a[l], l});
		}
		if(r<=n){
			ds.erase(ds.find({a[r], r}));
			a[r] += x;
			ds.insert({a[r], r});
		}
	}
	vector<pair<int,int>> temp;
	for(auto u:ds){
		temp.push_back({u.y, u.x});
	}
	sort(temp.begin(), temp.end());
	for(auto u:temp){
		cout << u.y << " ";
	}cout<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

LCA, 没啥好说的

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;
#define debug(x) cout<<#x<<": "<<x<<endl
#define N 100010
vector<pair<int,int>> edge[N];
int n,m,k;
int dep[N],fa[20][N];
int rout[N];
queue<int> q;

void bfs(){
	for(int i=1;i<=n;++i) dep[i]=-1;
	dep[1]=0;
	q.push(1);
	while(q.size()){
		auto u=q.front(); q.pop();
		for(auto v:edge[u]){
			int ver = v.x, w=v.y;
			if(dep[ver]==-1){
				dep[ver] = dep[u] + w;
				q.push(ver);
				fa[0][ver] = u;
				for(int i=1;i<=19;++i){
					fa[i][ver] = fa[i-1][fa[i-1][ver]];
				}
			}
		}
	}
}

int lca(int x,int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i=19;i>=0;--i){
		if(dep[fa[i][x]] >= dep[y])
			x = fa[i][x];
	}
	if(x==y) return x;
	for(int i=19;i>=0;--i){
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x], y=fa[i][y];
	}
	return fa[0][x];
}

int dist(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}

void solve(){
	cin >> n >> k;
	for(int i=1;i<n;++i){
		int x,y,z;
		cin >> x >> y >> z;
		edge[x].push_back({y, z});
		edge[y].push_back({x, z});
	}
	bfs();
	vector<int> a(k+1);
	for(int i=1;i<=k;++i){
		cin >> a[i];
	}

	int now = a[1];
	long long time = 0;
	for(int i=1;i<=k;++i){
		time += dist(now, a[i]);
		now = a[i];
	}

	cout << time - dist(a[1], a[2]) << " ";
	now = a[1];
	for(int i=2;i<=k;++i){
		int temp = time;
		temp -= dist(now, a[i]);
		if(i!=k){
			temp -= dist(a[i], a[i+1]);
			temp += dist(now, a[i+1]);
		}
		cout << temp << " ";
		now = a[i];
	}cout << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}
/*
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
*/

树上差分，也是LCA，最后再DFS一下

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;
#define debug(x) cout<<#x<<": "<<x<<endl
#define N 100010

int n,m,k;
vector<int> edge[N];
pair<int,int> p[N];
int w[N],dep[N],fa[20][N];
pair<int,int> edges[N];

void bfs(){
	for(int i=1;i<=n;++i) dep[i]=-1;
	queue<int> q;
	q.push(1);
	dep[1]=1;
	while(q.size()){
		auto u=q.front(); q.pop();
		for(auto v:edge[u]){
			if(dep[v]==-1){
				dep[v]=dep[u]+1;
				q.push(v);
				fa[0][v] = u;
				for(int i=1;i<=19;++i)
					fa[i][v]=fa[i-1][fa[i-1][v]];
			}
		}
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x, y);
	for(int i=19;i>=0;--i){
		if(dep[fa[i][x]] >= dep[y])
			x=fa[i][x];
	}
	if(x==y) return x;
	for(int i=19;i>=0;--i){
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x], y=fa[i][y];
	}
	return fa[0][x];
}

int f[N];

void dfs(int u,int pre){
	f[u] = w[u];
	for(auto v:edge[u]){
		if(v!=pre){
			dfs(v, u);
			f[u] += f[v];
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<n;++i){
		int x,y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
		edges[i] = {x, y};
	}
	bfs();
	for(int i=1;i<=m;++i){
		cin >> p[i].x >> p[i].y;
		w[p[i].x] ++, w[p[i].y] ++;
		w[fa[0][lca(p[i].x, p[i].y)]] -= 1;
		w[lca(p[i].x, p[i].y)] -= 1;
	}
	dfs(1, -1);
	int ans = -1;
	for(int i=1;i<n;++i){
		int x=edges[i].x, y=edges[i].y;
		if(dep[x]<dep[y]) swap(x, y);
		//y-x
		if(f[x]==m){
			ans=max(ans, i);
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

C++小错 span class token 蓝桥杯 B组蒟蒻

有关蓝桥杯 2023 C++ B组 (个人代码，可能有小错误)的更多相关文章

ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
ruby-on-rails - 浏览 Ruby 源代码 - 2
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
ruby - 模块嵌套代码风格偏好 - 2
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。最佳答案这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？最佳答案是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
ruby - Net::HTTP 获取源代码和状态 - 2
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。最佳答案在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur
程序员如何提高代码能力？ - 2
前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源
华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2
华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o
7个大一C语言必学的程序 / C语言经典代码大全 - 2
嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

蓝桥杯 2023 C++ B组 (个人代码，可能有小错误)

有关蓝桥杯 2023 C++ B组 (个人代码，可能有小错误)的更多相关文章

随机推荐