题解 算法 数学day2
《算法竞赛》---三指针
双指针(尺取法) 1.找出指定和的整数对 p37(书页) 哈希表 #include<bits/stdc++.h> using namespace std; int a[100010]; int main() { ios::sync_with_stdio(false);cin.tie();cout.t ......
《算法竞赛》---二分
整数二分经典模型 1.最大值最小化(最大值尽量小) 序列划分 p48 #include<bits/stdc++.h> using namespace std; int n,k; //long long sum; int a[1000000]; bool check(int x) { long lon ......
《算法竞赛》---搜索
搜索 二叉树搜索 bfs搜索二叉树 p98 #include<bits/stdc++.h> using namespace std; const int N=1e5; int n; char a[100000]; struct node { char value; int lson,rson; }t ......
P4093 [HEOI2016/TJOI2016] 序列 题解
题目链接:序列 对于 LIS 问题,很显而易见的有 dp方程为: \[dp_i=\max{dp_j}+1 \ (j<i,a_j \le a_i) \text{ dp表示以某个位置结尾的最长 LIS} \]本题考虑到对于转移的两位置,如果能从 \(j \rightarrow i\),那么在以上条件成立 ......
《算法竞赛》题解---三分
三分法 模板三分法 #include<bits/stdc++.h> #define eps 1e-8//或者 const double eps=1e-8;--主要是double using namespace std; int n; double a[15],l,r; double check(do ......
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\) 个块,对 ......
具体数学第六章习题选做(genshining)
11.对于 \(n\ge 0\),求以下式子的封闭形式。 \[\sum_k(-1)^k{n\brack k} \]由于 \[\sum{n\brack k}x^k=x^{\overline n} \]原式即等于 \((-1)^{\overline n}=[n=0]\)。 12.证明斯特林反演。代入即可 ......
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\) ......