壊すとword│E-olv

menu icon

CodeChef FEB16月赛

2016.02.26 13:56 Fri| 3 visits oi_2016| 2016_刷题日常| Text

CHEFDETE Chef-Detective

输出所有的叶子结点，傻题是也。

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

int n, cnt[100005];

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 main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        ++cnt[read()];
    for (int i = 1; i <= n; ++i)
        if (!cnt[i]) printf("%d ", i);
    return 0;
}

STROPR Chef and Strange Operations

单独计算序列中的每一个数对于答案的贡献，傻不拉叽的组合数各种推。讲道理还不是那么好推吧。

 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 P 1000000007

int test, n, x;
long long m, inv[100005], a[100005], c[100005];

inline long long read()
{
    long long 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 main()
{
    inv[1] = 1;
    for (int i = 2; i <= 100000; ++i)
        inv[i] = inv[P % i] * (P - P / i) % P;
    cin >> test;
    while (test--)
    {
        cin >> n >> x >> m;
        for (int i = 1; i <= n; ++i)
            a[i] = read() % P;
        c[0] = 1;
        for (int i = 1; i < x; ++i)
            c[i] = ((m - 1) % P * inv[i] % P + 1) * c[i - 1] % P;
        long long ans = 0;
        for (int i = 1; i <= x; ++i)
            ans = (ans + a[i] * c[x - i]) % P;
        cout << ans << endl;
    }
    return 0;
}

DEVLDISC Devu and a light discussion

构造题。先构造出来一个四元环，在上面挑一个点作为起点。之后在另外三个点上各连出来一个爪，一共消耗结点数为7。当节点数变多的时候，再继续往出连爪就好了。当节点数小于7的时候，手画半天发现无解。

 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;

int test, n;

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        if (n <= 6)
        {
            puts("-1");
        }
        else
        {
            printf("%d\n", n);
            puts("1 2\n1 3\n2 4\n3 4\n2 5\n3 6");
            for (int i = 7; i <= n; ++i)
                printf("4 %d\n", i);
            puts("1");
        }
    }
    return 0;
}

RECTLOVE Rectangles of Love

纯粹傻题一道。开始的时候读错题以为选出的矩形必须在整个矩形的边缘，后来调试了好久发现我就是一只勤劳的逗逼。

 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;

int test, n, m, k;
long long pos;

int main()
{
    ios::sync_with_stdio(false);
    cin >> test;
    while (test--)
    {
        cin >> n >> m >> k;
        long double ans = 0, x, y;
        for (int i = 1; i <= k; ++i)
            cin >> pos, x = (pos - 1) / m + 1, y = (pos - 1) % m + 1,
            ans += x*(n-x+1)/n/(n+1)*y*(m-y+1)/m/(m+1)*4;
        cout << fixed << setprecision(10) << ans << endl;
    }
    return 0;
}

SEATL Sereja and Two Lines

谜之时间复杂度。分别考虑每一种颜色，求出它所有出现次数最多的行和列，然后枚举行和列的组合方式，判断它是否同时出现在交点处。

算时间复杂度吧！首先我们用O(NM)的时间遍历了好几遍矩阵。之后枚举每一种颜色出现次数最多的行和列。由于当找到一个异色交叉点就会退出循环，而我们枚举的交叉点两两不同，所以最坏情况下也只会将所有点遍历一遍，时间复杂度O(NM)。

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

#define N 1000005

