OI
30 minutes read (About 4532 words)

「CQOI2017」系列题解

小Q的棋盘

小Q 正在设计一种棋类游戏。在小Q设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点，编号为 $0,1,2, \cdots, V-1$，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小Q 现在想知道，当棋子从格点 $0$ 出发，移动 $N$ 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

题解

签到题，直接贪心找最长链就完了，时间复杂度 $O(n)$，你一定要 dp 也是可以的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * created by xehoth on 26-04-2017
 */
#include <bits/stdc++.h>

std::vector<int> edge[110];
int v, n, dep[110], max;

inline void dfs(const int u, const int pre) {
    if (dep[u] <= n) {
        max = std::max(max, dep[u] + n + 2 >> 1);
        for (register int i = 0, v; i < edge[u].size(); i++)
            if ((v = edge[u][i]) != pre) dep[v] = dep[u] + 1, dfs(v, u);
    }
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cin >> v >> n;
    for (register int i = 1, a, b; i < v; i++)
        std::cin >> a >> b, edge[a].push_back(b), edge[b].push_back(a);
    dfs(0, 0), std::cout << (max < v ? max : v);
    return 0;
}

小Q的草稿

题解

把三角形拆成三条线段，以每个点为中心极角排序，然后用 set 维护线段做扫描线，set 按照到中心点的距离排序，因为三角形不相交 所以大小关系不会变，遇到一个点就判断最近的线段是否挡住了。

代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}
}

const double PI = acos(-1.0);
const double EPS = 1e-12;
const int MAXN = 6020;

inline int cmp(double x) {
    return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1);
}

template<class T>
inline int sign(T x) {
    return x == 0 ? 0 : (x < 0 ? -1 : 1);
}

struct Point {
    double x, y, ang;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    inline Point operator-(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }

    inline Point operator+(const Point &b) const {
        return Point(x + b.x, y + b.y);
    }

    inline Point operator*(const double &k) const {
        return Point(x * k, y * k);
    }

    inline bool operator<(const Point &b) const {
        return ang < b.ang;
    }

    inline bool operator == (const Point &b) const {
        return x == b.x && y == b.y;
    }
    
    inline double len() {
        return sqrt(x * x + y * y);
    }

    inline void getAngle() {
        ang = atan2(y, x);
    }

    inline void input() {
        static int x, y;
        IO::read(x), IO::read(y);
        this->x = x, this->y = y;
    }
};

inline double dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}

inline double cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

inline Point getIntersection(const Point &a1, const Point &a2, const Point &b1, const Point &b2) {
    Point u = a1 - b1, av = a2 - a1, bv = b2 - b1;
    double t = cross(bv, u) / cross(av, bv);
    return a1 + av * t;
}

const Point O = Point(0, 0);
Point base;

struct Line {
    Point u, v;
    int id, in;
    double ang;
    Line() {}
    Line(const Point &u, const Point &v, int in, int id, double ang) : 
        u(u), v(v), in(in), id(id), ang(ang) {}
    
    inline bool operator < (const Line &b) const {
        return u == b.u ? cross(v - u, b.v - u) < 0 : 
            getIntersection(u, v, O, base).len() < 
            getIntersection(b.u, b.v, O, base).len();
    }
} line[MAXN];

inline bool comparator(const Line &a, const Line &b) {
    return cmp(a.ang - b.ang) < 0 || cmp(a.ang - b.ang) == 0 && a.in > b.in;
}

int lineCnt, tot;
std::multiset<Line> set;
std::multiset<Line>::iterator it[MAXN];
Point point[MAXN], p[MAXN];
Point tri[MAXN][3], t[MAXN][3];

inline void add(const Point &u, const Point &v, int id) {
    u.ang > v.ang ? (line[lineCnt++] = Line(v, u, 1, id, v.ang), 
    line[lineCnt++] = Line(u, v, 0, id, u.ang)) : 
    (line[lineCnt++] = Line(u, v, 1, id, u.ang), 
    line[lineCnt++] = Line(v, u, 0, id, v.ang));
}

inline double calc(const Line &s) {
    Point a = getIntersection(s.u, s.v, O, base);
    return a.len();
}

