2017-2018 ICPC Asia Tsukuba Regional

比赛地址 ：Codeforces Gym 101986

还没补完：DK

A - Secret of Chocolate Poles

除了最下面一块黑，每块黑和下面的白组成一块，简单计数。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007 

ll f[N], ans;

int main() {
    int l = rd(), k = rd();
    f[1] = f[k] = 1; ++k;
    for (int i = 3; i <= l; ++i) {
        f[i] += f[i - 2];
        if (i > k) f[i] += f[i - k];   
    }
    for (int i = 1; i <= l; ++i) ans += f[i];
    printf("%lld\n", ans);
    return 0;
}

B - Parallel Lines

给定 \(m\ (m\le 16,\) 偶数\()\) 个点，两两配对，问得到的线段平行关系最多有多少组。

注意要求全部点都用上，所以搜索两两配对的方案，可以变成每次给编号最小的那个点找配对点，复杂度变成 \(\mathcal{O}((m-1)!!)\) 。

然后数相同的方向向量的个数，对每个方向向量维护一个计数器即可，复杂度 \(\mathcal{O}((m-1)!!)\) 。计算量约为 \(2\times 10^6\) 。

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;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 17
#define M 1007 
#define fr first
#define sc second

map<pii, int> f;

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

pii operator - (const pii &a, const pii &b) {return {a.fr - b.fr, a.sc - b.sc};}
pii operator / (const pii &a, const int &k) {return {a.fr / k, a.sc / k};}

pii a[N];

bool vis[N];

int s[N][N], cnt[M];

int n, idcnt, ans, res;

inline int c2(int x) {return x * (x - 1) / 2;}

inline void add(int x) {res -= c2(cnt[x]); ++cnt[x]; res += c2(cnt[x]);}

inline void del(int x) {res -= c2(cnt[x]); --cnt[x]; res += c2(cnt[x]);}

// (m - 1)!! = 2027025 
void dfs(int p) {
    if (p == n / 2) {ans = max(ans, res); return;}
    int A = 0;
    for (int i = 1; i <= n; ++i) 
        if (!vis[i]) {vis[i] = true; A = i; break;}
    for (int i = A + 1; i <= n; ++i)
        if (!vis[i]) {
            vis[i] = true; add(s[A][i]); dfs(p + 1);
            vis[i] = false; del(s[A][i]);
        }
    vis[A] = false;
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) {a[i].fr = rd(); a[i].sc = rd();}
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            pii tmp = (a[i] < a[j] ? a[j] - a[i] : a[i] - a[j]);
            tmp = tmp / gcd(abs(tmp.fr), abs(tmp.sc));
            if (!f[tmp]) f[tmp] = ++idcnt;
            s[i][j] = f[tmp];
        }
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

*C - Medical Checkup

\(n\) 个人去依次做检查，第 \(i\) 个人检查每个项目都需要 \(t_i\) 分钟，必须严格按照 \(1\dots \infty\) 的顺序做检查。

问 \(T\) 时刻每个人都在做或等待做第几个检查。

观察发现对于每个人，从他前面的 \(\max t_i\) 那个人开始，做检查的时间是连续的没有间隔了。

可以当作从 \(\arg\max t_i\) 开始的火车，每节长度为 \(t_i\) ，从某时刻进入一个隧道每秒前进一，隧道每 \(\max t_i\) 一个关卡。

换句话说，除了第一个检查，后面的每个检查都需要 \(\max t_i\) 的时间进行，所以答案就是 \(\displaystyle \lfloor\frac{T - \sum_{j=1}^i t_j}{\max t_i}\rfloor + 2\) 。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int main() {
    int n = rd(), t = rd(), mx = 0;
    for (int i = 1; i <= n; ++i) {
        int nw = rd(); mx = max(mx, nw);
        if (t >= 0) t -= nw; // t is the starting time of the second check
        printf("%d\n", t < 0 ? 1 : t / mx + 2);
    }
    return 0;
}

*E - Black or White

