https://ac.nowcoder.com/acm/contest/5961

C. 二维动点

 

题意：平面上有一些点，每次选一个点移动到该点与当前位置所成直线上任意一处，问从（0，0）到（x，y）的最少移动次数。

容易发现最多移动3次。

当目标就是原点时，移动0次。

当目标在某点与原点直线上时，移动1次。

当目标与任意两点的连线都和这两点与原点的连线平行，即目标与任意两点，以及原点 都构成平行四边形时，移动3次。

其它情况都移动2次。

注意一些细节：

不论是询问时还是已有的点， x==0&&y==0x==0\&\&y==0 时都要注意特判！！

要两边都平行！！

要用map.count()！！

map.size()==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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
typedef pair<int, int>pii;
map<pii, int>mp;
int gcd(int x, int y) {
    if (x < y)swap(x, y);
    return y == 0 ? x : gcd(y, x%y);
}
int n, q;
int x[N], y[N];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        if (x[i] == 0 && y[i] == 0) { i--, n--; continue; }
        int t = gcd(x[i], y[i]);
        mp[pii(x[i] / t, y[i] / t)] = 1;
    }
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a == 0 && b == 0) { puts("0"); continue; }
        int t = gcd(a, b);
        if (mp.count(pii(a / t, b / t))) { puts("1"); continue; }
        if ((int)mp.size() <= 1) { puts("-1"); continue; }
        if (n >= 3) { puts("2"); continue; }
        if (1ll * (a - x[1])*y[2] == 1ll * x[2] * (b - y[1]) && 1ll * (a - x[2])*y[1] == 1ll * x[1] * (b - y[2]))puts("3");
        else puts("2");
    }
    return 0;
}

 

D. 最小公倍数

 

题意：给出一个数n，你可以将它拆成一个长度任意的序列aia_i满足n=∑i=1kain = \sum_{i=1}^ka_i，一个集合的lcm定义为集合中所有数的lcm（空集的lcm为1），一个序列的权值定义为：这个序列的所有子集中不同lcm的个数，要求最大化你拆出来序列的权值，答案对109+710^9 + 7取模。

dp+数论

向序列中加入一个质数，它一定能产生最多的lcm，所以考虑把n拆成几个质数的和。

因为质数的大小对于lcm个数没有影响，所以尽量选小的。保证能存下。

如果没有质数可以选了，就要考虑质数的幂次，因为它相比于其它合数，包含只少不多的因子。产生的新lcm也就只多不少。

所以就成了个完全背包问题，把质数看做物品，要考虑拿几个。注意这里不同的是拿了 pkp^k 则 p1,p2,⋯ ,pk−1p^1,p^2,\cdots,p^{k-1} 都要拿，因为空着不划算。

由于答案要取模，所以没法比大小，所以要另外存真实结果，取log。

C++里的log是自然对数ln，要用log2，否则超时。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;
int prime[N];
bool is_prime[N];
int vis[N];
int sieve(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) { vis[i] = i; prime[cnt++] = i; is_prime[i] = true; }
        for (int j = 0; j < cnt; j++) {
            if (i*prime[j] > n)  break;
            vis[i*prime[j]] = prime[j];
            if (i%prime[j] == 0)
                break;
        }
    }
    return cnt;
}
typedef pair<double, ll>pii;
pii dp[N];
int main() {
    scanf("%d", &n);
    int to = sieve(n), c = 0, sm = 0;
    while (sm <= n && c < to)sm += prime[c++];
    dp[0] = pii(0, 1);
    for (int i = 0; i < c; i++) {
        for (int j = n; j >= 1; j--) {
            int p = prime[i], s = prime[i], k = 1;
            for (; s <= j; p *= prime[i], s += p, k++) {
                pii tmp = pii(dp[j - s].first + log2(k + 1), dp[j - s].second*(k + 1) % mod);
                dp[j] = max(dp[j], tmp);
            }
        }
    }
    pii ans = pii(-1, 0);
    for (int i = 0; i <= n; i++)ans = max(ans, dp[i]);
    printf("%lld\n", ans.second);
    return 0;
}

 

E. 游走配对

 

题意：给定一个无向图，只有点权 aia_i，路径的长度为路径上点权和，给定q个起点和终点，每次选一队没有选过的，作为这次的起点终点，一个点每被经过一次，点权就增加 bib_i，要求最小化q次的代价和，并求代价和。

费用流

能想到网络流就很简单了。

有点权，所以拆点；每次经过时点权不同，所以拆出多条边，每条边容量为1，费用为 ai+k⋅bia_i+k\cdot b_i。

S向q个起点连边，容量1；q个终点向T连边，容量1。费用都是0。

要最大化流量，也就是要流满q。

要最小化费用，也就是最小的代价和。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
typedef pair<int, int>pii;
struct E
{
    int from, to, cp, v;
    int rev;
    E() {}
    E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
    int n, m, s, t;
    vector<E> edges;
    vector<int> G[N];
    bool inq[N];     //是否在队列
    int d[N];        //Bellman_ford单源最短路径
    int p[N];        //p[i]表从s到i的最小费用路径上的最后一条弧编号
    int a[N];        //a[i]表示从s到i的最小残量
    void init(int _n, int _s, int _t) {
        n = _n; s = _s; t = _t;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear(); m = 0;
    }
 
    void addedge(int from, int to, int cap, int cost) {
        edges.push_back(E(from, to, cap, cost, 0));
        edges.push_back(E(to, from, 0, -cost, 1));
        G[from].push_back(m++);
        G[to].push_back(m++);
    }
 
    bool BellmanFord(int &flow, int &cost) {
        for (int i = 0; i < n; i++) d[i] = INF;
        memset(inq, 0, sizeof inq);
        d[s] = 0, a[s] = INF, inq[s] = true;
        queue<int> Q; Q.push(s);
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            inq[u] = false;
            for (int& idx : G[u]) {
                E &e = edges[idx];
                if (e.cp && d[e.to] > d[u] + e.v) {
                    d[e.to] = d[u] + e.v;
                    p[e.to] = idx;
                    a[e.to] = min(a[u], e.cp);
                    if (!inq[e.to]) {
                        Q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        if (d[t] == INF) return false;
        flow += a[t];
        cost += a[t] * d[t];
        int u = t;
        while (u != s) {
            edges[p[u]].cp -= a[t];
            edges[p[u] ^ 1].cp += a[t];
            u = edges[p[u]].from;
        }
        return true;
    }
 
    pii go() {
        int flow = 0, cost = 0;
        while (BellmanFord(flow, cost));
        return pii(flow, cost);
    }
} MM;
int n, m, q;
int cnt[2][N];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    int S = 0, T = 2 * n + 1;
    MM.init(2 * n + 2, S, T);
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        for (int j = 1; j <= n; j++)MM.addedge(i, n + i, 1, a + (j - 1)*b);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        MM.addedge(u + n, v, INF, 0);
        MM.addedge(v + n, u, INF, 0);
    }
    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x);
        cnt[0][x]++;
    }
    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x);
        cnt[1][x]++;
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[0][i] > 0)MM.addedge(S, i, cnt[0][i], 0);
        if (cnt[1][i] > 0)MM.addedge(i + n, T, cnt[1][i], 0);
    }
    printf("%d\n", MM.go().second);
    return 0;
}