2019 Multi-University,Nowcoder Day 3

Problem A

Unsolved.

Problem B

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

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

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

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

Problem C

Unsolved.

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 (+)

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)$，听说卡常很厉害