当前位置：网站首页>十三届蓝桥杯B组国赛

十三届蓝桥杯B组国赛

2022-07-01 19:36:00 【Zqchang】

目录

A

在这里插入图片描述
01背包，多了一个限制，加一维，多的限制就是总和是2022

代码

这里要明白状态，dp[i][i] 指的是拿个i个数了，总和是j

我一开始没按照背包写，自己就对着状态转移方程写起来了，然后就写了个

// for(int i=1; i<=10; i++)
// for(int j=1; j<=2022; j++)
// for(int k=0; k<j; k++)
// dp[i][j] += dp[i-1][k];

它有个错误，就是目前数的总和是j，当前选的k
这个代码不能做到不重不漏，比如dp[2][10]它会把一些方案算两边

而对于正解代码，它枚举当前选的数，枚举完再枚举总和，这样就是用当前选的对后面做贡献，这样只会算一次

朴素版

#include <bitsdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
    
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {
    if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {
    x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
    
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
    
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll f[2023][11][2023];

void work() {
    
	f[0][0][0] = 1;
	for(int i = 1; i <= 2022; ++i) {
    
		for(int j = 0; j <= 10; ++j) {
    
			for(int k = 0; k <= 2022; ++k) {
    
				if(k < i) f[i][j][k] = f[i - 1][j][k];
				else {
    
					f[i][j][k] = f[i - 1][j][k];
					if(j) f[i][j][k] += f[i - 1][j - 1][k - i];
				}
			}
		}
	}
	printf("%lld\n", f[2022][10][2022]);
}

int main() {
    
	/*ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);*/
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
    
		work();
	}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

dp版

#include<bits/stdc++.h> 
using namespace std;
#define int long long
int dp[11][2222];//拿个多少个数，和是什么 

signed main()
{
    
	dp[0][0] = 1;
	
	for(int i=1; i<=2022; i++)//枚举到选某一个数
		for(int j = 10; j>=1; j--)//前两个是背包，先枚举物品，再枚举体积
		 	for(int k=i; k<=2022; k++)//枚举总和是多少
		 		dp[j][k] += dp[j-1][k-i];
	
// for(int i=1; i<=10; i++)
// for(int j=1; j<=2022; j++)
// for(int k=0; k<j; k++)
// dp[i][j] += dp[i-1][k];
	 		
	cout << dp[10][2022] << endl;
	return 0; 
}

B

在这里插入图片描述
枚举一下算一算角度就可以

当时我错在，觉得他是会一格一格的跳，导致我算出来好几个答案

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

signed main()
{
    
	for(int s=0; s<=6; s++)
		for(int f=0; f<60; f++)
			for(int m=0; m<60; m++)
			{
    
				double m1 = m / 60.0 * 360;
				double f1 = f / 60.0 * 360 + m1 / 60;//加的其实是把秒换成分钟求角度，下面的同理 
				double s1 = s / 12.0 * 360 + f1 / 12;
				double A = abs(f1 - s1), B = abs(f1 - m1);
				A = min(A, 360 - A); B = min(B, 360 - B);
				if(fabs(A - 2 * B) <= 1e-9) printf("%d %d %d\n", s, f, m); 
			}
	return 0; 
}

C

卡牌
在这里插入图片描述
在这里插入图片描述
考试的时候写了个暴力。。。现在被人一提醒，发现是二分

#include<bits/stdc++.h> 
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 2e5 + 10;
int a[N], b[N];
int n, m;
bool check(int mid)
{
    
	int res = 0;
	for(int i=1; i<=n; i++)
	{
    
		if(mid > a[i] + b[i]) return false;
		if(mid > a[i]) res += mid - a[i];
	}
	if(res > m) return false;
	else return true;
}
signed main()
{
    
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i];
	for(int i=1; i<=n; i++) cin >> b[i];
	
	int l = 0, r = n;
	while(l < r)
	{
    
		int mid = (l + r + 1) >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	
	cout << l << endl;
	return 0; 
}

D最大数字

D最大数字
在这里插入图片描述
两种办法，一种暴力一种dp

在赛场上写了一个贪心，尬死

#include<bits/stdc++.h> 
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 2e5 + 10;
int a, b;
int f[20][110][110];//表示前i位用了j个A，k个B，所得到的最大前缀是多少 
int r[20];
string s;

int transA(int a, int b)
{
    
	return (a + b) % 10;
}

int transB(int a, int b)
{
    
	return (a - b + 10) % 10;
}
signed main()
{
    
	cin >> s >> a >> b;
	for(int i=0; i<s.size(); i++)
		r[i+1] = s[i] - '0';
		
	int n = s.size();
	
	f[0][0][0] = 0;
	for(int i=1; i<=n; i++)
	{
    
		for(int j=0; j<=a; j++)
		{
    
			for(int k=0; k<=b; k++)
			{
    
				f[i][j][k] = f[i - 1][j][k] * 10 + r[i];
				for(int l = 0; l <= min(j, 9ll); l++)
					f[i][j][k] = max(f[i][j][k], f[i - 1][j - l][k] * 10 + transA(r[i], l));
				for(int l = 0; l <= min(k, 9ll); l++)	
					f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - l] * 10 + transB(r[i], l));
			}
		}
	}
	
	cout << f[n][a][b] << endl;
	return 0; 
}

