- 博客(27)
- 收藏
- 关注
RSS订阅原创 atcoder abc229 G - Longest Y
题目：分析：1. 如果不是交换，而是替换任意一个'.' 为'Y',那么，我们可以使用滑动窗口来做，因为如果[l,r]窗口如果不满足条件，那么[l,r+1]必然也不会满足，那么每次我们可以先使得[l,r]是满足条件的窗口2. 那么现在如果是交换，那么和1不同的是cost不一样，但是如果我们知道一个区间内的最小cost，就可以继续使用滑动窗口的框架来做，也就是如果[l,r]可以在k代价以内完成聚合。滑动窗口本质上是利用了一个单调性的特征3. 首先我们需要对原来的数组进行一个预处理。 ..
2021-11-28 14:40:54
589
原创 【codeforce-650F2】 Flying Sort (Hard Version)
题目【codeforce-650F2】 Flying Sort (Hard Version)DP使用一种排序加单调队列的dp做法，参考博客，具体做法如下：代码class F1{ //CF650F2 Flying Sort (Hard Version) （思维）承接E题，这个相关类型的题目进行练习public: void solve(){ //双关键字排序+单调栈寻找最长连续子序列 //key:值域需要连续,有点单调栈的意思 //相同
2021-02-06 16:27:55
150
原创 【CF95B】lucky-numbers
题目思路使用dfs进行搜索剪枝，时间复杂度是O(n)，分析如下：结合代码：首先，如果当前代码中的ok是true，则整个递归返回；接下来都是ok是false的情况如果s[i]>7，则直接返回，一种选择若4<s[i]<=7,则当前只能有一种选择-7，dfs回溯之后，不可能选择4，所以只有一种选择如果s[i]<=4,则先选择4，后选择7，看似有两种选择：a. 选择4，如果成功，直接返回b. 如果不成功，选择7，这时候ok 一定是true，所以如果sum7>0，则之
2020-12-24 19:16:30
176
2
原创 【cf-6111C 一道动态规划的好题】
题目思路这是一道网格图上的动态规划的题，需要在原来的经典问题上进行一些修改，中间一些细节比较好，很能锻炼人的思维，需要结合代码理解代码class p611C {public: void solve() { int h, w; cin >> h >> w; vector<string> g(h); for (int i = 0; i < h; i++) cin >> g[i]
2020-10-29 15:06:31
105
原创 cf-666 div2: E Monster Invaders （动态规划）
题意思路动态规划，状态方程见代码代码class E {public: void update(ll &a, ll b) { a = a < b ? a : b; } void solve() { ll n, r1, r2, r3, d; cin >> n >> r1 >> r2 >> r3 >> d; vector<ll>
2020-09-02 15:48:48
220
原创 cf-1400 E [动态规划] Clear the Multiset
题目思路动态规划法：dp[i][j]是处理到前i个数，且已经使用了j个操作1的答案根据当前a[i]和j之间的关系进行转移，转移方程见代码分治法：每次去数组中的最小值，减掉，递归分治；每次和区间长度进行比较代码class E {public: vector<int> a; int DP(int left, int right) { if(left > right) return 0; if(left ==
2020-08-28 11:22:50
134
原创 CF-1291C:Mind Control （优雅地暴力决策）
题目思路数据量较短，可以枚举。题目中存在两种决策，且最后答案只取决于数组左边选了多少人，右边选了多少人（根据这个进行枚举）选择可以劝说的人，如何进行决策选择对于无法劝说的人，如何进行选择这样，我们使用两个for循环来嵌套的枚举所有可能的组合形式，这样答案∑i=0kmax(决策可控制的人){∑j=0m−1−imin(决策不可控制的人)} \sum_{i=0}^{k}max(决策可控制的人)\left \{ \sum_{j=0}^{m-1-i}min(决策不可控制的人) \right \}
2020-08-24 14:16:29
140
原创 POJ 3465 [battle] 优先级队列+反悔贪心
题意你是强大的英雄朱仁功。 经过一系列具有挑战性的任务之后，您终于要面对最终的老板-一条叫做黑龙的黑龙。 由于他的压倒性优势，您必须仔细计划自己的行动。战斗一开始你有H1生命值（HP），而黑龙有H2。 每次执行动作，黑龙都会攻击您，并在第i轮造成艾点伤害。 您有三种动作。攻击。 您攻击黑龙，并造成x点伤害。防守。 您专注于避免受到黑龙的攻击。 此举使黑龙的这一轮攻击无效。愈合。 您可以自愈，为自己增加生命值。 您的HP没有上限。如果任何人的HP下降到0或等于0以下，他就会死亡。 如果您无法在N
2020-08-04 22:29:19
134
原创 可反悔贪心-codeforce 867E - Buy Low Sell High
题意已知接下来N天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,当然,希望这N天内能够赚足够多的钱.输入:第一行一个整数天数N(2<=N<=300000).第二行N个数字p1,p2...pN(1<=pi<=106)p_1,p_2...p_N(1<=pi<=10^6)p1,p2...pN(1<=pi<=106),表示每天的价格.输出: N天结束后能获得的最大利润.思路这种可反悔式的贪心算法，就是
2020-08-04 17:50:06
542
原创 codeforces 1288C Two Arrays
题目思路Dp思想，将两个序列合并变成a1,a2,...am,bm,bm−1,...b1a_1,a_2,...a_m,\mathbf{ b_m,b_{m-1},...b1}a1,a2,...am,bm,bm−1,...b1那么这个序列只要单调不减就可以了。所以，问题转化成了一个序列中元素的取值在[1,n][1,n][1,n]范围内，满足单调不减的序列有多少种我们可以设dp[i][j]dp[i][j]dp[i][j]表示序列在第iii个位置，取值小于等于jjj的方案数我们可以列出方程:
2020-07-28 21:27:26
104
原创 Codeforces 1380E Merging Towers(LCA+倍增)
题目思路树建模+LCA倍增+前缀和PS:一道很好的训练题，能够学到很多技巧和知识代码#include <bits/stdc++.h>#define ll long longusing namespace std;const int N = 200043;const int L = 20;int tin[2 * N];int tout[2 * N];int p[2 * N];//记录节点i的父节点p[i];int idx[N];//记录idx[i]，数字i在哪个idx[
2020-07-28 11:47:10
189
原创 【codeforces】1385G-Columns Swaps 一道好题
题目思路：图论建模+染色+求连通分量（详情以后再补，这里记录一下，一道好题，能学到很多知识）代码#include<bits/stdc++.h>#define ll long long#define ii pair<int,int>#define pll pair<ll,ll>using namespace std;vector<vector<ii>> g;int zero,one;int id;//记录连通分量的编号voi
2020-07-24 21:28:18
247
原创 【尺取法】HDU 1937 Finding Seats
题目思路固定一个矩形的边，然后根据固定行间距里的单调性，使用尺取法进行求解。注意，这个的条件是求满足条件的最小值，需要注意枚举时，拓展边界的次序，有的时候是以right为主，有的时候是以left为主，需要到时候分析一下。代码int grid[310][310];void V(){ int k,r,c; while(scanf("%d %d %d",&r,&c,&k)&&r&&c&&k){ ch
2020-07-17 23:05:06
83
原创 序列变换 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
189
原创 【二分+树状数组】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
94
原创 奇偶二分 HDU 4768 Flyer
题目思路这道题也是一道二分题，解决二分题的关键点在于找到体现问题单调性的状态上。在本题中，通过题意知道，是要找到那个只收到奇数个传单的那个人，而题目中说了其他人保证会收到偶数个传单，所以，这里需要利用一个小的数论性质：奇数+偶数=奇数偶数+偶数=偶数然后我们就可以二分那个接收奇数个传单的编号xxx了：如果在区间[1,x][1,x][1,x]内的传单数量为偶数，说明还没有遇到那个天选之人，需要扩大x的值如果在区间[1,x][1,x][1,x]内的传单数量为奇数，说明天选之人已经出现，需要缩
2020-07-09 20:10:19
95
原创 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
406
原创 二分嵌套二分的 二分题-POJ3685- Matrix
题目思路这道题，通过观察可以发现公式可知，每一列都是单调递增的，但是每一行不一定单调的。所以，我们首先二分答案midmidmid，然后按列枚举，在每一列中，因为具有单调性，从而可以二分出每一列中数值小于等于midmidmid的数量，然后能够根据整个矩阵中计算出的≤\leq≤mid的数量，进行二分答案。注意：最外层二分答案的时候，是要寻找满足条件的下界里面嵌套的二分，是要寻找到满足条件的上界这两个二分在代码的写法上有所不同代码（PS:POJ的c++真坑，好多好用的语法都不能用了，QAQ）
2020-07-06 14:36:10
171
原创 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=0nv[i]void E1() { int n, p; ci
2020-07-02 16:01:05
136
原创 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
624
1
原创 LeetCode-146-LRU缓存机制-3个Map解决问题
题目运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。算法使用时间戳动态地更新每
2020-05-25 19:15:16
129
原创 【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
179
原创 【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
164
原创 【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
788
原创 【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
186
原创 【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
176
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人