- 博客(586)
- 收藏
- 关注
RSS订阅原创 网易互娱9.27号19点研发岗笔试题解
一共四道编程. 前两道比较简单就不说了, 主要讲讲3，4道.第三题: 开心消消乐就是给你个M*N的二维矩阵, 每个块有一个颜色, 如果它的四周有相同的颜色那么就是连在一起的, 每次点击一个色块(要能点击消除尽量多的, 如果有数量相同的点击编号小的)进行消除, 然后消除后上面的掉下来, 如果某一列消失了, 右边的补过来. 问最后这个矩阵还剩多少个方块…题解: 按照题意模拟即可, 每次dfs找...
2019-09-28 18:49:16
1522
原创 阿拉伯数字金额转中文大写金额 base C++
#include <bits/stdc++.h>using namespace std;string snum[] = {"零", "壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"};string sdecimal[] = {"角", "分"};string sinterval[] = {"元", "万", "亿", "万"};stri...
2019-09-11 21:47:12
513
原创 LeetCode #4 寻找两个有序数组的中位数
传送门题意: 给定两个有序数组, 求中位数思路: 中位数实际上就是找中间那最多两个数, 然后两个数组又是有序的, 所以可以转换成求两个有序数组合并后的第k大问题, 所以我们需要有一个函数求 对于两个有序数组求第k大, 那么如何最快的求第k大了，很明显我们在两个数组中同时各取一半的数字(k/2) , 如果第一个数组的这位置(起始位+k/2-1)的数字比第二个的小， 那么说明这第k大肯定是不在第一...
2019-08-15 14:20:24
651
原创 LeetCode 560 Subarray Sum Equals K【前缀和】
传送门题意: 有多少个连续子序列和为给定的k,思路: 连续, 就要想到前缀和, 所以我们利用前缀和的性质, 相减等于中间的和, 那么直接记录每个前缀的次数, 然后累加即可, 注意这类问题 0 这个数都是会作为默认点加的! 不要忘了，想想也是对的AC Codeclass Solution {public: int subarraySum(vector<int>&...
2019-04-21 23:08:09
417
原创 LeetCode 1,167, 15, 18 (2, 3, 4)数之和相关问题
传送门1这类题都是给定个类似 a + b + … = x, 问有方案数. 我们对于这种都用拆分的思想, 然后用小的去解决大的, 首先我们说2 sum.我们对n个数先排序, 然后两个指针, 一个开头，一个结尾, 然后往中间动, 如果x - b > a (b是后面的指针指的值, a是前面的指针指的值)， 很明显如果再让j(后面的指针)动, 那么x - b会越大, 所以要让i(前面的指针)动,...
2019-04-21 22:46:34
181
原创 LeetCode 124 Binary Tree Maximum Path Sum
传送门题意: 跟定一颗带点权二叉树, 问其任意一条路径的最大值是多少.(路径, 任意一点出发和结束的路径)思路: 其实就两种情况, 一是左右子树加上本身结点构成一条路, 二是将自己和左右子树更优的连接起传给父亲结点成路. 所有的情况就是这两种情况的综合，所以按照这个写就行了.AC Code/** * Definition for a binary tree node. * struct...
2019-04-19 01:46:20
186
原创 LeetCode 4 Median of Two Sorted Arrays【经典题目】
传送门题意: 给定两个有序数组, 要求在O(log(m+n))的复杂度之内求出合并后的中位数思路: 数据水，线性的也能过. 但是面试遇到就不一定能过了. 所以还是得想正解. 有个log，所以我们用二分来做, 具体做法就是每次算一算第k/2在哪里, 分别取出中间的来比较, 再按照大小关系递归算出，第k大在哪里, 每次递归减少k/2, 所以就是logk(k ≈ m + n), 所以复杂度合理!A...
2019-04-19 01:42:36
144
原创 LeetCode 342 4的幂
传送门题意: 就是判断一个数是不是4的幂思路: 2的幂已经写烂了, 4的幂的话也是在2的幂的基础上考虑的, 首先要保证是2的幂，然后观察4的幂的性质, 发现2进制的1一定在奇数位上, 那么我们需要一个用来验证奇数位上1的数字, 那就是0x55555555, 因为0x5 = 0101, 所以可以验证, 同理类似的题目都是这样做.AC Codeclass Solution {public:...
2019-04-18 23:50:50
248
原创 LeetCode 137 只出现了一次的数组||
传送门题意: 只有一个数字出现了一次, 其余数字都出现了三次. 问一次的那个数字是多少.思路: 相信2次的已经做烂了, 那么这道改编的了?一个二进制位只能表示0或者1。也就是天生可以记录一个数出现了一次还是两次。x ^ 0 = x;x ^ x = 0;要记录出现3次，需要两个二进制位。那么上面单独的x就不行了。我们需要两个变量，每个变量取一位：ab ^ 00 = ab;ab ^ a...
2019-04-18 21:35:17
156
原创 Codeforces #251 D题 Devu and his Brother 【三分】
传送门题意: 给定一个长度为n的a数组, 和一个长度为m的b数组, 每次可以选任意一个数组的任意一个元素, 让它+ or - 1, 问最少执行多少步，可以使得a数组的最小值 >= b数组的最大值.思路: 很明显, 我们需要找到那个临界值, 并且一定是处于一个中间水平，太大或者太小都不行, 所以可以用三分处理, 然后统计答案就行, 详情看代码实现.AC Codeconst int ma...
2019-03-20 01:40:08
198
原创 西北大学校赛B题 北境之都 【三分】
传送门题意: 给定n座房子的高度, 要求任意两座房子的高度差在m以内, 每个房子只能改变一次高度，将一个房子的高度改变k米的花费是k^2万元，求最低要花费多少万元思路: 很明显, 将一个房子的高度放在过高或者过低的都是不最优, 而是中间的某个值, 比如样例就是45, 所以我们可以三分一下最低高度x, 然后x + m作为最高高度, 比x小的变为x, 比x+m 大的变为 x + m, 然后取最优值...
2019-03-19 21:35:20
300
原创 LeetCode 834 Sum of Distances in Tree
传送门题意: 给定一棵树, 输出每个点到其他点的距离之和.思路: 首先我们先dfs一遍, 存下每个点的子节点数(包括自己), 和一个值称dp, dp[u] 表示u的所有子节点到u的距离之和, 那么很容易也可以在第一次dfs中维护, 那么此时dp[0] (假设0是根节点), 就是0的答案, 那么其他的答案了, 实际上可以通过父亲的ans来转移, 此时ans[0] = dp[0], 那么假设0的字...
2019-03-19 15:04:46
265
原创 HDU 6446 Tree and Permutation【思维】好题!
传送门题意: 给定一个n, 那么1-n是一个排列, 定义某个排列(x y z)的值为x - y, x - z在树上的最短距离和, 求这个排列的全排列的值相加等于多少, 树的形态会给出.思路: 算边的贡献, 首先对于任意一个排列, 它是树上某点到其他点的距离之和, 然后由于全排列, 实际上就是树上任意两点之间的距离之和(考虑顺序), 首先树上任意两点之间的和我们会求(考虑每条边的贡献, 即边的两...
2019-03-19 14:58:10
195
原创 LeetCode 810 Chalkboard XOR Game【思维】
传送门题意: 给定n个数, 两个人轮流上去删除一个数字, 如果在某个人删除后, 剩下的数字异或等于0，那么这个人就输了, Alice 先手, 如果它能赢return TRUE.思路: 考思维, 首先全部数字异或等于0需要二进制的每一位上1出现偶数次, 那么如果刚开始就异或等于0，Alice肯定就赢了嘛, 否则如果剩下的数字是偶数Alice也一定能赢, 因为每次删除一个数字后剩下的数量一定是奇数...
2019-03-19 14:45:03
242
原创 LeetCode 793 Preimage Size of Factorial Zeroes Function【思维】
传送门题意: 给定一个x! 后零的个数k(<1e9), 问满足x的数字有多少个.思路: 很好的一道题, 我们一步步解决.1: 如何求x的阶乘末尾0的个数?10进制中只有2和5相乘才会得到10，也就是每有一对2和5，就多一个末尾的0而阶乘又是从1开始乘到x，所以2的个数总是比5多，那么问题转化为求x！中有多少个5作为因子公式为 k = x/5 + x/5^2 + x / 5^3 +...
2019-03-19 14:36:14
227
原创 LeetCode 995 Minimum Number of K Consecutive Bit Flips【思维】
传送门题意: 给定一个长度为n的01数组, 每次可以将连续的k位翻转(o -> 1, 1 - > 0), 问能否将整个数字变成全1，能的话最少翻转多少次.思路: 很明显可以分析出的是, 一但遇到0了，那么一定要翻转, 并且以后都不能再翻转它了, 也就是跟着翻转下去, 所以一个很暴力的想法就出来, 直接每次暴力翻转连续的k位, 那么复杂度是接近于n^2的, 所以我们就不写了, 那么我...
2019-03-19 14:31:25
218
原创 leetcode 1015 Numbers With Repeated Digits
传送门题意: 给定一个N，求1 - N中，输出至少有一位数字是重复的数字的个数.思路: 很明显, 这道题要用数位dp, 考虑两点, 一是前导零的影响, 二是记录的应该是每一位的次数, 而不能是简单的标记和清空标记, 比如101 和 110. 所以状态想好为dp[i][j][k] 表示起始位i, 当前位j, 是否已经有重复位数k(0 or 1) , 然后做记忆化搜索就行, 没啥坑点.AC Co...
2019-03-18 20:40:13
581
原创 小米OJ编程比赛 2月常规赛 Carryon 数数字
传送门题意: 给定l, r通过以下步骤求答案1: 需要将 l 到 r 之间的数全部转化成 16 进制，然后连起来2: 将连起来的数又转化成 10 进制3: 将最终结果对 15 取模数据范围：1 <= L <= R <= 1e12思路: 首先推导, 假设区间[L, R] 转化为16进制后连起来为 xyz. 那么答案是多少了.ans = (x * 16 ^ 2 + y ...
2019-03-18 19:30:32
340
原创 HDU 2089 数位dp解法
传送门(数位dp入门题)题意: 就是求给定区间内数字中不含4和连号62思路: 很入门的数位dp, dp[len][state] 表示当前第len 位，并且前一位是否是6, 然后记忆化搜索即可, 因为每到一个位置的数字, 都有两种状态, 需要分开考虑.ll dp[30][2], shu[30];ll dfs(int st, int state, int limit) { if (s...
2019-03-18 17:34:59
242
原创 LightOJ 1205 Palindromic Numbers
传送门题意: 求给定区间内回文数字的数量思路: 很明显求区间内满足某种条件的数字个数, 就用数位dp, 然后想好状态, 我这是三维dp[st][cur][state] 表示起始位是st, 当前位是cur, 是否构成回文数字(state1是,. 0否)然后就是内部循环怎么写了, 总体思路就是前一半的位置上的数字任意填, 然后到可以填后一半时，不仅要填，还要对称的填，然后依次记忆化搜索即可l...
2019-03-18 17:21:37
152
原创 谈数位DP
在了解数位dp之前，先来看一个问题： 例1.求a~b中不包含49的数的个数. 0 &amp;lt; a、b &amp;lt; 2*10^9注意到n的数据范围非常大，暴力求解是不可能的，考虑dp,如果直接记录下数字，数组会开不起，该怎么办呢？要用到数位dp. 数位dp一般应用于：求出在给定区间[A,B]内，符合条件P(i)的数i的个数.条件P(i)一般与数的大小无关，而与 数的组成 有关.这样，我...
2019-03-17 22:54:38
164
原创 牛客练习赛 41 B 题 【简单的dp计数】
传送门题意: 就n个数，开始分数为0, 第i次操作可以有两种选择1: 给分数加上a[i]2: 给分数乘-1问n次过后分数为-666并且任意一次操作后分数不能是666的方案数是多少? (%1e8+7)思路: 很明显的dp计数, dp[i][j] 表示 i 次操作后分数为 j 的方案数, 那么转移方程是dp[i][j] = dp[i-1][j-a[i]] + dp[i-1][-j];去掉...
2019-03-02 15:27:47
220
原创 求一个单独的球和n个球的相交体积【模板】
模板如下: 所有的类似题都可以经过这个模板改编例如: 求两球相交, 两球相并, 等等相关#define PI acos(-1.0)#define ll long long intconst int maxn = 1e2 + 5;using namespace std;struct point { // 这里的点是指球 double x,y,z; point() { ...
2019-03-01 20:22:02
646
原创 Codeforces Global Round 1 E 题【思维】
传送门题意: 给定n个数的两个数组, c数组和t数组, 每次可以选择一个i(1 &lt; i &lt; n) 使得c[i] = c[i+1] + c[i-1] - c[i]; 问能不能再进行若干次这样的操作后使得c数组变成t数组.思路: 问题的解决点就是变换等式, C[i] = C[i+1] + C[i-1] - C{i], 假设变换后的为C2[i], 那么稍作转换可发现C2[i] - C[i...
2019-02-27 20:37:32
183
原创 2018年CCCC比赛L1 天梯赛座位分配
题目地址这道题巨坑啊，当时卡了好久还是没得全分，主要有两个坑点.1: 只有一个学校的时候, 此时就是直接从1开始+2插就行2: 最坑的还是，题目说的是只剩一所学校的时候, 该所学校的人要分开坐, 样例刚好是第二所学校结束，也就是最后一个编号是80，所以下一个是82开始, 但是如果最后一所学校的最后一个以有编号的是79, 那么只有该所学校时，第一个人员的编号时81 ！！！， 也就是我们需要判断...
2019-02-26 00:19:03
356
原创 POJ-3764 The xor-longest Path 【思维 + 01字典树】
传送门题意: 给定一棵带权树，求树上一条简单路径，经过的边异或值最大.思路：任意一条u-&gt; v的路径f(u, v) = f(1, u) ^ f(1, v), 所以我们可以把从1出发到某个点的异或值全部算出来，然后问题就变成了从这些值中选择两个数异或最大，那么就是01字典树的问题了，所以就解决了. 还是注意字典树内存问题AC Codeconst int maxn = 1e5 + 5;...
2018-10-25 19:34:10
290
原创 CodeForces - 662A Gambling Nim【思维 + 线性基好题】
传送门题意: 每张卡片正面和反面都有一个数字, 然后现在以一种方式每张卡片选一面放在上面, 问放在上面的数字异或为0的概率为多少思路: 我们假设S = a[i] ^ a[i+1] ^ … ^ a[n], c[i] = a[i] ^ b[i], 再假设我们选择了k个c[i], 所以这次异或的结果可以表示为S ^ c[i] ^ … ^ c[k], 说明选到了的k张卡片我们选择b[i]的一面, 剩下...
2018-10-09 14:16:06
319
原创 BZOJ 2957 楼房重建 【线段树经典模型维护区间LIS】
传送门题意：每次会在一个坐标上修建一个新楼房, 问每天修建完后能看到多少栋楼房.思路：如果一栋楼房它的斜率大于前面的任何一个那么就能被看到, 所以我们要维护一个区间之间的合并问题, 其实用分块很好写 , 但是时线段树的一个经典模型, 所以我们就用线段树了.AC Codeconst int maxn = 1e5+5;int n, q;struct node { int tl, ...
2018-10-09 09:56:28
459
原创 BZOJ 4919 大根堆【set启发式合并 维护树上LIS】
传送门题意: 对于一颗有点权的树, 如果i是j的祖先, 那么要满足vi > vj, 问最多可以在这棵树上选择多少个点可以满足这个条件.思路: 那么这就是树上lis，怎么维护了, 每个点依旧像普通数组这样, 那么就有合并, 要合并某个点和儿子的数字, 然后依旧还是g[i]表示lis长度为i时, 最小的a[i]可以是多少, 那么直接就查lower_bound就行, 又要排序, 和重值, 所以...
2018-10-09 09:47:55
400
原创 线段树区间排序问题两道经典问题 UESTC 1919 和 CF 558E
CF - 558E题意: 给定一个字符串, q次操作, 每次操作一个区间, 0表示让这个区间降序, 1 表示升序, 问最后字符串的样子.思路: 区间排序问题, 凡是区间排序问题, 并且里面涉及到的种类不多大概60左右, 都是可以用线段树维护的, 并且种类越少越好排, 所以我们直接用线段树维护当前这个区间每个种类的数量, 这里只有26种, 然后对于每次排序, 我们首先计算出这个区间的每一种种类数...
2018-10-09 09:37:00
1935
原创 洛谷 P2279 树上k距离覆盖问题【贪心 + 思维】
传送门题意: 给定一颗树, 若在i点安放了一个消防站, 那么在树上距离它不超过2的所有点都可以被照顾到, 那么要让整棵树都要照顾到最少需要安放多少个消防站,思路: 贪心, 就是找最深没被覆盖到的点, 并在它的祖父处设一个消防站. 考虑到这个点的所有子孙后代都已经被覆盖了, 因此这时覆盖祖父能盖到更多额外的点, 并保证结果不会更差.我们在输入时只要预处理出深度(边输入边处理)并排序, 碰到已覆...
2018-10-06 19:34:35
2549
原创 洛谷 P3398 仓鼠找sugar 【思维 + LCA】
传送门题意: 就是给定一棵树, 然后有q次询问, 每次给出树上的两条路径, 问着两条路径是不是有没有公共点思路: 通过画一系列的图可知, 如果两条路径有公共点, 那么一定有一条路径的LCA是在另一条路径上的, 那么我们现在如何判断一个点x是不是再一条路径上了？如果点x在路径u-&gt;v上, 那么一定满足dep[x] &gt;= dep[LCA(u, v)], 并且LCA(u, x) == x...
2018-10-05 21:15:38
250
原创 第十四届华中科技大学程序设计竞赛 部分有趣题的题解(A, C, I, L)
传送门A: 题意: 就是定义树上的一个三元组(a, b, c) 成立的条件是|dis(a, c) - dis(b, c)| % 2 == n % 2; 给定一棵树, 问树上这样的三元组有多少个.思路: 分析可知, 我们肯定是把枚举c, 然后判断每一个c有多少个a, b, 可以填, 然后我们发现填这个是和n的奇偶性有关, n为奇, 那么一定时奇-偶(或者相反), 那么我们要知道的就是对于树上每...
2018-09-25 13:48:49
491
原创 洛谷P1525 关押罪犯 【思维 + 二分图判定】
传送门题意: 给出m对憎恨关系, 有一个憎恨值, 现在要将这n个人分成两堆人, 要求这两堆人中存在的憎恨值最大的最小, 问这个值是多少.思路: 这种问题首先是二分, 然后我们如何check这个答案, 我们将所有边的憎恨值大于我们这个答案的新建一幅图, 然后我们判断能否避免掉这幅图的每一个边的关系, 怎么做了才能避免了？ 实际上就是有憎恨关系的两个人一定要放在不同的集合中, 然后怎么判断不能放在...
2018-09-24 20:34:38
261
原创 经典的三色小球相邻小球颜色不同,摆成一排的方案数【】
题目描述: 有三种颜色的球, 每种球的数量分别是a, b, c, 问把这三种小球摆成一排, 相邻小球颜色不同的方案数是多少?思路: dp, dp[i][j][k][l] 表示剩ijk个 最后一个是l颜色, 那么讨论一下最后的颜色的种类就直接转移就行了.AC Codetypedef long long ll;ll dp[22][22][22][4];void solve() { i...
2018-09-20 21:11:45
5061
3
原创 洛谷P2921 Trick or Treat on the Farm 【思维 + 对图的一些操作】
传送门 题意: 给出每个编号下一个要到达的编号, 问最后每个标号可以到达的编号数量(具体可以看样例)思路: 很明显有环的情况需要考虑, 所以实际上这是一副链环的有向的非联通图, 有自环的情况. 所以我们有先把链的情况删掉, 然后统计出每个环的大小, 然后再次累加到那些链的上面就行了. 就按照这个实现即可. 具体细节还要自己思考下…AC Codeconst int maxn = 1...
2018-09-11 16:38:54
242
原创 洛谷 P1330 封锁阳光大学 【思维 + 二分图判定】
传送门 题意: 可以占领一点, 然后和这个点相邻的边都被封锁了, 如果在占领的这一点的相邻边的点再次被占领的就会有冲突, 问占领所有的边并且没有冲突最少要占领多少个点.思路: 很明显, 如果我们占领了一个点, 相当于我们把这个点丢到一个集合中, 相邻的点放到另一个集合中, 然后另一个集合中的点的相邻点又可以放在之前的那个集合中了, 因为条件是等价的, 所以着很明显就是判定二分图的过程, 所以...
2018-09-11 16:26:55
237
原创 2018徐州网络预选赛 J 题 Maze Designer 【思维 + 最大生成树 + LCA】
传送门 题意：给定一个n*m的矩阵, 除了边界, 其他相邻的边都有一个代价, 现在我们需要在这个矩形中选择一些边封起来, 代价就是开始输入的代价, 我们要让封起来的代价和尽量的小, 并且封起来后, 矩阵中任意两点之间的最短路径是唯一的, 现在不告诉你具体是怎样封的(但是这个矩形已经进行了封墙的操作), 然后q个询问, 每次询问两个点, 他们在这个已经处理过的矩形中的最短路径是多少.思路: 其...
2018-09-10 12:43:52
280
1
原创 【(完全)K分图的判定】
描述: 对于一个无向图, 如果能划分成若干(k)个集合, 使得任意两个同一集合内的点之间没有边相连, 任意两个不同集合内的点之间有边相连, 则称该图为完全k分图, 现在就是对于给定的一个图进行判断k是多少. (n <= 1e3)思路: 我们对于原图的补图进行并查集维护, 如果两个点之间没有边, 则他们一定在同一个集合内, 因为如果不在同一个集合, 但是他们之间已经没有边了, 一定不满足先...
2018-09-09 21:43:30
1837
原创 牛客练习赛 25 E题 定向 【桥 + 思维】 无向图定方向变强连通图
传送门 题意: 给定一个无向图, 然后你要给这幅图每条边加上一个方向, 使得这个图是有向图强连通思路: 关键在于如何判断无解的情况, 如果能保证当前的图有解, 那么直接dfs一下就可以出答案. 仔细想想知道. 其实就是判断一下当前这幅图是否有”桥” , 联通分量的定义的桥, 如果有桥则一定无解, 否则就有解, 然后dfs一下就可以得到答案了. 细节请看代码 AC Codeconst i...
2018-08-25 00:03:06
760
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人