4 whq20151637

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 52w+

序列变换 HDU - 5256 (化归+LIS+二分)

题意我们有一个数列A1,A2…An,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。请输出最少需要修改多少个元素。参考思路代码void M(){ int t; sc(t); for(int kase=1;kase<=t;kase++){ int n; sc(n); vector<int> a(n,0); for(int i=0;i<n

2020-07-11 15:37:52

【二分+树状数组】HDU 5493 Queue

题意参考思路代码主要是记录一下自己的写的代码,中间debug好久,在一些小地方犯错#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<ctime>#include<vector>#include<map>#include<algorithm>#include<set>#inclu

2020-07-10 23:28:02

奇偶二分 HDU 4768 Flyer

题目思路这道题也是一道二分题,解决二分题的关键点在于找到体现问题单调性的状态上。在本题中,通过题意知道,是要找到那个只收到奇数个传单的那个人,而题目中说了其他人保证会收到偶数个传单,所以,这里需要利用一个小的数论性质:奇数+偶数=奇数偶数+偶数=偶数然后我们就可以二分那个接收奇数个传单的编号xxx了:如果在区间[1,x][1,x][1,x]内的传单数量为偶数,说明还没有遇到那个天选之人,需要扩大x的值如果在区间[1,x][1,x][1,x]内的传单数量为奇数,说明天选之人已经出现,需要缩

2020-07-09 20:10:19

POJ-3104 Drying(贪心分析+二分)

题意思路这道题可以二分总的晾干时间,注意需要理解出题目的意思,就是一件衣服可以自然烘干,也可以使用散热器烘干。所以假设一件衣服最后的烘干时间是xxx,那么我们可以假设自然烘干无时无刻不再进行,也就是说,其中有xxx的水分被自然烘干,那么对于一件包含a[i]a[i]a[i]水分的衣服来说:假如a[i]≤xa[i]\leq xa[i]≤x,那么就可以直接忽略掉,把宝贵的散热器留给其他衣服用假如a[i]>xa[i] > xa[i]>x,那么说明这件衣服除了自然烘干外,剩下的水分必须使用

2020-07-07 13:04:15

二分嵌套二分的 二分题-POJ3685- Matrix

题目思路这道题,通过观察可以发现公式可知,每一列都是单调递增的,但是每一行不一定单调的。所以,我们首先二分答案midmidmid,然后按列枚举,在每一列中,因为具有单调性,从而可以二分出每一列中数值小于等于midmidmid的数量,然后能够根据整个矩阵中计算出的≤\leq≤mid的数量,进行二分答案。注意:最外层二分答案的时候,是要寻找满足条件的下界里面嵌套的二分,是要寻找到满足条件的上界这两个二分在代码的写法上有所不同代码(PS:POJ的c++真坑,好多好用的语法都不能用了,QAQ)

2020-07-06 14:36:10

codeforces 654 div2 E1

codeforces 654 div2 E1题目链接题解参考补充细节枚举xxx,从小到大,xxx的上界是max{a[i]}max\left \{ a[i] \right \}max{a[i]}先对aaa数组进行排序,之后,针对每个xxx:枚举每个位置iii上可以选择的方案数v[i]v[i]v[i],这里参考代码进行理解最后以xxx开始的枚举方案总数=∏i=0nv[i]\prod_{i=0}^{n}v[i]∏i=0n​v[i]void E1() { int n, p; ci

2020-07-02 16:01:05

Atcoder-dp_e Knapsack 2 超大背包优化

一道有意思的超大背包优化题目链接题目描述限制条件思路这道题因为背包的重量太大了1e9,所以传统的使用dp[i]表示重量为i的最大价值为dp[i]这样的表示方法不再适用。需要倒逼着去想新的方法。我们发现N*v[i]的总价值比较小1e5左右,所以,可以用dp[i]表示得到当前价值i的最小体积为dp[i]。这样我们使用W去搜索那些dp[i]的值小于W的最大的i。代码void E(){ //价值比较小,将dp[i]转化为获得当前i的价值的最小体积,然后根据W寻找符合要求的解; i

2020-06-22 21:58:04

【kuangbin带你飞-区间DP-6】H-String painter HDU - 2476

题目链接题意思路代码

2020-05-26 17:01:27

LeetCode-146-LRU缓存机制-3个Map解决问题

题目运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。写入数据 put(key, value) - 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。算法使用时间戳动态地更新每

2020-05-25 19:15:16

【kuangbin带你飞-区间DP-5】G - You Are the One HDU - 4283

题目链接题目The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the show itself. The show is hold in the Small hall, so it attract a lot of boys and girls. Now there are n boys enrolling

2020-05-25 16:40:31

【kuangbin带你飞-区间DP-4】F - Food Delivery ZOJ - 3469

题目链接题目When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.Suppose there are N people living in a straight street that is just lies on an X-co

2020-05-24 17:56:33

【kuangbin带你飞-区间DP-3】E - Multiplication Puzzle POJ-1651

题目链接:(http://poj.org/problem?id=1651)题目大意给你一个卡片数组,每个卡片都带有一个正整数。现在让你从卡片数组中那卡片,每次拿一个不放回,每次拿的时候的得分是该卡片的数和左右两边卡片数之积。且卡片的开头和结尾不允许拿走,问你这样操作,最后之剩首尾两张卡片的时候,最小的得分是多少。InputThe first line of the input contains the number of cards N (3 <= N <= 100). The seco

2020-05-23 13:04:15

【kuangbin带你飞-区间DP-2】 非常好的dfs+dp题 CodeForces - 149 D-Coloring Brackets

题意:给你一个合法的括号序列,现在让你给这个序列染色,染色的条件如下:每对()有且只有一个括号被染色 相邻的括号如果都被染色了,那么其颜色不能相同 每个括号只能涂蓝色,红色,或者不涂任何颜色现在让你求染色方案总数,并且最后结果mod 1e9+7算法思路:依据每对括号进行dp,因为括号存在嵌套,所以需要使用dfs进行递归处理 为了知道每个左括号对应右括号,需要提前进行预处理 dp状态方程为dp[l][r][i][j] 表示区间【l,r】的左右两个端点分别涂颜色i和颜色j方案数 需要注

2020-05-23 00:25:44

【kuangbin带你飞-区间DP-1】A-cake-ZOJ3537

题意You want to hold a party. Here's a polygon-shaped cake on the table. You'd like to cut the cake into several triangle-shaped parts for the invited comers. You have a knife to cut. The trace of each cut is a line segment, whose two endpoints are two ver

2020-05-20 21:54:06
勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。