jerans-CSDN博客

原创 leetcoder 19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/删掉链表的倒数第n个节点想着什么空间换时间记录什么的。。。真的很蠢。。。。代码一看便懂/** * Definition for singly-linked list. * struct ListNode { * int val; * ...

2019-03-04 19:36:27 344

原创 leetcode 15 3sum 16 3sumclosest

https://leetcode.com/problems/3sum/2sum：找到一组两元组，使得和为某个数先排序，假设从小到大排序后，设头尾两个指针，若当前指针指向元素和小于零则移动指针增大元素，反之大于零则减小元素3sum：找所有的三元组，使得三者和为零n^2做法先排序，固定一个点，将问题转化为2sum问题class Solution {public: ...

2019-02-26 20:46:43 215

原创 leetcoder 11. Container With Most Water

leetcode.com/problems/container-with-most-water/左右两点向内缩，当左端点（le）值小于右端点（ri）值时，移动左端点，因为对于当前 le，不存在一个比 ri 靠左的端点可以得到更优的结果。class Solution {public: int maxArea(vector<int>& height) { ...

2019-02-23 20:20:05 201

原创贝壳找房户外拓展（中等）扫描线

https://nanti.jisuanke.com/t/27118在线段树上写了矩阵乘法，其实只是2*2的矩阵，手写转移似乎更好。#include<bits/stdc++.h>using namespace std;const int mo = 323232323;const int maxn = 1e5 + 100;struct I_node{ int p, q, x, ...

2018-06-07 19:14:21 322

原创蓝桥杯训练4.18

1.好好学习#include<bits/stdc++.h>using namespace std;int main(){ int cnt = 0, ans = 0; vector<int>w; w.push_back(1); w.push_back(1); w.push_back(2); w.push_back(3); do{ if(w[0] == 1...

2018-04-18 22:27:22 203

题意：给n个数，从这n个数里，任意选一些数，使得这些数的平均值减去中位数尽可能的大精度卡的好恶心啊。。。。。首先发现集合个数一定是奇数，任何一个个数为偶数的集合，都可以通过去掉中间较大的那个数，来增大或不变这个值如1 2 3 4 可以去掉3变成1 2 4排序后，枚举每个数做中位数，然后三分集合个数确定中位数之后，剩下的数肯定是越大越好，会发现这个值并不是随着集合个数单调变化的，所以要三分求凸点。直...

2018-04-16 12:48:32 368

原创 Mod problem FZU - 2108 栈模拟

题意：定义了一种数值表示方式，给出这种表示方式下的表示，求原数值，模拟。由于重复的次数都是个位数，最多也就是重复10000次，所以可以模拟这个重复的过程输出取模后的结果，那就每一步都取模就行了，重复之后会有一个和前面的值合并的问题发现用栈更好实现这个过程开始写的时候感觉码量会很大，动手写会发现其实还好#include<stdio.h>#include<iostream>...

2018-04-14 23:01:31 241

原创 FZU 2105 Digits Count 线段树

题目：点击打开链接题意：n个数字，四种操作，区间AND OR XOR 一个数，区间求和数字范围很小，所以可以按位去操作，区间AND和区间OR其实就可以理解为区间置0或置1，XOR为区间取反，AND和OR是可以一起操作的，但结合XOR，如果用一个lazy标记是不可行的，所以开两个lazy标记，一个是有没有区间置数，第二个是有没有区间取反。区间置数：无论有没有取反标记，都应该置为相应数，并且要把取...

2018-04-13 22:59:50 412

原创 HDU - 5361

题意：n个点，可以在点和点之间互相跳，给出在每个点跳一次的花费，以及他可以跳到的范围，求从第一个点跳到所有点的最小花费。很像单源最短路，但直接暴力肯定不行，因为是从第一个点开始跳，发现已经跳到的点一定是最小花费，后续不需要在考虑这个点，因此可以想办法优化掉，第一个想到的是双向链表，但发现维护起来并不合适，后来又想到直接用并查集就可以了，用并查集求每个点右边的第一个没去掉的点，也就是可以入队的点。去...

2018-04-13 22:45:26 158

原创 BZOJ 3566: [SHOI2014]概率充电器概率dp

题目：点击打开链接树形概率dp，刚开始以为每个点的概率应该是其他点对其概率贡献加和，然后WA看了题解才明白并不是，两个事件的并事件的概率应为P(a | b) = P(a) + P(b) - P(ab)独立事件 P(ab) = P(a) * P(b)举个样例31 2 501 3 500 1 1并不能认为1充电的概率是1的求概率的时候把直接加换成上式就可以了#include<bits/stdc+...

2018-04-13 22:35:03 154

原创 ZOJ - 2770 差分约束

题意：n个军营，给出每个军营的最大人数，m个估计，表示一段区间内的军营的最少人数和，现在让你求所有军营的最小可能人数和利用前缀和构造不等式关系，形成差分约束系统，其实就是跑一遍最短路就可以了#include<bits/stdc++.h>#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const int maxn = 2000;...

2018-04-13 22:21:53 283

原创 HDU - 6031 Innumerable Ancestors

题意：给一棵树，m次查询，每次查询给两个集合，从这两个集合里分别选一个结点，使得这两个节点的lca的深度最大。考虑dfs序为5，6，7的三个节点，5，6的lca深度一定大于等于5，7的lca深度所以可以讲查询集合按dfs序排序，然后类似尺取的操作，使得每一对dfs序接近的节点都做一次lca，选一个最深的就可以了#include<bits/stdc++.h>using namesp...

2018-04-09 10:47:01 160

原创 CodeForces - 618D Hamiltonian Spanning Tree 思维

题目：点击打开链接题意：n个点的无向完全图，所有边权都是y，给出一个生成树，并把生成树上的n-1条边边权改为x，求这个图的最小边权和的欧拉通路，只输出最小边权和x > y 时应尽量使用生成树上的边，每个点只能经过一次，相当于一个链状结构，问题等于去掉最少的边使得树变成多条链然后就不会了55555看了题解才会，太强了，短短10行代码。。。。。贪心策略：每个点都尽可能的和子节点构成链状结构，从...

2018-03-29 22:45:14 178

原创 Codeforces Round #447 (Div. 2) B C 思维

好久没打cf。。感觉智商已经退化到了零点，随便找了一套div2补一补。。。。B题就卡住了http://codeforces.com/contest/894/problem/BB题意是给一个n*m的方格，往每个格子里填1或-1，有多少种填的方法使得每行每列乘积都等于k，k已知，-1或1n，m范围很大第一想法，推组合数？？？？？？感觉毫无头绪。。。纸上画画，发现当（n+m）

2017-12-12 21:52:47 295

原创 LightOJ - 1258 Making Huge Palindromes KMP

https://vjudge.net/problem/26968/origin题意：给一个串，问最少添加一个任意字符可以使其变成一个回文串思路是拓展KMP，将串反过来匹配，利用extend数组，第一个可以拓展到有重叠部分的下标之前的就是要添加的#include#include#include#includeusing namespace std;const int maxn=

2017-11-13 22:12:38 238

原创 hihocoder1426||UVALive - 7672 What a Ridiculous Election

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=569416北京现场赛题目题意：每次有三种可行操作1:交换相邻两个数位2:把某一个数位加1,取模103:把某一个数位乘2,取模102操作最多能用3次，3操作最多能用2

2017-11-11 22:24:42 257

原创 hdu 5175 思维

http://acm.hdu.edu.cn/showproblem.php?pid=5175给一个大数n，1e10的范围求1~n里有多少个数m满足gcd(m,n)==m^n（异或）好思路。。看的题解。。设m=n^x原式子变为gcd(n^x,n)==x那么x一定是n的因子，所以直接根n枚举n的因子即可#includeusing namespace std

2017-11-09 21:29:49 233

原创 hdu 5414 CRB and String||QDUOJ GZS and String

https://www.qduoj.com/problem/6/题意是给两个字符串s,t，每次操作是在s的某个字符c后面添加一个字符d，但要求d！=c，问能不能经过某些操作后使构造出t串贪心几个感觉比较好的样例aaabaaaaabaNoaaabaaaabbbaYesbaabaaYesabbabbYescatca

2017-11-08 21:46:32 205

原创 C. Naming Company 贪心

http://codeforces.com/contest/794/problem/C题意：两个人每个人有一个长度n的字符集合，构造一个长度为n的字符串A是希望字符串字典序越小越好，B希望字符串字典序越大越好贪心，首先可以明确A，B都有一个必选集合，A要选（n+1）/2个，必会选自己有的最小的前几个，B必选自己有的最大的前几个如果A当前能选的最小的小于B当前能选的最大的，那么必定是

2017-10-23 21:24:40 292

原创 hdu 5963 博弈

http://acm.split.hdu.edu.cn/showproblem.php?pid=5963题意：中文题博弈，找了下规律，瞎几把写了个N*M的dfs，T了，没想到能过小数据。。。。看了下题解，大多是找规律，其实仔细想想，好像很对修改暴力修改就好了查询：对每个查询只看这个点直接相连的边里有几个为1的，奇数个则Girl Win ,偶数个Boy Win仔细分析一下，单

2017-10-17 12:29:53 207

原创 hdu5033Building 单调栈

http://acm.split.hdu.edu.cn/showproblem.php?pid=5033好题啊，不得不说是好题，尤其是听cys讲过后，简直茅塞顿开题意：坐标轴上n个点上有高h的线段，q次查询，每次查询给一个坐标x，问在（x，0）点上看不到线段的视角范围是多少离线求，讲查询点和线段点整合在一起排个序，求左边看不到线段的角，也就是和左边线段上端点的最大夹角，同方法求

2017-10-14 20:06:31 246

原创 hdu5492Find a path dp

http://acm.split.hdu.edu.cn/showproblem.php?pid=5492题意：一个n*m方格，每个格子上有自己的权值，从1,1出发每次只能从(x, y) 走向(x + 1, y) 或 (x, y +1)，终点n，m，路径长度必然就是n+m-1，求(N+M−1)∑N+M−1i=1(Ai−Aavg)2的的的的最小值，其中Ai是路径上的第i个权值，Aavg是

2017-10-14 19:33:28 228

原创 hdu5573Binary Tree 思维构造

http://acm.split.hdu.edu.cn/showproblem.php?pid=5573题意：满二叉树，节点x左儿子标号是2*x，右儿子标号是2*x+1，每个节点权值即标号，从1号节点开始，走一段长度为k的路径，自己选择每个节权值加或减，问最后能不能凑成n想了很久都没思路，甚至还想到了打表找规律，徒劳。。。。。。看了题解，发现。。。。。。。。。。。稍微拐个歪就能想到

2017-10-14 19:10:02 207

原创 hdu 5035 Delivery 概率

http://acm.split.hdu.edu.cn/showproblem.php?pid=5035题意：有个人A去银行办理业务，有n个窗口，已知每个窗口关于时间的办好业务的概率密度函数是 p(ti = t) = kie^(-kit) ，还有每个窗口已经有人正在办理业务，并且已知每个窗口正在办理业务的人已经办理的时间，现在让你求A办好业务所需要的时间期望要注意这个时间期望有两部分，

2017-10-14 11:35:35 206

原创 HihoCoder 1233 Boxes BFS

https://hihocoder.com/problemset/problem/1233题意：有很多个大小不同的盒子，排成一排，可以类似汉诺塔一样的移动他们，每次只能移动每个位置最顶上的那个盒子，只能移动到和他相邻的位置上去，并且是小盒子只能放在大盒子上面，问最后把这些盒子排成一个大小从小到大的顺序，需要的最少的次数，如果不可以，输出-1想到是状态压缩从终点往回BFS预处理，但想歪了压缩

2017-10-11 20:52:35 210

原创 CodeForces - 372C Watching Fireworks is Fun dp

http://codeforces.com/problemset/problem/372/C题意：在一条街道上（线段），有m个烟花，给出每个烟花的位置和燃放的时间，以及一个b【i】值，当烟花燃放时，你在街道的x（1=b【i】-abs（a【i】-x），刚开始你可以在任意位置，之后可以移动你的位置，每秒可移动d个单位，求所有烟花燃放完之后的乐趣值最大值dp【i】【j】表示看完前i个烟花

2017-10-11 20:05:51 357

原创 Codeforces Round #439 (Div. 2) E. The Untended Antiquity 二维线段树||二维树状数组

http://codeforces.com/contest/869/problem/E题意：n*m的矩阵，q次操作，三种类型类型1：给指定矩阵加上围栏类型2：给指定矩阵去掉围栏类型3：查询两点是否存在一条不通过围栏的路加围栏是全包，也就相当于加了围栏后只能是里面走向里面，外面走向外面，这样就可以给这块平面附一个值，判断能不能走直接判相等就可以了，因为有矩阵叠加的情况，也就是围栏

2017-10-07 21:58:09 375

原创 hdu-4777Rabbit Kingdom 树状数组

http://acm.split.hdu.edu.cn/showproblem.php?pid=4777题意：给一段序列，多个查询，查询某段区间内和其他数都互质的数的个数接触过类似的题目，但训练时竟没有想到树状数组，搜了发题解，看到树状数组四个字，立马就把题解关掉了，想了想，好像不难做必然是离线处理，套路类似spoj D-query需要修改的地方就是，以因子为索引寻找前驱，w

2017-10-05 17:39:48 282

原创 hdu 4803 贪心

http://acm.split.hdu.edu.cn/showproblem.php?pid=4803题意是两个数，x，y，x指个数，y指价值总和，两种操作，操作1：x+1（个数加一，总和在加一个单价，也就是y+=y/x），操作2：y+1（总和加一,个数不变，其实也相当于单价变高），问你从x=1，y=1开始，到达给的某个x1，y1，最少需要几步操作可以去向单价方面考虑，既然要到达x1

2017-09-30 23:51:09 309

原创 hdu 4424 Conquer a New Region 并查集

http://acm.hdu.edu.cn/showproblem.php?pid=4424题意是一棵树，每条边有边权，定义两点之间距离为两点之间路径上最小的那个边权，找一个点，使其他所有点到这个点的距离和最大想了半天树形dp，没思路，看了题解，发现好巧妙巧妙运用并查集，先按照边权从大到小对所有边排序，然后对于当前边，可以连接两个集合，注意集合内是已经通过之前更大的边连接好的，并查集的

2017-09-30 00:57:06 216

原创 2017西安网络赛 E. Maximum Flow F. Trig Function 组合数

E. Maximum Flowhttps://nanti.jisuanke.com/t/17118从0到n-1，n个点，权值为点标号，每个点都有向标号大于自己的点有一条有向边，边权为两结点权值异或值求从0到n-1的最大流量找到规律是结果为sum（max（i，i^(n-1)）(i=1->n-1)然后就可以根据数位来求这个结果了#includeusing n

2017-09-28 15:26:12 209

原创 2017南宁网络赛 I. GSM Base Station Identification 暴力

https://nanti.jisuanke.com/t/17316题意：给10个点，判断这十个点在定义的哪个块内脑子短路了，还想着找找规律判断一下什么的，带歪了队友。。。。。。直接暴力就好啊，题目保证了数据很小，把给定范围内的所有块的中点坐标预处理出来，和给定点距离最近的中心点即所求块#includeusing namespace std;struct point{

2017-09-28 15:11:38 213

原创 hdu-5726 GCD 思维||二分

http://acm.hdu.edu.cn/showproblem.php?pid=5726两种做法，一个是仿照hdu5869 的那种做法，好写很多，复杂度也较优，不得不说那个思维很强hdu-5869：1575ms#includeusing namespace std;const int maxn=1e5+10;vector >w[maxn];int a[maxn];ma

2017-09-23 01:24:01 243

原创 hdu-Sort 二分

http://acm.hdu.edu.cn/showproblem.php?pid=5884二分加多叉哈夫曼树优雅的优先队列可以卡过，但必定不会有双队列O（n）写更优雅，学到了需要注意的坑点是，k叉哈夫曼树，每次减少k-1个元素，当（n-1）%k！=0时，也就是每次减掉k-1个，最后剩的数多于一个时如果最后在拿掉这些并不是最优的，最后必然剩很多大数，更优的策略应该是先拿掉这些多余的

2017-09-23 01:16:59 184

原创 hdu-5834 Magic boy Bi Luo with his excited tree 树形dp

http://acm.hdu.edu.cn/showproblem.php?pid=5834神级烦的一个树形dpdp1【0】【x】代表从x结点向下走并且回到x结点的最大值dp1【1】【x】代表从x结点向下走，并且不回到x结点的最大值（去向某一个子树分支，通过index【x】记录）dp1【1】【x】代表从x结点向下走，并且不回到x结点的第二大值dp2【0】【x】代表从x结点向父节

2017-09-23 01:00:46 234

原创 hdu-5861 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=5861题意是每段路有路灯，每个路灯只能开关一次，每个路灯开一天需要一定花费，给定每天需要用的路灯线段，求每一天的总的最小花费因为只能开关一次，所以路灯的花费必定就是从第一次使用一直到最后一次使用，这样就是线段树裸的区间修改操作了最后整体查询一遍，对每个路灯使用的日期，左端点加，右端点减，前缀和即花费

2017-09-23 00:54:06 232

原创 codeforces 451E. Devu and Flowers 组合数+容斥

题意：n个不同盒子，每个盒子里有ai个小球，总共拿s个，问有多少种选法如果盒子里求是无限个，直接插板法就可以求了对于有了个数限制，可以容斥来做，需要去掉的是个数超限的，那么我先保证他个数超限（拿ai+1个），然后对剩下的小球（s-ai-1）按原来的插板法求放法就可以了#include#define eps 1e-9#define PI 3.141592653589793#

2017-09-17 00:51:09 337

原创 HDU - 5794 A Simple Chess lucas+容斥

有些点不能走，从1，1走到n，m，每次只能走日字（象棋马），问有多少种走法，从一个点到指定点的走法可以组合数求解关于组合数，这篇博客的图很形象http://www.cnblogs.com/hchlqlz-oj-mrj/p/5740838.html然后排个序容斥掉不能走的点就可以了#include#define eps 1e-9#define PI 3.1415926535897

2017-09-17 00:45:54 213

原创 To My Girlfriend HDU - 5800 dp

那个式子可以想成有两个物品必拿，有两个物品必不拿，最后体积小于等于m的方案数也是同样想到了n^3的dp，必然会T，走进死沟，看了题解，才想到...不要考虑太多，对每个物品，有四种拿的状态，拿，必定拿，不拿，必定不拿这样就裸的转移就可以了#includeusing namespace std;int a[1005];long long dp[2][1005]

2017-09-17 00:40:52 214

原创 HDU - 5881 Tea 思维

题意是倒茶，你只知道茶壶里水是L，R，可以壶里留1体积，往两个杯子里倒，最后两个杯子里面茶的体积差不能大于1首先会想到肯定要向第一个杯子里倒（l+1）/2 体积的茶，这样下一步就可以往另一个杯子里到(l+1)/2 +1体积，这样两次倒掉的总体积是L+2，如果R-1大于L+2的话就需要继续倒，每次最多往一个杯子里倒两体积，倒多的话可能壶里没水，违反规则，这样在特判先R#include

2017-09-17 00:33:56 277

空空如也

空空如也