模拟赛 - NOI 模拟二

2015.12.12 17:48 Sat| 13 visits oi_2016| 2016_竞赛日常| Text

BZOJ2161 布娃娃

很简单的一道题,有两种解法:

  • 整体二分,很显然的解法,时间复杂度 O(N log N^2)。
  • 将修改按照左端点排序,询问按照 p 排序,然后从左往右扫一遍,维护一颗权值线段树,听起来很好写。时间复杂度 O(N log N)。

然而读入太过恶心了……我在写代码的时候写了一个 if 然后把这一段缩了起来……

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

#define N 100005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n;
int padd, pfirst, pmod, pprod, cadd, cfirst, cmod, cprod;
int ladd, lfirst, lmod, lprod, radd, rfirst, rmod, rprod;
int p[N], c[N], l[N], r[N], tag[N * 12], ans[N], pos[N], temp[N], sum;
vector<int> v, vp;
vector<int> d[N];

void insert(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y) { tag[pos] += z; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lson, l, mid, x, y, z);
    if (y > mid) insert(rson, mid + 1, r, x, y, z);
}

int query(int pos, int l, int r, int x)
{
    if (l == r) return tag[pos];
    int mid = (l + r) >> 1;
    if (x <= mid) return tag[pos] + query(lson, l, mid, x);
    else return tag[pos] + query(rson, mid + 1, r, x);
}

void change(int x, int y)
{
    for (int i = 0; i < (int)d[x].size(); ++i)
        insert(1, 0, pmod, l[d[x][i]], r[d[x][i]], y);
}

int now;
void solve(int sl, int sr, int l, int r)
{
    if (sl > sr) return;
    if (l == r) { for (int i = sl; i <= sr; ++i) ans[pos[i]] = l; return; }
    int mid = (l + r + 1) >> 1;
    while (mid > now) change(now++, -1);
    while (mid < now) change(--now, 1);
    int tl = sl, tr = sr;
    for (int i = sl; i <= sr; ++i)
    {
        int t = query(1, 0, pmod, p[pos[i]]);
        if (t >= pos[i]) temp[tr--] = pos[i];
        else temp[tl++] = pos[i];
    }
    for (int i = sl; i <= sr; ++i)
        pos[i] = temp[i];
    solve(sl, tr, l, mid - 1); solve(tl, sr, mid, r);
}

int main()
{
    if (true)
    {
        cin >> n;
        cin >> padd >> pfirst >> pmod >> pprod;
        cin >> cadd >> cfirst >> cmod >> cprod;
        cin >> ladd >> lfirst >> lmod >> lprod;
        cin >> radd >> rfirst >> rmod >> rprod;
        p[1] = pfirst % pmod;
        for (int i = 2; i <= n; ++i)
            p[i] = (1ll * p[i - 1] * pprod + padd + i) % pmod;
        c[1] = cfirst % cmod;
        for (int i = 2; i <= n; ++i)
            c[i] = (1ll * c[i - 1] * cprod + cadd + i) % cmod;
        l[1] = lfirst % lmod;
        for (int i = 2; i <= n; ++i)
            l[i] = (1ll * l[i - 1] * lprod + ladd + i) % lmod;
        r[1] = rfirst % rmod;
        for (int i = 2; i <= n; ++i)
            r[i] = (1ll * r[i - 1] * rprod + radd + i) % rmod;
        for (int i = 1; i <= n; ++i)
            if (l[i] > r[i]) swap(l[i], r[i]);
    }

    for (int i = 1; i <= n; ++i)
        vp.push_back(p[i]), vp.push_back(l[i]), vp.push_back(r[i]);
    sort(vp.begin(), vp.end());
    vp.erase(unique(vp.begin(), vp.end()), vp.end());
    for (int i = 1; i <= n; ++i)
        p[i] = lower_bound(vp.begin(), vp.end(), p[i]) - vp.begin() + 1,
        l[i] = lower_bound(vp.begin(), vp.end(), l[i]) - vp.begin() + 1,
        r[i] = lower_bound(vp.begin(), vp.end(), r[i]) - vp.begin() + 1;
    pmod = vp.size();
    for (int i = 1; i <= n; ++i)
        v.push_back(c[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; ++i)
        c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin() + 1,
        d[c[i]].push_back(i), pos[i] = i;
    now = v.size() + 1;

    solve(1, n, 0, v.size());
    for (int i = 1; i <= n; ++i)
        if (ans[i] != 0) ans[i] = v[ans[i] - 1] % 19921228;
    for (int i = 1; i <= n; ++i)
        sum = (sum + ans[i]) % 19921228;
    cout << sum << endl;
    return 0;
}

BZOJ3996 线性代数

简单推一下就能够发现,如果 A[i] 为 1,就会产生 C[i] 的代价。如果 A[i] 和 A[j] 同时为 1,就会产生 B[i][j] 的收益。然后同文理分科建图跑网络流。

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

#define inf 0x7fffffff

int n, ans, b[605][605], c[605];
int s, t, head[360700], d[360700];

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

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    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 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;
    s = 0; t = n + n * n + 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            b[i][j] = read(); ans += b[i][j];
            add(i * n + j, t, b[i][j]);
            add(i, i * n + j, inf);
            if (i != j) add(j, i * n + j, inf);
        }
    for (int i = 1; i <= n; ++i)
        c[i] = read(), add(s, i, c[i]);
    cout << ans - dinic() << endl;
    return 0;
}

