- 博客(37)
- 收藏
- 关注
RSS订阅原创 习题：战争调度（dp）
题目传送门思路dp[i][j]dp[i][j]dp[i][j]表示以i号节点为根节点字数有j个平民参加战争的最大值ans=maxi=1n{dp[1][i]}ans=\max _{i=1}^{n} \{dp[1][i]\}ans=maxi=1n{dp[1][i]}那么考虑转移额，貌似也很简单dp[i][j]=maxi=0sizedp[lson][j−i]+dp[rson][i]dp...
2019-10-22 20:51:38
148
原创 习题：消防局的设立（贪心）
题目传送门思路有一个很明显的性质，两个消防局之间的距离越长越好，有了这个性质之后就可以开始贪心了定义dis[u]dis[u]dis[u]为u节点距离消防站的距离之后我们可以求出u节点的儿子节点的dis[son]dis[son]dis[son]的最大值和最小值如果maxx−minn<=3maxx-minn<=3maxx−minn<=3则dis[u]=minn+1di...
2019-10-22 20:34:13
154
原创 习题：砍树（二分）
题目传送门思路很明显的一道二分板子题。。。代码#include<iostream>#include<vector>#include<algorithm>using namespace std;#define int long longint n,m;int l,r,mid;vector<int> v;bool check(i...
2019-10-22 20:28:04
162
原创 习题：最优贸易（dp）
题目传送门思路首先一点，从买水晶球的地方一定可以到卖水晶球的地方，也就是说我们可以从起点开始走，中间存一个最小值就行了设minn[u]为u从起点到u地中间价格最低的地方dp[u]为u从起点到u的答案那么什么时候退出呢？就是minn[u]和dp[u]不被更新的时候代码#include<iostream>#include<climits>#include&...
2019-10-21 19:16:35
106
原创 习题：定价（杂题）
题目传送门思路从荒谬度的定义入手，也就是说我们每次加l一定是加l的qkpow(10,l的数位)之后暴力做就行了代码#include<iostream>#include<climits>using namespace std;int t;int l;int r;int t1;int t2;int ans;int limit=INT_MAX;in...
2019-10-21 19:12:13
232
原创 习题：hankson的趣味题（数论）
题目传送门思路很简单的一个推导已知r=gcd(b0,x)r=gcd(b0,x)r=gcd(b0,x)则b1=b0∗x/rb1=b0*x/rb1=b0∗x/rb1/b0=x/rb1/b0=x/rb1/b0=x/rb1/x=b0/rb1/x=b0/rb1/x=b0/r最终gcd(b1/b0,b1/x)==1gcd(b1/b0,b1/x)==1gcd(b1/b0,b1/x)==1有了这...
2019-10-21 18:54:21
177
原创 习题：Easy SSSP(搜索&贪心)
题目链接思路看见n的范围，果断dfs，但是如果是单纯的dfs，必炸无疑，之后考虑优化的问题，因为题目存在有负边所以我们先搜索与当前这个点相连的点的边权最小的开始搜会好一点代码#include<iostream>#include<vector>#include<cstring>#include<cstdlib>#include&...
2019-10-09 13:54:13
178
原创 习题：小星星（容斥&子集DP）
题目洛谷链接思路很明显的一道容斥的题目，因为从树上映射到图上可能有重复的部分所以我们将重复的删去，再进行计数之后我们考虑DP的转移设dp[i][j]dp[i][j]dp[i][j]为树上映射到图上之后的方案总数，dp[i][j]dp[i][j]dp[i][j]的方案总数与图上连接两个点的边有关，运用乘法原理相乘即可代码#pragma GCC optimize(fast)#inc...
2019-10-09 13:45:09
121
原创 习题：太空梯（DP）
题目有一群牛要上太空。他们计划建一个太空梯-----用一些石头垒。他们有k（1<=k<=400）种不同类型的石头，每一种石头的高度为hi(1<=hi<=100)，数量为ci(1<=ci<=10),并且由于会受到太空辐射，每一种石头不能超过这种石头的最大建造高度ai(1<=ai<=40000)。帮助这群牛建造一个最高的太空梯。输入格式第一行为一个...
2019-10-05 17:26:58
276
原创 习题：逛公园（记忆化搜索）
题目策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从1号点进去，从N号点出来。策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号...
2019-10-05 16:36:10
192
原创 习题：数字计数（数位DP+差分）
题目原题来自：ZJOI 2010给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码 (digit) 各出现了多少次。输入格式仅包含一行两个整数 a，b含义如上所述。输出格式包含一行10个整数，分别表示0~9在[a,b]中出现了多少次。思路很明显如果直接求[a,b]比较难，因为要考虑到各种各样的进位问题但是如果求[1,n]就比较简单了，于是差分的想法自然而然就出现了接着...
2019-09-29 13:58:19
172
原创 习题：生日礼物（博弈论）
题目下个月就是奶牛Z的生日啦，为了给奶牛Z购买生日礼物，奶牛A和奶牛B决定去挑选奶牛Z最喜欢的青草来作为送给奶牛Z的生日礼物。现在，奶牛A和奶牛B买来了n堆青草，从左数起，第i堆青草的甜度为ai。奶牛A认为奶牛Z喜欢甜的青草，而奶牛B认为奶牛Z喜欢不甜的青草。因此，奶牛A希望选出来的青草是最甜的，奶牛B希望选出来的是最不甜的青草。为了解决这个问题，奶牛A与奶牛B决定玩一个游戏，他们俩每次可以...
2019-09-27 13:32:31
286
原创 习题：大理石（状压DP）
题目zz是一位大理石收藏家，他在家里收藏了n块各种颜色的大理石，第i块大理石的颜色为ai。但是zz觉得这些石头在家里随意摆放太过凌乱，他希望把所有颜色相同的石头放在一起。换句话说，zz需要对现有的大理石重新进行排列，在重新排列之后，对于每一个颜色j，如果最左边的颜色为j的大理石是第l块大理石，最右边的颜色为j的大理石是第r块大理石，那么从第l块大理石到第r块大理石，这些石头的颜色都为j。由于这...
2019-09-26 14:02:31
144
1
原创 习题：猜数字（杂论）
题目zz作为hb中学最著名的猜测大师，他对几乎所有的事情都可谓料事如神。这不，zz又将大展身手，准备进行新一轮事件的猜测。现在，zz手里有n个数字，他需要猜出一个数字，使得这n个数字都是这个数字除1和它本身外的所有的其他因数。zz觉得这种问题过于简单，不屑于回答，于是就把这个问题丢给了你们。思路第一眼看到这道题，直接就是想的是对每一个因数进行质因数分解，之后再来构造但是仔细想一想设这数为...
2019-09-26 13:39:13
194
原创 习题：区间素数个数（min25）
题目：求区间[1~n]的素数个数。数据范围n<=1e11思路不看数据范围能想到的第一个就是欧筛，但是一看数据范围，我真的佛了。。。接着介绍一个好东西min25min25筛就是能快速求f(n)f(n)f(n)的前缀和，但是别急，min25筛对f这个函数有要求，首先f必须是积性函数，也就是说gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1时，f(a)∗f(b)=f...
2019-09-19 14:09:08
741
原创 习题：Cipele （二分&贪心）
题目在将大部分钱花在各种项目上之后，Nadan决定为他的软件开发人员提供高质量的鞋。幸运的是，Nadan在他的地下室发现了N双左脚穿的鞋子和M双右脚穿的鞋子，由于它们的来源不明，因此这些鞋子有各种各样的尺寸。Nadan要求你尽可能多的给这些鞋子配对（重要的是所有的鞋子配对后就不能再选择新的鞋子），每双鞋子有一只左脚穿的和一只右脚穿的。在搭配时，你应该确保这些鞋的丑陋值最小，丑陋值是指所有的...
2019-08-24 19:56:05
230
原创 习题：Maja（dp，滚动数组）
题目：Maja和蜜蜂在一片神奇的草地上为花授粉，这块草地可以表示为一个n行m列的矩形，在第i行第j列中有CIJ朵没有授粉的花。Maja的蜂巢位于第a行第b列，她将从她的蜂巢开始为这些花授粉，去草地上的某些块授粉，然后再返回她的蜂巢。每次操作，Maja可以向相邻的上下左右中的一个方格移动，而且她永远不会离开草地。每次她经过的某块草地，都会给这块草地上所有未授粉的花授粉。但草地很神奇，一旦Ma...
2019-08-24 19:52:43
102
原创 习题：Deblo（树形DP）
题目：大约30年前，年轻的Krešo首次参加了全国信息学竞赛。与今天相似的，比赛的开幕都是由一系列演讲者组成，他们试图通过演讲激励参加者们并展现竞赛的重要性。观众们热情地每隔几秒钟鼓掌一次，但Krešo被其中一位发言者的一句话激怒了，因为这位发言者声称他更赞赏逻辑运算而非逻辑运算，因为无论获胜者是谁，Mirko和Slavko都会是这次竞赛的获胜者，而不是Mirko或Slavko。Krešo这时...
2019-08-24 19:30:18
188
原创 题目：NLO (模拟)
在Žabnik村的当地人多年来一直与UFO进行斗争，UFO在稻田里创造了许多个圆圈，这种行为在夏天割草是尤其明显。让我们想象一个由n行m列组成的矩形稻田，左上角坐标为(1,1)，右下角坐标为(n,m)。每块稻田内都有一定数量的草，最初，所有稻田的草量都等于1，在K天内，圆形UFO每天都降落在地上，在地面盘旋，在第i天一早，半径为Ri的UFO在坐标(xi,yi)的稻田上着陆，收割掉UFO覆盖的稻...
2019-08-23 19:50:15
557
原创 习题：sajam(推理)
习题：Milo正聚精会神的组建自己的圣诞集市，他将把这个集市组建成整个欧洲最好的圣诞集市。晚上结束，到关灯的时间了，但有些人相当无礼，并没有关掉桌上的灯。由于电费越来越贵，Milo希望所有的灯都能很快的关掉，为此，他使用了传奇电子平板电脑（LEET）来达到这个目的，但他同时也需要你的帮助。Milo的圣诞集市有N行，每行有N个摊位。在LEET上，Milo有两个按钮：·按下第一个按钮，Mi...
2019-08-23 19:44:51
118
原创 习题：Redistricting （单调队列）
习题：奶牛们的最大城市Bovinopolis正在重新划分势力范围—生活在那里的主要是两个品种的奶牛（Holsteins和Guernseys），他们之间始终都有争执，因为两种奶牛都希望自己能在Bovinopolis的政府中保持足够的影响力。Bovinopolis的大都市区域由N（1≤N≤3*1e5）个牧场组成，每个牧场包含一头奶牛，她可以是Holsteins，也可以是Guernseys。...
2019-08-23 19:38:36
125
原创 习题：Kisik（贪心）
题目：银河国家殖民地联盟（CAIN）决定在火星上为K个家庭建造一座城市，因此，必须要为每个家庭建造一座房子，即一共K座房子。对于每个家庭，将可以选择从银河系最好的建筑师准备的N种建筑中选择一种。对于所有的建筑物，都是矩形，第i种建筑宽Wi，高Hi。此外，由于CAIN推广各种品种，所有的家庭将获得不同的设计。各个建筑彼此相邻建造，因此，他们的底部位于同一条线上。建成后，因为城市需要充满空气，...
2019-08-23 19:29:22
125
原创 习题：旅行（树链剖分）
题目：传送门思路：实际上我们需要解决两个问题首先，是如何计算评级，可能会想到前缀和，但是前缀和的修改时间复杂度太高，不能适应需求接着就想到了树链剖分，无论是修改，还是查询，时间复杂度都是O(n*logn)接着要解决的就是统计哪一些城市，也就是宗教的问题在这里，可以针对每一个宗教都建一棵线段树。具体的统计有点类似LCA代码：//树链剖分（貌似并没学），每一...
2019-08-08 11:12:19
133
原创 回顾：线段树
概念：将一个数组分成一段一段，用树状的数组将其储存。大概如此操作：单点修改：从根节点一直遍历到叶子节点单点查询：同单点修改区间查询：因为线段树的每一个节点都是一个区间，所以我们只需将查询的区间分为几个在线段树节点上的区间就行了区间修改：重要的是懒标记，也就是说，当修改一个区间的时候，我们只需要修改几个大的区间，并将值保留下来，在需要用到小区间的时候再去修改代码（...
2019-08-01 21:37:26
57
原创 习题：新的开始（最小生成树）
题目：样例输入4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0 样例输出9思路：很明显，这是一道最小生成树的题，但是最小生成树考虑的只有边，没有点权此时我们考虑转换点权，建一个虚点，这个点与其他所有点相连的边的边权即为这个点的点权代码#include<iostream...
2019-07-31 21:36:39
296
原创 习题：玩具装箱（斜率优化）
题目：传送门思路：首先考虑暴力，那么设dp[i]为以前i号元素的最小值s[i]为前i号元素的前缀和那么转移方程即为dp[i]=min{ dp[j]+(i-j-1+s[i]-s[j]-l)^2 }显然朴素的时间复杂度为O（n^2）那么我们化简一下式子设有两个点a，b向i进行转移，且a比b优那么dp[a]+(i-a-1+s[i]-s[a]-l)^2<dp[b]+(...
2019-07-30 21:27:04
114
原创 习题：国王（状压DP）
题目：B. 国王内存限制：64 MiB时间限制：500 ms标准输入输出题目类型：传统评测方式：文本比较提交提交记录返回比赛题目描述原题来自：SGU 223在 n*n的棋盘上放k 个国王，国王可攻击相邻的 8个格子，求使它们无法互相攻击的方案总数。输入格式只有一行，包含两个整数 n 和k 。输出格式每组数据一行为方案总数，若不能够放置则输出 0。样...
2019-07-29 19:53:10
1083
原创 习题：修剪草坪（DP，单调队列）
题目：. 修剪草坪内存限制：512 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：文本比较题目描述在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。FJ 有 n 只排成一排的奶牛，编号为 1到 n。每...
2019-07-28 19:47:22
509
原创 习题：烽火传递（DP，单调队列优化）
题目：烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。在某两个城市之间有 n座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。现在输入n和每个烽火台的代价ai，请计算总共最少的代价在两城市之间来准确传递情报。输入格式第一行是，表示n个烽火台和连续烽火台数 m；...
2019-07-28 19:40:31
865
原创 习题：最短母串（状压）
题目：A. 最短母串内存限制：512 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：文本比较题目描述给定n 个字符串，要求找到一个最短的字符串，使得这 n个字符串都是它 的子串。输入格式第一行是一个正整数，表示给定的字符串的个数；以下的 n+1 行，每行有一个全由大写字母组成的字符串。输出格式只有一行，为找到的最短的字符串...
2019-07-28 19:22:42
135
原创 习题：摆渡车（记忆化搜索）
题目：有n名同学要乘坐摆渡车从人大附中前往人民大学，第i位同学在第ti分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费m分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。 凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？ 注意：...
2019-07-27 20:10:29
494
原创 习题：usmjeri（LCA）
题目：给一棵N个节点的树，编号从1到N，再给定m对点(u，v),你要将树上的每条无向边变为有向边，使得给定的点对都满足u能到达v或v能到达u。问有多少种不同的方案，答案对(1e9+7)求余。输入格式第一行两个正整数N and M(1 ≤ N, M≤ 3*1e5 ),表示树的结点个数，和点对的个数。接下来N-1行，每行两个整数，表示树上的边。接下来M行，每行两个不同的...
2019-07-27 20:07:11
81
原创 习题：san(搜索)
题目：题目描述时间:1000ms空间64MB游戏世界中有N个楼从左到右排列，从左到右编号为1到N，第i幢楼的高度为Hi,楼上的金币数为Gi,游戏可以从任意一个楼开始且包涵几步。每一步玩家可以从当前位置向右跳（可以跳过一些楼）但必须跳到不低于当前楼的高度的楼上。他到了楼上后，可以得到楼上的金币。他可以在跳任意步（可以是零步）后结束游戏，但是要保证收到的金币数要大于等于K，现在想...
2019-07-27 19:57:57
184
原创 回顾：矩阵加速
矩阵基础矩阵其实就是一个个线性方程组的组合，所以可以利用矩阵来进行加速矩阵乘法：直接贴板子struct node{ long long n,m; long long a[105][105]; node operator * (const node &b) { node c; c.n=n; c.m=b.m; for(int i=1;i<=n;...
2019-07-27 14:12:08
106
1
原创 习题：savrsen(数论，欧拉筛)
如果一个数等于它的所有因数（小于自身的）之和，那么这个数就是完美的。例如，28是完美的，因为28=1+2+4+7+14。基于这个定义，我们数字n的不完美度定为f（n），它等于n与n的所有因数（小于n的）之和的差的绝对值，因此完美数的不完全度为0，其余自然数的不完全度都大于0。例如：●f（6）=|6-（1+2+3）|=0●f（11）=|11-（1）|=10●f（24）=|24-（...
2019-07-26 13:49:32
215
原创 习题：天降馅饼（tarjan缩点）
题目描述今天是K公司成立百年的日子，在这个喜庆的日子里，K公司决定给所有到他们线下门店的顾客发红包。林老师得知这个消息后，立马出门抢红包去啦。在林老师居住的P市内，一共有n家K公司的门店，在n家门店之间，有m条单向连通的道路，每家门店所发放的红包金额大小不同，且林老师在同一家门店只能领取一次红包（即第二次到达同一家门店是没有红包领取的）。林老师从离家最近的门店s开始出发抢红包，一路沿着单向道路...
2019-07-07 09:55:56
123
原创 习题：足球比赛（搜索优化）
题目描述 M中学一年一度的足球比赛开始啦，林老师作为一个热心观众，在得到消息后急急忙忙的赶到了M中学，可惜的是，当林老师赶到M中学时，所有的比赛都已经结束啦。最后林老师只得到了所有队伍的总积分表，林老师想知道，今年M中学的足球比赛一共有多少种可能的比赛情况（所有的足球队两两之间都会进行一场比赛，胜者得3分，败者得0分，打平得1分，任何两个球队之间有胜负关系不同的情况视为两种比赛情况）。...
2019-07-07 09:42:36
645
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人