Difference between revisions of "2019 Multi-University,Nowcoder Day 3"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 43: | Line 43: | ||
== Problem I == | == Problem I == | ||
− | + | Upsolved by Xiejiadong. | |
+ | |||
+ | 题意:一个新数列是通过原来数列的每三个数产生一个中位数得到的,给出新数列,求一个任意的原数列。 | ||
+ | |||
+ | 题解:一个结论是,如果有解,那么一定可以让每个位置最终的值,是它所能影响到的 $3$ 个中位数之一。 | ||
+ | |||
+ | 于是我们可以处理出每个数影响到的三个数,然后 $f[i][j][k]$ 表示位置为 $i-1$ 的数取他影响的 $j$ 个数,位置为 $i$ 的数取他影响的 $k$ 个数的方案是否存在。 | ||
+ | |||
+ | dp 转移的时候记录前置转移状态,最后 dfs 一下输出一个可行解就行了。 | ||
== Problem J == | == Problem J == |
Revision as of 05:49, 26 July 2019
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
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)$,听说卡常很厉害