2020/05/09：\\
第二场团队赛：2019 ICPC Asia Yinchuan Regional[[https://www.jisuanke.com/contest/5527]]\\
==== 比赛过题情况: ====
当场过题情况：\\
A:思路&代码：Yuki\\
B:思路&代码：Wzy\\
C:\\
D:思路&代码：Wzy\\
E:\\
F:思路&代码：Wzy\\
G:思路&代码：Yuki\\
H:\\
I:思路&代码：Yuki\\
J:\\
K:思路：Yuki&Famer 代码：Yuki\\
L:\\
M:\\
N:思路&代码：Famer\\
==== 题解： ====
**A：**
题意：给出一个n，然后给出n个名字、颜色、分数，然后给出5个奖励名字和一个奖励颜色，从n个中选择5个，选出的5个名字不重复，如果出现一个奖励名字，则获得10%的总评分数，出现一个奖励颜色，则获得20%的总评分数，求最大的总评分数。

思路：因为每个名字只能选一个，将卡片按名字分类，只能选5张卡片，加成最多为150%\\
dp求解，f[i][j][k]表示前i种名字，已经选了j张卡片，加成为10*k%时的最大（未加成）的分数和\\
可得：f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k-p]+a[x])，x是任意名字为i的卡片，p是x的加成\\

**B：**签到题\\

**C：**\\
题意：给定一个二进制表示的n，让你找满足如下要求的数对（i，j）的个数
$0 \leqslant j \leqslant i \leqslant n$
$ i & n = i $
$ i & j = 0 $

思路：打表发现对于单个i满足上述规律的j的数量为$2^{(num \ of \ 0 \ in(i)_2)}$
因此对着n的二进制可以从后往前dp计算每一位能够贡献出多少个i，这些i能够贡献出多少0

**D：**\\
计算 $$\sum_{a_i\le m} \big[ (\gcd(a_1,\cdots,a_n)==d)\prod_{j=1}^n a_j^k\big]$$\\
其中 $$m,d\le 10^5,n\le 10^{100000} ,k\le 10^9$$\\
解：设$$r=\left \lfloor \frac{m}{d} \right \rfloor  $$
则原式等于  $$d^{nk} \sum_{a_i\le r} \big[(\gcd(a_1,\cdots,a_n)==1)\prod_{j=1}^n a_j^k\big]$$
反演一下得 $$d^{nk}\sum_{d_0=1}^r \mu(d_0) \sum_{a_i\le r,d_0|a_i}(\prod_{j=1}^n a_j^k)$$
根据对称性 $$ \sum_{a_i\le r,d_0|a_i}(\prod_{j=1}^n a_j^k)=d_0^{nk}(\sum_{j=1}^\left \lfloor \frac{r}{d_0} \right \rfloor j^k)^n$$
所以就是要求$$d^{nk}\sum_{d_0=1}^r \mu(d_0)d_0^{nk}(\sum_{j=1}^\left \lfloor \frac{r}{d_0} \right \rfloor j^k)^n$$
由于n只在指数上出现，可以用$$a^{\phi(p)} \equiv 1 \pmod{p}$$
把n干掉 再处理一下\(j^k\)的前缀和\\
就可以求了\\
最后吐槽一下 这道题的模数p居然不是个质数！！！！！

**E：**\\
题意：定义一个multiset的权值为里面任意两个数的异或和的平方的和。\\
现在给出一棵有根树(1为根)，每个点有点权，定义p(x,k)为x子树中距离x不超过k的所有点的点权构成的multiset的权值，现在要对每个i∈[1,n]求p(i,k)

思路：

**F：**\\
计算$$\sum_{a=2}^n \bigg( a\sum_{b=a}^n \left \lfloor \log_{a} b \right \rfloor \left \lceil \log_{b} a \right \rceil \bigg)$$
其中\(n\le 10^{12}\)\\
解：显然，\(\left \lceil \log_{b} a \right \rceil =1\)\\
当\(a\le \sqrt{n}\)时:   \(\left \lfloor \log_{a} b \right \rfloor\)至多有\(\log n\)种取值，枚举即可\\
当\(a> \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor=1\) 可以直接求和\\

**G：**\\
线段树水题

**H：**\\
题意：给出一张图，有x条无向边，有y条有向边，保证无向边都是正权值，有向边可能有负权值，并且保证如果一条有向边ai→bi，那么在该图中，bi不可能到达ai现在询问从s出发到任意一点的最短路。

思路：把无向边连成的每个联通块看成一个新点，并且有有向边将他们连接起来是一个DAG。并且无向图的连通块里面没有负权边，可以跑dijkstra，然后根据拓扑序dp一下即可。每次dijkstra开始要把与上一层的连通块有边的点都压入栈中。（详细见代码...）

AC代码：[[https://paste.ubuntu.com/p/xxHYmNthqc/]]

**I:**\\
题意：进制转换\\
题解：由于使用c++需要高精度，所以此题使用了python\\

**J:**\\

**K：**\\
题意：求两个矩阵的最大子矩阵，每个n*m的矩阵中填满互不相同的1-n*m的数。\\
题解：1.求某个矩阵的某个位置最多向上延申多少，再对每一行用单调栈求解

**L：**

**M:**

**N：**签到题