洛谷专题

洛谷P1364 医院设置

P1364 医院设置题目描述设有一棵二叉树，如图：其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 1 1 1。如上图中，若医院建在 1 1 1 处，则距离和 = 4 + 12 + 2 × 20 + 2 × 40 = 136 =4+12+2\times20+2\tim

洛谷 P4317 花神的数论题

花神的数论题题目背景众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。题目描述话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。花神的题目是这样的：设 sum ( i ) \text{sum}(i) sum(i) 表示 i i i 的二进制表示中 1 1 1 的个数。给出一个正整数 N N N ，花神要问

记一次洛谷刷题让人摸不到头脑的报错——Runtime Error.Received signal 6: Aborted / IOT trap.

报错题目外星密码 - 洛谷具体报错信息 Runtime Error.Received signal 6: Aborted / IOT trap. 错误代码 #include <iostream>#include <cstring>using namespace std;string sol() {string s = "";string t = "";char c = '

洛谷 P3809：后缀排序 ← 后缀数组

【题目来源】https://www.luogu.com.cn/problem/P3809【题目描述】读入一个长度为 n 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。【输入格式】一行一个长度为 n 的仅包含大小写英文字母或数字的字符串。【输出格式】一行，

【洛谷】动态规划之最长公共子序列

前言：本系列目的是记录日常所刷的题，有的是自己想出来的题，有的是看了大佬题解后想明白的题题目 P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前提：两个排列都是1到n的排列，说明元素都是相同的只是顺序不同，思路：把LCS转换成LIS 原因：通过离散化可以得到一个性质。离散化步骤： A:3 2 1 4

洛谷 P3379 [模板] 最近公共祖先（LCA）

【模板】最近公共祖先（LCA）题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入格式第一行包含三个正整数 N , M , S N,M,S N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来 N − 1 N-1 N−1 行每行包含两个正整数 x , y x, y x,y，表示 x x x 结点和 y y y 结点之间有一条直接连

洛谷官方提单——【入门4】数组——python

洛谷官方提单——【入门4】数组小鱼比可爱题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示代码小鱼的数字游戏题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定代码【深基5.例3】冰雹猜想题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示代码 [NOIP2005 普及组] 校门外的树题目描述输入格式输出格式样例 #1

洛谷P10397题解

题目描述给定一条 std::freopen 语句，输出其操作的文件名称。形式化地，std::freopen 语句都应该恰好是 std::freopen("<title>","<mode>",<stream>); 其中 <title> 为其操作的文件名称。其至少包含一个字符，并且只可能包含下列几种字符：大写英文字符；小写英文字符；阿拉伯数字；英文半角句点 .。 <mode> 为文

【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集 - 洛谷,并查集代码!!!

并查集的实现_牛客题霸_牛客网描述给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。 boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合 void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的

洛谷 1359.租用游艇

思路：线性dp。这道题有点像区间dp，又不全像。管他的，反正是dp的题目，主要是思路为好，什么类型的只要自己能分析出来，其实都是一样的核心思路，都是递推嘛，只不过换了个递推的对象。这里用的二维dp,令dp[i][j]是从i到j的最小租金数。我们想，题目中需要我们求到1-n的最小租金，那么我们能否从头遍历呢？这里教大家一个技巧，那就是递推的时候，要求大数，必定从小数开始递推；反过来，要求

洛谷 1111.修复公路

思路：并查集这里需要用到结构体，本来开始的时候作者还为怎么存储那么多数据而烦恼，反倒是忘记了有结构体这种解法了。并查集其实并不是实际意义上的无向图，这一点大家需要铭记，我们在找共同根的时候还是需要全部结点都遍历一下去判断一下根的，而不是随便选择一个数就行了。作者在这里就犯蠢了，把并查集认为是无向图了。其他的地方，就是对于结构体数组进行排序的时候是按照时间的从短到长进行排序的。上代码

P1706 全排列问题洛谷

原题链接：https://www.luogu.org/problemnew/show/P1706 思路：把1~n存在一个数组中，再开另一个数组use，把已使用的数字置为0，用过的置为1，对于每一层dfs，都遍历一遍use，dfs，回溯······ 代码： #include<iostream>#include<cstdio>using namespace std;int a[20],us

P1219 八皇后洛谷

原题链接https://www.luogu.org/problemnew/show/P1219 八个皇后不能有两个或以上同时处于同一行，同一列，同一个对角线，也就是说，每行最多一位皇后只要对每行皇后所处位置进行枚举，满足条件后输出即可直接上代码： // luogu-judger-enable-o2#include<iostream> #include<cstdio>using na

洛谷P1040-加分二叉树-dp+二叉树

