Difference between revisions of "2019 Multi-University,Nowcoder Day 3"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Unsolved. == Problem B == Solved by Xiejiadong. == Problem C == Unsolved. == Problem D == Unsolved. == Problem E == Unsolved. == Problem F == Unsol...")
 
 
(24 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:定义 $S(x)$ 表示与结点 $x$ 相邻的点集,给出一列边。要求支持下面两个操作:
 +
 
 +
* 将一个区间的边状态置反(本来存在的删除,本来删除的加上);
 +
 
 +
* 判断 $S(x)$ 和 $S(y)$ 是否相同。
 +
 
 +
题解:一个我不太知道的套路:边集 $S(x)$ 可以用一个整数来表示,我们通过给每个点一个随机的权值,然后将点集里面的点权值异或起来得到 $S(x)$ 。
 +
 
 +
然后维护的话,考虑把边序列分块。
 +
 
 +
每次修改操作,可以变成两边块单点修改,中间的块,记录一下当前整个块的状态。
 +
 
 +
查询的时候,每个点的 $S(x)$ ,就是单点的状态和相关块状态的异或,判断两个 $S$ 是否相等即可。
 +
 
 +
所以需要预处理每个块与相关联点的抑或。
  
 
== Problem B ==
 
== Problem B ==
  
Solved by Xiejiadong.  
+
Solved by Xiejiadong. 00:19:55 (+)
 +
 
 +
题意:求 $0/1$ 数列中包含 $0/1$ 数量相等的最长子串和子序列。
 +
 
 +
题意:子序列,显然就是尽可能多得找 $0/1$ ,那么答案就是 $0/1$ 数量 min 的两倍。
 +
 
 +
对于子串,如果一个子串的 $0/1$ 数量相等的话,那么他们前缀和相等,前缀和以后,处理相同数的最远位置就好了。
  
 
== Problem C ==
 
== Problem C ==
  
Unsolved.
+
Upsolved by Kilo_5723.
 +
 
 +
题意:给定一个首尾为 1,部分位置被删除的 ETT 序列 $\{a_n\}$,将其还原。
 +
 
 +
题解:合法的 ETT 序列中,若 $a_l=a_r$,则 $a_{l+1 \dots r-1}$ 之间出现的值不能在 $a_{1 \dots l-1}$ 和 $a_{r+1 \dots n}$ 中出现,同时可以将 $a_{l \dots r}$ 替换成 $a_l$ 而不影响 ETT 的性质。
 +
 
 +
考虑每次将现 ETT 序列中 $a_l=a_r$ 且 $a_{l+1 \dots r-1}$ 互不相同的段落 $a_{l \cdots r}$。对于其中所有被删除的位 $a_p=-1$,我们可以证明只要 $a_{p-2},a_{p-1}\neq -1,a[l]$,就可以将 $a_p$ 替换成 $a_{p-2}$ 而不影响 ETT 的性质。这个性质对 k+2 也同样生效。
 +
 
 +
在将所有满足这种条件的位置全部删除之后,我们把 $a_{l+2*k}$ 的所有被删除的位置都填上 $a_l$,再用没有出现过的元素填满剩下的空隙,就能将 $a_{l\dots r}$ 缩成一个数 $a_l$。最后将 $a_{1\dots n}$ 缩点之后所有的删除位置都应该填上了值,此时的序列就是答案。
  
 
== Problem D ==
 
== Problem D ==
  
Unsolved.
+
Upsolved by Weaver_zhu. (-3)
 +
 
 +
题意:求出二元组的个数 $(i,j)$ 使得 $A(i^j) \equiv 0 \pmod{p}, (i \le n, j \le m)$,其中 $A(i)$ 为 $i$ 个数字 $1$ 链接起来的数
 +
 
 +
题解:把数字用等比数列加起来得 $\frac{10^{i^j}-1}{9} \equiv 0 \pmod{p}$,特判 $p=2,3,5$ 的情况,剩下的转化为求 $i^j\equiv 0 \pmod{x}$,其中 $x$ 是最小的正整数满足 $10^x \equiv 0\pmod{p}$。然后再用上欧拉定理。如何计数呢,枚举 $x$ 的素因子组成,$i$ 必须也包含素因子。分成两种情况,一种是 $x|i$,这样 $j$ 怎么着都行,另一种考虑 dfs $i$ 中包含 $x$ 的素因子组成,$j=cnt(n/cur) \times (m-minj+1)$,其中 $cur$ 是 $x$ 素因子乘起来的结果,$minj$ 是最小的 $j$ 使得 $i^j$ 能整除以 $x$,这个 dfs 的时候都能维护。实际上 dfs 复杂度玄学,但是能过。
 +
 
 +
由于场上分解质因数写挂了,这题没过。
  
 
== Problem E ==
 
== Problem E ==
Line 21: Line 57:
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Upsolved by Xiejiadong. (-10)
 +
 
 +
题意:求最大的子矩阵,保证子矩阵中的任意两个元素的差 $\le m$ 。
 +
 
 +
题解:考虑枚举上下行边界,把每一列的 max 信息和 min 信息压在一起,然后题目就变成了找一个最长的子区间,使得 max - min $\le m$ 。
 +
 
 +
这个可以用单调队列优化, max 信息维护单调递减数列, min 信息维护单调递增数列,每次从队尾加入元素,将超过 $m$ 的信息从队头移出。
 +
 
 +
明明都是 $O(n^3)$ ,场上 ST 表被卡自闭了。
  
 
== Problem G ==
 
== Problem G ==
  
Unsolved.
+
Upsolved by Weaver_zhu.
 +
 
 +
题意:定义一个取石子游戏的游玩过程:单人游戏,若石子总和为奇数,最少的一个石子堆拿走一个。若为偶数,可挑选两个非空石子堆各取走一个。如果不能取了石子还没取完就输了。给定一些石子堆,求有多少个二元组 $(l,r)$ 使得区间的石子堆是能赢的。
 +
 
 +
题解:首先有个结论:最多的石子小于等于剩下石子总和时,是能赢的。考虑统计不可行的区间:然后枚举每个最大值,向左枚举左端点,向右扩展直到求出最大的不可行区间。比不可行区间少的区间肯定更不可行。看似是个 $O(n^2)$ 的暴力,实际上输出统计的情况,竟然发现是 $O(n)$ 的,实际上也比 $O(nlogn)$ 的不知道快到哪里去了。感性来讲不可行的区间是少的也是短的,严谨的并不会证明。
  
 
== Problem H ==
 
== Problem H ==
  
Solved by Kilo_5723.
+
Solved by Kilo_5723. 00:11:52 (+)
 +
 
 +
题意:给出 $2k$ 个坐标在 $[-1000,1000]$ 的整点,求一条直线,使其不经过给定的点,且左右两侧有相同数量的点。
 +
 
 +
题解:按 $x-y$ 的顺序对点的坐标排序,在第 $k$ 个点的上方 $\frac{1}{2}$ 单位距离划一条微微向右下倾斜的直线即可。
 +
 
 +
因为前一天正好讨论了这样的题目,喜提一血。
  
 
== Problem I ==
 
== Problem I ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:一个新数列是通过原来数列的每三个数产生一个中位数得到的,给出新数列,求一个任意的原数列。
 +
 
 +
题解:一个结论是,如果有解,那么一定可以让每个位置最终的值,是它所能影响到的 $3$ 个中位数之一。
 +
 
 +
于是我们可以处理出每个数影响到的三个数,然后 $f[i][j][k]$ 表示位置为 $i-1$ 的数取他影响的 $j$ 个数,位置为 $i$ 的数取他影响的 $k$ 个数的方案是否存在。
 +
 
 +
dp 转移的时候记录前置转移状态,最后 dfs 一下输出一个可行解就行了。
  
 
== Problem J ==
 
== Problem J ==
  
Solved by Weaver_zhu.
+
Solved by Weaver_zhu. 01:18:37 (+3)
 +
 
 +
题意:模拟 LRU
 +
 
 +
题解:用时间标记维护一个 set,再用一个 map 记录名字到时间标记的映射。这样既可以通过时间标记访问,又可以通过名字访问。复杂度 $O(nlogn)$,听说卡常很厉害

Latest revision as of 13:54, 11 September 2019

Problem A

Upsolved by Xiejiadong.

题意:定义 $S(x)$ 表示与结点 $x$ 相邻的点集,给出一列边。要求支持下面两个操作:

  • 将一个区间的边状态置反(本来存在的删除,本来删除的加上);
  • 判断 $S(x)$ 和 $S(y)$ 是否相同。

题解:一个我不太知道的套路:边集 $S(x)$ 可以用一个整数来表示,我们通过给每个点一个随机的权值,然后将点集里面的点权值异或起来得到 $S(x)$ 。

然后维护的话,考虑把边序列分块。

每次修改操作,可以变成两边块单点修改,中间的块,记录一下当前整个块的状态。

查询的时候,每个点的 $S(x)$ ,就是单点的状态和相关块状态的异或,判断两个 $S$ 是否相等即可。

所以需要预处理每个块与相关联点的抑或。

Problem B

Solved by Xiejiadong. 00:19:55 (+)

题意:求 $0/1$ 数列中包含 $0/1$ 数量相等的最长子串和子序列。

题意:子序列,显然就是尽可能多得找 $0/1$ ,那么答案就是 $0/1$ 数量 min 的两倍。

对于子串,如果一个子串的 $0/1$ 数量相等的话,那么他们前缀和相等,前缀和以后,处理相同数的最远位置就好了。

Problem C

Upsolved by Kilo_5723.

题意:给定一个首尾为 1,部分位置被删除的 ETT 序列 $\{a_n\}$,将其还原。

题解:合法的 ETT 序列中,若 $a_l=a_r$,则 $a_{l+1 \dots r-1}$ 之间出现的值不能在 $a_{1 \dots l-1}$ 和 $a_{r+1 \dots n}$ 中出现,同时可以将 $a_{l \dots r}$ 替换成 $a_l$ 而不影响 ETT 的性质。

考虑每次将现 ETT 序列中 $a_l=a_r$ 且 $a_{l+1 \dots r-1}$ 互不相同的段落 $a_{l \cdots r}$。对于其中所有被删除的位 $a_p=-1$,我们可以证明只要 $a_{p-2},a_{p-1}\neq -1,a[l]$,就可以将 $a_p$ 替换成 $a_{p-2}$ 而不影响 ETT 的性质。这个性质对 k+2 也同样生效。

在将所有满足这种条件的位置全部删除之后,我们把 $a_{l+2*k}$ 的所有被删除的位置都填上 $a_l$,再用没有出现过的元素填满剩下的空隙,就能将 $a_{l\dots r}$ 缩成一个数 $a_l$。最后将 $a_{1\dots n}$ 缩点之后所有的删除位置都应该填上了值,此时的序列就是答案。

Problem D

Upsolved by Weaver_zhu. (-3)

题意:求出二元组的个数 $(i,j)$ 使得 $A(i^j) \equiv 0 \pmod{p}, (i \le n, j \le m)$,其中 $A(i)$ 为 $i$ 个数字 $1$ 链接起来的数

题解:把数字用等比数列加起来得 $\frac{10^{i^j}-1}{9} \equiv 0 \pmod{p}$,特判 $p=2,3,5$ 的情况,剩下的转化为求 $i^j\equiv 0 \pmod{x}$,其中 $x$ 是最小的正整数满足 $10^x \equiv 0\pmod{p}$。然后再用上欧拉定理。如何计数呢,枚举 $x$ 的素因子组成,$i$ 必须也包含素因子。分成两种情况,一种是 $x|i$,这样 $j$ 怎么着都行,另一种考虑 dfs $i$ 中包含 $x$ 的素因子组成,$j=cnt(n/cur) \times (m-minj+1)$,其中 $cur$ 是 $x$ 素因子乘起来的结果,$minj$ 是最小的 $j$ 使得 $i^j$ 能整除以 $x$,这个 dfs 的时候都能维护。实际上 dfs 复杂度玄学,但是能过。

由于场上分解质因数写挂了,这题没过。

Problem E

Unsolved.

Problem F

Upsolved by Xiejiadong. (-10)

题意:求最大的子矩阵,保证子矩阵中的任意两个元素的差 $\le m$ 。

题解:考虑枚举上下行边界,把每一列的 max 信息和 min 信息压在一起,然后题目就变成了找一个最长的子区间,使得 max - min $\le m$ 。

这个可以用单调队列优化, max 信息维护单调递减数列, min 信息维护单调递增数列,每次从队尾加入元素,将超过 $m$ 的信息从队头移出。

明明都是 $O(n^3)$ ,场上 ST 表被卡自闭了。

Problem G

Upsolved by Weaver_zhu.

题意:定义一个取石子游戏的游玩过程:单人游戏,若石子总和为奇数,最少的一个石子堆拿走一个。若为偶数,可挑选两个非空石子堆各取走一个。如果不能取了石子还没取完就输了。给定一些石子堆,求有多少个二元组 $(l,r)$ 使得区间的石子堆是能赢的。

题解:首先有个结论:最多的石子小于等于剩下石子总和时,是能赢的。考虑统计不可行的区间:然后枚举每个最大值,向左枚举左端点,向右扩展直到求出最大的不可行区间。比不可行区间少的区间肯定更不可行。看似是个 $O(n^2)$ 的暴力,实际上输出统计的情况,竟然发现是 $O(n)$ 的,实际上也比 $O(nlogn)$ 的不知道快到哪里去了。感性来讲不可行的区间是少的也是短的,严谨的并不会证明。

Problem H

Solved by Kilo_5723. 00:11:52 (+)

题意:给出 $2k$ 个坐标在 $[-1000,1000]$ 的整点,求一条直线,使其不经过给定的点,且左右两侧有相同数量的点。

题解:按 $x-y$ 的顺序对点的坐标排序,在第 $k$ 个点的上方 $\frac{1}{2}$ 单位距离划一条微微向右下倾斜的直线即可。

因为前一天正好讨论了这样的题目,喜提一血。

Problem I

Upsolved by Xiejiadong.

题意:一个新数列是通过原来数列的每三个数产生一个中位数得到的,给出新数列,求一个任意的原数列。

题解:一个结论是,如果有解,那么一定可以让每个位置最终的值,是它所能影响到的 $3$ 个中位数之一。

于是我们可以处理出每个数影响到的三个数,然后 $f[i][j][k]$ 表示位置为 $i-1$ 的数取他影响的 $j$ 个数,位置为 $i$ 的数取他影响的 $k$ 个数的方案是否存在。

dp 转移的时候记录前置转移状态,最后 dfs 一下输出一个可行解就行了。

Problem J

Solved by Weaver_zhu. 01:18:37 (+3)

题意:模拟 LRU

题解:用时间标记维护一个 set,再用一个 map 记录名字到时间标记的映射。这样既可以通过时间标记访问,又可以通过名字访问。复杂度 $O(nlogn)$,听说卡常很厉害