第十三届蓝桥杯大赛软件赛国赛B组C/C++(个人题解)

分享一下赛中的想法和一部分的思路，没有验证对不对，有大佬看到错误滴滴我~~
国一不就有手就行

• • 试题 A: 2022（DP）
  • 试题 B: 钟表（模拟）
  • 试题 C: 卡牌（二分check）
  • 试题 D: 最大数字（dfs）
  • 试题 E: 出差（dij）
  • 试题 F: 费用报销（dp）
  • 试题 G: 故障（概率题）
  • 试题 H: 机房（lca）
  • 试题 I: 齿轮（数学题and调和级数）
  • 试题 J: 搬砖（dp）

os：2022¹⁰应该要跑很久吧，那可怎么办呀，不回来了呀。哦，好像可以DP~

思路
定义 dp_i,x,y 表示第 i 个数等于 x 且前 i 个数和为 y 的方案数。
状态转移参看代码，时间复杂度 O( n⁴ )，得跑几秒，多等等~
记得开 ll

#include
#define ll long long
using namespace std;

ll dp[15][2500][2500];

int main(){

	for(int i = 1; i <= 2022; i++) dp[1][i][i] = 1;
		
	for(int i = 2; i <= 10; i++){
		for(int j = 1; j<= 2022; j++){
			for(int z = j; z <= 2022; z++){
				for(int k = j+1; k+z <= 2022; k++){
					dp[i][k][k+z] += dp[i-1][j][z];
				}
			}
		}
	}
	
	ll sum = 0;
	for(int i = 0; i <= 2022; i++) sum += dp[10][i][2022];
	
	cout << sum << endl;
			
    return 0;
}

// 379187662194355221

os：00:00:00不就是答案么，垃圾题。
正在阅读理解的我，看到了公告：00:00:00除外
os：*****

思路
一个小时是 30°，一分钟是 6°，一秒是 6°

#include
#define ll long long
using namespace std;

int main(){

	int res = 0;
	for(int i = 0; i <= 6; i++){
		for(int j = 0; j < 60; j++){
			for(int z = 0; z < 60; z++){
				double s = 30.0 * (i+(j*60.0+z)/3600.0);
				double f = 6.0 * (j+z/60.0);
				double m = z * 6.0;
				double a = fabs(f - s); if(a > 180) a = 360 - a;
				double b = fabs(f - m); if(b > 180) b = 360 - b;
				if(a == 2 * b){
					cout << i << " " << j << " " << z << " " << a << " " << b << endl;
					res++;
				}
			}
		}
	}
	
	cout << res << endl;
			
    return 0;
}

// 4 48 0

os：嗯~，二分大水题

思路
二分能凑出的套牌数，二分check即可~~
时间复杂度 O( n*log(1e18) )

#include
#define ll long long
using namespace std;

const int maxn = 2e5 + 5;
ll a[maxn], b[maxn];
ll n, m;

bool check(ll cnt){
	ll sum = m;
	for(int i = 1; i <= n; i++){
		if(a[i] >= cnt) continue;
		ll num = cnt - a[i];
		if(num <= b[i] && num <= sum){
			sum -= num;
			continue;
		}
		return 0;
	}
	return 1;
}