P1040-加分二叉树这道题放在深度优先搜索的训练题中，可是我实在没有看出来应该怎么搜索。看了题解以后才看出来是一个很简单的dp(我果然还是太菜了) 看出dp并且算出来最大的分数不是很复杂，关键是输出给定中序遍历序列的二叉树的先序遍历，要用一个数组保存在dp的时候确定的根节点，觉得不是很容易想到。 AC代码： #include<cstdio>#include<cstring>#includ

洛谷 P1008 [NOIP1998 普及组] 三连击

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC 4.0 BY-SA协议。因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。违者必究，谢谢配合。个人主页：blog.csdn.net/jzwalliser 题目洛谷 P1008 [NOIP1998 普及组] 三连击 [NOIP1998 普及组] 三连击题目背景本题为提交答案题，您可以写

洛谷 P1179 [NOIP2010 普及组] 数字统计

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC 4.0 BY-SA协议。因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。违者必究，谢谢配合。个人主页：blog.csdn.net/jzwalliser 题目洛谷 P1179 [NOIP2010 普及组] 数字统计 [NOIP2010 普及组] 数字统计题目描述请统计某个给定范围

洛谷 P1028 [NOIP2001 普及组] 数的计算（递推，数学）

[NOIP2001 普及组] 数的计算题目描述给出正整数 n n n，要求按如下方式构造数列：只有一个数字 n n n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。请你求出，一共有多少个合法的数列。两个合法数列 a , b a, b a,b 不同当且仅当两数列长度不同或存在一个正整数 i

洛谷 B2123 字符串 p 型编码

字符串 p 型编码题目描述给定一个完全由数字字符（‘0’,‘1’,‘2’,…,‘9’）构成的字符串 str ，请写出 str 的 p 型编码串。例如：字符串 122344111 可被描述为 1个1、2个2、1个3、2个4、3个1 ，因此我们说122344111 的 p 型编码串为 1122132431 ；类似的道理，编码串 101 可以用来描述 1111111111 ；0000000000

洛谷 P3806 [模板] 点分治 1 题解

【模板】点分治 1 题目描述给定一棵有 n n n 个点的树，询问树上距离为 k k k 的点对是否存在。输入格式第一行两个数 n , m n,m n,m。第 2 2 2 到第 n n n 行，每行三个整数 u , v , w u, v, w u,v,w，代表树上存在一条连接 u u u 和 v v v 边权为 w w w 的路径。接下来 m m m 行，

洛谷 B3969 [GESP202403 五级] B-smooth 数题解

思路我们只要求出每个数的最大质因数，再一个个判断是否满足要求即可。如何找到每个数的最大质因数呢？其实，我们可以在埃氏筛法的基础上进行改进，从而达到算出最大质因数的目的。让我们先来了解一下埃氏筛法，知道的人可以跳过。埃氏筛法，首先定义一个 bool 型数组（初始全部赋值为 1 1 1，再后面我们用 f l a g flag flag 进行代替），如果 f l a g i flag_

洛谷 P1541 [NOIP2010 提高组] 乌龟棋

思路：暴力DP‘“ 其实在想到暴力dp之前，作者寻思着这个题目可能和”摆花“那道题差不多，就用那种思想想了一下，结果其实不是这样的。这里并不能开二维进行推进。由于我们在二维表示的时候，代表的含义就是在走了i个格子用了j个票子所积累到的最大积分。其实DP思路上看起来是没有什么错误的，但是呢，我这里忽略掉了：这里的票子是分种类的，也就是说，这里的票子并不是自由选的，我们必须保证这个票子正好用完，

【洛谷 B3637】最长上升子序列题解（动态规划+最长上升子序列）

最长上升子序列题目描述这是一个简单的动规板子题。给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。输入格式第一行，一个整数 n n n，表示序列长度。

洛谷 P1021 邮票面值设计

原题链接：[NOIP1999 提高组] 邮票面值设计 - 洛谷目录题目描述解题思路：代码实现：题后总结：题目描述给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N+K≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 MAX，使在 1 至 MAX 之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为 1 分

洛谷 B3968 [GESP202403 五级] 成绩排序题解

讲解由于一个学生包含语文、数学、英语三科的成绩，所以我们可以先定义一个结构体，在里面存储语文分数、数学分数、英语分数、总分、语文与数学的总分、语文与数学的最高分、排名和原始位置，结构体代码如下： struct score{int c,m,e/*语数英的成绩*/,total/*总分*/,cm/*语文与数学的总分*/,max_cm/*语文与数学的最高分*/,num/*初始位置*/,ranking

田忌赛马【洛谷P1650】

P1650 田忌赛马 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<iostream>#include <algorithm>#include<cstdio>#include <map>using namespace std;const int N=1e5+100;int n;map<int,int>a,b;//映射，速度->数量int

每日写题（洛谷第三章：循环结构 1.找最小值）

#include<bits/stdc++.h>using namespace std;int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++)cin>>a[i];int min=a[0];int temp;for(int i=0;i<n;i++){if(a[i]<min){temp=a[i];a[i]=min;min=temp;}}cout<