钉耙 题解 算法 联赛
2023 百度之星决赛题解
T4 传信游戏 建反向边,从入度为 \(0\) 的结点开始搜 T5 喵喵卫士,全靠你了\(\star\) 考虑暴力枚举每个点的深度,发现只要知道相邻两层的深度就能用组合数算方案数,自然想到按层 DP,把上一层的点数记到状态里 赛时做法 按深度从小到大 DP 的话想要记录每个点是否被用过,以保证深度达 ......
P3203 弹飞绵羊 题解
Question P3203 [HNOI2010] 弹飞绵羊 一条直线上摆着 \(n\) 个弹簧,每个弹簧有一个弹力系数 \(k_i\),当绵羊走到第 \(i\) 个弹簧时,会被弹到第 \(i+k_i\) 个弹簧,如果 \(i+k_i>n\) 则会被弹飞,有两个操作 1 x 查询 \(x\) 处的绵 ......
P1085题解
思路 1.定义校内时间/校外时间/最大值 (记录不高兴值) /记录星期 int n,m,maxx=-1,tmp; 2.使用循环输入并判断 for(int i=1;i<=7;i++){//循环一周的日期 cin>>n>>m; if(n+m>8 && maxx<n+m){//如果津津不高兴了且它比以往的 ......
P5722题解
说两句哈,等差数列求和公式是\((A_1+A_n)\times d \over 2\),所以其实可以一行代码解决,但是我没高斯聪明,于是我不打算用等差数列求和公式。 //(等差数列求和公式) int n; cin>>n; cout<<(1+n)*1/2; 思路 1.定义及输入截止的数/计数器 int ......
P5718题解
思路 1.定义及输入最小值的变量/输入个数/每个数 int n,m,minn=1001; cin>>n; 2.循环输入每个数并找最小值 while(n--){ cin>>m; minn=min(minn,m); } (用for循环也可以) for(int i=1;i<=n;i++){ cin>>m; ......
P1307题解
思路 1.定义及输入原数/反转后的数 int n,cnt=0;//反转后的数一定要归零! cin>>n; 2.用while循环反转 while(n!=0){//只要n还没有被分解完,就继续分解 cnt=cnt*10+n%10;//cnt每次*10再加上分离出的数位(*10为了防0) n/=10;// ......
day13 代码随想录算法训练营 递归遍历
题目: 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 我的感悟: 用helper内部函数写更好 理解难点: 代码难点: 代码示例: 前序 # Definition for a binary tree node. # class TreeNode: # def __ini ......
ABC335E题解
洛谷题面 感觉有点毒瘤,不过还是有些 trick 在的。 题意翻译(复制于洛谷题面): 给定一个 \(N\) 个点 \(M\) 条无向边的图,图上每个点都有其颜色。求所有经过点权单调不降的路径中,出现的不同颜色的个数最多是多少。 由于是单调不降的路径,所以可以点权大的点到点权小的点的路径对结果没有影 ......
【学习笔记】KMP 相关算法
KMP 单模式串匹配,比较平凡所以不说了,比较有借鉴意义的每次拓展一位和 \(nxt\) 数组能极大减少不合法的匹配,时间复杂度 \(O(|s|+|t|)\)。 引出一个定义,记满足 \(s[1,i]=s[|s|-i+1,|s|]\) 的前缀为字符串 \(s\) 的 \(\mathrm{border ......
【算法】【线性表】【链表】反转链表II
1 题目 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1: 输入:head = [1,2,3,4,5], left = 2, right = 4 输出 ......
读算法霸权笔记13_读后总结与感想兼导读
1. 基本信息 算法霸权:数学杀伤性武器的威胁 [美] 凯西·奥尼尔(Cathy 著 中信出版社,2018年9月出版 1.1. 读薄率 书籍总字数220千字,笔记总字数32359字。 读薄率32359÷220000≈14.71% 1.2. 读厚方向 算法的力量:人类如何共同生存? 极简算法史:从数学 ......
【算法】【线性表】【链表】反转链表
1 题目 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例 2: 示例 3: 输入:head = [] 输出:[] 提示: 链表中节点的数目范围是 [0, 5000] -5000 <= No ......
P3730 曼哈顿交易题解
题目链接:曼哈顿交易 比较容易想的题,观察下首先不带修改,考虑维护的东西:次数作为权值,这玩意很显然很难在线维护,考虑下离线算法。看到这种和次数有关的权值,典型的单点加入和删除是非常好找到变化的,那么就莫队离线算法吧。 考虑下莫队如何来做,涉及到权值第 \(k\) 大,解决方法挺多的,但时限容易知道 ......
(坚持每天都写算法)算法复习与学习part1基础算法1-5
今天是写题,数的的三次方根。 使用二分法,浮点数不能位运算直接/2即可。 //这道题很难想到二分,二分查找是查找,就是找哪个地方有目标数 //一般是用在区间上的, //总结:二分要求是有查找条件且是查找,符合这两个条件就可以考虑 //不过这里可以把从0到n的浮点数当成一个区间,看数值范围的话,n的话 ......
CF1687C Sanae and Giant Robot 题解
题目链接:https://codeforces.com/contest/1687/problem/C 题意简述 有两个长为 \(n\) 的数列 \(a\) 和 \(b\)。有 \(m\) 条线段,你可以进行任意次以下操作: 选择一条线段 \([l, r]\),若 \(\sum\limits_{i = ......
P2801 教主的魔法 题解
Question P2801 教主的魔法 有一个 \(n\) 个元素的序列 \(a\),有两种操作 M L R W 对区间 \([L,R]\) 内每个数都加 \(W\) A L R C 询问区间内有多少数字大于或等于 \(C\) Solution 一个比较经典的分块题 暴力分成 \(t\) 个块,对 ......
2023 CCPC 桂林题解
gym H. Sweet Sugar 一个经典贪心是从下到上,如果子树 \(u\) 剩下的部分(一定包含 \(u\))包含合法连通块,那么这个连通块给答案贡献 \(1\),切断 \(u\) 与 \(fa[u]\) 的边 key observation:如果一个连通块权值和为 \(x\),那么一定可以 ......
P1980题解
自定义函数 定义一个自定义函数find_num用来记录数字x在该数里的个数。 int find_num(int n,int m){ int cnt=0; while(n!=0){ if(n%10=m){ cnt++; } n/=10; } return cnt; } 思路 1.定义及输入截止数/含有 ......
P1923题解
博文T3航站楼 ✈ P1923【深基9.例4】求第 k 小的数 预先准备 排序用函数 sort,不会用着参看文章sort用法 头文件 #include<algorithm> 及一个数组 a[5000005] 为了保证输入效率,我们用 scanf 进行输入。不会者可参看文章scanf用法 思路 1.定 ......
P1271题解
博文T4航站楼 ✈ P1271【深基9.例1】选举学生会 预先准备 本题需要用到排序函数 sort,不会者参看文章sort用法 头文件 #include<algorithm> 还需用到一个数组 a[2000005] 思路 1.定义及输入 n,m :选举人数/投票人数 int n,m; cin>>n> ......
P5015题解
博文T2航站楼 ✈ P5015标题统计 数组及变量准备 变量 string n 输入的标题 int cnt=0 计数器 预先准备 getline函数: 可用于输入带空格的字符串,格式如下 getline(cin,字符串名,结束字符); 思路 getline输入字符串\(n\) getline(cin ......
(坚持每天都写算法)算法基础复习part1基础算法1-4——二分
二分使用的前提是有序性的条件如果要找以下情况: 1.找大于等于数的第一个位置 2.找小于等于数的第一个位置 二分使用的前提是无序性的条件下如果要找以下情况: 1.找最大值 2.找最小值 二分法一般有边界问题,如果是有序性的条件下的话只要记住一句话:有加必有减。 这里是示例代码: int mid = ......
1.9模拟赛 T3题解
简要题意 求一个抽象函数,满足 \(∀𝑥 ∈ ℤ, 𝑓(𝑥) + 𝐶 = 𝑓(2𝑓(𝑥) − 𝑥 + 1)\),给定 \(n\) 个点,使得 \(\sum |f(x_i)-y_i|\) 最小,输出最小值 思路 对这个函数进行一次迭代,可以得到 \(f(x+2C)=f(x)+2C\) ......
CF1886E I Wanna be the Team Leader 题解
Problem - E - Codeforces I Wanna be the Team Leader - 洛谷 差一点就想到了/ll 遇到困难?排序肯定不会变差! 性质:每个项目分配的程序员肯定是一段(显然) \(m\) 很小?考虑设 \(dp_{i,S}\) 表示考虑前 \(i\) 个人选项目集 ......
文心一言 VS 讯飞星火 VS chatgpt (175)-- 算法导论13.3 4题
四、用go语言,Teach 教授担心 RB-INSERT-FIXUP可能将 T.nil.color 设为 RED,这时,当 z 为根时第1行的测试就不会让循环终止。通过讨论 RB-INSERT-FIXUP永远不会将 T.nil.color 设置为 RED,来说明这位教授的担心是没有必要的。 文心一言 ......
CF1886D Monocarp and the Set 题解
Monocarp and the Set - 洛谷 Problem - D - Codeforces 非常之降智 加入一个数让他满足他是最大值需要判断前面加入的那些数中最大的是哪个,但删除一个数让他满足是最大值只需要直接把他删掉即可 因此我们要反着考虑这个问题: 如果当前是 <,则删除最小的数,有一 ......
【题解】LibreOJ 3089 「BJOI2019」奥术神杖
先考虑这个权值 \(\sqrt[c]{\prod\limits_{i = 1}^c V_i}\)。 感觉找不到好的方法算出精确值,但是能发现只用比大小。 于是考虑取个对数成 \(\frac{1}{c}\times \ln(\prod\limits_{i = 1}^c V_i) = \frac{1}{ ......
MCM_算法篇
from pixiv Cellular Automata 参考文章: 元胞自动机的实现与应用 这篇文章将CA的实现给出,具体实现细节可以看: Python 实现基于元胞自动机的生命游戏 澳洲变燠洲,考拉成烤拉!澳大利亚山火为什么难以控制? ......
[AGC004F]Namori题解
简要题意 略 思路 先考虑树的的情况,直接黑白染色,统计子树和的绝对值即可 再考虑奇环,发现这时会有两个同色相邻点,只需把多余的操作,在这两个点处理掉即可 最后考虑偶环,先断掉一条边,最后再考虑这条边的贡献,推一下柿子,就变成了初中数学题,取中位数即可 code #include<bits/stdc ......