然后来个暴力写法吧

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int r[20];
signed main()
{
    
	int s, a, b;
	cin >> s >> a >> b;
	int res = s;
	int n = 0;
	while(s)
	{
    
		r[n++] = s % 10;
		s /= 10;
	}
	for(int i=0;  i < 1ll << n; i++)
	{
    
		int aa = a, bb = b;
		int ans = 0;
		for(int j=n-1; j>=0; j--)
		{
    
			ans *= 10;
			if( (i >> j) & 1)
			{
    
				int a1 = 9 - r[j];
				if(a1 <= aa)
				{
    
					ans += 9;
					aa -= a1;
				} 
				else
				{
    
					ans += r[j] + aa;
					aa = 0;
				}
			}
			else
			{
    
				int b1 = r[j] + 1;
				if(b1 <= bb)
				{
    
					ans += 9;
					bb -= b1;
				} 
				else
				{
    
					ans += r[j] - bb;
					bb = 0;
				}
			}
		}
		res = max(res, ans);

	}
	cout << res << endl;

	return 0;
}

E 出差

感觉没啥好说的，最短路裸题

出差

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define PII pair<int, int>
const int N = 1010, M = 10010;
int g[N][N];
int n, m;
int t[N];
int dist[N];
bool st[N];
void dij()
{
    
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	for(int i=1; i<n; i++)
	{
    
		int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
       for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
	}
	
	cout << dist[n] - t[n]<< endl;
}
signed main()
{
    
	fast;
	cin >> n >> m;
	int a, b, c;
	memset(g, 0x3f, sizeof g);
	for(int i=1; i<=n; i++) cin >> t[i];
	
	for(int i=1; i<=m; i++)
	{
    
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c + t[b]);
		g[b][a] = min(g[b][a], c + t[a]);
	}
	
// for(int i=1; i<=n; i++) 
	dij();
	return 0;
}

F 费用报销

费用报销

f[N][N]考虑了前i个票据，得到了j元，在这个状态下，上一次选的id的最小值

紧接着就是一个01背包的变形，害，01背包学废了
思想就是，把能凑出来的符合条件的总金额都凑出来，记录一下最后选的是哪一个，以便后续判断日期符不符合规定，为什么要找最小的符合的日期，因为日期越小，后面符合的可能性就越大！，最后从m倒着往前枚举一下

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 5010;
int n, m, k;
int mon[N], da[N], v[N];
int month[] = {
    0, 31, 28, 31, 30, 31,30, 31, 31, 30, 31, 30, 31};
int day[N];
int f[N][N];//考虑了前i个票据，得到了j元，在这个状态下，上一次选的id的最小值 
struct node
{
    
	int time;
	int val;
}r[N];

bool cmp(node a, node b)
{
    
	return a.time < b.time;
}
signed main()
{
    
	fast;
	cin >> n >> m >> k;
	for(int i=1; i<=12; i++) month[i] += month[i-1];
	for(int i=1; i<=n; i++)
	{
    
		cin >> mon[i] >> da[i] >> r[i].val;
		r[i].time = month[mon[i] - 1] + da[i];
	}
	r[0].time = -400, r[0].val = 0;
	
	sort(r + 1, r + 1 + n, cmp);
	
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0; 
	
	for(int i = 1; i <= n; ++i) 
	{
    
		for(int j = 0; j <= m; ++j) 
		{
    
			f[i][j] = f[i - 1][j];
			if(f[i][j] == INF && j >= r[i].val) //如果这个金额j没被弄出来过，就可以试着弄出来
			{
    
				int pre = f[i - 1][j - r[i].val];//先找到它的上一个看看有没有
				if(pre < INF && r[i].time - r[pre].time >= k) f[i][j] = i;//如果有，并且符合条件，就凑出来
			}
		}
	}
	for(int i = m; i >= 0; --i) 
		if(f[n][i] < INF) 
		{
    
			cout << i << endl;
			break;
		}
			
	return 0;
}