inline int solve(int n) {
    std::sort(p, p + n);
    std::sort(line, line + lineCnt, comparator);
    set.clear();
    register int ret = 0, i = 0, j = 0;
    for (; i < n; i++) {
        while (j < lineCnt && (cmp(line[j].ang - p[i].ang) < 0 
            || (cmp(line[j].ang - p[i].ang) == 0 && line[j].in))) {
            base = line[j].u;
            (line[j].in) ? (it[line[j].id] = set.insert(line[j]), 0) :
                (set.erase(it[line[j].id]), 0);
            j++;
        }
        if (set.empty()) {
            ret++; 
            continue;
        }
        base = p[i];
        double dis = calc(*set.begin());
        if (cmp(p[i].len() - dis) <= 0) ret++;
    }
    return ret;
}

int main() {
    register int V, T;
    IO::read(V), IO::read(T);
    for (int i = 1; i <= V; ++i)
        point[i].input();
    for (int i = 1; i <= T; ++i)
        for (int j = 0; j < 3; ++j)
            tri[i][j].input();

    int ans = 0;
    for (int i = 1; i <= V; ++i) {
        int cnt = 0;
        for (int j = i + 1; j <= V; ++j) {
            p[cnt++] = point[j] - point[i];
            p[cnt - 1].getAngle();
        }
        tot = lineCnt = 0;
        for (int j = 1; j <= T; ++j) {
            for (int k = 0; k < 3; ++k)
                t[j][k] = tri[j][k] - point[i];
            t[j][3] = t[j][0];
            Point u, v;
            double mx = 0;
            for (int k = 0; k < 3; ++k) {
                double ang = dot(t[j][k], t[j][k + 1]) / t[j][k].len() / t[j][k + 1].len();
                ang = acos(ang);
                if (ang > mx)
                    mx = ang, u = t[j][k], v = t[j][k + 1];
            }
            u.getAngle(), v.getAngle();
            double d = fabs(u.ang - v.ang);
            if (d < PI) {
                add(u, v, tot++);
            } else {
                Point tmp = getIntersection(u, v, O, Point(-1.0, 0));
                tmp.ang = PI * cmp(u.ang);
                add(u, tmp, tot++);
                tmp.ang = PI * cmp(v.ang);
                add(v, tmp, tot++);
            }
        }
        int ret = solve(cnt);
        ans += ret;
    }
    printf("%d", ans);
    return 0;
}

小Q的表格

小Q 是个程序员。
作为一个年轻的程序员，小Q 总是被老C 欺负，老C 经常把一些麻烦的任务交给小Q 来处理。每当小Q不知道如何解决时，就只好向你求助。为了完成任务，小Q 需要列一个表格，表格有无穷多行，无穷多列，行和列都从 $1$ 开始标号。

为了完成任务，表格里面每个格子都填了一个整数，为了方便描述，小Q 把第 $a$ 行第 $b$ 列的整数记为 $f(a,b)$,为了完成任务，这个表格要满足一些条件：

  1. 对任意的正整数 $a, b$,都要满足 $f(a, b) = f(b, a)$；
  2. 对任意的正整数 $a, b$,都要满足 $b * f(a, a + b) = (a + b) * f(a, b)$。为了完成任务，一开始表格里面的数很有规律，第 $a$ 行第 $b$ 列的数恰好等于 $a * b$，显然一开始是满足上述两个条件的。

为了完成任务，小Q 需要不断的修改表格里面的数，每当修改了一个格子的数之后，为了让表格继续满足上述两个条件，小Q 还需要把这次修改能够波及到的全部格子里都改为恰当的数。由于某种神奇的力量驱使，已经确保了每一轮修改之后所有格子里的数仍然都是整数。为了完成任务，小Q还需要随时获取前 $k$ 行前 $k$ 列这个有限区域内所有数的和是多少，答案可能比较大，只需要算出答案 $\text {mod } 1000000007$ 之后的结果。

题解

令 $gcd(a, b) = d$，则 $f(a, b) = \frac {ab} {d^2} f(d, d)$，这时我们就可以降一维，只用存 $f(d)$ 表示 $f(d, d)$ 就好了。
那么

