洛谷专题

洛谷 P10584 [蓝桥杯 2024 国 A] 数学题（整除分块+杜教筛）

题目思路来源登录 - Luogu Spilopelia 题解参考了两篇洛谷题解，第一篇能得出这个式子，第二篇有比较严格的复杂度分析结合去年蓝桥杯洛谷P9238，基本就能得出这题的正确做法代码 #include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<map>#include<uno

洛谷P8502题解

[problem] \color{blue}{\texttt{[problem]}} [problem] [Solution] \color{blue}{\texttt{[Solution]}} [Solution] 这题最恶心的地方是卡空间。我们先考虑不卡空间时怎么做。直接并不好做，我们考虑正难则反，即利用容斥原理。答案应为从 a a a 没有任何限制经过 m m m 条

洛谷：P1085 [NOIP2004 普及组] 不高兴的津津

1. 题目链接 https://www.luogu.com.cn/problem/P1085 P1085 [NOIP2004 普及组] 不高兴的津津 2. 题目描述题目描述：津津每天要上课还要上辅导班，每天学习超过8小时就不开心，帮忙检查下津津的下周日程安排，然后告诉我她哪天不高兴输入：7行数据，每行2个小于10的非负整数，分别代表在学校的时间和辅导班的时间输出：哪天最不高兴，如果有

【洛谷P3366】【模板】最小生成树解题报告

洛谷P3366 -【模板】最小生成树题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。输入格式第一行包含两个整数 N , M N,M N,M，表示该图共有 N N N 个结点和 M M M 条无向边。接下来 M M M 行每行包含三个整数 X i , Y i , Z i X_i,Y_i,Z_i Xi,Yi,Zi，表示有一条长度为 Z

洛谷：P5714 【深基3.例7】肥胖问题

1. 题目链接 https://www.luogu.com.cn/problem/P5714 P5714 【深基3.例7】肥胖问题 2. 题目描述题目描述：BMI计算:m / (h * h)，m是体重(kg)，h是身高(m) 小于18.5：体重国轻，Underweight 小于等于18.5且小于24：正常，Normal 大于等于24：肥胖，不仅要输出BMI值，换行，输出Overweigh

洛谷 P1141 01迷宫 (dfs解决)

题目描述有一个仅由数字 0 与 1 组成的 n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。输入格式第一行为两个正整数 𝑛,𝑚。下面 𝑛 行，每行 𝑛 个字符，字符只可能是 0 或者

【洛谷P3374 P3368】树状数组

提示本文只记录模板，不做详细解释 P3374 树状数组1 原题链接 #include <iostream>#define lowbit(x) x&(-x)#define N 5*(int)1e5+1using namespace std;int n,m,num[N];long long tree[N];void add(int idx,int val){while(idx<=

【洛谷P2054洗牌】AC代码(扩展欧几里得+二分快速幂+二分龟速乘)

题目描述题目链接为了表彰小联为Samuel星球的探险所做出的贡献，小联被邀请参加Samuel星球近距离载人探险活动。由于Samuel星球相当遥远，科学家们要在飞船中度过相当长的一段时间，小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后，大家觉得单纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。对于扑克牌的一次洗牌是这样定义的，将一叠N（N为偶数

洛谷 P3379：最近公共祖先（LCA）← RMQ+欧拉序

【题目来源】https://www.luogu.com.cn/problem/P3379【题目描述】如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。【输入格式】第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来 N−1 行每行包含两个正整数 x,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。接下来 M 行每

洛谷：P1001 A+B Problem

1. 题目链接 https://www.luogu.com.cn/problem/P1001 A+B Problem 2. 题目描述输入两个整数a和b，输出它们的和。输入：两个整数输出：一个整数 3. 我提交的题解 /*https://www.luogu.com.cn/problem/P1001A+B Problem题目描述：输入两个整数a和b，输出它们的和。输入：两个整数

小玉买文具（洛谷-P1421）

题目描述班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是1元9角，而班主任给小玉的钱是a元b角，小玉想知道，她最多能买多少只签字笔呢。输入输出格式输入格式：输入的数据，在一行内，包括两个整数，依次表示a和b，a<=10000,b<=9。输出格式：输出一个整数，表示小玉最多能买多少只签字笔。输入输出样例输入样例#1： 10 3 输出样例#1： 5

小鱼的数字游戏（洛谷-P1427）

题目描述小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字（长度不一定，以0结束，最多不超过100个，数字不超过2^32-1），记住了然后反着念出来(表示结束的数字0就不要念出来了)。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。输入输出格式输入格式：一行内输入一串整数，以0结束，以空格间隔。输出格式：

排队接水（洛谷-P1223）

题目描述有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入输出格式输入格式：输入共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。输出格式：输出有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到

