【蓝桥杯】1024 第 2 场算法双周赛

新生【算法赛】 - 蓝桥云课 (lanqiao.cn)

#include <iostream>
using namespace std;
int main()
{
  printf("15");
  return 0;
}

铺地板【算法赛】 - 蓝桥云课 (lanqiao.cn)

只要面积乘积是\(6\)的倍数即可,特判一下宽和高

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

void solve() {
    
    i64 n,m;
    cin >> n >> m;
    
    if((n * m) % 6 == 0){
        if(n >= 2 && m >= 3 || n >= 3 && m >= 2){
            cout << "Yes\n";
            return ;
        }
    }

    cout << "No\n";
    
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

摆玩具【算法赛】 - 蓝桥云课 (lanqiao.cn)

把高度差处理出来排个序,从前面取\((n-1)-(m-1)\)个值即可,高度差大的我们直接在那里分开就能把大的丢掉了

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, m;
    cin >> n >> m;
    vector<int> a(n), ans;
    for (auto &i : a) cin >> i;

    for (int i = 1; i < n; i ++) {
        ans.push_back(a[i] - a[i - 1]);
    }

    i64 sum = 0;
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size() - m + 1; i ++)
        sum += ans[i];

    cout << sum << '\n';


    return 0;
}

通关【算法赛】 - 蓝桥云课 (lanqiao.cn)

本来当时都想到用队列做了,但是脑子抽了没想起优先队列

建好树后把第一个点放进优先队列里,在闯过关卡后就把这个关卡连着的关卡放进优先队列里,这样就能保证每次闯关从最小的关卡要求开始闯关

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

struct Node{
	int s,k;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,p;
    cin >> n >> p;
    vector<int> g[n + 1];
    vector<Node> info(n + 1);

    for(int i = 1;i <= n;i ++){
    	int f;
    	cin >> f >> info[i].s >> info[i].k;
    	g[f].push_back(i);
    }

    i64 ans = 0;
    priority_queue<PII, vector<PII>,greater<PII>> Q;
    Q.push({info[1].k,1});
    while(Q.size() && p >= Q.top().first){
    	auto [k,id] = Q.top();
    	Q.pop();

    	ans ++;
    	p += info[id].s;
    	for(auto i : g[id]){
    		Q.push({info[i].k,i});
    	}
    }

    cout << ans << '\n';
    return 0;
}

串门【算法赛】 - 蓝桥云课 (lanqiao.cn)(树的直径)

考察树的直径,之前一直没遇到过这种题,这次算是积累经验了

要保证每个点都要访问,就应该选择一条路作为正路,这样正路上的点就只要走一次即可,而正路上其他的分支都需要走进去又退出来一共走两次,所以我们开始可以将所有的路径乘\(2\)存下来,然后去找一条最长的路径也就是树的直径作为正路,然后前者减去后者即可

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

vector<vector<PII>> g;
vector<i64> d;

int n, c;

i64 D = 0;
i64 dfs(int u, int fa)
{
	i64 max1 = 0, max2 = 0;
	for (auto [v, w] : g[u]) {
		if (v == fa) continue;
		i64 dis = dfs(v, u) + w;
		if (dis > max1) max2 = max1, max1 = dis;
		else if (dis > max2) max2 = dis;
	}
	
	D = max(D, max1 + max2);

	d[u] = max1;
	return d[u];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	g.resize(n + 1);
	d.resize(n + 1);

	i64 ans = 0;
	for (int i = 1; i < n; i ++) {
		int x, y, w;
		cin >> x >> y >> w;
		ans += 2 * w;
		g[x].emplace_back(y, w);
		g[y].emplace_back(x, w);
	}

	dfs(1, 0);

	cout << ans - D << '\n';

	return 0;
}