$$ans = \sum_{d = 1}^{n}f(d)\sum_{i = 1}^n \sum_{j = 1}^n \left [gcd \left (i, j \right ) = d \right ] \frac {i * j} {d^2}$$ $$ans = \sum_{d = 1}^n f(d) \sum_{i = 1}^{\lfloor \frac {n} {d} \rfloor} \sum_{j = 1}^{\lfloor \frac {n} {d} \rfloor} \left [ gcd \left (i, j \right ) = 1 \right ]i * j$$ $$ans = \sum_{d = 1}^n f(d) \sum_{i = 1}^{\lfloor \frac {n} {d} \rfloor }i^2 \varphi(i)$$

然后分块维护 $f$ 就好了。

代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/*
 * created by xehoth on 26-04-2017
 */
#include <bits/stdc++.h>

namespace {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), 0) : 0;
    *oh++ = c;
}

template<class T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        if (x < 0) print('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}
}

namespace SharedData {

const int MOD = 1e9 + 7;

inline int fixUp(int x) {
    return x < MOD ? x : x - MOD;
}

inline int fixDown(int x) {
    return x < 0 ? x + MOD : x;
}

inline void add(int &x, int v) {
    x = fixUp(x + v);
}

inline void add(int *x, int *v) {
    *x = fixUp(*x + *v);
}

inline void add(int *x, int v) {
    *x = fixUp(*x + v);
}
}

namespace Force {

using namespace SharedData;

const int MAXN = 4e6 + 5;

#define long long long

int m, n;

int blockSize;
int blockPos[MAXN], blockNum;

int revBlockPre[MAXN], revBlockSuf[MAXN];

int sum[MAXN], blockSum[MAXN], f[MAXN], q[MAXN], *qp = q;

inline int query(int x) {
    return x > blockSize ? fixUp(sum[x] + blockSum[blockPos[x]]) : sum[x];
}

inline void modify(int x, int y) {
    register int d = fixDown(y - fixDown(query(x) - query(x - 1)));
    register int *i = sum + x, *end = sum + revBlockPre[blockPos[x]];
    while (i <= end) add(i++, d);
    i = blockSum + *(blockPos + x) + 1, end = blockSum + blockNum;
    while (i < end) add(i++, d);
}

inline void initBlock() {
    blockSize = sqrt(n) * 3 / 2;
    for (register int i = 1; i <= n; i++)
        blockPos[i] = (i - 1) / blockSize;
    blockNum = blockPos[n] + 1;
    for (register int i = 1, *p = blockPos + 1; i <= n; i++) revBlockPre[*p++] = i;
    for (register int i = n, *p = blockPos + n; i; i--) revBlockSuf[*p--] = i;
}


inline void init() {
    for (register int i = 1, *p = blockPos + 1; i <= n; i++) {
        sum[i] = (long)i * i % MOD;
        add(blockSum[*p + 1], sum[i]);
        i != revBlockSuf[*p++] ? (add(sum[i], sum[i - 1]), 0) : 0;
    }
    for (register int *i = blockSum + 1, *end = blockSum + blockNum; i < end; i++)
        add(i, i - 1);
    f[1] = 1;
    for(register int i = 2; i <= n; i++) {
        !f[i] ? (f[i] = (long)i * i % MOD * (i - 1) % MOD, *qp++ = i) : 0;
        for (register int *j = q; ; j++) {
            if (i * *j > n) break;
            if (i % *j == 0) {
                f[i * *j] = (long)*j * *j * *j % MOD * f[i] % MOD;
                break;
            }
            f[i* *j] = (long)f[i] * f[*j] % MOD;
        }
    }
    for (register int *i = f + 2, *end = f + n; i <= end; i++)
        add(i, i - 1);
}

inline void solve() {
    read(m), read(n);
    initBlock();
    init();
    while (m--) {
        register int a, b, k;
        register long x;
        read(a), read(b), read(x), read(k);
        register int d = std::__gcd(a, b);
        modify(d, x / (a / d) / (b / d) % MOD);
        register int i = 1, s = 0;
        while (i <= k) {
            register int j = k / (k / i);
            s = (s + (long)fixDown(f[j] - f[i - 1]) * query(k / i)) % MOD;
            i = j + 1;
        }
        print(s), print('\n');
    }
}
}

int main() {
    Force::solve();
    flush();
    return 0;
}

老 C 的任务

老 C 是个程序员。

最近老 C 从老板那里接到了一个任务——给城市中的手机基站写个管理系统。作为经验丰富的程序员，老 C 轻松地完成了系统的大部分功能，并把其中一个功能交给你来实现。

