2020-2021:teams:i_dont_know_png:week_summary_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/09 15:18] potassium [团队会议] |
2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/16 21:04] (当前版本) potassium |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020.05.04-2020.05.10 周报 ====== | + | ====== 2020.05.03-2020.05.09 周报 ====== |
| 团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。 | 团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。 | ||
| 行 11: | 行 11: | ||
| 本周无团队训练。 | 本周无团队训练。 | ||
| - | =====团队会议===== | + | ===== 团队会议 ===== |
| - | 2020.5.9 确定[[.:training_plan_2020spring|训练计划]] | + | 2020.5.9 建立[[.:skill_tree|技能树]]，确定[[.:training_plan_2020spring|训练计划]] |
| - | =====个人训练===== | + | |
| - | ====nikkukun==== | + | ===== 个人训练 - nikkukun ===== |
| - | === 比赛 === | + | ==== 比赛 ==== |
| 本周冯如杯，没有打比赛。 | 本周冯如杯，没有打比赛。 | ||
| - | === 学习总结 === | + | ==== 学习总结 ==== |
| - | == 容斥原理 == | + | === 容斥原理 === |
| 容斥的一些理解： | 容斥的一些理解： | ||
| 行 45: | 行 44: | ||
| - | == 图论 == | + | === 图论 === |
| 平面图的一些相关结论： | 平面图的一些相关结论： | ||
| 行 54: | 行 53: | ||
| - | === 本周推荐 === | + | ==== 本周推荐 ==== |
| - | * [[https://codeforces.com/contest/1342/problem/F|1342F - Make It Ascending]] | + | === ARC 092 F - Two Faced Edges === |
| - | * 位运算 DP | + | |
| - | * 最优性的转移需要想一想 | + | |
| - | * 通过改变 DP 状态减小空间。这题要记录三个状态：last, cnt, mask。一开始的想法是用 ''%%f[last][cnt][mask]%%'' 表示一个状态是否存在，这样数组很大，会爆。即使后来变成了 ''%%f[last][mask]%%'' 记录最小 ''%%cnt%%''，两个 $2^{15}$ 级别的数也会爆。正解是使用 ''%%f[cnt][mask]%%'' 记录最小 ''%%last%%''，这样由于 ''cnt'' 的级别非常小，整体数组是不会爆的。 | + | |
| + | [[https://atcoder.jp/contests/arc092/tasks/arc092_d|题目链接]] | ||
| + | **题意**：给一个 $n$（$\leq 1,000$）个点和 $m$（$\leq 2 \times 10^5$）条边的有向图，求反转每一条边的方向后，整个图的强联通分量是否改变。 | ||
| - | ====qxforever==== | + | **题解**：$u, v$ 在同一个 SCC 中的充要条件是 $u, v$ 可以相互到达。这题只需要通过讨论两个点的连通情况就能解决。 |
| + | 此外，本题要求一个“不通过某条边，是否能从 $u$ 走到 $v$”的问题（或者说，是否还有通过其他边到达的方法）。通过依次以每条边作为起点，给当前未访问的点标记最早能到达它的边的编号 $low_i$，再把边的枚举顺序反过来，记录最早能到达它的编号 $upp_i$。这相当于说，对一个点 $i$，边 $[low_i, upp_i]$ 中存在边可以到达，只要区间长度不小于 $1$，就有两条以上的方法可以到达。 | ||
| - | === 比赛 === | + | 这个思路可以用于寻找“是否有一种以上的方案选择”的问题。 |
| + | |||
| + | |||
| + | ===== 个人训练 - qxforever ===== | ||
| + | |||
| + | |||
| + | ==== 比赛 ==== | ||
| 2020.05.01 [[.:qxforever:codeforces_round_638_div._2|Codeforces Round #638 (Div. 2)]] | 2020.05.01 [[.:qxforever:codeforces_round_638_div._2|Codeforces Round #638 (Div. 2)]] | ||
| 行 73: | 行 78: | ||
| 2020.05.03 [[.:qxforever:qkoi_r1|QkOI Round1]] | 2020.05.03 [[.:qxforever:qkoi_r1|QkOI Round1]] | ||
| - | ===学习总结=== | + | ==== 学习总结 ==== |
| 无 | 无 | ||
| - | ===本周推荐=== | + | ==== 本周推荐 ==== |
| - | 无 | + | [[2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1#E|[QkOI#R1] E Quark and Game]] 想不到 |
| - | ====Potassium==== | + | ===== 个人训练 - Potassium ===== |
| - | ===比赛=== | + | ==== 比赛 ==== |
| 无 | 无 | ||
| - | ===学习总结=== | + | ==== 学习总结 ==== |
| - | == 莫比乌斯反演 == | + | === 莫比乌斯反演 === |
| 莫比乌斯反演：$g(n)=\sum_{d|n}f(d)$，则$f(n)=\mu *g$ | 莫比乌斯反演：$g(n)=\sum_{d|n}f(d)$，则$f(n)=\mu *g$ | ||
| 行 132: | 行 137: | ||
| $id=1*\phi$（枚举约数，每个约数求出小于他且与他互质的个数，即求这个约数为分母的真分数个数，它们的和必为$n$，例子见下： | $id=1*\phi$（枚举约数，每个约数求出小于他且与他互质的个数，即求这个约数为分母的真分数个数，它们的和必为$n$，例子见下： | ||
| - | $\frac 1{12}\frac 2{12}\frac 3{12}\frac 4{12}\frac 5{12}\frac 6{12}\frac 7{12}\frac 8{12}\frac 9{12}\frac {10}{12}\frac {11}{12}\frac {12}{12}$ | + | $$\frac 1{12}\frac 2{12}\frac 3{12}\frac 4{12}\frac 5{12}\frac 6{12}\frac 7{12}\frac 8{12}\frac 9{12}\frac {10}{12}\frac {11}{12}\frac {12}{12}$$ |
| 可以化简为 | 可以化简为 | ||
| - | $\frac 1{12},\frac 5{12},\frac 7{12},\frac{11}{12}$（$\phi(12)=4$） | + | * $\frac 1{12},\frac 5{12},\frac 7{12},\frac{11}{12}$（$\phi(12)=4$） |
| - | $\frac 1{6},\frac 5{6}$（$\phi(6)=2$） | + | * $\frac 1{6},\frac 5{6}$（$\phi(6)=2$） |
| - | $\frac 1{4},\frac 3{4}$（$\phi(4)=2$） | + | * $\frac 1{4},\frac 3{4}$（$\phi(4)=2$） |
| - | $\frac 1{3},\frac{2}{3}$（$\phi(3)=2$） | + | * $\frac 1{3},\frac{2}{3}$（$\phi(3)=2$） |
| - | $\frac 12$（$\phi(2)=1$） | + | * $\frac 12$（$\phi(2)=1$） |
| - | $\frac 11$（$\phi(1)=1$） | + | * $\frac 11$（$\phi(1)=1$） |
| - | 根据$id=1*\phi$，有$\phi=id*\mu$ | + | 根据$id=1*\phi$，有$\phi=id*\mu$。 |
| 题目略（摸了，下次再补） | 题目略（摸了，下次再补） | ||
| 行 154: | 行 159: | ||
| 常用套路：$\sum_{i}\sum_{j}f(i,j)$变换为$\sum_{k}\sum_{i}\sum_{j}[f(i,j)=k]$这样拆出来，比如$f(i,j)=\gcd(i,j)$的时候拆出来比较容易进行反演之类的操作。 | 常用套路：$\sum_{i}\sum_{j}f(i,j)$变换为$\sum_{k}\sum_{i}\sum_{j}[f(i,j)=k]$这样拆出来，比如$f(i,j)=\gcd(i,j)$的时候拆出来比较容易进行反演之类的操作。 | ||
| - | == 组合数学 == | + | === 组合数学 === |
| 需要注意的一个式子：$\sum_{i=L}^{R}C_{i}^{x}=C_{R+1}^{x+1}-C_L^{x+1}$。其实就是对$C_i^x=C_{i+1}^{x+1}-C_{i}^{x+1}$求和。 | 需要注意的一个式子：$\sum_{i=L}^{R}C_{i}^{x}=C_{R+1}^{x+1}-C_L^{x+1}$。其实就是对$C_i^x=C_{i+1}^{x+1}-C_{i}^{x+1}$求和。 | ||
| - | ===本周推荐=== | + | ==== 本周推荐 ==== |
| - | 无 | + | |
| + | === CF994F Compute Power === | ||
| + | |||
| + | [[https://codeforces.com/contest/994/problem/F|题目链接]] | ||
| + | |||
| + | **题意**：$n\leq 50$个任务，每个任务$a,b$两个属性$(1\leq a_i\leq 10^8,1\leq b_i\leq 100)$。有一些机器，每台机器可以执行最多两次任务，执行两次的时候要求第二个任务比第一个任务的$a$小。设第一次执行任务的集合为$S$，最小化$\frac{\sum_{i\in S}a_i}{\sum_{i\in S} b_i}$。 | ||
| + | |||
| + | **题解**：根据01分数规划套路，二分答案$m$，即求${\sum_{i\in S}a_i-mb_i}\leq 0$能否满足。按$a$从大到小、$a-mb$从大到小排序，合并一下$a$相同的项（可以在$dp$的时候进行这一步，要记录第$i$项开始与第$i$项的$a$相同的元素有$cnt_i$个），按顺序枚举，分别加入$S$或补集$C_US$，有任意时刻$S$中元素多于$C_US$。于是设$f[i][j]$表示到$i$，有$j$个分配到$1$且可用（可分配一个$2$）的任务的最小值，则对于一个$i$，枚举分配给第二个任务的个数$k\in[0,cnt_i]$，有 | ||
| + | |||
| + | $$f[i][j+(cnt_i-k)-k]=\min(f[i][j+(cnt_i-k)-k],f[i-1][j]+\sum_{l=i+k}^{i+cnt_i-1} (a_l-m\times b_l))$$ | ||
| + | |||
| + | 这题需要记录的地方在于，将相同的项合并，从而简化$dp$过程。 | ||
2020-2021/teams/i_dont_know_png/week_summary_1.1589008717.txt.gz · 最后更改: 2020/05/09 15:18 由 potassium
