XJOI200813 题解

模拟赛

又是一天两场的 XJOI noi 模拟赛，每天都是暴力选手 被吊着打 /kk

赛1 赛2

1A

写了 $n^2$ 的 dp，一遍过样例好评（。）正解是 dp 优化，然而这题 dp 有很多种，我这种没法优化的样子（看起来很笨！）

来看看flying2018大佬的题解

1B

暴力没写就特别不应该。模并不会对正确性有影响。。。30分还是很好拿到的。考虑 $gcd = 1$ 的那档子分，画一画图找规律就好了呗，60分也不难啊。

1C

60分这么香你为什么不写？啊？啊？？啊？？！$T = 2$ dp, $f[i, j]$ 表示第 $i$ 个区间能否和第 $i + 1$ 个区间交换；$l_i = i$ 的那档子分打个表找规律就出来了，$g[i] = 2g[i - 1] + i - 2$

2A

题目好像出锅了，咕咕

2B

不会，咕咕

—-分割线—-

来订正了。思维有点难度但并不是很毒的图论题，图论我太菜了啊 /kk 专题要刷起来了！

显然操作二和三建反图预处理一波就好了，难点在操作一。原题是 [POI2014]RAJ-Rally

考虑 DAG 的性质。设 x 的拓扑序为 dfn[x], 对于一条边 (x, y) 显然 dfn[x] < dfn[y]。强制走 (x, y) 的话显然拓扑序在 dfn[x] ~ dfn[y] 之间的点都不会经过，于是想到用 (x, y) 来更新那些点。

具体来说，设拓扑序比 x 小的集合为 A，比 x 大的集合为 B，以 x 为终点的最长路径为 dt[x]，为起点的最长路径为 ds[x], $f[x] = \max\limits_{(u, v) \in E, u \in A, v \in B}(dt[u] + 1 + ds[v])$

预处理这个 f, 发现每次 x 增大，A 只会多一个数，B 只会少一个数，可以动态维护最大值。

这篇博客的图非常清晰，可以帮助理解动态维护的过程

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e5 + 10;
int n, m, K;
int degt[N], degs[N], dt[N], ds[N], ans[N], id[N], tot;
struct edge { int x, y; }e[N];
vector<int> gt[N], gs[N];
queue<int> q;
multiset<int> s;
multiset<int>::iterator it;

int main() {
    cin >> n >> m >> K;
    rep(i, 1, m) {
        int x, y; scanf("%d%d", &x, &y);
        e[i].x = x, e[i].y = y;
        degt[y]++, degs[x]++;
        gt[x].push_back(y), gs[y].push_back(x);
    }
    rep(i, 1, n) if (!degt[i]) q.push(i);
    while (q.size()) {
        int x = q.front(); q.pop();
        id[++tot] = x;
        for (int i = 0; i < gt[x].size(); i++) {
            int y = gt[x][i];
            dt[y] = max(dt[y], dt[x] + 1);
            if (!(--degt[y])) q.push(y);
        }
    }
    rep(i, 1, n) if (!degs[i]) q.push(i);
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = 0; i < gs[x].size(); i++) {
            int y = gs[x][i];
            ds[y] = max(ds[y], ds[x] + 1);
            if (!(--degs[y])) q.push(y);
        }
    }

    rep(i, 1, n) s.insert(ds[i]);
    rep(o, 1, n) {
        int x = id[o];
        s.erase(s.find(ds[x]));
        for (int i = 0; i < gs[x].size(); i++) {
            int y = gs[x][i];
            s.erase(s.find(ds[x] + 1 + dt[y]));
        }
        ans[x] = *s.rbegin();
        s.insert(dt[x]);
        for (int i = 0; i < gt[x].size(); i++) {
            int y = gt[x][i];
            s.insert(dt[x] + 1 + ds[y]);
        }
    }

    while (K--) {
        int ty, x; scanf("%d%d", &ty, &x);
        if (ty == 1) {
            printf("%d\n", ans[x]);
        } else if (ty == 2) {
            printf("%d\n", dt[x] + ds[x]);
        } else {
            printf("%d\n", dt[e[x].x] + ds[e[x].y] + 1);
        }
    }
    return 0;
}

2C

min25筛和暴搜均可 AC（雾）不会 min25 就只能写暴搜啦！

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
ll n, P;
ll mark[N], p[N], tot, cnt[N];

void sieve(int n) {
    rep(i, 2, n) {
        if (!mark[i]) p[++tot] = i, cnt[i] = 1;
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            mark[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
    rep(i, 2, n) cnt[i] += cnt[i - 1];
}

ll dfs(ll x, ll t) {
    if (t > tot || x * p[t] > n) return 1;
    if (x * p[t] * p[t] > n) return cnt[min(P, n / x)] - t + 2;  // 优秀的剪枝们
    ll ret = dfs(x, t + 1);
    for (; x * p[t] <= n; ) {
        x *= p[t];
        ret += dfs(x, t + 1);
        x *= p[t];
    }
    return ret;
}

int main() {
    cin >> n >> P;
    sieve(P);
    printf("%lld\n", dfs(1, 1));
    return 0;
}