由于一个基站的面积相对于整个城市面积来说非常的小，因此每个的基站都可以看作坐标系中的一个点，其位置可以用坐标 $(x, y)$ 来表示。此外，每个基站还有很多属性，例如高度,功率等。运营商经常会划定一个区域，并查询区域中所有基站的信息。

现在你需要实现的功能就是，对于一个给定的矩形区域，回答该区域中（包括区域边界上的）所有基站的功率总和。如果区域中没有任何基站，则回答 $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
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
 * created by xehoth on 29-04-2017
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template<class T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        if (x < 0) print('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}

}

namespace Task {

const int MAXN = 100005;

#define long long long

struct Node {
    int x, y, id, val;
    long ans;

    inline bool operator<(const Node &p) const {
        return x < p.x;
    }
} q[MAXN << 2], node[MAXN];

long d[MAXN << 2], ans;

int tot, xcnt, ycnt;

inline void modify(int k, int v) {
    for (; k <= ycnt; k += k & -k) d[k] += v;
}

inline long query(int k) {
    register long ret = 0;
    for (; k; k ^= k & -k) ret += d[k];
    return ret;
}

inline bool cmp(Node a, Node b) {
    return a.id < b.id;
}

int n, m;

inline void init() {
    using namespace IO;
    static int xVal[MAXN << 2], yVal[MAXN << 2];
    read(n), read(m);
    xcnt = n, ycnt = n;

    for (register int i = 1; i <= n; i++) {
        read(node[i].x), read(node[i].y), node[i].id = i, read(node[i].val);
        xVal[i] = node[i].x, yVal[i] = node[i].y;
    }

    for (register int i = 1, x1, x2, y1, y2; i <= m; i++) {
        read(x1), read(y1), read(x2), read(y2);
        xVal[++xcnt] = x1, xVal[++xcnt] = x2, yVal[++ycnt] = y1, yVal[++ycnt] = y2,
        xVal[++xcnt] = x1 - 1, yVal[++ycnt] = y1 - 1;

        q[++tot].x = x1 - 1, q[tot].y = y1 - 1, q[tot].id = i, q[tot].val = 1,
        q[++tot].x = x1 - 1, q[tot].y = y2, q[tot].id = i, q[tot].val = -1,
        q[++tot].x = x2, q[tot].y = y1 - 1, q[tot].id = i, q[tot].val = -1,
        q[++tot].x = x2, q[tot].y = y2, q[tot].id = i, q[tot].val = 1;
    }

    std::sort(xVal + 1, xVal + xcnt + 1);
    std::sort(yVal + 1, yVal + ycnt + 1);
    xcnt = std::unique(xVal + 1, xVal + xcnt + 1) - (xVal + 1);
    ycnt = std::unique(yVal + 1, yVal + ycnt + 1) - (yVal + 1);

    for (register int i = 1; i <= n; i++) {
        node[i].x = std::lower_bound(xVal + 1, xVal + xcnt + 1, node[i].x) - xVal,
        node[i].y = std::lower_bound(yVal + 1, yVal + ycnt + 1, node[i].y) - yVal;
    }
    
    for(register int i = 1; i <= tot; i++) {
        q[i].x = std::lower_bound(xVal + 1, xVal + xcnt + 1, q[i].x) - xVal,
        q[i].y = std::lower_bound(yVal + 1, yVal + ycnt + 1, q[i].y) - yVal;
    }

    std::sort(q + 1, q + tot + 1);
    std::sort(node + 1, node + n + 1);
}

inline void solve() {
    using namespace IO;
    init();

    for (Node *p = node + 1, *r = node + n, *i = q + 1, *ir = q + tot; i <= ir; i++) {
        for (; p <= r && p->x <= i->x; p++)
            modify(p->y, p->val);
        i->ans = query(i->y);
    }
    
    std::sort(q + 1, q + tot + 1, cmp);
    
    Node *p = q;
    for (register int i = 1; i <= m; i++) {
        ans = (p + 1)->val * (p + 1)->ans + 
              (p + 2)->val * (p + 2)->ans +
              (p + 3)->val * (p + 3)->ans +
              (p + 4)->val * (p + 4)->ans;
        p += 4;
        print(ans), print('\n');
    }
}
}

int main() {
    Task::solve();
    IO::flush();
    return 0;
}

老 C 的方块

题解