BZOJ2137 submultiple

对于每一个读入的 p,将 1 到 p+1 的 k 次方和累乘进答案里面就可以了。对于前 40 分,快速幂预处理 k 次方和,O(1) 处理询问。对于中间 20 分,用三次方和公式 1^3 + 2^3 + ... + n^3 = ((n * (n + 1)) / 2)^2,O(1) 处理询问。对于最后 40 分,用倍增玩,列式子二项式定理展开什么的,时间复杂度好像是 O(K log 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

int n;
long long k, p, ans = 1;

long long power(long long a, long long b)
{
    long long re = 1;
    a %= mod;
    while (b)
    {
        if (b & 1) re = re * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return re;
}

long long sump[100005], c[13][13], sum[13][65];

void getans(long long x, int k, int d)
{
    if (x == 1) { sum[k][d] = 1; return; }
    long long t = x >> 1;
    getans(t, k, d + 1);
    sum[k][d] = sum[k][d + 1];
    long long temp = 1;
    for (int i = k; i >= 0; --i)
        sum[k][d] = (sum[k][d] + sum[i][d + 1] * c[k][i] % mod * temp % mod) % mod,
        temp = temp * (t % mod) % mod;
    if (x & 1) sum[k][d] = (sum[k][d] + power(x % mod, k)) % mod;
}

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()
{
    cin >> n >> k;
    if (k >= 13)
    {
        for (int i = 1; i <= 100000; ++i)
            sump[i] = (sump[i - 1] + power(i, k)) % mod;
        for (int i = 1; i <= n; ++i)
            ans = ans * sump[read() + 1] % mod;
        cout << ans << endl;    
    }
    else if (k == 3)
    {
        for (int i = 1; i <= n; ++i)
        {
            long long x = read() + 1;
            long long t1 = x, t2 = x + 1;
            if (t1 % 2 == 0) t1 /= 2;
            else t2 /= 2;
            t1 = (t1 % mod) * (t2 % mod) % mod * (t1 % mod) % mod * (t2 % mod) % mod;
            ans = ans * t1 % mod;
        }
        cout << ans << endl;
    }
    else
    {
        for (int i = 0; i <= k; ++i)
        {
            c[i][0] = 1;
            for (int j = 1; j <= i; ++j)
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
        for (int i = 1; i <= n; ++i)
        {
            long long x = read();
            memset(sum, 0, (k + 1) * sizeof(sum[0]));
            for (int i = 0; i <= k; ++i)
                getans(x + 1, i, 0);
            ans = ans * sum[k][0] % mod;
        }
        cout << ans << endl;
    }
    return 0;
}

BZOJ3122 [Sdoi2013]随机数生成器

大爷的 PPT 骗我,并不需要拓展 BSGS,保证 P 是素数。

这道题就是一大团麻烦的分类讨论,如果 a 大于等于 2,发现通项公式里有一部分是 a 为公比的等比数列。代入公式,然后挪一挪就可以把一坨乱七八糟的东西放到等式的右面去,等式的左面化成 a 的 n-1 次幂。再套用 BSGS 就结束了。

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

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

int bsgs(int a, int b, int p)
{
    map<int, int> m;
    if (!(a %= p)) return b ? -2 : 1;
    int blo = ceil(sqrt(double(p)));
    for (int i = 0, t = 1; i < blo; ++i)
    {
        if (m.find(t) == m.end()) m[t] = i;
        t = 1ll * t * a % p;
    }
    int inv = power(a, p - blo - 1, p);
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(b) != m.end())
            return i * blo + m[b];
        b = 1ll * b * inv % p;
    }
    return -2;
}

int test, p, a, b, x, t;

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> p >> a >> b >> x >> t;
        if (x == t)
        {
            cout << 1 << endl;
        }
        else if (a == 0)
        {
            cout << (b == t ? 2 : -1) << endl;
        }
        else if (a == 1)
        {
            if (b == 0)
                cout << (t == 0 ? 2 : -1) << endl;
            else
                cout << 1ll * power(b, p - 2, p) * (t - x + p) % p + 1 << endl;
        }
        else
        {
            int inv = power(a - 1, p - 2, p);
            t = (t + 1ll * b * inv) % p;
            t = 1ll * t * power((x + 1ll * b * inv) % p, p - 2, p) % p;
            cout << bsgs(a, t, p) + 1 << endl;
        }
    }
    return 0;
}