2020-2021:teams:famerwzyyuki:2020_05_09

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:famerwzyyuki:2020_05_09 [2020/05/15 16:23]
yuki
+++ 2020-2021:teams:famerwzyyuki:2020_05_09 [2020/05/15 19:32] (当前版本)
yuki
@@ 行 11: / 行 11: @@
 G:思路&代码：Yuki\\
 H:\\
-题意：给出一张图，有x条无向边，有y条有向边，保证无向边都是正权值，有向边可能有负权值，并且保证如果一条有向边ai→bi，那么在该图中，bi不可能到达ai现在询问从s出发到任意一点的最短路。
 I:思路&代码：Yuki\\
 J:\\
@@ 行 29: / 行 28: @@
 **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：**\\
@@ 行 44: / 行 50: @@
 **E：**\\
+题意：定义一个multiset的权值为里面任意两个数的异或和的平方的和。\\
+现在给出一棵有根树(1为根)，每个点有点权，定义p(x,k)为x子树中距离x不超过k的所有点的点权构成的multiset的权值，现在要对每个i∈[1,n]求p(i,k)
+思路：
 **F：**\\
@@ 行 57: / 行 67: @@
 **H：**\\
 题意：给出一张图，有x条无向边，有y条有向边，保证无向边都是正权值，有向边可能有负权值，并且保证如果一条有向边ai→bi，那么在该图中，bi不可能到达ai现在询问从s出发到任意一点的最短路。
+思路：把无向边连成的每个联通块看成一个新点，并且有有向边将他们连接起来是一个DAG。并且无向图的连通块里面没有负权边，可以跑dijkstra，然后根据拓扑序dp一下即可。每次dijkstra开始要把与上一层的连通块有边的点都压入栈中。（详细见代码...）
+AC代码：[[https://paste.ubuntu.com/p/xxHYmNthqc/]]
 **I:**\\
@@ 行 73: / 行 87: @@
 **N：**签到题

2020-2021/teams/famerwzyyuki/2020_05_09.1589530984.txt.gz · 最后更改: 2020/05/15 16:23 由 yuki