int test, n, m, cnt[N], mc1[N], mc2[N];
vector<int> a[N], v1[N], v2[N];

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 main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            a[i].resize(m + 1);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                a[i][j] = read();
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
                ++cnt[a[i][j]];
            for (int j = 1; j <= m; ++j)
            {
                int t = a[i][j];
                if (cnt[t] > mc1[t]) mc1[t] = cnt[t], v1[t].clear();
                if (cnt[t] == mc1[t]) v1[t].push_back(i);
                cnt[t] = 0;
            }
        }
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
                ++cnt[a[j][i]];
            for (int j = 1; j <= n; ++j)
            {
                int t = a[j][i];
                if (cnt[t] > mc2[t]) mc2[t] = cnt[t], v2[t].clear();
                if (cnt[t] == mc2[t]) v2[t].push_back(i);
                cnt[t] = 0;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                int t = a[i][j], flag = 1;
                for (int k = 0; k < (int)v1[t].size(); ++k)
                    for (int l = 0; l < (int)v2[t].size(); ++l)
                        if (a[v1[t][k]][v2[t][l]] != t) { flag = 0; break; }
                ans = max(ans, mc1[t] + mc2[t] - flag);
                v1[t].clear(), v2[t].clear(), mc1[t] = mc2[t] = 0;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

MTMXSUM Matrix Maximum Sum

发现生成矩阵的公式里面含有 i 和 j，我们不妨将式子做一下变形，发现 i 和 j 只需要在读入的时候顺便加进 Ai 和 Bj 里面就可以了。

于是现在我们需要求出对于每一个 K，所有 K*K 矩阵内的最大值之和。发现 A 和 B 两个序列可以分开计算最大值，最后直接相乘即可。

单独考虑一个序列，它在 K 递增的时候，依次变成下面的样子：

5 8 6 9

8 8 9

8 9

9

好像一个三角形的样子。考虑某一个 Ai 的出现次数，在最下层一定为一次，之后依次增大为两次、三次……直到旁边更大的元素（或边界）来将其覆盖，之后维持出现次数不变。当它遇到另一边的更大元素时，次数又会开始减小直到 0。

用单调栈扫一下，预处理出每一个元素两边更大的元素位置，之后递推一下就可以了。最终当两个序列的答案合并时直接相乘即可。

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

#define mod 1000000007
#define N 100005

int n, a[N], b[N], ans1[N], ans2[N];

inline void solve(int re[], int a[])
{
    stack<int> s;
    int l[N] = {0}, r[N] = {0};
    for (int i = 1; i <= n; ++i)
    {
        while (!s.empty() && a[i] > a[s.top()]) s.pop();
        l[i] = s.empty() ? i - 1 : i - s.top() - 1, s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = n; i >= 1; --i)
    {
        while (!s.empty() && a[i] >= a[s.top()]) s.pop();
        r[i] = s.empty() ? n - i : s.top() - i - 1, s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 1; i <= n; ++i)
    {
        re[1] = (re[1] + a[i]) % mod;
        re[l[i] + 2] = (re[l[i] + 2] - a[i] + mod) % mod;
        re[r[i] + 2] = (re[r[i] + 2] - a[i] + mod) % mod;
        re[l[i] + r[i] + 3] = (re[l[i] + r[i] + 3] + a[i]) % mod;
    }
    for (int upd = 0, i = 1; i <= n; ++i)
    {
        upd = (upd + re[i]) % mod;
        re[i] = (re[i - 1] + upd) % mod;
    }
}

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 main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read() + i;
    solve(ans1, a);
    for (int i = 1; i <= n; ++i)
        b[i] = read() + i;
    solve(ans2, b);
    for (int i = 1; i <= n; ++i)
        printf("%lld ", 1ll * ans1[i] * ans2[i] % mod);
    return 0;
}

CALLSCHE Call Center Schedule

网络流傻题，建图有点麻烦？题解忘记了考虑 N 的情况？还需要特判开会太多使得有人吃不上饭或者工作超时的情况。

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

#define N 20000
#define M 1000000
#define inf 0x3f3f3f3f

int test, p, ds, h, n, lt, rt;
int f[75][75][75], mee1[75][75], mee2[75][75];
int s, t, head[N], cnt, d[N];

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

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;
}

queue<int> q;

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) 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, inf);
    return re;
}

inline int daypos(int x, int y) { return p + (x - 1) * ds + y; }
inline int lunpos(int x, int y) { return p + p * ds + (x - 1) * ds + y; }
inline int clipos(int x, int y) { return p + 2 * p * ds + (x - 1) * h + y; }
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 main()
{
    cin >> test;
    while (test--)
    {
        memset(head, 0, sizeof head), cnt = 1;
        memset(mee1, 0, sizeof mee1);
        memset(mee2, 0, sizeof mee2);
        cin >> p >> ds >> h >> n;
        s = 0, t = p + 2 * p * ds + ds * h + 1;
        for (int i = 1; i <= p; ++i)
            add(s, i, read());
        cin >> lt >> rt;
        int sum = 0;
        for (int x, i = 1; i <= ds; ++i)
            for (int j = 1; j <= h; ++j)
                x = read(), sum += x, add(clipos(i, j), t, x);
        for (int i = 1; i <= p; ++i)
            for (int j = 1; j <= ds; ++j)
                for (int k = 1; k <= h; ++k)
                {
                    f[i][j][k] = read();
                    if (k >= lt && k <= rt) mee2[i][j] += f[i][j][k] ^ 1;
                    mee1[i][j] += f[i][j][k] ^ 1;
                }
        for (int i = 1; i <= p; ++i)
            for (int j = 1; j <= ds; ++j)
            {
                if (mee1[i][j] > n || mee2[i][j] > rt - lt)
                    { puts("No"); goto end; }
                add(i, daypos(i, j), n - mee1[i][j]),
                add(daypos(i, j), lunpos(i, j), rt - lt - mee2[i][j]);
                for (int k = 1; k <= h; ++k)
                    if (f[i][j][k] && k >= lt && k <= rt)
                        add(lunpos(i, j), clipos(j, k), 1);
                    else if (f[i][j][k])
                        add(daypos(i, j), clipos(j, k), 1);
            }
        puts(dinic() == sum ? "Yes" : "No");
        end:;
    }
    return 0;
}

SEAPERMS Sereja and Permutations

先不考虑修改，我们可以在 O(N^2) 的时间内求出这道题的答案。

