• 十三届蓝桥杯B组国赛

    目录

    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];

    • 1
    • 2
    • 3
    • 4

    它有个错误，就是目前数的总和是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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    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; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    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; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    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; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    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; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    然后来个暴力写法吧

    #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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    H 机房

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

  • 相关阅读:
    Mongodb认证入库并进行多版本缓存使用
    perl下批量修改远程服务器密码
    【vue3】webpack和vite介绍与使用【超详细】
    Redis 19 事务
    Blazor前后端框架Known-V1.2.8
    python:for循环的格式、while循环的用法、input(从键盘输入字符串)、print用法、函数库的导入及使用
    彻底搞懂MySql的B+Tree
    R语言电信公司churn数据客户流失 k近邻（knn）模型预测分析
    机器学习笔记 - 时间序列预测研究：法国香槟的月销量
    设计模式之-单例模式
  • 原文地址：https://blog.csdn.net/weixin_51176105/article/details/125504380