2 weixin_43726650

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 23w+

习题:战争调度(dp)

题目传送门思路dp[i][j]dp[i][j]dp[i][j]表示以i号节点为根节点字数有j个平民参加战争的最大值ans=max⁡i=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:44:43

习题:消防局的设立(贪心)

题目传送门思路有一个很明显的性质,两个消防局之间的距离越长越好,有了这个性质之后就可以开始贪心了定义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:30:35

习题:砍树(二分)

题目传送门思路很明显的一道二分板子题。。。代码#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:27:09

习题:最优贸易(dp)

题目传送门思路首先一点,从买水晶球的地方一定可以到卖水晶球的地方,也就是说我们可以从起点开始走,中间存一个最小值就行了设minn[u]为u从起点到u地中间价格最低的地方dp[u]为u从起点到u的答案那么什么时候退出呢?就是minn[u]和dp[u]不被更新的时候代码#include<iostream>#include<climits>#include&...

2019-10-21 19:14:31

习题:定价(杂题)

题目传送门思路从荒谬度的定义入手,也就是说我们每次加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:07

习题: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:46:54

习题:Easy SSSP(搜索&贪心)

题目链接思路看见n的范围,果断dfs,但是如果是单纯的dfs,必炸无疑,之后考虑优化的问题,因为题目存在有负边所以我们先搜索与当前这个点相连的点的边权最小的开始搜会好一点代码#include<iostream>#include<vector>#include<cstring>#include<cstdlib>#include&...

2019-10-09 13:48:33

习题:小星星(容斥&子集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:38:24

习题:太空梯(DP)

题目有一群牛要上太空。他们计划建一个太空梯-----用一些石头垒。他们有k(1<=k<=400)种不同类型的石头,每一种石头的高度为hi(1<=hi<=100),数量为ci(1<=ci<=10),并且由于会受到太空辐射,每一种石头不能超过这种石头的最大建造高度ai(1<=ai<=40000)。帮助这群牛建造一个最高的太空梯。输入格式第一行为一个...

2019-10-05 16:51:25

习题:逛公园(记忆化搜索)

题目策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图,且没有 自环和重边。其中1号点是公园的入口,N号点是公园的出口,每条边有一个非负权值, 代表策策经过这条边所要花的时间。策策每天都会去逛公园,他总是从1号点进去,从N号点出来。策策喜欢新鲜的事物,它不希望有两天逛公园的路线完全一样,同时策策还是一个 特别热爱学习的好孩子,它不希望每天在逛公园这件事上花费太多的时间。如果1号...

2019-10-05 16:25:39

习题:数字计数(数位DP+差分)

题目原题来自:ZJOI 2010给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码 (digit) 各出现了多少次。输入格式仅包含一行两个整数 a,b含义如上所述。输出格式包含一行10个整数,分别表示0~9在[a,b]中出现了多少次。思路很明显如果直接求[a,b]比较难,因为要考虑到各种各样的进位问题但是如果求[1,n]就比较简单了,于是差分的想法自然而然就出现了接着...

2019-09-29 13:53:33

习题:生日礼物(博弈论)

题目下个月就是奶牛Z的生日啦,为了给奶牛Z购买生日礼物,奶牛A和奶牛B决定去挑选奶牛Z最喜欢的青草来作为送给奶牛Z的生日礼物。现在,奶牛A和奶牛B买来了n堆青草,从左数起,第i堆青草的甜度为ai。奶牛A认为奶牛Z喜欢甜的青草,而奶牛B认为奶牛Z喜欢不甜的青草。因此,奶牛A希望选出来的青草是最甜的,奶牛B希望选出来的是最不甜的青草。为了解决这个问题,奶牛A与奶牛B决定玩一个游戏,他们俩每次可以...

2019-09-27 13:25:41

习题:大理石(状压DP)

题目zz是一位大理石收藏家,他在家里收藏了n块各种颜色的大理石,第i块大理石的颜色为ai。但是zz觉得这些石头在家里随意摆放太过凌乱,他希望把所有颜色相同的石头放在一起。换句话说,zz需要对现有的大理石重新进行排列,在重新排列之后,对于每一个颜色j,如果最左边的颜色为j的大理石是第l块大理石,最右边的颜色为j的大理石是第r块大理石,那么从第l块大理石到第r块大理石,这些石头的颜色都为j。由于这...

2019-09-26 13:47:57

习题:猜数字(杂论)

题目zz作为hb中学最著名的猜测大师,他对几乎所有的事情都可谓料事如神。这不,zz又将大展身手,准备进行新一轮事件的猜测。现在,zz手里有n个数字,他需要猜出一个数字,使得这n个数字都是这个数字除1和它本身外的所有的其他因数。zz觉得这种问题过于简单,不屑于回答,于是就把这个问题丢给了你们。思路第一眼看到这道题,直接就是想的是对每一个因数进行质因数分解,之后再来构造但是仔细想一想设这数为...

2019-09-26 13:31:47

习题:区间素数个数(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 13:44:16

习题:Cipele (二分&贪心)

题目在将大部分钱花在各种项目上之后,Nadan决定为他的软件开发人员提供高质量的鞋。幸运的是,Nadan在他的地下室发现了N双左脚穿的鞋子和M双右脚穿的鞋子,由于它们的来源不明,因此这些鞋子有各种各样的尺寸。Nadan要求你尽可能多的给这些鞋子配对(重要的是所有的鞋子配对后就不能再选择新的鞋子),每双鞋子有一只左脚穿的和一只右脚穿的。在搭配时,你应该确保这些鞋的丑陋值最小,丑陋值是指所有的...

2019-08-24 19:56:05

习题:Maja(dp,滚动数组)

题目:Maja和蜜蜂在一片神奇的草地上为花授粉,这块草地可以表示为一个n行m列的矩形,在第i行第j列中有CIJ朵没有授粉的花。Maja的蜂巢位于第a行第b列,她将从她的蜂巢开始为这些花授粉,去草地上的某些块授粉,然后再返回她的蜂巢。每次操作,Maja可以向相邻的上下左右中的一个方格移动,而且她永远不会离开草地。每次她经过的某块草地,都会给这块草地上所有未授粉的花授粉。但草地很神奇,一旦Ma...

2019-08-24 19:52:43

习题:Deblo(树形DP)

题目:大约30年前,年轻的Krešo首次参加了全国信息学竞赛。与今天相似的,比赛的开幕都是由一系列演讲者组成,他们试图通过演讲激励参加者们并展现竞赛的重要性。观众们热情地每隔几秒钟鼓掌一次,但Krešo被其中一位发言者的一句话激怒了,因为这位发言者声称他更赞赏逻辑运算而非逻辑运算,因为无论获胜者是谁,Mirko和Slavko都会是这次竞赛的获胜者,而不是Mirko或Slavko。Krešo这时...

2019-08-24 19:30:18

题目: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

习题:sajam(推理)

习题:Milo正聚精会神的组建自己的圣诞集市,他将把这个集市组建成整个欧洲最好的圣诞集市。晚上结束,到关灯的时间了,但有些人相当无礼,并没有关掉桌上的灯。由于电费越来越贵,Milo希望所有的灯都能很快的关掉,为此,他使用了传奇电子平板电脑(LEET)来达到这个目的,但他同时也需要你的帮助。Milo的圣诞集市有N行,每行有N个摊位。在LEET上,Milo有两个按钮:·按下第一个按钮,Mi...

2019-08-23 19:44:51

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。