1019考试总结

1019考试总结

T2

​ 题目大意:

​ 随着川普的支持率逐日下降,让川普下台的呼声越来越大,国会被迫进行了一次表决,每一位议员都有权利选择支持川普还是反对川普,若反对的议员严格超过一半,则川普只能卸任。议员共N个,每个议员有两个属性:威望度Wi和忠诚度Hi。在表决的时候,每个议员支持川普的概率为Hi / 100。Kano拿出了K百万元,想要通过贿赂议员的方式来增加川普下台的可能性。每个议员每收下1百万元,那么他的忠诚度便会减少10,减少到0的时候就不可再减少了。即便这样,表决还是可能以支持的结果收场,那么Kano将派出刺客,暗杀所有投了支持票的议员。设所有投了支持票的议员的威望度总和为S,则成功暗杀的概率为A / (A+S)(A为常数)。若暗杀失败,则Kano也将会被捕。现在Kano想知道,在最优策略下,自己被捕的可能性是多少。N ,K <= 9

一看数据范围铁腚缩索。考试的时候没跑出来样例,瞎搜搜了个10pts,考后才完全明白题意。

​ 我们先把(K)百万元可能分配的方案数都搜出来,存到一个vector中。因为这些钱肯定都用完最优。然后我们枚举那些人支持那些人反对,那么川普没有下台的概率就是支持的那些人的概率乘上(1-不支持的那些人的概率)。如果说反对人数小于一半,那么就要派出刺客,也就是要计入答案。

​ 最后把所有的(K)百万元可能分配的方案得到的结果取最小值就好了。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 10;
int n, k, A;
double ans;
int bit[N];
vector <int> v;
struct people { int s, h; } a[N];

double calc(int s) {
    int tmp[N]; double res = 0;
    for(int i = 1;i <= n; i++) 
        tmp[i] = max(0, a[i].h - 10 * (s % 10)), s /= 10;  
    for(int i = 0;i < (1 << n); i++) {
        double tmp1 = 1; int tmp2 = 0, num = 0;
        for(int j = 1;j <= n; j++) {
            if((i & (1 << (j - 1)))) tmp1 *= 1.0 * tmp[j] / 100, num ++, tmp2 += a[j].s;
            else tmp1 *= (1 - 1.0 * tmp[j] / 100);
        }
        if(n - num < (n + 1) / 2) res = res + tmp1 * (1 - 1.0 * A / (A + tmp2));
    }
    return res;
}

void dfs(int x, int sum, int s) {
    if(x == n + 1) { if(sum == k) v.push_back(s); return ; }
    for(int i = 0;i <= k - sum; i++) dfs(x + 1, sum + i, s + i * bit[x - 1]); 
}

int main() {

    n = read(); k = read(); A = read(); ans = 1e9;
    bit[0] = 1;
    for(int i = 1;i <= 9; i++) bit[i] = bit[i - 1] * 10;
    for(int i = 1;i <= n; i++) 
        a[i].s = read(), a[i].h = read();
    dfs(1, 0, 0); 
    for(int i = 0;i < (int)v.size(); i++) ans = min(ans, calc(v[i]));
    printf("%.6lf", ans);

    fclose(stdin); fclose(stdout);
    return 0;
}

T3

​ 题目大意:给定一颗(n)个节点的树,每次给一个节点加一个数字(a),那么这个节点的所有祖先都要加上这个数字,问(m)次操作都做完后每个点不同的数字的个数。(n, m <= 1e5, a <= 1e9)

​ 正解树上查分。考场上拿bitset骗了80pts。机房里一个大佬线段树合并切了%%%。

​ 我们考虑将(m)次操作排序,以数字(a)为第一关键字,以dfs序(dfn[i])为第二关键字从小到大排序。为什么这么排序呢?假设现在要在两个节点上+a,那么为了避免重复,应该在他们的LCA上-a。以此类推,按dfs序排序后两两进行此操作就好了。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 1e5 + 5;
int n, m, cnt, tot, cnt1;
int d[N], fa[N][21], pos[N], dfn[N], dep[N], head[N];
struct cj { int x, y; } b[N];
struct edge { int nxt, to; } e[N];

void add(int x, int y) {
    e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; 
}

int cmp(cj a, cj b) {
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

void dfs(int x) {
    pos[dfn[x] = ++ tot] = x; 
    if(x != 0) dep[x] = dep[fa[x][0]] + 1;
    for(int i = head[x]; i ; i = e[i].nxt) dfs(e[i].to);
}

void dfs2(int x) {
    for(int i = head[x]; i ; i = e[i].nxt) 
        dfs2(e[i].to), d[x] += d[e[i].to];
}

void make_pre() {
    for(int i = 1;i <= 20; i++)
        for(int j = 0;j < n; j++) fa[j][i] = fa[fa[j][i - 1]][i - 1];
}

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

int main() {

    n = read(); m = read();
    for(int i = 1, x;i < n; i++) { x = read(); fa[i][0] = x; add(x, i); } 
    dfs(0);
    for(int i = 1, x;i <= m; i++) x = read(), b[i].y = read(), b[i].x = dfn[x];
    make_pre();
    sort(b + 1, b + m + 1, cmp);
    int pre = -1;
    for(int i = 1;i <= m; i++) {
        int x = pos[b[i].x];
        d[x] ++; 
        if(pre != -1) d[LCA(pre, x)] --;
        pre = x;
        if(i < m && b[i].y != b[i + 1].y) pre = -1;
    }
    dfs2(0);
    for(int i = 0;i < n; i++) printf("%d
", d[i]);
    return 0;
}
原文地址:https://www.cnblogs.com/czhui666/p/13843367.html