B进制星球（洛谷-P1604）

题目描述话说有一天，小Z乘坐宇宙飞船，飞到一个美丽的星球。因为历史的原因，科技在这个美丽的星球上并不很发达，星球上人们普遍采用B（2<=B<=36）进制计数。星球上的人们用美味的食物招待了小Z，作为回报，小Z希望送一个能够完成B进制加法的计算器给他们。现在小Z希望你可以帮助他，编写实现B进制加法的程序。输入输出格式输入格式：共3行第1行：一个十进制的整数,表示进制B。第2-3行：每行一

洛谷 AT_abc358_c [ABC358C] Popcorn 题解

题目翻译在 AtCoder 乐园里，有 N N N 个爆米花摊位，有 M M M 种不同口味的爆米花，第 i i i 种爆米花的编号为 i i i。高桥知道每个摊位售卖的爆米花有哪些，用 N N N 个长度为 M M M 的字符串表示 S S S，若 S i S_i Si 为： o：说明这个摊位出售第 i i i 种爆米花。x：说明这个摊位不出售第 i i i 种爆

幂次方（洛谷-P1010）

题目描述任何一个正整数都可以用 2 的幂次方表示。例如 137=2^7+2^3+2^0 同时约定方次用括号来表示，即 a^b 可表示为 a(b)。由此可知， 137 可表示为：2(7)+2(3)+2(0) 进一步：7=2^2+2+2^0(2^1用2表示)，并且 3=2+2^0 所以最后 137 可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0) 又如：1315=2^{10}

疯狂的采药（洛谷-P1616）

题目描述 LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最

采药（洛谷-P1048）

题目描述辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰

最小费用最大流（洛谷-P3381）

题目描述如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。输入输出格式输入格式：第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。

洛谷 CF1985B Maximum Multiple Sum 题解

题目翻译给定一个 n n n，寻找一个 x x x 使得： 2 ≤ x ≤ n 2\le x\le n 2≤x≤n。所有小于等于 n n n 的 x x x 的倍数的和最大。输出这个 x x x。本题每个样例有 t t t 组测试数据。思路对于这道题，可以枚举 x x x 的值，找到符合要求的 x x x。显然，对于每一个 x x x 直接暴力累加倍数

【洛谷】P1111：修复公路

闲来无事找个题目（做完后才想到写个博客，所以图片是后来拍的）：哇，是个并查集的题诶。怀揣着好奇心，我点进去看了看。题目传送门我随手打开csacademy，建了个图。怎样才能让任意两个村庄都存在至少一条修复完成的路呢？我想了想，惊讶地发现这道题十分简单。任意两节点都存在一条路，那就是树，要从图中扣树，图又是无向图，那不就是最小生成树嘛。所以，这道题就是个模板题。

【洛谷】P4263：投票统计

传送门嗯... 首先看一下这道题。投票统计题目描述为了总结过去一段时间的命题工作，王队长组织了“我最喜欢的题目”评选活动，并邀请各位选手给题目进行投票。具体来说，每道题目有一个正整数作为它的编号，一共有 n 名选手给它们进行投票，每位选手投且仅投给一道题，其中第 i 位选手所投票的题目编号为 ai。由于投票的选手众多，所以王队长请你来帮忙统计得票数。你需要找出收获选手投票最

洛谷题解 - P1036 [NOIP2002 普及组] 选数

目录题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示代码题目描述已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn，以及 1 1 1 个整数 k k k（ k < n k<n k<n）。从 n n n 个整数中任选 k k k 个整数相加，可分别得到一系列的和。例

洛谷题解 - P1192 台阶问题

目录题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示代码题目描述有 N N N 级台阶，你一开始在底部，每次可以向上迈 1 ∼ K 1\sim K 1∼K 级台阶，问到达第 N N N 级台阶有多少种不同方式。输入格式两个正整数 N , K N,K N,K。输出格式一个正整数 a n s ( m o d 100003 ) ans

洛谷P1305 新二叉树（树的基本遍历）

题目描述输入一串二叉树，输出其前序遍历。输入格式第一行为二叉树的节点数 𝑛。(1≤𝑛≤26) 后面 𝑛 行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。空节点用 * 表示输出格式二叉树的前序遍历。这道题就是树最基本的遍历代码如下： #include <bits/stdc++.h>using namespa

洛谷P3269 [JLOI2016] 字符串覆盖

题目描述字符串A有N个子串B1,B2,...,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上（子串之间可以重叠）这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。输入格式第一行包含一个正整数T，表示数据组数。保证T<=10。接下来依次描述T组数据，每组数据中：第一行包含一个由小写字母组成的字符串，表示母串A。第二行包含一个整数N，表