hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

Stressful Training

题意：有n台笔记本电脑，它们有一个初始电量ai，和每分钟耗电量bi,有一场训练需要持续k分钟，在每一分钟开始时电量不能为负，你能使用一个多大功率的充电器使其能完成训练，如果没有，则输出-1. 思路：二分枚举答案，如果一个超大的功率都不行，则说明没有，输出-1，判断一个功率是否可行，可以记录在该功率时...

二分

2020-09-29

1 633

[SCOI2009]最长距离

题意：有一个n*m的地图，为1表示为有障碍物，你可以移走t个障碍物，求二个可以相互到达的点最大的欧几里德距离? 思路：dfs暴力求出每一个点在移走t个障碍物后能到达的点，然后暴力求最大距离。代码： #include <bits/stdc++.h> typedef long long l...

dfs

2020-09-28

0 552

List Of Integers

题意：给你x、p、k三个数，让你求大于x的第k个与p互素的数？思路：求出p的质因子，然后求小于等于x的与p互质的个数求出为j，题意就相当于求大于0的第k+j个与p互素的数了，二分枚举答案，求小于等于某一个数与p互质的个数使用容斥原理计算得出。代码： #include<cstdio> ...

二分容斥

2020-09-25

1 637

蚯蚓

题意：有n条蚯蚓，在m秒内每一秒选择最长的一条蚯蚓分成二份，其余蚯蚓增长q长度，然后按要求输出。思路：用二个队列进行模拟，维护二个队列的单调性，一个队列加入长的，另一个队列加入短的，这样二个队列就是单调的，队列中保持0时刻的长度。代码： ...

模拟队列

2020-09-01

2 669

[SCOI2009]生日礼物

题意：有一个有n个彩珠、m种彩珠的彩带，使每一种彩珠都包含的最小长度是多少？思路：离散+尺取法代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=99824435...

离散尺取法

2020-08-27

1 612

[SCOI2010]游戏

题意：你有n件装备，每件装备有两个属性，每件装备只能用一次，你打boss时属性只能从1开始连续用装备攻击，求你的最大攻击次数。思路：二分图匹配问题，属性与物品编号连边，从1开始匹配，用匈牙利算法，冲突时进行改变。代码： #include <bits/stdc++.h> typedef...

2020-08-27

1 712

Mr. Kitayuta, the Treasure Hunter

题意：有一个由30001个小岛组成的群岛，编号为0-30000，一字排开，首先从0岛跳的d岛，然后每一次跳的距离与上一次的距离绝对值等于小于1，有些岛有宝石。思路：dp:ma[i]表示i岛的宝石数目。dp[i][j]表示跳到i时跳的距离为250-j+d时收集的最大宝石数。初始化dp[d][250]...

dp

2020-08-27

1 537

树学

题意：给你一颗树，你选择一个节点当根，求所有点的深度和最少为多少？思路：树状dp+换根一开始随便选一个点当根计算结果。dp[i]表示以i为根的子树节点的深度和。se[i]表示以i为根的子树的节点数目。换根：dp[v]=dp[u]+n-2*se[v];(v为u的子节点，根从u转向v时，以v为根的子树...

树状结构换根

2020-08-22

1 577

Accumulation Degree

题意：给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。思路：树状dp+换根：flow[i]为以i为子树i到子树叶子节点的流量最大值。ans[i]表示以i为根节点时的答案。flow[u]= min(flow[v],cost(u,v))(v为u的子节...

换根树状dp

2020-08-22

1 775

选课

题意：你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？思路：树状dp没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条...

树状dp

2020-08-22

5 537