Chaos Slover 补档计划 - 树与数

2015.12.02 17:32 Wed| 7 visits oi_2016| ChaosSlover补档计划| Text

BZOJ1977 [BeiJing2010组队]次小生成树 Tree

jkxing 的 PPT 里东西可真是杂啊……不知道怎么想的叫做【树与数】。

求严格的次小生成树,需要预处理出每一段中边权的最大值和次大值。之后枚举每一条非树边,替换掉链上的权值最大且小于这条边的边权的边。

  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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;

#define M 300005
#define N 100005
#define inf 0x3f3f3f3f

int n, m, f[N], vis[M];
int head[N], deep[N], fa[N][17], val[N][17], val2[N][17];

struct data
{
    int x, y, w;
    bool operator <(const data &p) const { return w < p.w; }
} p[M];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

long long kruscal()
{
    long long re = 0;
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int fx = find(p[i].x), fy = find(p[i].y);
        if (fx == fy) continue;
        f[fy] = fx; vis[i] = 1;
        add(p[i].x, p[i].y, p[i].w);
        add(p[i].y, p[i].x, p[i].w);
        re += p[i].w;
    }
    return re;
}

void dfs(int x)
{
    deep[x] = deep[fa[x][0]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x][0])
            fa[edge[i].to][0] = x, val[edge[i].to][0] = edge[i].val,
            dfs(edge[i].to);
}

void getval()
{
    for (int j = 1; j <= 16; ++j)
        for (int i = 1; i <= n; ++i)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            val[i][j] = max(val[i][j - 1], val[fa[i][j - 1]][j - 1]);
            if (val[i][j - 1] == val[fa[i][j - 1]][j - 1])
                val2[i][j] = max(val2[i][j - 1], val2[fa[i][j - 1]][j - 1]);
            else
                val2[i][j] = max(min(val[i][j - 1], val[fa[i][j - 1]][j - 1]),
                    max(val2[i][j - 1], val2[fa[i][j - 1]][j - 1]));
        }
}

int lca(int x, int y)
{
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 16; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 16; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int getans(int x, int y, int z)
{
    int l = lca(x, y), re = 0, re2 = 0;
    for (int i = 16; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[l])
        {
            if (val[x][i] == re)
                re2 = max(re2, val2[x][i]);
            else
                re2 = max(min(re, val[x][i]), max(re2, val2[x][i]));
            re = max(re, val[x][i]);
            x = fa[x][i];
        }
    for (int i = 16; i >= 0; --i)
        if (deep[fa[y][i]] >= deep[l])
        {
            if (val[y][i] == re)
                re2 = max(re2, val2[y][i]);
            else
                re2 = max(min(re, val[y][i]), max(re2, val2[y][i]));
            re = max(re, val[y][i]);
            y = fa[y][i];
        }
    return z == re ? z - re2 : z - re;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        p[i].x = read(), p[i].y = read(), p[i].w = read();
    long long ans = kruscal(); int ans2 = 0x3f3f3f3f;
    dfs(1);
    getval();
    for (int i = 1; i <= m; ++i)
        if (!vis[i])
            ans2 = min(ans2, getans(p[i].x, p[i].y, p[i].w));
    cout << ans + ans2 << endl;
    return 0;
}

BZOJ3667 Rabin-Miller算法

Miller-Rabin 算法判定一个数是否是素数,加上 Rho 因数分解。

Rho 算法为随机化算法,期望时间复杂度 O(n^(1/4))。

至于乘法爆 long long 的问题呢,用我们用快速乘就会 TLE,我的代码大概用的是黄学长的乘法(其实这是错误的!错误的!)。黄学长判断了如果出现负数,就加上 p。其实这也是没有道理的呢!如果不考虑 long long 相乘爆 double,应该减去 0x8000…0000 才对。

算了,这题就算这么过了吧……

 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
#include <bits/stdc++.h>
using namespace std;

long long multi(long long a, long long b, long long p)
{
    long long tmp = (a * b - (long long)((long double)a * b / p + 1e-8) * p);
    return tmp < 0 ? tmp - 0x8000000000000000ll : tmp;
}

long long power(long long a, long long b, long long p)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = multi(re, a, p);
        a = multi(a, a, p); b >>= 1;
    }
    return re;
}

bool witness(long long a, long long n)
{
    long long u = n - 1; int t = 0;
    while (u % 2 == 0) ++t, u >>= 1;
    long long x = power(a, u, n);
    for (int i = 1; i <= t; ++i)
    {
        long long y = multi(x, x, n); 
        if (y == 1 && x != 1 && x != n - 1)
            return true;
        x = y;
    }
    if (x != 1) return true;
    return false;
}