G 故障

故障
模拟

贝叶斯公式
两个写法

要注意特判一下都是0的情况，这种情况下，不能进行除法，所以要单独拉出来

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 50, M = 30;
int pw[N], px[N][M];//原因出现概率，原因对应的现象出现的概率 
int xx[M];//出现了多少个现象 
bool vis[N];//标记哪些原因不成立，概率为0 
bool vv[M];//标记出现的现象分别是哪些 
int n, m, k;
double res[N]; //存答案 
int id[N];//用来排序 
const double eps = 1e-8 ;

bool cmp(int a, int b)
{
    
	if(fabs(res[a] - res[b]) > eps) return res[a] > res[b];
	else return a < b;
}

signed main()
{
    
// fast;
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> pw[i];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin >> px[i][j];
	
	cin >> k;
	for(int i=1; i<=k; i++) 
	{
    
		cin >> xx[i];
		vv[xx[i]] = 1;
	}
	int tot = 0;
	for(int i=1; i<=n; i++)
	{
    
		for(int j=1; j<=k; j++)
		{
    
			if(px[i][xx[j]] == 0) vis[i] = 1;
			break;
		}
		if(!vis[i]) tot += pw[i]; 
	}
		
	if(tot == 0)
	{
    
		for(int i = 1 ; i <= n ; i ++){
    
			printf("%lld 0.00\n" , i) ;
		}
		return 0 ;
	}
	
	double num = 0;
	for(int i=1; i<=n; i++)
	{
    
		res[i] = 1.0;
		if(vis[i]) res[i] = 0.0;
		else
		{
    
			for(int j=1; j<=m; j++)
			{
    
				if(vv[j]) res[i] *= px[i][j] / 100.0;
				else res[i] *= (100 - px[i][j]) / 100.0;
			}
			res[i] *= pw[i] * 1.0 / tot;
			num += res[i];
		}
	}
	
	if(fabs(num) < eps){
    
		for(int i = 1 ; i <= n ; i ++){
    
			printf("%lld 0.00\n" , i) ;
		}
		return 0 ;
	}
	
	for(int i=1; i<=n; i++)
	{
    
		id[i] = i;
		if(!vis[i])
		{
    
			res[i] = res[i] / num * 100;
		}
	}
	
	sort(id + 1, id + 1 + n, cmp);
	
	for(int i=1; i<=n; i++)
	{
    
		printf("%lld %.2lf\n", id[i], res[id[i]]);
	}
	return 0;
}

AC代码，感觉跟上一个也一样

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 50, M = 30;
int pw[N], px[N][M];//原因出现概率，原因对应的现象出现的概率 
int xx[M];//出现了多少个现象 
bool vis[N];//标记哪些原因不成立，概率为0 
bool vv[M];//标记出现的现象分别是哪些 
int n, m, k;
double res[N]; //存答案 
int id[N];//用来排序 
const double eps = 1e-8 ;

bool cmp(int a, int b)
{
    
	if(fabs(res[a] - res[b]) > eps) return res[a] > res[b];
	else return a < b;
}

signed main()
{
    
// fast;
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> pw[i];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin >> px[i][j];
	
	cin >> k;
	for(int i=1; i<=k; i++) 
	{
    
		cin >> xx[i];
		vv[xx[i]] = 1;
	}
	
	double num = 0;
	for(int i=1; i<=n; i++)
	{
    
		res[i] = 1;
		for(int j=1; j<=m; j++)
		{
    
			if(vv[j]) res[i] *= px[i][j] / 100.0;
			else res[i] *= (100 - px[i][j]) / 100.0;
		}
		res[i] = res[i] * pw[i] / 100.0;
		num += res[i];
	}
	
	if(fabs(num) < eps){
    
		for(int i = 1 ; i <= n ; i ++){
    
			printf("%lld 0.00\n" , i) ;
		}
		return 0 ;
	}
	
	for(int i=1; i<=n; i++)
	{
    
		id[i] = i;
		res[i] = res[i] * 100.0 / num ;
	}
	
	sort(id + 1, id + 1 + n, cmp);
	
	for(int i=1; i<=n; i++) printf("%lld %.2lf\n", id[i], res[id[i]]);
	return 0;
}

H 机房

机房
LCA裸题吧
明天上代码，困了

原网站

版权声明
本文为[Zqchang]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51176105/article/details/125504380

边栏推荐

猜你喜欢

随机推荐