给两个长度为 \(n\) 的 \(01\) 序列 \(S,T\) ，每次可以把第一个序列连续至多 \(k\) 个位置刷成 \(0\) 或 \(1\) 。

问把第一个序列改成第二个最少操作多少次。

设 \(f[i]\) 表示把前 \(i\) 个刷成正确的最小操作次数。

  • \(S[i]=T[i],\ f[i] \leftarrow f[i - 1]\)
  • 枚举刷 \(i\) 的那一刷是从第 \(j\) 个开始的，\(f[i]\leftarrow \min\{f[j]+cost(j+1,i)\}\)

考虑把一个长度不超过 \(k\) 的序列刷出来的最小代价，发现是每次把左右两个一起刷，代价即 段数 \(/2 + 1\) 。

\(f[i] = f[j] + (sum[i] - sum[j + 1] + 1) / 2 + 1\) 按照 \(2 * f[j] - sum[j + 1]\) 决策单调性，单调队列优化一下。

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007

char s[N], t[N];

int sum[N], f[N];

deque<int> pos;

int main() {
    pos.push_back(0);
    int n = rd(), m = rd();
    scanf("%s", s + 1); scanf("%s", t + 1);
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (t[i] != t[i - 1]);

    // the number of segments in [l, r] : sum[r] - sum[l + 1] + 1
    auto val = [&](int p) {return 2 * f[p] - sum[p + 1];};
    for (int i = 1; i <= n; ++i) {
        if (s[i] == t[i]) f[i] = f[i - 1];
        else {
            while (i - pos.front() > m) pos.pop_front();
            f[i] = f[pos.front()] + (sum[i] - sum[pos.front() + 1] + 1) / 2 + 1;
        }
        while (!pos.empty() && val(pos.back()) >= val(i)) pos.pop_back();
        pos.push_back(i);
    }
    printf("%d\n", f[n]);
    return 0;
}

*F - Pizza Delivery

给定一张有向图，问把每条边翻转后（临时修改），\(1\) 到 \(2\) 最短路是否变长 / 不变 / 变短。

原图跑出来 \(1\) 的单源最短路 \(dis[1][u]\) ，反图跑出来 \(2\) 的单源最短路 \(dis[2][u]\) 。

原图最短路是 \(dis[1][2]\) ，翻转 \((u\to v,w)\) 后经过这条边的最短路是 \(dis[1][v] + dis[2][u] + w\) 。

变短可以直接判断。然后如果不是所有最短路都必须经过原来的 \((u\to v,w)\) ，那么最短路不变，否则是变长。

求最短路同时求出 \(cnt[1][u]\) 表示原图 \(1\) 到 \(u\) 的最短路条数，\(cnt[2][u]\) 表示反图 \(2\) 到 \(u\) 的最短路条数。

判断最短路必经边可以哈希（取模）最短路计数。最短路必经边的条件：

  1. 在最短路上： \(dis[1][u]+dis[2][v] + w == dis[1][2]\)
  2. 所有最短路都经过：\(cnt[1][u]\times cnt[2][v] \equiv cnt[1][2]\pmod {a\ prime\ number}\)

最后考虑一下多条完全相同且在最短路上的重边是否会有问题（即认为每条都是必经边）？

答案是不会有问题，因为最短路条数是 \(cnt[1][u]\times cnt[2][v]\times k\) ，可以理解为乘法原理。

upd：当然第二问也可以只保留 \(1\) 到 \(2\) 最短路中的边，然后建图求桥。

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

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

template<typename T>
inline bool getmin(T &a, T b) {return a > b ? (a = b, true) : false;}

#define mp make_pair

#define N 100007

int n, m, tot, hd[N], hdr[N];

struct edge{int to, nxt, w;} e[N << 1];

void add(int u, int v, int w) {
	e[++tot] = {v, hd[u], w}; hd[u] = tot;
	e[++tot] = {u, hdr[v], w}; hdr[v] = tot;
}

#define mod 1000000007

