TopCoder TCO2015

2016.03.01 13:49 Tue| 17 visits oi_2016| 2016_刷题日常| Text

1A250 Similars

预处理出区间内的整数包含不同数字的情况。接下来枚举每一个可能的数字集合,判断它的出现次数是否大于 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
#include <bits/stdc++.h>
using namespace std;

class Similars
{
public:
    int maxsim(int L, int R)
    {
        int calc[1024] = {0}, re = 0;
        for (int i = L; i <= R; ++i)
        {
            int now = 0, t = i;
            while (t) now |= 1 << (t % 10), t /= 10;
            if (i == 0) now = 1;
            ++calc[now];
        }
        for (int i = 0; i < 1024; ++i)
        {
            int cnt = 0;
            for (int j = 0; j < 1024; ++j)
                if ((i & j) == i) cnt += calc[j];
            if (cnt >= 2)
            {
                int now = 0;
                for (int j = 0; j < 10; ++j)
                    if (i & (1 << j)) ++now;
                re = max(re, now);
            }
        }
        return re;
    }
};

1A500 Autogame

可以发现,如果两个标记走了一会重合了,那么它们之后将会形影不离。先假定初始在每一个点上都放一个标记,用倍增处理出走 K 步之后,每一个点上分别有多少标记。如果一个点上出现了多个标记,那么这些标记在一开始最多只能放一个。不同的点之间互不影响,答案乘积即可。

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

class Autogame
{
public:
    int wayscnt(vector<int> a, int K)
    {
        int n = a.size();
        vector<int> _a;
        _a.resize(n);
        int size[55] = {0}, _size[55] = {0};
        for (int i = 1; i <= n; ++i)
            size[i] = 1; 
        while (K)
        {
            if (K & 1)
            {
                for (int i = 1; i <= n; ++i)
                    _size[a[i - 1]] += size[i];
                for (int i = 1; i <= n; ++i)
                    size[i] = _size[i], _size[i] = 0;
            }
            for (int i = 0; i < n; ++i)
                _a[i] = a[a[i] - 1];
            swap(a, _a); K >>= 1;
        }
        int re = 1;
        for (int i = 1; i <= n; ++i)
            re = 1ll * re * (size[i] + 1) % 1000000007;
        return re;
    }
};

1A1000 Revmatching

Hall结婚定理:对于一个二分图G,设点集中的两部分顶点组成的集合分别为X、Y,G中存在完美匹配的充要条件为X中的任意k个点至少与Y中的k个点相邻。

那么对于这道题而言,我们可以枚举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
#include <bits/stdc++.h>
using namespace std;

class Revmatching
{
public:
    int smallest(vector<string> A)
    {
        int n = A.size(), re = 0x3f3f3f3f;
        for (bitset<21> t = 1; !t.test(n); t = t.to_ulong() + 1)
        {
            int sum[21] = {0}, cnt = 0;
            for (int i = 0; i < n; ++i)
                if (t.test(i) && ++cnt)
                    for (int j = 0; j < n; ++j)
                        sum[j] += (A[i][j] - '0');
            sort(sum, sum + n), reverse(sum, sum + n);
            int now = 0;
            for (int i = cnt - 1; i <= n; ++i)
                now += sum[i];
            re = min(re, now);
        }
        return re;
    }
};

1B250 TheNicePair

乍一看好像codeforces有一道很类似的题。再一看这是一个sb暴力。

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

int v[1005], p[205], tot;

