v0rd
v0rd
全部文章
分类
题解(13)
归档
标签
去牛客网
登录
/
注册
v0rd的博客
全部文章
(共13篇)
题解 | #位操作练习#
不转换为二进制,直接用位运算实现循环移位 实现16位二进制的循环移位,可以先判断移出位是否为1,然后将原数字左移1位,再加上移出位,之后和0xffff进行与操作,取低16位。最多循环16次即可得出结果 #include <iostream> #include <string>...
C++
位运算
2022-03-13
8
351
题解 | #最小邮票数# 01背包
KY14 01背包问题 将dp数组初始化为INF,状态转移方程为 dp[j] = min[dp[j-cents[i]+1, dp[j]] 初始化方式为 if(j == cents[i]) dp[j] = 1; 完整代码如下 #include <cstdio> #in...
C++
动态规划
2022-02-10
1
268
题解 | #合唱队形#
KY73 这个题乍一看挺难的,但好好想想还是能找到解决办法的。题目暗含的意思是求一个极值,但该极值不是简单的数值,需要再深入一步。 我想到的解决方法是转化成求解最长上升子序列,但题目要求的是前升后降,这可咋办呢?很简单,前序后序求两次即可。 然后进行两次排序,这样就获取到了各个点前面有多少个数,后面...
C++
动态规划
2022-02-09
0
552
题解 | #找出直系亲属#
该题目应该诞生于二孩政策之前,因为每个家庭只有一个孩子。 如果画出图来,可以发现是一颗倒立的二叉树,以孩子为“根节点”,但是这个题不能从孩子这个“根”向下搜索,而应该从孩子为出发点,沿着其父母向上搜索。所以类比树的双亲表示法,用结构体来存储一个结点的父母。 之后用dfs搜索两个结点之间是否连通即可,...
C++
DFS
2022-02-07
2
479
题解 | #Is It A Tree?#
这道题比较麻烦的一点在于需要借助多个辅助数组。 因为结点的值并不处于一个连续的区间,所以需要一个辅助数组来标记结点所取到的值 树的一个关键性质就是除根结点外,其他结点的入度为1,故可以用一个数组来记录所有的入度。这个数组也可用于在进行判断时首先根据入度来找根节点。 然后用并查集来判断是否连通,如果不...
C++
并查集
2022-02-07
0
283
题解 | #八皇后#
经典题目,在求解全排列算法的基础之上,增加一个判断条件,即斜线上是否存在元素。 判断是否共线的条件是|[Yj - Yi]| == |[Xj - Xi]| #include <cstdio> #include <cstring> #include <cmath> ...
C++
深度优先搜索
回溯
2022-01-26
0
281
题解 | #玛雅人的密码#
KY2012 BFS+STL 题目很明显要用BFS来搜索全部的状态,切换状态只需要交换相邻两元素即可。 故想到了用map来存储每一个状态的信息 #include <cstdio> #include <cstring> #include <iostream> #in...
C++
广度优先搜索
2022-01-26
0
307
题解 | #2的幂次方#
KY103 这个题有点意思 大体思路:首先设置一个辅助数组,按下标保存2^0, 2^1, 2^2.... 2^14。 递归时从后往前依次将数字减去2的k次幂,如果能减去,则递归分解k 递归的终止条件为:当前要分解的数字为0或者1。如果当前数字为0,则直接输出即可,如果为1,则说明减去一个2^1 刚刚...
C++
递归
分治
2022-01-25
2
507
题解 | #代理服务器#
第一次尝试时错误地将题目理解成了求解需要切换多少次(忽略了次序要求) 之后更改思路,想到应该选择能跑最远的agent,但机械地选择了在整体区间上进行。 学习评论区@愣头青丶别处仰望 大佬的代码后改正了想法。即利用所有agent来划分区间,选择能跑最远的那个,之后再重新选择(这才是贪心的思想所在)。如...
C++
贪心
2022-01-24
0
350
题解 | #进制转换#
字符串除法 void div(char num[], int end){ char res[32]; int idx = 0, cin=0, k=0, tmp; while(idx <= end){ res[idx] = (cin*10...
C++
字符串
数学
2022-01-23
0
238
首页
上一页
1
2
下一页
末页