5 Xingw-Xiong

尚未进行身份认证

我要认证

明天的你一定会感谢现在拼命努力的自己...

等级
TA的排名 7k+

博客迁移通知

博客迁移通知大家好,本人博客迁移到http://xingw-xiong.ac.cn, 镜像域名:http://xingw-xiong.site.CSDN Blog上过多的广告实在影响用户的阅读体验,所以本人决心在自己的VPS搭一个博客,即便 SEO 做得不如CSDN。...

2018-11-09 14:53:25

[LeeCode 887. 鸡蛋掉落] DP+二分

[LeeCode 887. 鸡蛋掉落] DP+二分分类: 动态规划 二分1. 题目链接[LeeCode 887. 鸡蛋掉落]2. 题目描述3. 解题思路首先,令dp[i][j]dp[i][j]dp[i][j]表示有iii个鸡蛋,建筑物为 jjj层时的答案. 那么, 我们容易想到下面的DP的状态转移方程: dp[i][j]=min{max(dp[i−1][j...

2018-09-02 17:40:14

[51Nod 1564 区间的价值]单调栈

[51Nod 1564 区间的价值]单调栈1. 题目链接[51Nod 1564 区间的价值]2. 题目描述3. 解题思路首先,用单调栈求出每个位置iii,求出LminiLminiL_{min_{i}}和RminiRminiR_{min_{i}},其中:Lmini=min{j}Lmini=min{j}L_{min_{i}}=\mathrm{min}\{j\}, 其中jj...

2018-08-20 17:07:39

[LeeCode 862. 和至少为 K 的最短子数组]单调栈

[LeeCode 862. 和至少为 K 的最短子数组]单调栈1. 题目链接[LeeCode 862. 和至少为 K 的最短子数组]2. 题意描述3. 解题思路首先,预处理出数组的前缀和preprepre, 当区间[l,r][l,r][l, r]的子数组和至少为KKK时,那么有: pre[r]≥pre[l−1]+Kpre[r]≥pre[l−1]+Kpre[r] \ge pr...

2018-08-17 19:12:25

[LeeCode 391. 完美矩形]找规律+线段树扫描线

[LeeCode 391. 完美矩形]找规律+线段树扫描线1. 题目链接[LeeCode 391. 完美矩形]2. 题意描述3. 解题思路首先,完美矩形是一种精确覆盖. 有下面两条性质: 1. 小矩形的面积之和等于大矩形的面积; 2. 矩形不能重叠,也就是矩形最大覆盖数为1.而且,很容易证明,满足上述两条性质,就一定是完美矩形. 对于第一条性质,只需要求出大矩形...

2018-08-17 00:22:02

[hdu 5017 Ellipsoid] 模拟退火

[hdu 5017 Ellipsoid] 模拟退火1. 题目链接[hdu 5017 Ellipsoid]2. 题意描述给定一个三维空间的椭球面方程,求椭球面上的点到原点(0,0,0)的最小距离。 3. 解题思路可以发现,椭球面上到原点的距离,具有一个极大值点和一个极小值点。 用模拟退火的方法可以近似搜索到全局最小。 这里因为只有一个极小值点,所以这里也不需要以一定...

2018-07-06 19:31:41

[计蒜客 阿里巴巴的手机代理商(中等)] 字典树

[计蒜客 阿里巴巴的手机代理商(中等)] 字典树分类:Data Structure Trie 1. 题目链接[计蒜客 阿里巴巴的手机代理商(中等)] 2. 题意描述阿里巴巴的手机代理商正在研究 infra 输入法的新功能。他们需要分析单词频率以改进用户输入法的体验。于是需要你在系统内核里面写一个 API。 API 有如下功能:添加操作:添加操作格式为insert bar...

2018-05-18 09:33:26

[csuoj 2078 查找第k大] O(n)算法求第k大/中位数

[csuoj 2078 查找第k大] O(n)算法求第k大/中位数分类:quick sort1. 题目链接[csuoj 2078 查找第k大]2. 题意描述小W有很强的好胜心,也有很明确的目标,总是希望当第k名,但是小W太菜了,经常达不到目标,于是他每次考试后都想知道第k名的分数是多少,然后以它为目标。 现在给出了每个人的分数,请求编程能力很强的你帮他迅速找到第k名的分数...

2018-05-04 13:23:03

谈谈数据结构-Treap

谈谈数据结构-Treap分类:Data Structure Treap 1. Treap原理Treap=(Binary Search)Tree + Heap。 Treap 去掉fix域和rotate过程,就是一个很简单的排序二叉树BST。 虽然在插入数据完全离散的情况下,BST的期望复杂度也是O(logn)O(log⁡n)O(\log n),但是,无论是在算法竞赛中,还是实际情...

2018-04-24 14:41:21

[Codeforces 193B Xor]暴搜

[Codeforces 193B Xor]暴搜分类:Brute force1. 题目链接[Codeforces 193B Xor]2. 题意描述给定四个长度为 n,下标从 1 到 n 的数组 a, b, k, p,保证 p[1], p[2], …, p[n] 是 1, 2, …, n 的一个排列。你要对数组 a 进行恰好 u 次操作,每次可以在以下两种操作中选择一种:对所...

2018-04-21 23:56:42

[Wannafly挑战赛14 B 前缀查询]字典树

[Wannafly挑战赛14 B 前缀查询]字典树分类:Data Structure Trie Tree Prefix Tree 1. 题目链接[Wannafly挑战赛14 B 前缀查询]2. 题意描述在一个 Minecraft 村庄中,村长有这一本小写字母构成的名册(字符串的表), 每个名字旁边都记录着这位村民的声望值,而且有的村民还和别人同名。 随着时间的推移,...

2018-04-21 14:17:28

[Wannafly挑战赛14 C 可达性]强连通分量

[Wannafly挑战赛14 C 可达性]强连通分量分类:Data Structure Strongly Connected Components1. 题目链接[Wannafly挑战赛14 C 可达性]2. 题意描述给出一个 0≤N≤1050≤N≤1050 ≤ N ≤ 10^5 点数、0≤M≤1050≤M≤1050 ≤ M ≤ 10^5 边数的有向图, 输出一个尽可能小的点集...

2018-04-20 22:37:55

[Wannafly挑战赛14 E 无效位置]线性基合并

[Wannafly挑战赛14 E 无效位置]线性基合并分类:math 线性基1. 题目链接[Wannafly挑战赛14 E 无效位置]2. 题意描述给一个1-base数组{a},有N次操作,每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前,所有不包含无效位置的区间的权值的最大值。输入描述: 第一行读入一个正整数(1&lt...

2018-04-20 22:26:09

[csu oj 2071 Spellcasting]贪心+微分方程

[csu oj 2071 Spellcasting]贪心+微分方程分类:Greedy math 1. 题目链接[csu oj 2071 Spellcasting]2. 题意描述【题意比较繁琐??】 一开始你有EEE点能量,能量可以用来造任意数量的元素(实数),并且立刻造完,造完之后加力量,力量的意思是每秒可以产生的能量数目。 现在有NNN种元素,每种元素每单位需用eie...

2018-04-17 22:33:16

OpenMP 编译移植

OpenMP 编译移植分类:Microblaze Openmp libgomp OpenMP介绍OpenMP (Open Multi-Processing)是一套支持跨平台共享内存方式的多线程并发的编程API,是使用C、C++和Fortran进行并发编程的一种强大方法。 目前,主流的C/C++编译器,比如GNU gcc ,Visual C++,甚至部分嵌入式编译工具链(如Riscv...

2018-03-12 22:06:12

[Codeforces 903 D. Almost Difference]树状数组+大数模板

Codeforces 903 D Almost Difference树状数组大数模板题目链接题意描述解题思路实现代码[Codeforces 903 D. Almost Difference]树状数组+大数模板分类:FenwickTree BigInteger template1. 题目链接[Codeforces 903 D. Almost Difference]2. 题意描述3. 解题思路思

2017-12-14 23:13:20

[hdu 6241 Color a Tree]二分+树形DP

[hdu 6241 Color a Tree]二分+树形DP分类:Binary Search Data Structure1. 题目链接[hdu 6241 Color a Tree]2. 题意描述一棵nn个节点的有根树。现在对它进行染色。有A+BA+B个限制条件。 其中有AA个条件为,第xix_i个节点的子树下染色顶点数目必须大于或等于yiy_i,有BB个条件为,对于不在第xix_i个节点的子树下

2017-12-10 23:38:21

[hdu 6239 Interview]数学OR打表

[hdu 6239 Interview]数学OR打表分类:Math 1. 题目链接[hdu 6239 Interview]2. 题意描述3. 解题思路明明知道公式似乎并不是很难,但是怎么就是推不对。 最后投机取巧的打了个表,然后就很容易找出规律。 概率论太差呀,很难想象这种题目在现场赛竟然是道金牌题?4. 实现代码#include <bits/stdc++.h>using namespace

2017-12-10 21:15:27

[51Nod 1394 差和问题]树状数组

[51Nod 1394 差和问题]树状数组分类:Data Structure FenwickedTree 1. 题目链接[51Nod 1394 差和问题]2. 题意描述3. 解题思路首先离线所有操作,并且所有数字进行离散化。 然后用树状数组维护每个数字出现的次数以及区间和。 对于操作1和操作2,我们可以看成一个单点更新的操作。 但是对于操作3的询问操作,似乎不能直接查询。不过既然答案是全局的,

2017-12-10 12:21:44

[Codeforces 724G. Xor-matic Number of the Graph]线性基+计数

[Codeforces 724G. Xor-matic Number of the Graph]线性基+计数分类:Data Structure bitmasks math1. 题目链接[Codeforces 724G. Xor-matic Number of the Graph]2. 题意描述一个边权非负整数的无向连通图,节点编号为11~nn,三元组<u,v,s>\mathrm{<u,v,s>}表示

2017-12-09 14:59:49

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!