void getprime(int s)
{
    for (int i = 2; i <= s; ++i)
    {
        if (!v[i]) p[++tot] = i;
        for (int j = 1; i * p[j] <= s; ++j)
        {
            v[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}

class TheNicePair
{
public:
    bool check(vector<int> A, int l, int r)
    {
        for (int i = 1; i <= tot; ++i)
        {
            int cnt = 0;
            for (int j = l; j <= r; ++j)
                if (A[j] % p[i] == 0)
                    ++cnt;
            if (cnt >= (r - l) / 2 + 1) return true;
        }
        return false;
    }
    int solve(vector<int> A)
    {
        getprime(1000);
        int n = A.size(), re = -1;
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j)
                if (j - i > re && check(A, i, j))
                    re = j - i;
        return re;
    }
};

1B500 TheTips

对于每一个点,DFS一遍得到它被取到的概率,求和即得总期望。

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

int head[55], vis[55];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[2505];

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

double dfs(vector<int> v, int x, int t)
{
    vis[x] = t;
    double re = 1 - 1.0 * v[x] / 100;
    for (int i = head[x]; i; i = edge[i].next)
        if (vis[edge[i].to] != t)
            re *= dfs(v, edge[i].to, t);
    return re;
}

class TheTips
{
public:
    double solve(vector<string> clues, vector<int> probability)
    {
        int n = clues.size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (clues[i][j] == 'Y')
                    add(j, i);
        memset(vis, -1, sizeof vis);
        double ans = 0;
        for (int i = 0; i < n; ++i)
            ans += 1 - dfs(probability, i, i);
        return ans;
    }
};

1B1000 TheTreeAndMan

给一棵有根树,求树中小人的个数。(这道题还真是生动形象)

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

#define mod 1000000007
#define N 2005

int head[N], deep[N], size[N], p5[N], sp5[N], ans;

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

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

void dfs(vector<int> p, int x)
{
    if (x) deep[x] = deep[p[x - 1]] + 1;
    int cnt = 0;
    for (int i = head[x]; i; i = edge[i].next)
        dfs(p, edge[i].to),
        p5[x] = (p5[x] + 1ll * size[x] * size[edge[i].to]) % mod,
        cnt = (cnt + 1ll * size[edge[i].to] * size[x]) % mod,
        size[x] += size[edge[i].to];
    for (int i = head[x]; i; i = edge[i].next)
    {
        int t = 1ll * size[edge[i].to] * (size[x] - size[edge[i].to]) % mod;
        ans += 1ll * sp5[edge[i].to] * (cnt - t + mod) % mod * deep[x] % mod;
        ans %= mod, sp5[x] = (sp5[x] + sp5[edge[i].to]) % mod;
    }
    ++size[x], sp5[x] = (sp5[x] + p5[x]) % mod;
}

class TheTreeAndMan
{
public:
    int solve(vector<int> parent)
    {
        int n = parent.size();
        for (int i = 1; i <= n; ++i)
            add(parent[i - 1], i);
        dfs(parent, 0);
        return ans;
    }
};

1C250 DevuAndPlantingTrees

发现在一个格子里面种树,那么在它及它周围的两列都不能再种树了。另外发现格子的上下层其实是等价的,没什么用。于是可以贪心扫一遍了。

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

class DevuAndPlantingTrees
{
public:
    int maximumTreesDevuCanGrow(vector<string> garden)
    {
        int n = garden[0].size(), re = 0, tag[55] = {0};
        for (int i = 0; i < n; ++i)
            if (garden[0][i] == '*' || garden[1][i] == '*')
                ++re, tag[max(i - 1, 0)] = tag[i] = tag[i + 1] = true;
        for (int i = 0; i < n; ++i)
            if (!tag[i]) tag[i] = tag[i + 1] = true, ++re;
        return re;
    }
};

1C450 UnrelatedPaths

其实就是求叶子结点的个数。

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

class UnrelatedPaths
{
public:
    int maxUnrelatedPaths(vector<int> parent)
    {
        int n = parent.size(), vis[55] = {0};
        for (int i = 0; i < n; ++i)
            ++vis[parent[i]];
        int re = 0;
        for (int i = 0; i <= n; ++i)
            if (!vis[i]) ++re;
        return re;
    }
};

1C1000 DevuAndBeautifulSubstrings

给定漂亮的子序列个数,求序列的种类数。直接DP就好了,设f[x][y][z]表示对于长度为x的序列,最长后缀漂亮子序列长度为y且漂亮子序列总数为z的方案数。然后随便转移一下。

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

class DevuAndBeautifulSubstrings
{
public:
    long long val[55] = {0}, dp[55][55][1500] = {{{0}}};
    long long countBeautifulSubstrings(int n, int cnt)
    {
        dp[1][1][1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 2; j <= i; ++j)
                for (int k = 1; k <= i * (i - 1) / 2; ++k)
                    dp[i][j][k+j] += dp[i-1][j-1][k];
            for (int j = 1; j < i; ++j)
                for (int k = 1; k <= i * (i - 1) / 2; ++k)
                    dp[i][1][k+1] += dp[i-1][j][k];
        }
        long long re = 0;
        for (int i = 1; i <= n; ++i)
            re += dp[n][i][cnt];
        return re * 2;
    }
};

2A300 ModModMod

记录每一个答案的出现次数,随着不断按顺序枚举模数,更新次数即可。由于模数只有不断减小才会对答案造成影响,时间复杂度为 O(R)。

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

class ModModMod
{
public:
    int size[10000005] = {0};

    long long findSum(vector<int> m, int T)
    {
        for (int i = 1; i <= T; ++i)
            size[i] = 1;
        for (int i = 0; i < (int)m.size(); ++i)
            while (T >= m[i])
                size[T % m[i]] += size[T], --T;
        long long re = 0;
        for (int i = 1; i <= T; ++i)
            re += 1ll * size[i] * i;
        return re;
    }
};

2A600 FoxMeeting

一群狐狸要走到一起去。题目要求的是走最远的狐狸最短走多少,显然可以二分答案。

狐狸们一定会存在往一个结点聚集的趋势,我们设它们聚集的中心点是p。由于我们限制了狐狸的行走长度,所以可能会存在一些狐狸只能走到与p有一定距离的结点。既然它要和点p间接相连,那么我们需要保证在从它停止的结点到终点p的路径上充满狐狸。对于一个二分出的答案,我们枚举点p,再找出所有需要被充满的结点。如果这些结点与能够到达它们的狐狸可以形成匹配,那么说明当前答案可行。

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

int s, t, cnt, head[105], d[105];
queue<int> q;

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

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

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k, edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, 0x3f3f3f3f);
    return re;
}

