- 博客(18)
- 收藏
- 关注
RSS订阅原创 牛客多校二 Cover the Tree（dfs序）
题目链接题意：给你一颗树，让你找出最少的链使得所有的链的并集覆盖所有的边。思路：要覆盖所有的边，首先可以确定一定是叶子到叶子的，所以条数已经可以确定一定是叶子节点数+12\frac{叶子节点数+1}{2}2叶子节点数+1，继续思考在dfs序情况下，把叶子节点按根节点的几个分支分类，尽可能满足 每一类都有叶子和其它类相连，这样每次连的时候就得连有相对距离较远的叶子。至于为什么不是最前与最后连，就是容易出现中间距离较近导致有些边无法覆盖。这是我的大致理解，至于证明题解已经给出，我看的不是很懂。代码：#
2020-07-14 23:04:06
145
原创 牛客多校第一场 Minimum-cost Flow（最小费最大流）
题目链接题意：给你一张有n个点m条边组组成的无向图，每条边的容量未知，但是给你每条边通过1流量所需要的花费，现在给你q个询问，每次询问的给你u，v表示将每条边的容量改为u/v，问你从1-n流过流量为1的最小花费是多少。思路：很快就能想到这是个最小费最大流问题，但是询问为1e5每次重新跑费用流一定是会超时的，但是我们知道每次询问我们需要的最大的流量和当前流量下的最小花费即可，因此我们可以跑一次就把所有的需要的流量和最小花费全部存在来，然后处理一下前缀就可以了，在询问中乱搞一下就可以把答案搞出来了。#in
2020-07-14 18:02:48
361
原创 实验四 动态规划算法设计与应用实验报告
实验四 动态规划算法设计与应用一. 实验目的和要求1.加深对动态规划算法的基本原理的理解，掌握用动态规划方法求解最优化问题的方法步骤及应用；2.用动态规划设计整数序列的最长递增子序列问题的算法，分析其复杂性，并实现；3.用动态规划设计求凸多边形的三角剖分问题的算法，分析其复杂性，并实现。4.选做题：用动态规划设计求解0/1背包问题的算法，分析其复杂性，并实现。二. 实验步骤实...
2020-04-11 20:11:42
3442
原创 2020年上学期第二场——FJUT&FJNU友谊赛 F，I题解
I 后缀自动机(SAM)拓扑序上dp模板签到题签到题，若石头总数为奇数则先手胜，反之后手胜。注意累加爆longlong，所以我们可以统计奇数的个数，若奇数的个数为奇数则先手胜，反之后手胜。好像卡cin了，抱歉没有注意到这个，下次保证不会卡cin。#include <bits/stdc++.h>typedef long long ll;using namespace std;i...
2020-02-29 18:25:39
264
原创 2020牛客寒假算法基础集训营1题解（完结）
A：honoka和格点三角形题意： 定义满足以下三个条件的三角形是“好三角形”：1.三角形的三个顶点均为格点，即横坐标和纵坐标均为整数。2.三角形的面积为1。3.三角形至少有一条边和x轴或y轴平行。思路：面积为1，那就是底为1高为2，底为2高为1。注意底为1高为2时不能有出现。以横着为底边举例：底2高1：下部横坐标可以取m-2种，高上部可以取m个，然后除了第一行和最后一行只能取一种...
2020-02-06 01:03:44
212
原创 Codeforces Round #615 (Div. 3)（完结）
A - Collecting Coins题意：给你四个数a,b,c,n;让你把n给个a，b，c三个数使a，b，c相等且n恰好分完思路：找出a，b，c中最大的先将其他两个加到最大的，然后判断剩下的n是否能被3整除即可；#include<bits/stdc++.h>#define accept return 0#define mes(a, b) memset(a, b, si...
2020-01-27 01:36:51
1303
原创 Educational Codeforces Round 80 (Rated for Div. 2)题解
A. Deadlinex+⌈dx+1⌉x + \lceil \frac{d}{x + 1} \rceilx+⌈x+1d⌉ 我们就可以想到基本不等式，即取x/2时不等式取到最大值，于是就可以得出答案。#include<bits/stdc++.h>using namespace std;typedef long long int ll;int main(){ int T;...
2020-01-15 18:12:32
196
原创 Codeforces Round #611 (Div. 3) 题解
A - Minutes Before the New Year计算距离0点还有几分钟，全部化成分钟来计算计算距离0点还有几分钟，全部化成分钟来计算计算距离0点还有几分钟，全部化成分钟来计算#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int T; cin >&g...
2020-01-10 17:36:56
185
原创 FJNU2019年低年级程序设计大赛题解（全）
问题 A: 你们要的暴力时间限制: 1 Sec 内存限制: 128 MB题目描述：已知某个数 x 的因子个数小于3个，那么称这个数 x 为good number。现在给你一段区间 [L,R] ,问你区间内是否存在good number区间[L,R]表示区间内元素为 L，L+1，L+2，。。。。R-1, R；1<= L<=R <= 1e9，保证L和R的差值不超过500...
2019-12-06 18:56:19
576
原创 CodeForces - 1243B2 Character Swap (贪心 + 模拟)
This problem is different from the easy version. In this version Ujan makes at most 2n swaps. In addition, k≤1000,n≤50 and it is necessary to print swaps themselves. You can hack this problem if you ...
2019-11-16 19:05:43
245
原创 FJUT 2019暑假第三次周赛 C - 郭先生的魔法阵
牛客原题，出题人zb背锅。题意：关于魔法阵问题，选择最小的代价并且满足题目所需的要求；思路: 从小到大枚举每个能量大小，计算出破坏魔法阵需要的代价，取最小的就好了，因为所需要的魔法币最多只有200，所以开两个大小为200的数组暴力枚举代价就好了。详细过程看代码注释。#include <ctime>#include <map>#include <set>...
2019-08-16 21:14:16
226
原创 FJUT 2019暑假第三次周赛 A - 人生的赌注
出题人如是说道做不出这个题可能是不知道逆元，这里介绍逆元的最简单的求法：费马小定理。其他的移步大佬微博：点这里公式就一个： p−1p ^ { -1}p−1 === pmod−2p^{mod - 2}pmod−2 推导点这里实现起来是这样的：比如答案让你求: ans = np\frac{n}{p}pn === n∗n *n∗ p−1p ^ { -1}p−1 =nnn ∗*∗...
2019-08-16 21:01:08
145
原创 ecust暑假网络训练赛一 — Tree （dfs+思维）
Consider a un-rooted tree T which is not the biological significance of tree or plant, but a tree as anundirected graph in graph theory with n nodes, labelled from 1 to n. If you cannot understand th...
2019-08-05 17:16:10
156
原创 qls的魔法（区间dp）
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话...
2019-07-11 11:43:18
295
原创 G - Supermarket POJ - 1456（并查集 优先队列两种写法）
超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.每天只能卖一个商品.现在你要让超市获得最大的利润.Input多组数据.每组数据第一行为一个整数N (0 <= N <= 10000), 即超市的商品数目之后N行各有两个整数, 第i行为 pi, di (1 <= pi, di <= 10000)Output对于每一...
2019-06-28 16:43:44
221
原创 福建师范大学2018级“Good bye 2018，Hello 2019”友谊赛F题题解
首先，祝贺大家度过了(单身的）2018年，开启(单身的)2019年。这个辞旧迎新的日子里，就让我们在A题中度过吧。那么开始看题面:Given a positive integer n, write a program to find out a nonzeromultiple m of n whose decimal representation contains only the dig...
2019-01-02 00:05:14
568
原创 **FJNU2018第三次欢乐良心（被狗吃了）友谊赛B题题解**
You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. In
2018-12-15 15:31:45
561
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人