int main(){

	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
			
	ll res = 0;
	ll l = 0, r = 1e18;
	while(l <= r){
		ll mid = l + r >> 1;
		if(check(mid)){
			res = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	
	cout << res << endl;
			
    return 0;
}

os：能加一定要加，得判断能不能减。不会是数位DP吧，***，算了，暴搜吧

思路
由题得，优先给高位变成大于原来的数。最好变成 9，但可能存在加操作不够的情况，尽量大即可。显然，也可以通过减操作变成 9。

综上，对于每一个数位都有两种选择，是加到 9 还是减到 9。

直接 dfs 暴力枚举每一种情况，加一个记忆化标记一下不重复搜索。时间复杂度 O(2^|n|)，|n| 表示 n 的位数。

#include
#define ll long long
using namespace std;

bool v[100][105][105]; 
ll c[100];
ll res, p[100];
void dfs(ll now, int pos, ll a, ll b){ // a+ b-
	if(v[pos][a][b]) return;
	v[pos][a][b] = 1;
	if(a == 0){
		for(int i = pos; i >= 1; i--){
			if(c[i]+1 <= b){
				now = now + (9-c[i]) * p[i-1];
				b -= c[i] + 1;
			}
		}
		res = max(res, now);
		return;
	}
	res = max(res, now);
	if(pos == 0) return;
	
	int tmp = min((9-c[pos]), a);
	dfs(now + tmp * p[pos-1], pos-1, a-tmp, b);
	
	if(c[pos]+1 <= b) dfs(now + (9-c[pos]) * p[pos-1], pos-1, a, b-c[pos]-1);
} 

int main(){

	ll n, a, b;
	scanf("%lld %lld %lld", &n, &a, &b);
	
	p[0] = 1;
	for(int i = 1; i <= 20; i++) p[i] = p[i-1] * 10;
	
	res = n;
	int m = 0;
	while(n){
		c[++m] = n % 10;
		n /= 10;
	}
	
	dfs(res, m, a, b);
	
	cout << res << endl;
			
    return 0;
}

os：嗯~，最短路裸题，你就拿这个考验选手，那个选手经不起这样的考验

思路
把点权当边权跑 dij 即可，res = dis[n] - c[n]。

#include
#define ll long long
using namespace std;

vector > ma[1005];
ll c[1005];

typedef struct Node{
	int to;
	ll w;
} node;

bool operator < (node A, node B){
	return A.w > B.w;
}

priority_queue qu;
ll dis[1005];

int main(){

	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &c[i]);
	for(int i = 1; i <= m; i++){
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		ma[u].push_back(make_pair(v, w));
		ma[v].push_back(make_pair(u, w));
	}
	
	for(int i = 1; i <= n; i++) dis[i] = 2e18;
	dis[1] = 0;
	qu.push({1, 0});
	while(!qu.empty()){
		int now = qu.top().to;
		qu.pop();
		for(auto i : ma[now]){
			int to = i.first;
			ll nval = dis[now] + i.second + c[to];
			if(nval < dis[to]){
				dis[to] = nval;
				qu.push({to, nval});
			}
		}
	}
	
	cout << dis[n]-c[n] << endl;
	
    return 0;
}

os：这搞毛呀，总不能枚举吧。先塞进去365张口头支票~

思路
观察数据，总金额不能超过 5000，一年也就 365 天。故而 365 * 5000 的 dp 妥妥可以过。
首先，这些支票的时间不是连续的，先塞进去 365+k 张支票(金额为零)使得时间连续。
定义：dp_x,y 表示前 x 天是否可以得到金额为 y 的方案。
状态转移方程参看代码~

#include
#define ll long long
using namespace std;

typedef struct Node{
	int id;
	ll w;
} node;

node v[2005];

bool cmp(node A, node B){
	if(A.id == B.id) return A.w < B.w;
	return A.id < B.id;
}

int M[20] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int f(int a, int b){
	int res = b;
	for(int i = 1; i < a; i++) res += M[i];
	return res;
}

ll dp[400][5005];

int main(){
	
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		int a, b, c;
		cin >> a >> b >> c;
		v[i].id = f(a, b);
		v[i].w = c;
	}
	for(int i = 1; i <= 365+k; i++){
		v[n+i].id = i;
		v[n+i].w = 0;
	}
	n += 365+k;	
	
	v[0].id = 0;
	sort(v+1, v+1+n, cmp);
	
	for(int i = 1; i <= n; i++){
		if(v[i].id != v[i-1].id && v[i].id-k > 0){ // 新的一天，把前k天的状态转移过来
			for(int j = 1; j <= m; j++) 
				dp[v[i].id-k][j] |= dp[v[i].id-k-1][j];
		}
		if(v[i].w == 0) continue;
		dp[v[i].id][v[i].w] |= 1;
		if(v[i].id <= k) continue;
		for(int j = 0; j <= m; j++){
			if(dp[v[i].id-k][j] && j + v[i].w <= m){
				dp[v[i].id][j + v[i].w] |= 1;
			}
		}
	}
	
	int res = 0;
	for(int i = 0; i <= m; i++) if(dp[365][i]) res = i;
	cout << res << endl;
	
    return 0;
}

os：这啥呀，概率题我咋能会，都是数论队友的题，猜结论吧

思路
就是硬猜的结论，看代码吧，一看知道咋算了

#include
#define ll long long
using namespace std;

ll p[100];
ll v[100][100];
ll a[100], c[100], d[100];

typedef struct Node{
	int id;
	double w;
} node;

node res[2005];

bool cmp(node A, node B){
	if(fabs(A.w - B.w) < 1e-3) return A.id < B.id;
	return A.w > B.w;
}

int main(){
	
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> v[i][j];
			if(v[i][j] != 0) a[i] |= (1<<(j-1));
		}
	}
	int k, flag = 0;
	cin >> k;
	for(int i = 1; i <= k; i++) cin >> c[i], d[c[i]] = 1, flag |= (1<<(c[i]-1));
	double sum = 0;
	for(int i = 1; i <= n; i++){
		res[i].w = p[i];
		res[i].id = i;
		for(int j = 1; j <= m; j++){
			if(d[j] == 1) res[i].w *= 1.0 * v[i][j];
			else res[i].w *= 1.0 * (100-v[i][j]);
		}
		sum += res[i].w;
	}
	for(int i = 1; i <= n; i++) res[i].w = res[i].w / sum*100;
	
	sort(res+1, res+1+n, cmp);
	
	for(int i = 1; i <= n; i++) printf("%d %.2lfn", res[i].id, res[i].w);
	
    return 0;
}

