SWOJ: /blog/24/6353cf688302fe4be9d03d0b

T1 暴龙的白菜

看似是个找规律，实际上是一个暴力模拟+前缀和。

先用预处理出长度为 $10^6$ 的数组 $s$（即题目中所描述的字符串），并计算其前缀和数组 $ss$，其中 $ss_i=ss_{i-1}+s_i$。对于每次询问给定的 $l,r$，输出 $ss_r-ss_{l-1}$ 即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1000010;

int s[N], ss[N], idx;
int num[10];
int t, l, r;

int num2char(int k) {
    int i = 0;
    while (k) {
        num[i] = k % 10;
        k /= 10, i ++;
    }
    return i-1;
}

int main() {
    int k = 1;
    while (idx <= 1000000) {
        int t = num2char(k);
        for (int i = 1; i <= k; ++i) {
            for (int j = t; idx <= 1000000 && j >= 0; --j)
                idx ++, s[idx] = num[j], ss[idx] = s[idx]+ss[idx-1];
        }
        k ++;
    }

//  for (int i = 1; i <= 55; ++i) cout << s[i];
//  cout << endl;

    scanf("%d", &t);
    while (t -- ) {
        scanf("%d%d", &l, &r);
        int sum = ss[r]-ss[l-1];
        printf("%d\n", sum);
    }
    return 0;
}

T2 So What Do We Do Now?

题目所求的是让每颗子树的极差最小。由于当子树内的数为连续正整数时，该子树的极差最小，为该子树的大小减 $1$. 所以我们可以以 dfs 序给每个节点赋值。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

usingnamespacestd;

constint N = 1e6+10;

int n, m, cnt;
int h[N], e[N*2], ne[N*2], idx;
bool vis[N];
int ans[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx, idx ++;
}

void solve(int u) {
    vis[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i]) if (!vis[e[i]]) solve(e[i]);
    ans[u] = cnt, cnt --;
}

int main() {
    scanf("%d", &n); cnt = n;
    for (int i = 1; i <= n; ++i) h[i] = -1;
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }

    solve(1);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return0;
}

T3 半岛铁盒

看到题目中有“最小的 $x\ge 1$”，可以猜想我们要使用二分；另外题目还说“无论初始点权如何”，所以我们可以考虑极限情况，即一个点的权值为无穷大，而其余点的权值为 $0$.

题目中提到，对于两个相邻的节点 $i,j$，有 $\dfrac{\min(w_i,w_j)}{\max(w_i,w_j)}\le \dfrac{1}{x}=y$.

设 $u$ 号节点的权值为无穷大，且重新分配后其权值仍然是最大的，那么对于任意与 $u$ 号节点相邻的节点 $i$，必定有 $w’_i\le w’_u\times y$，再接着向下推，对于任意与 $i$ 号节点相邻的节点 $j$，一定有 $w’_j\le w’_u\times y^2$，以此类推。

将所有点的权值加起来，得到一个不等式：

$$\sum_{i\ge 0} a_iy^i\le \dfrac{q}{p}$$

其中，$a_i$ 表示与 $u$ 距离为 $i$ 的顶点数量。特别地，$a_0=1$（$u$ 到自身距离为 $0$）。$a_i$ 可以通过 $\texttt{bfs}$ 求出。

由于左侧关于 $y$ 单调递增，所以可以二分求解。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e3+10, M = 6e4+10;
const double eps = 1e-15;

int n, m, p, q;
double ans = 0;
int h[N], ne[M], e[M], idx;
int d[N], a[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

double quick_pow(double a, int b) {
    double res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

void bfs(int u) {
    queue<int> q;
    q.push(u);
    memset(a, 0, sizeof a), memset(st, 0, sizeof st);
    a[0] = 1, d[u] = 0, st[u] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                d[j] = d[t]+1;
                st[j] = 1;
                a[d[j]] ++;
                q.push(j);
            }
        }
    }
}

bool check(double mid) {
    double sum = 0;
    for (int i = 0; a[i]; ++i) {
        sum += (double)a[i] * quick_pow(mid, i);
    }
    return (sum <= (double)q / p);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n; ++i) h[i] = -1;
    while (m -- ) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }

    for (int i = 1; i <= n; ++i) {
        bfs(i);
        double l = 0, r = 1.0;
        while (r - l >= eps) {
            double mid = (l + r) / 2.0;
            if (check(mid)) l = mid;
            else r = mid;
        }
        ans = max(ans, 1.0 / l);
    }

    printf("%.7f\n", ans);
    system("pause");
    return 0;
}