bool miller_rabin(long long n, int s)
{
    if (n == 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 1; i <= s; ++i)
        if (witness(rand() % (n - 1) + 1, n))
            return false;
    return true;
}

long long pollard_rho(long long n)
{
    long long x = rand() % (n - 1) + 1;
    long long y = x; int k = 2, i = 1;
    while (true)
    {
        x = (multi(x, x, n) - 1 + n) % n;
        long long d = __gcd(abs(y - x), n);
        if (d != 1) return d;
        if (++i == k)
            y = x, k = k * 2;
    }
}

long long getans(long long n)
{
    if (n == 1) return 0;
    if (miller_rabin(n, 2)) return n;
    if (n % 2 == 0) return max(getans(n >> 1), 2ll);
    long long t = pollard_rho(n);
    while (t == n) t = pollard_rho(n);
    return max(getans(t), getans(n / t));
}

int test;
long long n;

int main()
{
    srand(20140355);
    cin >> test;
    while (test--)
    {
        cin >> n;
        if (miller_rabin(n, 2))
            puts("Prime");
        else
            cout << getans(n) << endl;
    }
    return 0;
}

BZOJ2048 [2009国家集训队]书堆

调和级数 1+1/2+1/3+…+1/n ≈ ln(n+1) + r,其中 r 为欧拉常数,约等于 0.5772156649015328。n 小暴力,n 大套公式。

书堆的长度为 m*(1/2+1/4+1/6+……+1/(2n))。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

long long n, m;
double sum;

int main()
{
    cin >> n >> m;
    if (n < 1000000)
        for (int i = 1; i <= n; ++i)
            sum += 1.0 / i;
    else
        sum = log(n + 1) + 0.5772156649015328;
    cout << (int)(sum * m / 2 - 1e-10) << endl;
    return 0;
}

BZOJ3000 Big Number

这作死的精度。我不想写题解了。

 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
#include <bits/stdc++.h>
using namespace std;

#define e 2.7182818284590452354
#define pi 3.14159265358979323846

long long n, k;

int main()
{
    while (cin >> n >> k)
    {
        if (n < 10000)
        {
            long double sum = 0;
            for (int i = 1; i <= n; ++i)
                sum += log(i);
            cout << (long long)(sum / log(k) + 1 + 1e-8) << endl;
        }
        else
        {
            cout << (long long)(trunc((n * log(n) - n + 0.5 * log(2 * pi * n)) / log(k)) + 1) << endl;
        }
    }
    return 0;
}

BZOJ4031 [HEOI2015]小Z的房间

关联矩阵:一个 n * n 的矩阵,第 i 行第 i 列的值为点 i 的度数,若 i, j 有边,则第 i 行第 j 列,第 j 行第 i 列为 -1。

Matrix-Tree 定理:关联矩阵的 n-1 阶主子式的行列式的值就是生成树的个数。

行列式求解:类似于高斯消元,用到了辗转相除的思想。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 105
#define mod 1000000000

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m, pos[15][15], d[N][N];
char str[15][15];

int det(int n, int d[N][N])
{
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            d[i][j] = (d[i][j] + mod) % mod;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            long long a = d[i][i], b = d[j][i];
            while (b)
            {
                long long t = a / b;
                a %= b, swap(a, b); ++cnt;
                for (int k = i; k < n; ++k)
                    d[i][k] = ((d[i][k] - t * d[j][k]) % mod + mod) % mod;
                for (int k = i; k < n; ++k)
                    swap(d[i][k], d[j][k]);
            }
        }
        if (!d[i][i]) return 0;
    }
    long long re = 1;
    for (int i = 0; i < n; ++i)
        re = re * d[i][i] % mod;
    re = cnt & 1 ? (mod - re) % mod : re;
    return re;
}

int main()
{
    cin >> n >> m;
    int tot = 0;
    memset(pos, -1, sizeof pos);
    for (int i = 1; i <= n; ++i)
        scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            pos[i][j] = (str[i][j] == '.' ? tot++ : -1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if (pos[i][j] == -1) continue;
            int cnt = 0;
            for (int k = 0; k < 4; ++k)
                if (pos[i + dx[k]][j + dy[k]] != -1)
                    d[pos[i][j]][pos[i + dx[k]][j + dy[k]]] = -1, ++cnt;
            d[pos[i][j]][pos[i][j]] = cnt;
        }
    cout << det(tot - 1, d) << endl;
    return 0;
}