os：树剖？emmm，lca，你就拿这个考验选手，那个选手经不起这样的考验

思路
dfs处理一下各个点的祖先和从根节点到 u 结点的点权和。
u != v时：res_u,v = sum[u] + sum[v] - sum[fa] * 2 + w[fa]
u == v时：res_u,v = sum[u] - sum[fa]

#include
#define ll long long
using namespace std;

const int maxn = 1e5;
vector ma[maxn];
int w[maxn];
int f[maxn][21];
int dep[maxn];

void dfs(int u, int fa){
	w[u] = w[fa] + ma[u].size();
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for(int i = 1; i < 21; i++) f[u][i] = f[f[u][i-1]][i-1];
	for(auto v : ma[u]){
		if(v == fa) continue;
		dfs(v, u);
	}
}

int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	if(x == y) return f[y][0];
	for(int i = 20; i >= 0; i--){
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	}
	for(int i = 20; i >= 0; i--){
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[y][0];
}

int main(){
	
	
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n; i++){
		int x, y;
		cin >> x >> y;
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	
	dfs(1, 0);
	
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		int fa = lca(x, y);
		if(x != y) cout << w[x] + w[y] - 2 * w[fa] + ma[fa].size() << endl;
		else cout << w[x] - w[fa] << endl;
	}
	
    return 0;
}

os：擦，这不是高中的题，不记得了

思路
通过角速度和线速度的关系推到，可以发现，边上两个轮的半径比就是前后角速度的比。
多次查询，肯定要预处理。
如何能快速的处理出来任意两个轮子的半径比。
我当时用的是 n * n^0.5 的写法。但是可以在调和级数(n * log)的时间复杂度内解决。
n * n^0.5 的写法：

#include
#define ll long long
using namespace std;

const int maxn = 2e6 + 5;
int r[maxn], v[maxn], res[maxn];

int main(){
	
	int n, q;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &r[i]), v[r[i]]++;
	
	for(int i = 1; i <= n; i++){
		for(int j = 2; j * j <= r[i]; j++){
			if(r[i] % j == 0){
				if(v[j]) res[r[i]/j] = 1;
				if(v[r[i]/j]) res[j] = 1;
			}
		}
		if(v[r[i]] > 1) res[1] = 1;
	}
	if(v[1]){
		for(int i = 1; i <= n; i++) res[r[i]] = 1;
	}
	
	while(q--){
		int x;
		cin >> x;
		if(x > 2e5 || res[x] == 0) cout << "NO" << endl;
		else cout << "YES" << endl;
	}
	
    return 0;
}

调和级数的写法

	for(int i = 1; i <= n; i++){
		if(v[i] == 0) continue;
		for(int j = 2*i; j <= n; j += i){
			if(v[j]){
				res[j/i] = 1;
			}
		}
		if(v[i] > 1) res[1] = 1;
	}

os：好难呀

思路
观察数据，会发现，这可能是一个大水题。
砖的重量不大，并且一个砖上放的砖头的重量和要小于这个砖。所以01背包即可。

ps：当时为了稳妥偏分，对于n比较小的情况作了二进制枚举，然后对于 n 比较大的情况写了dp。

#include
#define ll long long
using namespace std;

typedef struct Node{
	int v;
	int w;
} node;

node v[2005];

bool cmp(node A, node B){
	if(A.w == B.w) return A.v > B.v;
	return A.w < B.w;
}

int dp[2005*20];

int main(){
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> v[i].w >> v[i].v;

	sort(v+1, v+1+n, cmp);
	
	if(n <= 20){
		int res = 0;
		for(int k = 1; k <= (1<
			int sum = 0, val = 0;
			for(int i = 0; i < n; i++){
				if((k>>i) & 1){
					if(v[i].w >= sum){
						sum += v[i].w;
						val += v[i].v;
					}
					else break;
				}
			}
			res = max(res, sum);
		}
		cout << res << endl;
	}
	else{
		for(int i = 1; i <= n; i++){
			for(int j = v[i].w; j >= 0; j--){
				dp[j+v[i].w] = max(dp[j+v[i].w], dp[j] + v[i].v);
			}
		}
		int res = 0;
		for(int i = 1; i <= n*20; i++) res = max(res, dp[i]);
		cout << res << endl;
	}

    return 0;
}