将原图染色，分层建图，设特殊边两边的方块为灰色，这两个方块的其他相邻方块分别为黑色和白色。

当两个灰色方块同时存在时，相邻的其他方块只能有一种颜色，那么容易建立最小割模型，S 向所有黑色方块连边，所有白色方块向 T 连边，容量为权值；灰色方块与相邻的黑色或白色方块连边，容量为无穷大；两个灰色方块之间连边，容量为两个方块权值的较小值。

代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
 * created by xehoth on 29-04-2017
 */
#include <bits/stdc++.h>

namespace IO {
inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}
}

namespace Maxflow {

const int MAXN = 100010;

struct Node {
    int v, f, index;

    Node(const int v, const int f, const int index) : v(v), f(f), index(index) {}
};

std::vector<Node> edge[MAXN];

inline void addEdge(const int u, const int v, const int f) {
    edge[u].push_back(Node(v, f, edge[v].size()));
    edge[v].push_back(Node(u, 0, edge[u].size() - 1));
}

int h[MAXN], gap[MAXN];

inline int sap(int v, int flow, int s, int t, int n) {
    if (v == t) return flow;
    register int rec = 0;
    static int iter[MAXN];
    for (register int i = iter[v]; i < edge[v].size(); i++) {
        Node *p = &edge[v][i];
        if (p->f > 0 && h[v] == h[p->v] + 1) {
            register int ret = sap(p->v, std::min(flow - rec, p->f), s, t, n);
            p->f -= ret, edge[p->v][p->index].f += ret, iter[v] = i;
            if ((rec += ret) == flow || h[v] >= n) return rec;
        }
    }
    if (!(--gap[h[v]])) h[s] = n;
    gap[++h[v]]++, iter[v] = 0;
    return rec;
}

const int INF = INT_MAX >> 1;

inline int sap(int s, int t, int n) {
    register int ret = 0;
    gap[0] = n;
    while (h[s] < n) ret += sap(s, INF, s, t, n);
    return ret;
}

/* s = 0, t = num + 1 */
int s, t, n, m, num;
/* n 行 m 列 */

typedef std::pair<int, int> Pair;

typedef std::map<Pair, Pair> Map;

Map map;

std::vector<int> v[MAXN];

/* special -> addEdge(i, j, min(w_i, w_j)) */

const int dir[2][3][2] = { -1, 0, 1, 0, 0, 1, -1, 0, 1, 0, 0, -1 };

inline void addSpecialEdge(const int x, const int y, const int d) {
    Map::iterator p1 = map.find(Pair(x, y)), p2 = map.find(Pair(x, y + d));

#ifdef DBG
    fprintf(stderr, "addSpecialEdge: ");
#endif

    addEdge(p1->second.first, p2->second.first, 
            std::min(p1->second.second, p2->second.second));
}

inline Map::iterator addINFEdge(const int x, const int y, const int d, bool rev = false) {
    Map::iterator p, o = map.find(Pair(x, y));
    for (register int k = 0; k < 3; k++) {
        if ((p = map.find(Pair(x + dir[d][k][0], y + dir[d][k][1]))) != map.end()) {

#ifdef DBG
    fprintf(stderr, "addINFEdge: ");
#endif       
            rev ? addEdge(p->second.first, o->second.first, INF) : 
                  addEdge(o->second.first, p->second.first, INF);
        }
    }
    return o;
}

inline void build() {
    s = 0, t = num + 1;

    for (register int i = 1; i <= n; i++) {
        for (register int j = 0; j < v[i].size(); j++) {
            register int x = i, y = v[i][j];
            
            if ((x & 1) && (y & 3) == 1) {
                if (j < v[i].size() - 1 && v[i][j + 1] == y + 1)
                    addSpecialEdge(x, y, 1);
            } else if ((~x & 1) && (y & 3) == 0) {
                if (j > 0 && v[i][j - 1] == y - 1) 
                    addSpecialEdge(x, y, -1);
            } else if ((x & 1) && (y & 3) == 2) {
                addINFEdge(x, y, 0);
            } else if ((~x & 1) && (y & 3) == 3) {
                addINFEdge(x, y, 1);
            } else if (((x + y) & 1) && (x & 1)) {
                Map::iterator o = addINFEdge(x, y, 0);
                addEdge(s, o->second.first, o->second.second);
            } else if ((x & 1) && ((x + y) & 1) == 0) {
                Map::iterator o = addINFEdge(x, y, 1, true);
                addEdge(o->second.first, t, o->second.second);
            } else if (((x + y) & 1) && (~x & 1)) {
                Map::iterator o = addINFEdge(x, y, 1);
                addEdge(s, o->second.first, o->second.second);
            } else {
                Map::iterator o = addINFEdge(x, y, 0, true);
                addEdge(o->second.first, t, o->second.second);
            }
        }
    }
}

inline void solve() {
    using namespace IO;
    /* n 行 m 列 */
    read(m), read(n), read(num);
    /* x -> 行, y -> 列, (x, y) -> (i, w), i -> [1, num] */
    for (register int i = 1, x, y, w; i <= num; i++)
        read(y), read(x), read(w), map[Pair(x, y)] = Pair(i, w), v[x].push_back(y);
    for (register int i = 1; i <= n; i++) std::sort(v[i].begin(), v[i].end());

    build();
    std::cout << sap(s, t, t + 1);
}
}