inline void add(int &a, int b) {a = (a + b >= mod ? a + b - mod : a + b);}

bool use[N];

int cnt[2][N];

ll dis[2][N];

typedef pair<ll, int> cur;

priority_queue<cur, vector<cur>, greater<cur>> q;

inline void dij(int u, int *h, int id) {
	memset(use, 0, sizeof(use));
	dis[id][u] = 0; cnt[id][u] = 1; q.push(mp(0, u)); 
	while (!q.empty()) {
		int u = q.top().second; q.pop();
		if (use[u]) continue; use[u] = true;
		for (int i = h[u], v; i; i = e[i].nxt)
			if (getmin(dis[id][v = e[i].to], dis[id][u] + e[i].w)) {
				cnt[id][v] = cnt[id][u]; q.push(mp(dis[id][v], v));
			} else if (dis[id][v] == dis[id][u] + e[i].w) add(cnt[id][v], cnt[id][u]);
	}
} 

int main() {
	int n = rd(), m = rd();
	for (int i = 1; i <= m; ++i) {
		int u = rd(), v = rd(), w = rd(); add(u, v, w);
	}
	memset(dis, 0x3f, sizeof(dis));
	dij(1, hd, 0); dij(2, hdr, 1);
	ll mnd = dis[0][2];
	for (int i = 1; i <= m; ++i) {
		int u = e[i * 2].to, v = e[i * 2 - 1].to, w = e[i * 2].w;
		if (dis[0][v] + dis[1][u] + w < mnd) puts("HAPPY");
		else if (dis[0][u] + dis[1][v] + w == mnd && 1ll * cnt[0][u] * cnt[1][v] % mod == cnt[0][2]) puts("SAD");
		else puts("SOSO");
	}
	return 0;
}

UPD：看了下 jiangly 的代码，发现了一个神奇的方法求最短路必经边，尝试描述一下原理：

对于最短路图上的每条边差分，起点点权 \(+1\) ，终点点权 \(-1\) ，然后按照 Dijkstra 的顺序求前缀和。

那么如果一条边 \((u,v,w)\) 在 \(1\) 到 \(2\) 最短路上 且 \(val[u]=1\) ，那么这条边是最短路必经边。

\(val[u]\) 的含义是只考虑 Dijkstra 顺序中在 \(u\) 之前的所有点，延伸出的最短路当前收敛到了多少条。

也就是当前最短路能走就走，只走 Dijkstra 顺序中在 \(u\) 之前的点，然后最终有多少条边可以继续往下走。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

template<typename T>
inline bool getmin(T &a, T b) {return a > b ? (a = b, true) : false;}

#define mp make_pair

#define N 100007

int n, m, tot, hd[N], hdr[N];

struct edge{int to, nxt, w;} e[N << 1];

void add(int u, int v, int w) {
    e[++tot] = {v, hd[u], w}; hd[u] = tot;
    e[++tot] = {u, hdr[v], w}; hdr[v] = tot;
}

bool use[N];

int pos[N], sum[N];

ll dis[2][N];

typedef pair<ll, int> cur;

priority_queue<cur, vector<cur>, greater<cur>> q;

inline void dij(int u, int *h, int id) {
    memset(use, 0, sizeof(use));
    dis[id][u] = 0; q.push(mp(0, u)); 
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (use[u]) continue; use[u] = true;
        if (!id) pos[u] = ++pos[0];
        for (int i = h[u], v; i; i = e[i].nxt)
            if (getmin(dis[id][v = e[i].to], dis[id][u] + e[i].w)) q.push(mp(dis[id][v], v));
    }
} 

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd(); add(u, v, w);
    }
    memset(dis, 0x3f, sizeof(dis));
    dij(1, hd, 0); dij(2, hdr, 1);
    ll mnd = dis[0][2];
    for (int u = 1; u <= n; ++u)
        for (int i = hd[u], v; i; i = e[i].nxt)
            if (dis[0][u] + e[i].w + dis[1][v = e[i].to] == mnd) {++sum[pos[u]]; --sum[pos[v]];}
    for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1];
    for (int i = 1; i <= m; ++i) {
        int u = e[i * 2].to, v = e[i * 2 - 1].to, w = e[i * 2].w;
        if (dis[0][v] + dis[1][u] + w < mnd) puts("HAPPY");
        else if (dis[0][u] + dis[1][v] + w == mnd && sum[pos[u]] == 1) puts("SAD");
        else puts("SOSO");
    }
    return 0;
}

