2020-2021:teams:famerwzyyuki:2020_05_09
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:2020_05_09 [2020/05/14 17:11] wzy2001wzy |
2020-2021:teams:famerwzyyuki:2020_05_09 [2020/05/15 19:32] (当前版本) yuki |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| 2020/05/09：\\ | 2020/05/09：\\ | ||
| - | 第二场团队赛：\\ | + | 第二场团队赛：2019 ICPC Asia Yinchuan Regional[[https://www.jisuanke.com/contest/5527]]\\ |
| - | 比赛过程:\\ | + | ==== 比赛过题情况: ==== |
| 当场过题情况：\\ | 当场过题情况：\\ | ||
| - | A:\\ | + | A:思路&代码：Yuki\\ |
| B:思路&代码：Wzy\\ | B:思路&代码：Wzy\\ | ||
| C:\\ | C:\\ | ||
| 行 9: | 行 9: | ||
| E:\\ | E:\\ | ||
| F:思路&代码：Wzy\\ | F:思路&代码：Wzy\\ | ||
| - | G:\\ | + | G:思路&代码：Yuki\\ |
| H:\\ | H:\\ | ||
| - | I:\\ | + | I:思路&代码：Yuki\\ |
| J:\\ | J:\\ | ||
| - | K:\\ | + | K:思路：Yuki&Famer 代码：Yuki\\ |
| L:\\ | L:\\ | ||
| M:\\ | M:\\ | ||
| - | N:\\ | + | 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：**签到题\\ | **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：**\\ | **D：**\\ | ||
| 计算 $$\sum_{a_i\le m} \big[ (\gcd(a_1,\cdots,a_n)==d)\prod_{j=1}^n a_j^k\big]$$\\ | 计算 $$\sum_{a_i\le m} \big[ (\gcd(a_1,\cdots,a_n)==d)\prod_{j=1}^n a_j^k\big]$$\\ | ||
| 行 32: | 行 48: | ||
| 就可以求了\\ | 就可以求了\\ | ||
| 最后吐槽一下 这道题的模数p居然不是个质数！！！！！ | 最后吐槽一下 这道题的模数p居然不是个质数！！！！！ | ||
| + | |||
| + | **E：**\\ | ||
| + | 题意：定义一个multiset的权值为里面任意两个数的异或和的平方的和。\\ | ||
| + | 现在给出一棵有根树(1为根)，每个点有点权，定义p(x,k)为x子树中距离x不超过k的所有点的点权构成的multiset的权值，现在要对每个i∈[1,n]求p(i,k) | ||
| + | |||
| + | 思路： | ||
| **F：**\\ | **F：**\\ | ||
| 行 37: | 行 59: | ||
| 其中\(n\le 10^{12}\)\\ | 其中\(n\le 10^{12}\)\\ | ||
| 解：显然，\(\left \lceil \log_{b} a \right \rceil =1\)\\ | 解：显然，\(\left \lceil \log_{b} a \right \rceil =1\)\\ | ||
| - | 当\(a\le \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor\)只有\(\log n\)种取值，枚举即可\\ | + | 当\(a\le \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor\)至多有\(\log n\)种取值，枚举即可\\ |
| 当\(a> \sqrt{n}\)时: \(\left \lfloor \log_{a} b \right \rfloor=1\) 可以直接求和\\ | 当\(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：**签到题 | ||
| + | |||
2020-2021/teams/famerwzyyuki/2020_05_09.1589447505.txt.gz · 最后更改: 2020/05/14 17:11 由 wzy2001wzy
