集训队p9248 2018
冯梓轩集训总结3
冯梓轩集训总结3——最短路 模版算法 Dijkstra 可以说是最常用的最短路算法了。主要思想是找到当前更新过的距离源点最近的点,然后用它的最短路去更新与它相连的点的最短路。对于距离源点最近,可以开一个小根堆维护,这样的时间复杂度为 \(O(m \log m)\)。 但是算法有一个弊端:所有边的边权 ......
期末集训总结
这个学期我们主要学了四个内容:序列DP,背包DP,区间DP,最短路。 序列DP 最长公共子序列 朴素模版 for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if (a[i]==b[ ......
期末集训总结
这个学期我们主要学了四个内容:序列DP,背包DP,区间DP,最短路。 序列DP 最长公共子序列 朴素模版 for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if (a[i]==b[ ......
2024寒假集训记录
2024.1.12 这次比赛结果不错,rank1,195pts,但还有提升空间 T1 赛时对着性质打,没想正解 其实可以简单树剖做到95 正解:考虑把路径拆成向上的一段和向下的一段,设起点为s,终点为t 那么向上的一段的一个点P被贡献的条件是\(dep[s]==dep[P]+w[P]\),向下的一段 ......
冯梓轩集训总结2
背包总结 模板 \(0/1\) 背包和完全背包已不需考虑。这里重点讨论多重背包 多重背包 问题描述:给定物品数量 \(n\) 和背包容量 \(m\),对于第 \(i\) 个物品,他的体积为 \(w_i\),价值为 \(v_i\),件数为 \(s_i\)。求最终能获得的最大价值。 朴素 显然,设 \( ......
冯梓轩集训总结1
集训总结1 第一次考试 这次考试考得很差,本来以为可以考 \(100 + 10 + 80 + 0 =190\) 分,结果爆了很多分,最后只考了 \(30 + 10 + 60 + 0 = 100\) 分,属实很炸裂。 A 自认为自己的位运算学的还可以(?),所以第一眼就知道这个题直接对 \(2^k\) ......
P4429 [BJOI2018] 染色
题面传送门 这么牛的结论题! 分别考虑每个联通块,不断去掉一度点显然不影响,我们依次给出几个手玩的结论: 性质 1:如果有奇环,那么无解。 只需要给奇环上的集合全部赋值 \(\{0,1\}\) 即可。 性质 2:若存在两个环的边不相交,那么无解。 考虑一个环,取其对称的两个点,分别记为 \(p,q\ ......
AT_joisc2018_b 题解
AT_joisc2018_b 题解 传送门 题意 有一个以原点为中心的正方形,有 \(n(n\le 100)\) 条不在正方形内部的线段,你需要画一些不在正方形内部的线段,使得这些线段可以把正方形围起来,要求最小化你画的线段的长度和。 思路 我们需要画出一条闭合折线,并且能够把正方形包围。 考虑我们 ......
[集训队作业2013] 城市规划(NTT)
一周一博客二专题计划 题面 n 个点的简单 (无重边无自环) 有标号无向连通图数目。 看着就很典 思路 设\(f(n)\)为n点连通图数目。设\(g(n)\)为n点不一定联通图数目,显然直接枚举每条边是否存在,\(g(n)=2^{\frac{n*(n-1)}{2}}\) \[g(n)=\sum_{i ......
集训杂记-省选篇
12/3 来到了衡实。 要先找回代码的感觉……做一做联赛 T4 吧。 12/4 被卡常了。 我不做了。 学网络流去。 最小割 一直不太清楚这个东西是干什么的……果然需要多做一些题掌握一些模型? 另外割成两块不是指彻底变成两块,而是源点和汇点之间不可达。 做了两个题,感觉好魔幻啊。 还是说尽量去总结一 ......
南外集训 2024.1.9 T3
逆天。 题意 给定一个带 ? 的 01 串,求所有填法下,后缀自动机节点的期望。\(1\le n\le 36\) 解法 后缀自动机节点数等于反串后缀树节点个数。这道题中,后缀树是一棵二叉树,记 \(a, b, c\) 表示其中有 \(0, 1, 2\) 个儿子的点个数。注意到 \(c = a - 1 ......
南外集训 2024.1.8 T3
题意 给定一个序列 \(a\),将之划分为两个子序列,使得两个序列前缀最大值的和之和最小。 \(1\le n\le 5\times 10^5, 1\le a_i\le 10^9\) 做法 首先 DP 很容易做到平方:考虑前 \(i\) 个数,其中一个子序列当前的最大值当然是前 \(i\) 个数的最大 ......
P4383 [八省联考 2018] 林克卡特树
P4383 [八省联考 2018] 林克卡特树 米奇妙妙题 题目的主要操作就是断掉一条边再连一条边权为\(0\)的边 我们考虑先不连那些后来加上的边权为\(0\)的边,先把所有的需要断的边都断掉,那么就形成了\(k+1\)个连通块 接下来的任务就是把所有的连通块连接在一起,可以发现,使得答案最大的连 ......
2023南京号家军集训游记
DAY -1(2023.7.29) 提前一天飞到南京,坐了一坤时飞机。 本来以为南京很热,不过因为台风的原因,这边竟然比成都还凉快一内内。 下飞机做网约车,气死我了,那个司机有点聪明,停在停车场喊我们跑去找他,又不告诉我们停车场在哪,本来都想取消订单的,但要付违约金,只有忍气坐车。到了后他又不把车停 ......
P6305 [eJOI2018] 循环排序
排序方案与 \(a_i\) 的具体数值无关,只与 \(a_i\) 的相对大小有关,所以离散化是显然的。 以下默认 \(a\) 已经离散化。 \(a\) 是排列 令 \(b\) 为 \(a\) 排序后序列,我们发现从 \(a\) 到 \(b\) 的方案是不好找的,但是 \(b\) 到 \(a\) 的方 ......
P4827 [国家集训队] Crash 的文明世界
题意: 给定一个 \(n\) 个点的树,对于每个点 \(u\),求 \(\sum_{v=1}^{n}(d_{u,v})^k\)。 \(n \le 5 \times 10^4,k \le 150\)。 分析: 一道思路很自然的数学题。 利用第二类斯特林数转化式子: \[\begin{aligned} ......
PicoCTF_2018_buffer_overflow_2
PicoCTF_2018_buffer_overflow_2 ret2text 32位程序函数参数劫持 vuln函数中存在溢出 存在后门函数 构造payload跳转到后门函数得到shell 这里要注意,跳转到后门函数的同时要传入两个参数a1 & a2,缺失参数会导致eof错误 from pwn im ......
南外集训 2024.1.5 T3
非常简单的一道题。要好好反思为什么没有做出来。 题意 给定一棵点带权的树,强制在线询问一条链上取恰好 \(m\) 个数按位与的最大值。\(1\le n\le 10^6, 1\le q\le 10^5, 1\le m\le 10, 0\le V< 2^{62}\)。 解法 考虑一个暴力:取出树链上所有 ......
P9247 [集训队互测 2018] 完美的队列题解
题目链接:[集训队互测 2018] 完美的队列 神仙数据结构题,看了很多题解才搞懂。在做此题之前,最好对分块很熟悉,对各类标记非常熟练。考虑题意说的种类是相对于全局的。我们可以考虑局部影响对全局影响。 人为规定:在第 \(m+1\) 时刻,无论队列中还有无元素,我们都把所有队列清空,便于后续的描述 ......
正睿省选第一轮集训 Day 2 组合计数
写出了所有题的解法。当然都没写代码。很多解法的深刻含义和启发意义还有待挖掘。当然其中有很多只不过是经典套路罢了。 LNOI2022 盒 有 \(n\) 个盒子,初始第 \(i\) 个盒子里有 \(a_i\) 个物品。每次可以从 \(a_i\) 向 \(a_{i+1}\) 移动一个物品,代价是 \(w ......
PicoCTF_2018_buffer_overflow_1
PicoCTF_2018_buffer_overflow_1 ret2text vuln函数中s变量存在溢出 存在后门函数 构造payload填充再跳转到后门函数win就可以得到flag from pwn import * io = process('./PicoCTF_2018_buffer_ov ......
P10009 [集训队互测 2022] 线段树 题解
题目链接:P10009 [集训队互测 2022] 线段树 神仙分块题,先给一下出题人的神仙官解:官解 前面还看得懂。后面是啥?这不是 ds 题咋和 dp、轮廓线扯上关系了。看了半天,还是这个启发了我: 其手玩下,在 Excel 里写一下,可以理解到这里其实是想表达的一个核心意思是啥:对于一组序列而言 ......
1210-1223首师附集训游记(补档)(x)
移到了博客园上,markdown的事情先咕咕着 最放飞自我的一集,因为这篇不是要交给老师看的集训总结~ 来集训认识两位车万佬,看鲜花❀看的自己也想写点了,所以这篇写的还真就有点非传统游记了,比较正常要交给老师的总结(虽然也带点发电)也都发在 blog 里了,可能那个能更精确一点?然而确实是缺点摸鱼的 ......
BJOI 2018 解题报告
P4427 [BJOI2018] 求和 谔谔题。这个问题看上去很不可维护,而且让我想到了 P5305 旧词。结果发现怎么 \(k\le50\),那我直接跑 \(50\) 遍不就好了? P4429 [BJOI2018] 染色 神仙题。考虑先用一些比较简单的情况搞到一些性质继续研究。那我们不妨只对原图黑 ......
PicoCTF_2018_rop_chain
PicoCTF_2018_rop_chain 函数参数劫持 整数型绕过 \x00绕过len() 函数vuln中存在栈溢出 flag是后门函数,只要满足win1 && win2和a1 = 0xDEADBAAD就可以得到flag 3.win1 & win2存在于.bss段上,但是可以利用win_func ......
铁人三项(第五赛区)_2018_rop
铁人三项(第五赛区)_2018_rop 函数参数劫持 32位泄露libc from pwn import * context.log_level = 'debug' #io = gdb.debug('./2018_rop','break *0x8048474') io = process('./20 ......
20231213-sdfz多校集训-DS
非 lxl 的 DS 不会线性代数,只能来写 DS 了。 20231226- 没有逻辑,直接放例题。 P1527 矩阵乘法 - 整体二分 P1527 [国家集训队] 矩阵乘法 给你一个 \(n \times n\) 的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第 \(k\) 小数。 \(1 \l ......
南外集训 2023.12.29 T1
首先枚举宝藏所在的点,设为根 \(rt\),考虑如果在某个时刻访问了若干个点,但是没有确定宝藏位置,那么满足什么条件。首先求出这些点的 LCA,设为点 \(p\),\(p\) 不可以是 \(rt\)。我们发现这时候我们已经确认了宝藏到 \(p\) 的距离,而且知道它不属于 p 的哪些子树(所有存在被 ......
2018 考研English英语二
Section III Translation 46.【真题译文】: 一个五年级的学生收到一份家庭作业:即从一系列职业中选择自己未来的职 业道路。他勾划了“宇航员”,但很快由将“科学家”添加到列表中,并也将其选中。 这个男孩相信,如果他读得足够多,他就可以探索尽可能多的他喜欢的职业道路。 所以他读书 ......