https://ac.nowcoder.com/acm/contest/3005

题解 https://ac.nowcoder.com/discuss/365889?type=101&order=0&pos=1&page=2

F. 树上博弈

 

题意：一棵树上两个人轮流走，不能走到对方在的点上，先不能走的人输，问有几种开局情况先手胜。

树形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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    } while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
int to[maxn << 1], nx[maxn << 1], st[maxn], tot;
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
int dn[maxn][2], fu[maxn][2];
void dfs1(int u, int _fa) {
    for (int i = st[u]; i;i=nx[i]) {
        int v = to[i];
        if (v == _fa)continue;
        dfs1(v, u);
        dn[u][0] += dn[v][1];
        dn[u][1] += dn[v][0] + 1;
    }
}
void dfs2(int u, int _fa) {
    for (int i = st[u]; i; i = nx[i]) {
        int v = to[i];
        if (v == _fa)continue;
        fu[v][0] += fu[u][1] + dn[u][1] - dn[v][0] - 1;
        fu[v][1] += fu[u][0] + 1 + dn[u][0] - dn[v][1];
        dfs2(v, u);
    }
}
int main() {
    n = read();
    for (int i = 2; i <= n; i++) {
        int p;
        p = read();
        add(i, p);
        add(p, i);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += fu[i][0] + dn[i][0];
    }
    cout << ans << endl;
    return 0;
}

 

G. 音乐鉴赏

 

题意：每个人有平时分，期末分数随机，问期末分数占比多少，能使得优秀率期望（大于90分）恰好为 10%10\%。

二分

题目比较难懂，优秀率期望是每个人达到90分以上的概率的平均值。

每个人优秀的概率为 1−90−(1−x)⋅aix⋅1901-\frac{90-(1-x)\cdot a_i}{x}\cdot \frac{1}{90}。求和后取平均值就是期望。是个单调函数。可以二分。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const double eps = 1e-8;
int n;
int a[maxn];
double check(double x) {
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (90.0 - (1 - x)*1.0*a[i]);
    }
    ans /= (90.0 * n * x);
    ans = 1 - ans;
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    double L = 0, R = 1;
    while (R - L > eps) {
        double mid = (L + R) / 2;
        if (check(mid) > 0.1)L = mid;
        else R = mid;
    }
    printf("%.2lf%%\n", L*100.0);
    return 0;
}

 

H. 坐火车

 

树状数组

题意：牛牛同学在车上，车上有 nn 个车厢，每一个车厢有一种颜色。 他想知道对于每一个正整数 $ x\in [1,\ n]$ ，集合 {(i, x, j) ∣ i<x<j, lx≤coli=colj≤rx}\{ (i,\ x,\ j)\ |\ i < x < j,\ l_x \le col_i = col_j \le r_x \} 中包含多少个元素。 换句话说，就是要求每一个车厢两边有多少对颜色相同的车厢，并且这一对车厢的颜色要在 lxl_x 到 rxr_x 之间。其中 colicol_i 代表 ii 号车厢的颜色，lx,rxl_x,r_x 代表颜色的限制。

每种颜色在当前车厢左右两边的数量可以动态更新，相同颜色的对数也可以在遍历的同时更新。把 lx,rxl_x,r_x 看作区间左右端点，就是区间和。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
int col[maxn], l[maxn], r[maxn];
ll sum[maxn], a[maxn], b[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int x, ll b) {
    for (int i = x; i < maxn; i += lowbit(i)) {
        sum[i] += b;
    }
}
ll query(int r) {
    ll ans = 0;
    for (int i = r; i > 0; i -= lowbit(i)) {
        ans += sum[i];
    }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &col[i], &l[i], &r[i]);
        b[col[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        b[col[i]]--;
        add(col[i], -a[col[i]]);
        printf("%lld%s", query(r[i]) - query(l[i] - 1), i == n ? "\n" : " ");
        add(col[i], b[col[i]]);
        a[col[i]]++;
    }
    return 0;
}

 

I. 匹配星星

 

题意： 天上有 nn 颗星星，每颗星星有二维坐标 (xi,yi)(x_i, y_i)，还有一个属性值 ziz_i，若两颗星星A, B满足 xA<xBx_A < x_B且 yA<yBy_A < y_B 且 zA<zBz_A < z_B，则这两颗星星可以配成一对，每颗星星最多只能在一对之中，求最多能配成多少对星星。

1≤n≤1051≤n≤10^5
0≤xi,yi≤1090 \le x_i, y_i \le 10^9
zi∈{0,1}z_i \in \{0, 1\}

贪心

每个为1的点和x，y比它小且y最大的0点匹配。

排序后二分找到x比它小的里面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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
struct X
{
	int x, y, z;
	bool operator<(const X& b) {
		return x == b.x ? z < b.z : x < b.x;
	}
}a[maxn];
multiset<int>st;
queue<X>q;
int ans;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
	}
	sort(a, a + n);
	multiset<int>::iterator it;
	for (int i = 0; i < n; i++) {
		if (a[i].z == 0)q.push(a[i]);
		else {
			while (!q.empty() && q.front().x < a[i].x) {
				st.insert(q.front().y);
				q.pop();
			}
			if ((it = lower_bound(st.begin(), st.end(), a[i].y)) != st.begin())st.erase(--it), ans++;
		}
	}
	cout << ans << endl;
	return 0;
}