灯又烬

题解

学习笔记(4) 未归档(2) 算法总结(2)

/ 注册

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

牛牛和牛可乐的赌约 [逆元]

题意 n面骰子，投m次，若每次均为n则牛牛赢，求牛牛输的概率。（读了半天的赢的概率，wa傻了都）题解直接对分母用费马小定理求逆元即可，概率为 code #include <bits/stdc++.h> #define reg register #define ll long long...

2020-09-20

0 610

联合权值

弱鸡也来写题解混牛币了~虽然太菜了只好写写暴力的水题.. 题解题目说，n个点n-1条边的无向连通图..这不就是树嘛..那见到树就喜欢去想dfs..求所有的有序点对，但是权值是无序的，所以只需把每个联合权值算两次即可考虑到距离为2的两点在树形结构中仅有两种，一是当前点的儿子节点与当前点的父亲节点，二...

2020-09-17

0 594

NC16884 食物链 [并查集]

题意存在一个环形食物链，即a->b->c->a，给出m条语句，均为两个动物是同一种，或者a吃b，问有多少句是假的，先入为主，若两句冲突，第一句为真。题解使用并查集。以每个动物自身等级为基准，设定所有其他动物的等级，具体表现就是：开n*3的数组，a代表a所在等级，a+n代表吃a...

2020-06-02

0 717

NC15808 任意点 [并查集]

题意平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。请问至少需要加多少个点，使得点对之间互相可以到达。题解如果n个点之间可以相互到达，则将n个点放入一个集合。所需添加的点数就是集合数-1故：可以遍历所有点对，若彼此可达，则使用并查集将二者并到一...

2020-06-02

1 945

NC14685 加边的无向图 [并查集]

题意一个 n 个点，m 条边的无向图，加边使无向图联通题解并查集板子题使联通的两点union，最后得到x棵树，即无向图的x个连通子图，两两之间填一条边即可得答案为x-1 Code #include <bits/stdc++.h> using namespace std; cons...

2020-06-02

0 582

NC14291 Cut [贪心]+[堆]

题意一个长度为n的序列，一次可将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和，求分成n个子序列需要的最大代价。题解反过来思考，令其从n个长度为1的序列合成为一个长度为n的序列。每次合成代价为两序列之和。这时这道题就跟合并果子题十分相似了(合并果子)，只需将小根堆换成大根堆即可得到...

堆贪心

2020-06-02

1 746

[JSOI2007]建筑抢修 [贪心]+[堆的应用]

题意一共有n个设施需要修复，给出每个设施修复需要的时长，和每个设施被修复好的最晚时间（deadline），求最多能修复好多少个设施。题解贪心，首先先将所有修复任务按照最晚时间由小到大排序，如果本题开始时间固定，那就直接按顺序计算即可（hdoj2037），但是因为每个设施的开始时间是弹性的，所以...

堆贪心

2020-06-02

0 576