13th Blue Bridge Cup group B national tournament

A

01 knapsack , One more limit , Add one dimension , The limit of many is that the sum is 2022

Code

Here we need to understand the state ,dp[i][i] It means taking a i Number. , The sum is j

I didn't write according to my backpack at first , I wrote about the state transition equation , And then I wrote a

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

It has a mistake , The sum of the current number is j, Currently selected k
This code cannot be repeated without omission , such as dp[2][10] It will count some schemes on both sides

For positive solution code , It enumerates the currently selected number , Enumerate the sum after enumeration , This is to contribute to the future with the currently selected , This will only count once

Plain version

#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 edition

#include<bits/stdc++.h> 
using namespace std;
#define int long long
int dp[11][2222];// Take how many numbers , And what it is  

signed main()
{
    
	dp[0][0] = 1;
	
	for(int i=1; i<=2022; i++)// Enumerate to select a certain number 
		for(int j = 10; j>=1; j--)// The first two are backpacks , First enumerate the items , Then enumerate the volume 
		 	for(int k=i; k<=2022; k++)// What is the sum of enumerations 
		 		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

Just enumerate and calculate the angle

I was wrong , I think he can jump one by one , As a result, I worked out several answers

#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;// What you add is actually changing seconds into minutes to find the angle , The same goes for the following  
				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

The card


During the exam, I wrote a violent ... Now I am reminded , Discovery is two points

#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 Maximum number

D Maximum number

Two ways , A kind of violence, a kind of dp

Wrote a greedy on the court , Die of embarrassment

#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];// Before presentation i It's a bit too late j individual A,k individual B, What is the maximum prefix obtained  
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; 
}

Then let's write in a violent way

#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 On a business trip

I feel like I have nothing to say , The shortest path

On a business trip

#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 Expense Reimbursement

Expense Reimbursement

f[N][N] Before considering i Notes , Got it j element , In this state , Last time I chose id The minimum value of

Then there is a 01 The deformation of the backpack , harm ,01 Backpack learning is useless
Thought is , Round up the total amount that meets the conditions that can be made up , Record which one you chose last , In order to judge whether the date is in conformity with the regulations , Why look for the smallest matching date , Because the smaller the date , The more likely it is to comply later ！, Finally from the m Enumerate backwards

#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];// Before considering i Notes , Got it j element , In this state , Last time I chose id The minimum value of  
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) // If this amount j Never got out , You can try to get it out 
			{
    
				int pre = f[i - 1][j - r[i].val];// First find its last one and see if it has 
				if(pre < INF && r[i].time - r[pre].time >= k) f[i][j] = i;// If there is , And meet the conditions , Just gather together 
			}
		}
	}
	for(int i = m; i >= 0; --i) 
		if(f[n][i] < INF) 
		{
    
			cout << i << endl;
			break;
		}
			
	return 0;
}

G fault

fault
simulation

Bayes' formula
Two ways of writing

Pay attention to the special judgment 0 The situation of , In this case , Cannot divide , So pull it out alone

#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];// Probability of cause , The probability of the phenomenon corresponding to the cause  
int xx[M];// How many phenomena have appeared  
bool vis[N];// Mark which reasons are not tenable , The probability of 0 
bool vv[M];// What are the phenomena of marks  
int n, m, k;
double res[N]; // Save the answer  
int id[N];// Used to sort  
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 Code , It feels the same to follow one

#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];// Probability of cause , The probability of the phenomenon corresponding to the cause  
int xx[M];// How many phenomena have appeared  
bool vis[N];// Mark which reasons are not tenable , The probability of 0 
bool vv[M];// What are the phenomena of marks  
int n, m, k;
double res[N]; // Save the answer  
int id[N];// Used to sort  
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 Computer room

Computer room
LCA Bare topic
Code tomorrow , sleepy