Tweetuzki

分类

一些算法(4) 未归档(2) 题解(14)

/ 注册

全部文章（共20篇）

【题解】蓝魔法师

题意：有一棵个点的树，求出有多少种断边方案，使得每个连通块大小不超过。。边连接的是树上的父亲和儿子节点，可以直接通过树边转移。因此考虑以为根变成有根树，然后进行树上 DP。记表示以为根的子树中，都满足条件，且所在连通块大小为的方案数。转移类似背包，加入一个子树时...

2020-08-04

0 897

【题解】2020牛客暑期多校训练营（第六场）Problem G

介绍一个简短的 G 题构造方案。先特判无解的情况，，或。注意到一个同色的环中必然存在一条边，使得它与或同色。如图：所以我们只需要保证同行 / 列没有两条相邻的边，且相邻两行 / 列同一列 / 行的边颜色不相同。这是很好构造的，对于，直接按顺序依次分配边权；对于，在...

2020-07-27

11 654

【题解】免费菜肴

这题是一个 01 背包的形式，唯一可能的解法是动态规划。但在本题未经处理的情况下，动态规划是不能使用的。因为原图上的转移不是有向无环图，带来了后效性，使得动态规划出错。于是我们需要安排一种转移顺序，使得原图的转移变成 DAG，从而应用动态规划解决问题。结论是，一定存在一种最优方案，使得对于任...

2020-04-27

1 892

【题解】Endless Pallet

题目传送门算法：min-max 容斥、树上背包、NTT。题意简述有一棵个点的树。一开始所有点都是白色，每次操作会随机选择条路径中的一条，将路径上所有点染黑。求所有点都被染黑的期望操作数。。多组数据。对取模。题解套路性地，我们使用 min-max 容斥。如果我们把树画出来，并...

2019-11-29

0 814

CSP-S2 2019 游记

我简直是咸鱼，一只彻头彻尾的咸鱼。慵懒，成为了我本次比赛的主调。 10 月 27 日晚上——也有可能是 10 月 28 日的凌晨，睡眼惺忪的我坐在书桌前，照常奋笔疾书着。作业本放回一本又拿出一本，练习材料做完一张又掏出一张，我就这样机械着循环反复着，完全看不到尽头。在这种困倦又疲劳的情形下，我申...

2019-11-18

1 2381

【题解】牛客NOIP暑期七天营-提高组1

T1: 最短路对于第一档部分分，构造一朵菊花，直接从向其他节点连对应权值的边即可。期望得分分。对于第二档部分分，我们希望每一个点都从最近的那个点连过来。也就是说，对于某个点，我们可以找到一个，满足并且尽可能大，然后从向连一条权值为的边。可以证明这样构造出的图一定是...

牛客NOIP暑期七天营-提高组1

2019-08-19

0 708

牛客OI周赛9-提高组题目记录

牛客OI周赛9-提高组题目记录昨天晚上做了这一套比赛，觉得题目质量挺高，而且有一些非常有趣而且非常清奇的脑回路在里边，于是记录在此。 T1: 扫雷题目链接设 \(f_i\) 表示扫到第 \(i\) 个雷的期望用时，那么我们要求的答案就是 \(f_n\)。我们不难写出一个递推式：...

线段树树动规

2019-04-27

0 630

拆点和拆边

目录拆点和拆边一、总述二、常见的有针对性的算法针对点权针对边权三、拆点过程实例 ...

图论

2019-02-23

1 668

动态 DP 学习笔记

不得不承认，去年提高组 D2T3 对动态 DP 起到了良好的普及效果。动态 DP 主要用于解决一类问题。这类问题一般原本都是较为简单的树上 DP 问题，但是被套上了丧心病狂的修改点权的操作。举个例子，我们来看一道例题。【模板】动态 DP 给定一棵 \(n\) 个点的树。\(i\) 号...

动态 DP 树动规树链剖分

2019-01-15

0 547

树杂谈（上）

目录树杂谈（上） 1. 树的基本概念和一些有关定义树的基本概念树相关的定义 2. 生成树 Kruskal 算法 Prim 算法 ...

树生成树最近公共祖先树链剖分

2018-12-22

1 915