Tweetuzki

题解

一些算法(4) 未归档(2)

/ 注册

全部文章 / 题解（共14篇）

【题解】蓝魔法师

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

2020-08-04

0 898

【题解】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

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

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

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

2019-08-19

0 709

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

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

线段树树动规

2019-04-27

0 630

题解 CF934A 【A Compatible Pair】 ——贪心

题意：给定两个数列 \(A\) 、 \(B\) ，元素个数分别为 \(n\) ， \(m\) \((2 \le n,m \le 50)\) 。数列中所有元素大小均在 \(-10^{9}\) 到 \(10^{9}\) 之间。现要求在 \(A\) 数列中删掉一个元素，使得 \(A\) 中任一...

贪心

2018-06-18

0 663

洛谷 P3381 【【模板】最小费用最大流】

题目描述如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。输入第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含四个正整数ui、vi、wi、fi，表示...

网络流

2018-02-06

0 556

洛谷 P3376 【【模板】网络最大流】

题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。输入第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）...

网络流

2018-02-04

0 478

洛谷 P1027 【Car的旅行路线】

题目描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例...

广搜最短路

2018-01-26

0 710