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

题意：求出二元组的个数$(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

Unsolved. (-10)

Problem G

Unsolved.

Problem H

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

Problem I

Unsolved.

Problem J

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

题意：模拟LRU

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