int main() {
    Maxflow::solve();
    return 0;
}

老 C 的键盘

题解

用 $f[i][j]$ 表示第 $i$ 个节点，排名为 $j$ 的方案数。对于每个点，把它的子树一棵一棵合并上来，设一棵子树 $A$ 排名为 $i$，另一棵子树 $B$ 有 $j$ 个元素插到 $i$ 的前面，合法的 $B$ 的排名是一个连续的区间，能用前缀和优化，$j$ 个数插到 $i$ 前面，$size[B]$ 个数插到 $i$ 后面，要乘两个组合数。

代码

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
/*
 * created by xehoth on 29-04-2017
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1);
    if (c == -1) {
        *buf = '\0';
        return -1;
    }
    do buf[s++] = c; while (c = read(), !isspace(c) && c != -1);
    buf[s] = '\0';
    return s;
}
}

namespace Dp {

const int MAXN = 110;
const int MOD = 1000000007;

#define long long long

long c[MAXN][MAXN];

std::vector<int> edge[MAXN << 1];

char s[MAXN];

inline void addEdge(const int u, const int v) {
    edge[u].push_back(v);
}

inline void init(const int n) {
    for (register int i = 0; i <= n; i++) c[i][0] = 1;
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= i; j++) {
            (c[i][j] = c[i - 1][j] + c[i - 1][j - 1]) >= MOD ? c[i][j] -= MOD : 0;
        }
    }
}

long size[MAXN], tmp[MAXN];

long dp[MAXN][MAXN], g[MAXN][MAXN];

inline void dfs(int x) {
    size[x] = dp[x][1] = g[x][1] = 1;
    register int v;
    for (register int i = 0; i < edge[x].size(); i++) {
        v = edge[x][i];
        dfs(v);
        memset(tmp, 0, sizeof(long) * (size[x] + size[v] + 1));
        for (register int i = 1; i <= size[x]; i++) {
            for (register int j = 0; j <= size[v]; j++) {
                if (s[v] == '<') {
                    tmp[i + j] += dp[x][i] * (g[v][size[v]] - g[v][j] + MOD) % MOD * 
                                  c[i + j - 1][i - 1] % MOD * 
                                  c[size[x] + size[v] - i - j][size[x] - i] % MOD;
                } else {
                    tmp[i + j] += dp[x][i] * g[v][j] % MOD * 
                                  c[i + j - 1][i - 1] % MOD * 
                                  c[size[x] + size[v] - i - j][size[x] - i] % MOD;
                }
            }
        }
        size[x] += size[v];
        for (register int i = 1; i <= size[x]; i++)
            dp[x][i] = tmp[i], g[x][i] = (g[x][i - 1] + tmp[i]) % MOD;
    }
}


inline void solve() {
    using namespace IO;
    register int n;
    read(n), init(n);
    read(s + 2);
    for (register int i = 1; i <= n; i++) {
        (i << 1) <= n ? (addEdge(i, i << 1), 0) : 0;
        (i << 1 | 1) <= n ? (addEdge(i, i << 1 | 1), 0) : 0;
    }
    dfs(1);
    std::cout << g[1][size[1]];
}

}

int main() {
    Dp::solve();
    return 0;
}
「补档计划」ISAP 和 HLPP 算法
「补档计划」Tarjan

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×