- 博客(14)
- 收藏
- 关注
RSS订阅原创 【天梯赛】功夫传人
【题意】给定一棵有根树,给定根的权z,从根开始遍历,每个节点的孩子的权都会变成原来的r%,如果这个节点在事先给定的序列rr里，那么他会把权值乘上rr[i]再传递给孩子。求编号在给定的序列里的节点的权值和。自己的WA点，没搞好传递关系，写错了，一开始写的是从爹就开始判断儿子是不是特殊节点，如果是特殊节点就乘上个rr[爹]，这完全搞混了好吧。WA点2:最后输出的时候取整数部分cout<<floor(ans) wa了4分。
2023-04-17 20:40:36
82
原创 【基础算法】表达式计算
后缀表达式对于计算机很容易计算，只需要从头部扫描字符串。然后遇到数字就入栈，遇到运算符就取出栈顶的两个数进行运算。最后把运算结果入栈，最后栈中就会剩一个数为答案。3.遇到右括号，弹出栈顶并输出，直到栈顶是左括号，然后左括号弹出（并不会输出左括号）。一般方法是，先把中缀表达式转成后缀表达式，然后计算后缀表达式的结果即可。可以扫描的时候，加些判断，把字符串转换成整数，然后计算。4.如果遇到运算符，检查栈顶，如果栈顶的符号优先级高于等于新符号，就。现给定一个中缀表达式，要求计算结果。2.遇到左括号直接入栈。
2023-02-14 22:28:11
283
原创 【模拟】需要注意的一些事情
1.一般循环模拟的题。原则就是不能留到下一次循环来检测,自己本次循环完就检查边界问题。（因为如果下次检测。while头部就会有一堆条件判断，很烦的）3.局部变量字符串(string)如果申请了，没有赋值空，会有一些乱码在里面。（其实和整型局部变量一样的道理）思维也挺拉的，列出一些事项需要注意。快CCCC和蓝桥杯了。2.结构体多属性比较。
2023-02-11 16:42:50
87
原创 【DP】没有上司的舞会（简单树形DP）
题意，给定一颗有根树，每个节点有一个权值，如果取父亲节点的权值，那么所有儿子节点的权值不能取。试规划一种节点选取方案，使得取到的节点权值和最大，只要求给出最大值。容易想到：父亲选了。父亲没选，儿子可以选，也可以不选。用dp[x][1]表示选了x节点后，x和其所有子孙的合规选法的最大权值和。用dp[x][0]表示没选x节点，其所有子孙的合规选法的答案权值和。(max(dp[x的儿子][1],dp[x的儿子][0]));状态的定义一定要明确好。不然父亲，儿子，孙子，容易搞晕的。(dp[x的儿子][0]);
2023-02-04 20:49:49
71
原创 【DP】环形石子合并
然后我们只需要考虑 合并[1,n],合并[2,n+1],合并[3,n+2],..........合并[n-1,2*n-1]的这些答案里面取一个最大和最小的即可，剩下的问题就是一个基础的石子合并的问题了。给定几堆石子，这几堆石子围成一个环，每次合并可以合并两堆相邻的石子，本次得分为这次合并的两堆石子数的和，多次合并后的得分加在一起。然后比较好考虑的一个性质是，合并一次[l,r]或者说本次合并[l,r]的花费等于sum_a[l][r]关于合并石子，我用的记忆化，比较方便，循环推感觉不是很好考虑。
2023-01-19 19:02:25
74
原创 关于最长上升子序列有关的一些思考[蓝书思考题]
按照这样修改，肯定会将整个序列构造成一个非严格上升子序列，如果序列的所有第i元素对应加i，那么显然，整个序列将变得严格上升。【理解（不算严格的证明）：很容易想到，除去非严格上升子序列里的元素，剩下的元素，只需要按照需要变成子序列里的元素就可以了，比如 5 1 1 4 2 6 1，最长非严格上升子序列 1 1 2 6，剩下的5 4 1，分别按照需要变成1 1 6即可】正确答案: 构造序列B[i]=A[i]-i,答案为序列长度-B的最长非严格上升序列长度。错误答案1：序列长度-最长非严格上升子序列长度。
2023-01-07 23:36:58
368
原创 【DP】摆花
实际上意思就是摆前i种花，用了j盆的方案数，可以从摆前i-1种花，用了0,1,....,k盆转移过来(k=j），那么很容易想到转移的时候，分别对应的，本阶段用了j-0，j-1,....,j-k盆花.给定一个A[i],第i种花不能摆放超过A[i]盆，并且花按种类编号1到n，并且摆放序列要求按编号升序。【注意,允许存在第i种花不摆放的情况！不难想到 用dp[i][j]表示摆放前i种花，用了j盆的方案数。如果j-k>a[i]那么就不能转移了。然后考虑实际上DP[i][0]=1。问摆放n种花m盆的方案数。
2023-01-07 11:55:58
341
原创 【DP】最长上升子序列
比如某时刻可能存在 3 2 1和3 2 2 2 2 1的数组。lower_bound(x)寻找第一个大于等于x的位置，找不到返回数组的尾部元素位置+1的位置。upper_bound(x) 寻找第一个大于x的位置，找不到返回数组的尾部元素位置+1的位置。这个洛谷题目注意，第一次找最长 非严格下降子序列，第二次找 最长 严格上升子序列。还有一个注意的地方。寻找最长严格下降子序列和寻找最长非严格下降子序列的区别。在降序序列上，upper_bound是第一个小于x的位置。扫描到300的时候 更新207为300。
2022-12-26 20:02:31
390
原创 【DP+拓扑】最大食物链计数
很容易想到拓扑排序后整个图变得有层级，到达点A的路径数等于A的前驱的路径数的和。即cnt[A]+=∑cnt[A的前驱节点] 所以都统计出来之后，最后扫一遍出度为0（终点）的cnt加起来就是答案。不断取出队头，从队头枚举后继，把后继的入度减一，如果后继的入度减为0了，那么直接把它入队。题意：给一张有向图。图保证无环，且存在若干个起点(入度为0)和若干终点(出度为0) 求起点到终点的路径数量。拓扑排序保证了DP无后效性。操作一个入度为0的节点的后继，保证了操作完后，该点不会再对后继有任何贡献。
2022-12-26 11:46:22
97
原创 【exgcd】扩展欧几里得
3.可以用来解线性同余方程a*x≡b (mod m) 等价于a*x-b=k*m等价于a*x-k*m=b等价于a*x+m*y=b。因为-5%3=1 （一般情况下取模如果结果是负数，那么就再加上这个模数，-5%3=-2 -2+3=1）4.x最小正整数解 ((c/d)*x0%(b/d)+(b/d))%(b/d)对于任意整数a,b,存在一对整数x,y 满足 ax+by=gcd(a,b)y的最小正整数解((c/d)*y0%(a/d)+(a/d))%(a/d)主要介绍扩展欧几里的和总结一些常用性质。
2022-12-25 20:46:53
362
原创 【网络编程】捕获网卡IP数据报
1 参数protocol用来指明所要接收的协议包，如果是象IPPROTO_TCP(6)这种非0、非255的协议，当操作系统内核碰到ip头中protocol域和创建socket所使用参数protocol相同的IP包，就会交给这个raw socket来处理，因此，一般来说，要想接收什么样的数据包，就应该在参数protocol里来指定相应的协议。这时候你可以调用bind来指定，指定之后，你的程序就用声明的这一块资源来做事，声明的本机IP和端口就被占用了。发送的数据需要自己填充IP包头，并且自己计算校验和。
2022-12-13 00:03:10
796
1
原创 【VS socket】不兼容老版本函数的问题
1>d:\windows kits\10\include\10.0.17763.0\um\winsock2.h(2219): note: 参见“gethostbyname”的。一般是低版本的函数不安全，取消预编译检查。在原来字符串后面打个分号，然后黏贴。当我们使用vs进行网络编程时出现。2.修改预处理器定义。
2022-12-12 17:57:38
164
原创 【新学期、新Flag】至顶峰见
我叫刑大锤，字天，号铠甲。我今年20岁，一张帅气的脸庞，隐隐透露出忧郁的气质。一出场便迷倒万千少女。我不需要读书，家里有矿，加氟是XX尚书，二品官员，不大，在四九城有套几百亩的房子。无车，但有私人飞机，无存款，但有余额。请你注意，我不是在炫耀，我只是陈述事实…嘿嘿嘿嘿嘿，以上介绍，纯属杜撰，如有雷同，纯属雷同。我姓刑，当年我爸爸生我的时候，为了让我的名字突出一些，所以给我起名----刑部尚书。你总得记住我了吧。
2022-09-21 17:04:59
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人