CF2059 Div.2
CF 2059 div.2
A Milya and Two Arrays
题目大意
给出两个长度相同的数组 $A, B$, 每个数组中的元素均重复出现 (即若 $x \in A$, 则 $x$ 在 $A$ 中出现次数大于等于 2).
现在定义 $C_i = A_i + B_i$, 问是否可以通过对 $A$ 的重新排列, 使得 $C$ 中不同元素个数不少于 3 种.
题解
手玩几个小样例不难发现, 无解当且仅当 $A, B$ 各自不同元素种类的个数和小于等于 3.
code
1const int N = 55;
2int n, a[N], b[N];
3void solve()
4{
5 read(n);
6 int mx = 0, mn = 1e9, cnt = 0;
7 for (int i = 1; i <= n; i++)
8 read(a[i]);
9 sort(a + 1, a + n + 1);
10 cnt += unique(a + 1, a + n + 1) - a - 1;
11 for (int i = 1; i <= n; i++)
12 read(b[i]);
13 sort(b + 1, b + n + 1);
14 cnt += unique(b + 1, b + n + 1) - b - 1;
15 puts(cnt <= 3 ? "NO" : "YES");
16}
17int main()
18{
19 int T = 1;
20 cin >> T;
21 while (T--)
22 solve();
23 flushout();
24 return 0;
25}B Cost of the Array
题目大意
给出一个长为 $n$ 的数组和一个偶数 $k$, 现在需要将该数组分成 $k$ 段子数组 (每段均连续). 接着将所有偶数段取出拼成新数组 $B$, 并在末尾加入数字 0. 定义花费为最小的 $i$ 满足 $B_i \ne i$. 求最小花费.
题解
- 当 $n = k$ 时, 划分方式唯一, 直接模拟求解即可.
- 当 $n \ne k$ 时, 答案不超过 2. 首先我们希望第二段的开头不是 1, 所以如果第 2 个数到第 $n - k + 2$ 个数中有不是 1 的数, 我们直接以此为第二段开头即可；否则由于 $k$ 是偶数, 第 2,3,4 位一定均是 1 ($n-k+2 \geq 4$), 所以直接取前 4 位单独成段即可 ($k \geq 4$). 而当 $k = 2$ 时, 说明该数组全是 1.
code
1const int N=2e5+10;
2int n,k,a[N];
3void solve()
4{
5 read(n),read(k);
6 for(int i=1;i<=n;i++)read(a[i]);
7 if(n==k)
8 {
9 for(int i=2;i<=n;i+=2)
10 {
11 if(a[i]!=i/2)
12 {
13 write(i/2);
14 return;
15 }
16 }
17 write(k/2+1);
18 return;
19 }
20 for(int i=2;i<=n-k+2;i++)
21 if(a[i]!=1)
22 {
23 write(1);
24 return;
25 }
26 write(2);
27 return;
28}
29int main()
30{
31 int T;
32 cin>>T;
33 while(T--) solve();
34 flushout();
35 return 0;
36}C Customer Service
题目大意
有 $n$ 条服务队列, 初始都为 0 个人, 接下来一共有 $n$ 个时刻, $a_{i,j} (a_{i,j} \geq 1)$ 表示第 $i$ 个队列在 $j$ 时刻来的客人.
并且在每个时刻来人后, 你必须选择恰好一条队列并将其清空.
请求出在这 $n$ 个时刻后, 这 $n$ 条队列最终人数的 MEX 最大是多少.
题解
首先考虑只有最后一个时刻被清空的队列是 0, 因为 $a_{i,j} \geq 1$. 而想要最终是 1 个人, 那么 $a_{i,n} = 1$ 且在 $n-1$ 时刻清空该队列. 如此重复可以得到最终是 $k$ 个人的队列一定满足最后 $k$ 个时刻来的人都是 1 个人并且在第 $k-1$ 时刻将其清空.
由此, 我们求出每条队列末尾连续 1 的长度, 然后从小到大贪心选取即可.
code
1const int N = 310;
2int T, n, a[N][N], b[N];
3
4int main()
5{
6 read(T);
7 while (T--)
8 {
9 read(n);
10 for (int i = 1; i <= n; i++)
11 b[i] = 0;
12 for (int i = 1; i <= n; i++)
13 for (int j = 1; j <= n; j++)
14 read(a[i][j]);
15 for (int i = 1; i <= n; i++)
16 for (int j = n; j; j--)
17 if (a[i][j] == 1)
18 b[i]++;
19 else
20 break;
21 sort(b + 1,b+n+1);
22 int ans = 0;
23 for(int i=1;i<=n;i++)
24 if(b[i]>=ans)ans++;
25 write(ans);
26 }
27 flushout();
28 return 0;
29}D Graph and Graph
题目大意
给出两个均含有 $n$ 个结点的无向图, 分别含有 $m_1, m_2$ 条边. 现在你在这两张图上各有一个初始结点 $s_1, s_2$. 每一次操作你都可以选择和你当前位置相邻的结点并移动过去 (两张图上均要移动). 设操作后你的位置是 $u_1, u_2$, 那么你这次操作的花费是 $|u_1 - u_2|$. 问在这样的操作规则下操作无限步后你的花费最小是多少, 如果是无穷请输出 -1.
题解
简单最短路题. 我们先考虑最后不是无穷的情况, 一定是有一条边在两个图中均存在, 并且可以做到在两张图上同时达到编号相同的一个端点上 (这里面其实蕴含了一个奇偶性, 但对实际做题没有影响). 考虑到一共只有 $n^2$ 个点对, 我们只要从 $(s_1, s_2)$ 从出发, 跑最短路, 当遇到上述不是无穷的情况就可以更新答案.
考虑边数一定不超过 $m_1 \times m_2$, 所以复杂度是 $O((n + m_1 \times m_2) \log(m_1 \times m_2))$. 可以通过.
code
1const int N = 1e3 + 10;
2int T, n, s1, s2, m1, m2, dis[N][N];
3vector<int> e1[N], e2[N];
4void graph_read(int &m, vector<int> *e)
5{
6 read(m);
7 for (int i = 1, u, v; i <= m; i++)
8 {
9 read(u), read(v);
10 e[u]. push_back(v);
11 e[v]. push_back(u);
12 }
13 return;
14}
15struct nod
16{
17 int u1, u2, dis;
18 bool operator<(const nod &b) const
19 {
20 return dis > b. dis;
21 }
22};
23
24priority_queue<nod> q;
25
26int main()
27{
28 read(T);
29 while (T--)
30 {
31 read(n), read(s1), read(s2);
32 for (int i = 1; i <= n; i++)
33 e1[i]. clear(), e2[i]. clear();
34 graph_read(m1, e1);
35 graph_read(m2, e2);
36 for (int i = 1; i <= n; i++)
37 for (int j = 1; j <= n; j++)
38 dis[i][j] = 1e9 + 10;
39 dis[s1][s2] = 0;
40 q. push({s1, s2, 0});
41 int ans = 2e9;
42 while (!q. empty())
43 {
44 nod now = q. top();
45 q. pop();
46 if (now. dis != dis[now. u1][now. u2])
47 continue;
48 for (int t1 : e1[now. u1])
49 for (int t2 : e2[now. u2])
50 {
51 if (now. u1 == now. u2 && t1 == t2)
52 ans = min(ans, now. dis);
53 if (dis[t1][t2] > now. dis + abs(t1 - t2))
54 {
55 dis[t1][t2] = now. dis + abs(t1 - t2);
56 q. push({t1, t2, dis[t1][t2]});
57 }
58 }
59 }
60 write(ans == 2e9 ? -1 : ans);
61 }
62 flushout();
63 return 0;
64}E Stop Gaming
题目描述
给你 $n$ 个数组, 每个数组的长度为 $m$. 让 $i$-th 数组中的 $j$-th 元素表示为 $a_{i,j}$. 保证所有 $a_{i,j}$ 都是不同的. 在一次操作中, 您可以执行以下操作:
- 选择某个整数 $i$ ($1 \leq i \leq n$) 和一个整数 $x$ ($1 \leq x \leq 2 \cdot n \cdot m$).
- 对于从 $i$ 到 $n$ 依次递增的所有整数 $k$, 进行以下操作:
- 将元素 $x$ 添加到 $k$-th 数组的开头.
- 将 $k$-th 数组中最后一个元素的值赋值给 $x$.
- 删除 $k$-th 数组中的最后一个元素.
换句话说, 你可以在任意数组的开头插入一个元素, 之后这个数组和后面所有数组中的元素都会向右平移一个. 最后一个数组的最后一个元素会被移除.
此外, 我们还给出了目标数组 $b_{i,j}$, 保证 $b_{i,j}$ 互不相同, 求最少的操作次数将 $a_{i,j}$ 变为 $b_{i,j}$, 并输出具体方案.
题解
我们先考虑求最少的次数. 这是一个贪心的过程, 因为我们希望尽可能的利用原本就存在的数. 那么我们来考虑能被利用的数的性质, 首先被利用的数肯定是 $b_{i,j}$ 的子序列. 其次, 这些数应该是 $a_{i,j}$ 的前缀, 因为根据上述操作, 我们无法间隔的留下 $a_{i,j}$.
那么我们就希望这个前缀尽可能长, 于是考虑从左至右贪心, 找到最远的可行位置. 一个位置是可行的一方面, 其左边所有需要操作的位置都"经历过" $k$ 的倍数, 只有这样才能在该位置后面添数, 这部分就对应了代码中 tot < m - (i - 2 + m) % m - 1 && dlt 这部分. 当无法达到时直接结束. 而另一方面, 该位置后面可能也需要添加元素, 所以该位置也得"经历过" $k$ 的倍数, 对应了代码中的 tot >= m - (i - 1 + m) % m - 1. 要注意的是, 不满足该条件也需要继续往后找, 因为后面可能有位置合法.
如此往复, 我们就可以得到最长的前缀, 然后减一下就得到最少步数.
第二部分, 求具体方案. 当我们知道长度后其实就是模拟这个过程, 考虑用线段树作为辅助数据结构, 要进行区间加减, 全局查询最右边的 0 (意味着该位置需要被操作了, 并且操作该位置不会影响左边的可操作性). 当某个位置操作完时, 将其赋值为 inf 即可. 而当全局最小值不是 0 后意味着操作结束.
code
1const int N = 3e5 + 10;
2int T, n, m, a[N], b[N], cnt[N], ct[N], val[N], pos[N];
3map<int, int> mp;
4struct Tree
5{
6 int mn, pos, tag;
7 void upd(int tg)
8 {
9 mn += tg;
10 tag += tg;
11 return;
12 }
13} tr[N << 2];
14void pushup(int rt)
15{
16 if (tr[ls]. mn < tr[rs]. mn)
17 {
18 tr[rt]. mn = tr[ls]. mn;
19 tr[rt]. pos = tr[ls]. pos;
20 }
21 else
22 {
23 tr[rt]. mn = tr[rs]. mn;
24 tr[rt]. pos = tr[rs]. pos;
25 }
26 return;
27}
28void pushdown(int rt)
29{
30 if (tr[rt]. tag)
31 {
32 tr[ls]. upd(tr[rt]. tag);
33 tr[rs]. upd(tr[rt]. tag);
34 tr[rt]. tag = 0;
35 }
36}
37void build(int rt, int l, int r)
38{
39 tr[rt] = {0, 0, 0};
40 if (l == r)
41 {
42 tr[rt] = {val[l], l, 0};
43 return;
44 }
45 int mid = (l + r) / 2;
46 build(ls, l, mid);
47 build(rs, mid + 1, r);
48 pushup(rt);
49}
50void change(int rt, int l, int r, int L, int R, int v)
51{
52 if (L <= l && r <= R)
53 return tr[rt]. upd(v);
54 pushdown(rt);
55 int mid = (l + r) >> 1;
56 if (L <= mid)
57 change(ls, l, mid, L, R, v);
58 if (mid < R)
59 change(rs, mid + 1, r, L, R, v);
60 pushup(rt);
61 return;
62}
63int main()
64{
65 read(T);
66 while (T--)
67 {
68 read(n), read(m);
69 mp. clear();
70 // mp[0] = n * m + 1;
71 for (int i = 1; i <= n * m; i++)
72 read(a[i]);
73 for (int i = 1; i <= n * m; i++)
74 read(b[i]), mp[b[i]] = i;
75 for (int i = 1; i <= n * m; i++)
76 pos[i] = mp[a[i]];
77 int len = 0;
78 for (int i = 1, tot = 0; i <= n * m; i++)
79 {
80 if (pos[i - 1] >= pos[i])
81 break;
82 int dlt = pos[i] - pos[i - 1] - 1;
83 cnt[i - 1] = dlt;
84 val[i - 1] = cnt[i - 1] ? m - (i - 2 + m) % m - 1 : 1e9;
85 if (tot < m - (i - 2 + m) % m - 1 && dlt)
86 break;
87 tot += dlt;
88 if (tot >= m - (i - 1 + m) % m - 1)
89 len = i;
90 }
91 cnt[len] = n * m - pos[len];
92 val[len] = cnt[len] ? m - (len - 1 + m) % m - 1 : 1e9;
93 for (int i = 0; i <= len; i++)
94 ct[i] = cnt[i];
95 write(n * m - len);
96 build(1, 0, len);
97 while (tr[1]. mn == 0)
98 {
99 int now = tr[1]. pos;
100 write((now + m - 1) / m + 1, ' '), write(b[pos[now] + ct[now]]);
101 if ((--ct[now]) == 0)
102 change(1, 0, len, now, now, 1e9);
103 if (now < len)
104 change(1, 0, len, now + 1, len, -1);
105 }
106 }
107 flushout();
108 return 0;
109}