将所有元素排一个序，从小到大依次把元素们往排列里面插。预处理出对于每一个元素，它能够被插在多少个小元素的后面，加上它还可以被插在最前面，很容易就可以算出来方案数。

之后对于一个修改，同样可以在 O(N) 之内处理。

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

#define N 200005
#define mod 1000000007

int n, d, m, a[N], p[N], v[N], inv[N], sum[N], cnt[N];
long long ans = 1ll;
vector<int> b;

void del(int x)
{
    ans = ans * inv[sum[x] + cnt[x]] % mod, --cnt[x];
    for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j)
        ans = ans * inv[sum[j] + cnt[j]] % mod * sum[j] % mod, --sum[j];
}

void ins(int x)
{
    ++cnt[x], ans = ans * (sum[x] + cnt[x]) % mod;
    for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j)
        ++sum[j], ans = ans * inv[sum[j]] % mod * (sum[j] + cnt[j]) % mod;
}

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 main()
{
    cin >> n >> d;
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    for (int i = 1; i <= n; ++i)
        b.push_back(a[i] = read());
    cin >> m;
    for (int i = 1; i <= m; ++i)
        p[i] = read(), b.push_back(v[i] = read());
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int x, i = 1; i <= n; ++i)
    {
        ++cnt[x = lower_bound(b.begin(), b.end(), a[i]) - b.begin()];
        for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j)
            ++sum[j];
    }
    for (int i = 0; i < (int)b.size(); ++i)
        for (int j = 1; j <= cnt[i]; ++j)
            ans = ans * (sum[i] + j) % mod;
    for (int i = 1; i <= m; ++i)
    {
        del(lower_bound(b.begin(), b.end(), a[p[i]]) - b.begin());
        ins(lower_bound(b.begin(), b.end(), a[p[i]] = v[i]) - b.begin());
        printf("%lld\n", ans);
    }
    return 0;
}

WRDSUM Weird Sum

神题，高精度取模，吓得我都写 Python 了。

首先考虑如何计算 $\sum_{i=1}^n i^k \mod P(n\le \sqrt[k]{10^{2016})}$。首先，P 是一个大质数，观察 k 次方和公式，分子的地方有一个 n，分母的地方不含 P，所以可以猜想 $\sum_{i=1}^P i^k \mod P=0$。于是我们直接将 n 对 P 取模不会有任何问题。

之后，我们用类似于组合数的东西预处理一个系数矩阵 coe，有公式 $\sum_{i=1}^n i^k = \sum_{i=1}^k coe[k][i]*{n+1\choose i+1}\mod P$。这样可以用 O(k^2) 的时间预处理，用 O(k) 的时间回答询问。

回到原题，我们可以发现，所有的无次方因子数的 F 值都是本身，而其他的数的 F 值等于其开方后的 F 值。我们不妨枚举 k，计算所有含有 k 次方因子且不含更高次方因子的数对答案的贡献。首先，k 不会大于 7000。我们可以预处理出 8000 项以内的莫比乌斯函数，之后进行容斥。

 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
mod = 998244353

coe = [[0], [0, 1]]

for i in range(2, 500):
    p = [0]
    for j in range(1, i):
        p.append((coe[-1][j - 1] + coe[-1][j]) * j % mod)
    p.append(coe[-1][-1] * i % mod)
    coe.append(p)

inv = [0, 1]
for i in range(2, 8000):
    inv.append(inv[mod % i] * (mod - mod / i) % mod)

def power_sum(n, k):
    if (k >= 500):
        re = 0
        for i in range(2, n + 1):
            re = (re + pow(i, k, mod)) % mod
        return re
    re = 0
    n = n % mod
    pa = (n + 1) % mod
    for i in range(1, k + 1):
        pa = pa * (n + 1 - i + mod) * inv[i + 1] % mod
        re = (re + coe[k][i] * pa) % mod
    return (re - 1 + mod) % mod

p = []
mu = [0 for i in range(8000)]
vis = [0 for i in range(8000)]

mu[1] = 1;
for i in range(2, 8000):
    if (vis[i] == 0):
        p.append(i); mu[i] = -1
    for j in p:
        if (i * j >= 8000): break
        vis[i * j] = 1
        if (i % j): mu[i * j] = -mu[i]
        else: mu[i * j] = 0; break

for test in range(int(raw_input())):
    n = int(raw_input())
    arr = [0, n]
    p = 0
    base = 1
    while (base < n):
        base *= 2; p += 1
    for i in range(2, p):
        l = 2
        r = arr[-1]
        ans = 0
        while (l <= r):
            mid = (l + r) / 2
            if (mid ** i <= n):
                l = mid + 1; ans = mid
            else:
                r = mid - 1
        arr.append(ans)

    ans = 0
    for i in range(1, len(arr)):
        cadd = power_sum(arr[i], 1)
        for j in range(2, 8000):
            aidx = i * j
            if (aidx >= len(arr)):
                break
            cadd += mu[j] * power_sum(arr[aidx], j)
        ans = (ans + cadd) % mod
    print ans
Newer