codeforces round 635 div2题解

codeforces round 635 div2题解报告.

早上打的virtual

A - Ichihime and Triangle

题意: 给你a, b, c, d, 让你找到再之间三个区间内的三角形数

题解: 找两边相同即可

1
2
3
4
R = lambda : map(int, input().split())
for _ in range(int(input())) :
    a, b, c, d = R()
    print(b, c, c)

B - Kana and Dragon Quest game

题意: 将一个数进行向下取整减半再加10, 或者减10, 问能够将数在限制内得到小于等于0

题解: 贪心地想,先进行第一种操作, 到不能使数更小, 则用第二种操作

1
2
3
4
5
6
7
8
9
10
11
12
R = lambda : map(int, input().split())
for _ in range(int(input())) :
    x, n, m = R()
    while x > 0 and n :
        if x // 2 + 10 > x :
            break
        x = x // 2 + 10
        n -= 1
    while x > 0 and m :
        x -= 10
        m -= 1
    print("YES" if x <= 0 else "NO")

C - Linova and Kingdom

题意: 给你一棵树, 一个节点被标记后得到地贡献是到根上未被标记地节点数量, 问你整棵树的值

题解: 首先, 容易得到最优情况下, 一个未被标记的节点,他的父亲也不会被标记. 反向思考, 先假设所有节点都被标记, 当取消一个节点的标记, 值的变动就是减去节点所有父亲, 加上节点子树大小, 因此, 记录下来贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-17 08:07:53
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 2e5 + 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;

vector<int> g[Ma];
int son[Ma], val[Ma];
void dfs(int u, int fa, int dp) {
	rap (i, g[u]) if (i != fa) {
		dfs(i, u, dp + 1);
		son[u] += son[i] + 1;
	}
	val[u] = son[u] - dp;
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int n, k; cin >> n >> k;
	rep (i, n - 1) {
		int u, v; cin >> u >> v;
		g[u].ep(v); g[v].ep(u);
	}
	dfs(1, -1, 0);
	nth_element(val + 1, val + k + 1, val + n + 1);
	cout << accumulate(val + k + 1, val + n + 1, 0ll) << endl;
    
    return 0;
}

D - Xenia and Colorful Gems

题意: 给你三种颜色的宝石, 让你从三种颜色中各挑一个, 得到x, y, z, \((x-y)^2+(y-z)^2+(z-x)^2\)最小

题解: 假设 x <= y <= z, 那么固定y, x就是对应序列中最大的小于y的宝石, z就是对应序列中最小的不小于y的宝石

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const ll inf = 0x3f3f3f3f3f3f3f3f;

ll ans;

ll pw(int t) {
	return 1ll * t * t;
}

void solve(const vector<int>& r, const vector<int>& g, const vector<int>& b) {
	rap (i, g) {
		auto tr = lower_bound(seg(r), i), tb = upper_bound(seg(b), i);
		if (tr == r.end() or tb == b.begin()) continue;
		--tb; cmin(ans, pw(*tr - i) + pw(i - *tb) + pw(*tr - *tb));
	}
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; cin >> T;
	while (T--) {
		int r, g, b; cin >> r >> g >> b;
		vector<int> R(r), G(g), B(b);
		rap (i, R) cin >> i;
		rap (i, G) cin >> i;
		rap (i, B) cin >> i;
		sort(seg(R)), sort(seg(G)), sort(seg(B));
		ans = inf;
		solve(R, G, B), solve(R, B, G);
		solve(G, R, B), solve(G, B, R);
		solve(B, G, R), solve(B, R, G);
		cout << ans << endl;
	}
    
    return 0;
}

E - Kaavi and Magic Spell

题意: 给你一个s串和前缀t串, 有一个空串a, 可以挨个将si放入a的前面或后面, 问你能得到多少种有t前缀的a字符串的方案

题解: 设dp[i][j] 为能满足t[i..j], 根据每次将si插入首或尾, 区间dp即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int Ma = 3300, inf = 0x3f3f3f3f, mod = 998244353;

int dp[Ma][Ma];
char s[Ma], t[Ma];

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	cin >> s >> t; int n = strlen(s), m = strlen(t);
	fep (i, 1, n + 2) dp[i][i - 1] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int l = 1; l < n - i + 2; ++l) {
			int r = l + i - 1;
			if (s[i - 1] == t[l - 1] or !t[l - 1])
				(dp[l][r] += dp[l + 1][r]) %= mod;
			if (s[i - 1] == t[r - 1] or !t[r - 1])
				(dp[l][r] += dp[l][r - 1]) %= mod;
		}
	}
	ll ans = 0;
	fep (i, m, n + 1) (ans += dp[1][i]) %= mod;
	cout << ans << endl;
    
    return 0;
}

F - Yui and Mahjong Set

Comments

⬆︎TOP