G - Rendezvous on a Tetrahedron

两只蚂蚁从正四面体一个顶点开始爬，给定初始面、方向、长度。

爬行路径过程中保证和边角度不变，保证除了开始不会经过任何顶点。问最后两只蚂蚁是否在同一个面。

角度不变相当于在四面体展开的图形上走直线，模拟即可。每次新走到的面都可以用上一个面的三个点判断得出。

讨论比较繁琐，解三角形需要灵活运用一下三角函数公式。\([0,\pi]\) 求角度用 \(\arccos\) 不要用 \(\arcsin\) 。

感觉三角函数递归套起来精度炸飞了。不知道怎么过的

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

const double pi = 3.141592653589793;
const double sin60 = sqrt(3) / 2.0;

// A = 0 | B = 1 | C = 2 | D = 3 || sum = 6

vector<int> simulate(int x, int y, int tar, double pos, double ang, double rem) {
    //printf("%d %d %d %.3lf %.3lf %.3lf\n", x, y, tar, pos, ang, rem); 
    double angtar = acos((2 * pos - 1) / 2.0 / sqrt(pos * pos + 1 - pos)); 
    if (ang < angtar) {
        double len = pos * sin60 / sin(pi * 2 / 3 - ang);
        if (rem <= len) return vector<int>{x, y, tar};
        return simulate(x, tar, 6 - x - y - tar, sin(ang) / sin(pi * 2 / 3 - ang) * pos, pi / 3 + ang, rem - len);
    } else {
        double len = (1 - pos) * sin60 / sin(ang - pi / 3);
        if (rem <= len) return vector<int>{x, y, tar};
        return simulate(tar, y, 6 - x - y - tar, 1 - sin(ang) / sin(ang - pi / 3) * (1 - pos), ang - pi / 3, rem - len);
    }
}

int main() {

    auto rdv = [&]() {
        char c = getchar();
        while (!isalpha(c)) c = getchar();
        return c - 'A';
    };

    auto getpos = [&]() {
        int x = rdv(), y = rdv();
        double ang = rd() * pi / 180, l = rd();
        double step1 = sin60 / sin(pi * 2 / 3 - ang); // The Law of Sines
        if (step1 >= l) return vector<int>{0, x, y};
        else return simulate(x, y, 6 - x - y, sin(ang) / sin(pi * 2 / 3 - ang), pi / 3 + ang, l - step1);  
    };
    vector<int> pos1 = getpos(); sort(pos1.begin(), pos1.end());
    vector<int> pos2 = getpos(); sort(pos2.begin(), pos2.end());
    puts(pos1 == pos2 ? "YES" : "NO");
    return 0;
}

*H - Homework

\(n\) 个作业，每个作业有释放时间 \(r_i\) 截止时间 \(d_i\) 种类 \(A/B\) 。

每天 \(x\) 先选择一个类别，然后如果该类还有没完成且可以完成的任务（ \(x\in [r_i,d_i]\) ），那么做掉 \(d_i\) 最小且编号最小的。

问最多 / 最少能完成多少个作业。

注意到 “做掉 \(d_i\) 最小且编号最小的” 是正确的贪心结构（是随便选的方案里的最优解）。

最多就是做一个二分图匹配。每天 \(x\) 可以匹配 \(x\in [r_i,d_i]\) 的所有 \(i\) 。

最少考虑开摆的策略：如果那天存在一类作业当天都做完了，那我自然选择这一类任务；否则就是挑某一类做掉一个。