class FoxMeeting
{
public:
    int n, mp[55][55], fa[55];
    vector<int> son[55];

    void getdist(vector<int> A, vector<int> B, vector<int> L)
    {
        memset(mp, 0x3f, sizeof mp);
        for (int i = 1; i <= n; ++i)
            mp[i][i] = 0;
        for (int i = 0; i < n - 1; ++i)
            mp[A[i]][B[i]] = mp[B[i]][A[i]] = L[i];
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    mp[j][k] = min(mp[j][k], mp[j][i] + mp[i][k]);
    }

    void dfs(int x)
    {
        for (int i = 0; i < (int)son[x].size(); ++i)
            if (son[x][i] != fa[x])
                fa[son[x][i]] = x, dfs(son[x][i]);
    }

    bool check(int len, int n, vector<int> foxes)
    {
        s = 0, t = n * 2 + 1;
        for (int root = 1; root <= n; ++root)
        {
            fa[root] = 0, dfs(root);
            int vis[55] = {0}, out = 0;
            for (int i = 0; i < (int)foxes.size(); ++i)
            {
                int p = foxes[i];
                while (mp[foxes[i]][p] <= len) p = fa[p];
                while (p) vis[p] = true, p = fa[p];
            }
            memset(head, 0, sizeof head), cnt = 1;
            for (int i = 1; i <= n; ++i)
            {
                if (!vis[i]) continue;
                add(s, i, 1), ++out;
                for (int j = 0; j < (int)foxes.size(); ++j)
                    if (mp[foxes[j]][i] <= len)
                        add(i, n + j + 1, 1);
            }
            for (int i = 0; i < (int)foxes.size(); ++i)
                add(n + i + 1, t, 1);
            if (dinic() == out) return true;
        }
        return false;
    }

    int maxDistance(vector<int> A, vector<int> B,
                    vector<int> L, vector<int> foxes)
    {
        n = A.size() + 1;
        for (int i = 0; i < n - 1; ++i)
            son[A[i]].push_back(B[i]),
            son[B[i]].push_back(A[i]);
        getdist(A, B, L);
        int l = 0, r = 5000000, re = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid, n, foxes)) r = mid - 1, re = mid;
            else l = mid + 1;
        }
        return re;
    }
};

2A950 TrianglePainting

神奇的定理,两个凸包按照题目叙述的方式合并等价于把组成它们的向量拎出来按顺序首尾相连形成的新凸包。这样我们就可以分别枚举两条边,计算贡献了。

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

class point
{
public:
    int id, x, y; double prob, t;
    point(int _id, int _x, int _y, int _prob)
    : id(_id), x(_x), y(_y), prob(1.0 * _prob / 100) { t = atan2(_y, _x); }
    bool operator <(const point &p) const { return t < p.t; }
};

class TrianglePainting
{
public:
    double expectedArea(vector <int> x1, vector <int> y1,
        vector <int> x2, vector <int> y2, vector <int> prob)
    {
        vector<point> v;
        int n = x1.size();
        for (int i = 0; i < n; ++i)
            if (x1[i] * y2[i] - x2[i] * y1[i] < 0)
                swap(x1[i], x2[i]), swap(y1[i], y2[i]);
        for (int i = 0; i < n; ++i)
            v.push_back(point(i, x1[i], y1[i], prob[i])),
            v.push_back(point(i, x2[i] - x1[i], y2[i] - y1[i], prob[i])),
            v.push_back(point(i, -x2[i], -y2[i], prob[i]));
        sort(v.begin(), v.end());
        double re = 0;
        for (int i = 0; i < (int)v.size(); ++i)
            for (int j = 0; j < i; ++j)
                re += (v[i].id == v[j].id ? 1 : v[j].prob) *
                        v[i].prob * (v[j].x * v[i].y - v[j].y * v[i].x);
        return re / 2;
    }
};