当前位置：网站首页>十三届蓝桥杯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裸题吧
明天上代码，困了
边栏推荐
猜你喜欢
BPR(贝叶斯个性化排序)
PWN攻防世界cgpwn2
leetcode刷题：二叉树01（二叉树的前序遍历）
2022安全员-B证考试练习题模拟考试平台操作
Importance of EDA tools to chip industry knowledge popularization
MySQL数据库驱动(JDBC Driver)jar包下载
2022安全员-A证考题及在线模拟考试
小鸟逃票登机，如何反思，应如何解决，飞机为何怕小鸟？
Develop those things: easycvr platform adds playback address authentication function
Flask 常用组件
随机推荐
STC 32-bit 8051 single chip microcomputer development example tutorial II i/o working mode and its configuration
【opencv】train＆test HOG+SVM
2022熔化焊接与热切割上岗证题目模拟考试平台操作
Niuke programming question -- must brush the string of 101 (brush the question efficiently, draw inferences from one instance)
功利点没啥！
Data analysts sound tall? Understand these points before you decide whether to transform
深度学习 神经网络基础
leetcode刷题：二叉树01（二叉树的前序遍历）
Richview RichEdit srichviewedit PageSize page setup and synchronization
What if win11 can't pause the update? Win11 pause update is gray. How to solve it?
如何用OpenMesh创建一个四棱锥
Target detection - Yolo series
leetcode刷题：二叉树02（二叉树的中序遍历）
联想电脑怎么连接蓝牙耳机？
杰理之、产线装配环节【篇】
新牛牛盲盒微信小程序源码_支持流量变现，带完整素材图片
Practical project notes (I) -- creation of virtual machine
leetcode刷题：栈与队列04（删除字符串中的所有相邻重复项）
[multithreading] realize the singleton mode (hungry and lazy) realize the thread safe singleton mode (double validation lock)
PLC模拟量输入 模拟量转换FB S_ITR（三菱FX3U）