用最小割描述这个贪心，割的含义就是完成这个任务：

  • 每天最多完成一个作业，拆点 \((x_l\to x_r,1)\) 。

  • 每个 \(A\) 类任务：\((S\to task_i, 1);\ \forall x\in [r_i,d_i],(task_i\to x_l,1)\)

  • 每个 \(B\) 类任务：\(\forall x\in [r_i,d_i],(x_r\to task_i,1);\ (task_i\to T, 1)\)

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}
 
// F is the type of flow
template<const int V, const int E, class F, const F flowInf>
struct Flow {
 
    int tot = 1, S, T, hd[V], cur[V], dis[V];
    struct edge{int to, nxt; F cap;} e[E << 1];
 
    void clear() {tot = 1; memset(hd, 0, sizeof(hd));}
    void add(int u, int v, F w) {
        e[++tot].nxt = hd[u], hd[u] = tot, e[tot].to = v, e[tot].cap = w;
        e[++tot].nxt = hd[v], hd[v] = tot, e[tot].to = u, e[tot].cap = 0;
    }
    inline bool bfs() {
        static int q[V], qhd, qtl; 
        memcpy(cur, hd, sizeof(hd));
        memset(dis, -1, sizeof(dis));
        q[qhd = qtl = 1] = S; dis[S] = 0;
        while (qhd <= qtl) {
            int u = q[qhd++];
            for (int i = hd[u], v; i; i = e[i].nxt)
                if (dis[v = e[i].to] == -1 && e[i].cap != 0) {
                    dis[v] = dis[u] + 1; q[++qtl] = v;
                }
        }
        return dis[T] != -1;
    }
    F dfs(int u, F rem) {
        if (u == T) return rem;
        F flow = 0;
        for (int i = cur[u], v; i && rem; i = e[i].nxt) {
            cur[u] = i; v = e[i].to;
            F nw = min(rem, e[i].cap);
            if (nw != 0 && dis[v] == dis[u] + 1) {
                int ret = dfs(v, nw);
                flow += ret; rem -= ret; 
                e[i].cap -= ret; e[i ^ 1].cap += ret;
            }
        }
        if (flow == 0) dis[u] = -1;
        return flow;
    }
    F dinic(int source, int sink) {
        S = source; T = sink; F flow = 0;
        while (bfs()) flow += dfs(S, flowInf);
        return flow;
    }
};

#define N 1207
#define M 1000007

Flow<N, M, int, 1000000000> f;

int l[N], r[N];

int main() {
    int n = rd(), m = rd();
    int S = N - 1, T = N - 2;
    for (int i = 1; i <= 400; ++i) f.add(S, i, 1);
    for (int i = 1; i <= n; ++i) {
        l[i] = rd(); r[i] = rd(); f.add(400 + i, T, 1);
        for (int j = l[i]; j <= r[i]; ++j) f.add(j, 400 + i, 1);
    }
    printf("%d\n", f.dinic(S, T)); f.clear();
    for (int i = 1; i <= 400; ++i) f.add(i, 400 + i, 1);
    for (int i = 1; i <= m; ++i) {
        f.add(S, 800 + i, 1);
        for (int j = l[i]; j <= r[i]; ++j) f.add(800 + i, j, 1);
    }
    for (int i = m + 1; i <= n; ++i) {
        f.add(800 + i, T, 1);
        for (int j = l[i]; j <= r[i]; ++j) f.add(400 + j, 800 + i, 1);
    }
    printf("%d\n", f.dinic(S, T));
    return 0;
}

UPD： 网络流感觉理论复杂度不对，看了下 jiangly 的代码果然有复杂度正确的 dp 做法。

I - Starting a Scenic Railroad Service

策略 1 就是冲突最大的人的冲突次数 \(+1\) ，排序维护一下即可；策略 2 就是任意时刻上车的最多人数。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

template<typename T>
inline bool getmin(T &a, T b) {return a > b ? (a = b, true) : false;}

#define N  200007

int sum[N];

pii s[N];

