当前位置：网站首页>十三届蓝桥杯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裸题吧
明天上代码，困了
边栏推荐
- 300 linear algebra Lecture 4 linear equations
- Win11 how to hide the taskbar? Win11 method to hide the taskbar
- Develop those things: easycvr platform adds playback address authentication function
- Keras machine translation practice
- [multithreading] lock strategy
- Practical project notes (I) -- creation of virtual machine
- 关于new Set( )还有哪些是你不知道的
- 8K HDR!｜ Hevc hard solution for chromium - principle / Measurement Guide
- 多个张量与多个卷积核做卷积运算的输出结果
- Write blog documents
猜你喜欢
leetcode刷题：二叉树01（二叉树的前序遍历）
What if win11 can't pause the update? Win11 pause update is gray. How to solve it?
300 linear algebra Lecture 4 linear equations
Richview RichEdit srichviewedit PageSize page setup and synchronization
Exclusive news: Alibaba cloud quietly launched RPA cloud computer and has opened cooperation with many RPA manufacturers
Richview trvdocparameters page parameter settings
300题线性代数 第四讲 线性方程组
极客DIY开源方案分享——数字幅频均衡功率放大器设计（实用的嵌入式电子设计作品软硬件综合实践）
2022年高处安装、维护、拆除考题模拟考试平台操作
![[multithreading] lock strategy](/img/97/5cacfd2de73d3c3b8acabf6b5c5ce3.png)
[multithreading] lock strategy
随机推荐
Review notes of Zhang Haifan in introduction to software engineering (Sixth Edition)
Stack overflow 2022 developer survey: where is the industry going?
Halcon知识：三维重构的一个尝试
牛客编程题--必刷101之字符串(高效刷题，举一反三)
Develop those things: easycvr cluster device management page function display optimization
股票手机开户哪个app好，安全性较高的
架构师毕业总结
Face recognition system opencv face detection
How to connect the two nodes of the flow chart
EMC-电路保护器件-防浪涌及冲击电流用
多个张量与多个卷积核做卷积运算的输出结果
极客DIY开源方案分享——数字幅频均衡功率放大器设计（实用的嵌入式电子设计作品软硬件综合实践）
On the usage of a magic function
网上开户是安全的吗?新手可以开炒股账户吗。
Develop those things: easycvr platform adds playback address authentication function
Using qeventloop to realize synchronous waiting for the return of slot function
Win11 how to hide the taskbar? Win11 method to hide the taskbar
Swiftui 4 new features complete toggle and mixed toggle multiple binding components
2022安全员-A证考题及在线模拟考试
There are four ways to write switch, you know