priority_queue<int, vector<int>, greater<int>> q;

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) {
		int l = rd(), r = rd() - 1;
		s[i] = make_pair(l, r); ++sum[l]; --sum[r + 1];
	}
	sort(s + 1, s + 1 + n);
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		int l = i, r = n;
		while (!q.empty() && q.top() < s[i].first) q.pop();
		while (l < r) {
			int mid = (l + r + 1) / 2;
			s[mid].first <= s[i].second ? l = mid : r = mid - 1;
		}
		q.push(s[i].second);
		ans = max(ans, r - i + (int)q.size());
	}	
	printf("%d ", ans);
	ans = 0;
	for (int i = 1; i < N; ++i) {sum[i] += sum[i - 1]; ans = max(ans, sum[i]);}
	printf("%d\n", ans);
	return 0;
}

*J - String Puzzle

一个长度为 \(n\ (n\le 10^9)\) 的未知串，给定 \(a\) 个位置上的字符，\(b\) 个信息，\(q\) 次询问是否能知道某个位置的值。

一条信息：\(1\le h < l\le r\le n\) ，表示 \(S[h,h+(r-l)] = S[l,r]\) ，且所有信息的 \([l,r]\) 无交。

首先肯定想先把所有应该相同的位置都找出来，但位置太多了，如果 border 太短可能整个串都要处理。

那么一个经典的思路就是把信息记录在某个特定的位置，所有等价位置都可以找到这个位置，然后打标记/查询。

不妨把这个位置定为可能的最靠前的位置。那么由于 \([l,r]\) 无交，每个位置利用哪条信息跳是确定的。

可以发现 \(S[h,l-1]\) 是 \(S[h,r]\) 天然的 border ，我们直接把 \(p\in[l,r]\) 跳到 \(h+(p-h)\mod (l-h)\) 。

可以发现这样每个信息最多用到一次，查询最靠前的等价位置复杂度就是 \(O(b)\) 的。模拟即可。

（当然也可以用 set 维护信息，每次 lower_bound 找到 \(p\in[l,r]\) 那个信息，但是复杂度不会变好就没用）

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1007

pair<int, char> hint[N];

int y[N], h[N], tot;

struct segpair{int l, r, h;} s[N];

map<int, char> f;

int main() {
	int n = rd(), a = rd(), b = rd(), q = rd();
	for (int i = 1; i <= a; ++i) {
		int p = rd();
		char c = getchar();
		while (!isalpha(c)) c = getchar();
		hint[i] = {p, c};
	}
	for (int i = 1; i <= b; ++i) {y[i] = rd(); h[i] = rd();}
	y[b + 1] = n + 1;
	for (int i = 1; i <= b; ++i) if (h[i]) s[++tot] = {y[i], y[i + 1] - 1, h[i]};
	
	auto find = [&](int p) {
		if (!tot) return p;
		for (int i = tot; i; --i) {
			if (p > s[i].r) return p;
			if (p < s[i].l) continue;
			p = s[i].h + (p - s[i].h) % (s[i].l - s[i].h);
		}
		return p;
	};

	for (int i = 1; i <= a; ++i) f[find(hint[i].first)] = hint[i].second;
	for (int i = 1; i <= q; ++i) {
		int pos = find(rd());
		putchar(f.find(pos) == f.end() ? '?' : f[pos]);
	}
	return 0;
}

Um_nik 队用了一个奇怪的科技把所有信息拆成 \(\log (r-l)\) 个 \([h,h+(r-l)]\) 和 \([l,r]\) 无交的信息：

设 \(len = l-h\) ，第一组 \([h,h+len-1],[l,l+len-1]\) ;

第二组将 \(len\) 倍长，\([h,h+2\times len-1],[l+len,l + 3\times len - 1]\) ;

第三组再倍长，以次类推，然后最后再剩下一小段。简单说就是按照 border 的\(2^k\) 倍长划分串。

这样子每组都没有交了，放到这个题就可以直接跳。不知道有啥用，简单记录一下。