洛谷

洛谷P1006 传纸条

双线程dp，一来一回可以看作两个人从同一个起点走到同一个终点 #include <iostream> #include <algorithm> #define f(_x,_y) for(_x1;_x<_y;_x) using namespace std; int map[55][55]{0},dp[55][55][55][55]{0},m,n; int main(void){int i,j,x1,y1…

【万题详解】P1048 [NOIP2005 普及组] 采药

题目描述链接——题目在这里！！！ 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草…

【C++算法】二分算法、二分模板详解，四道例题带详细注释

文章目录 [toc]1）整数二分2）解二分题步骤AcWing 789.数的范围洛谷 P1873.EKO/砍树洛谷 P1678.烦恼的高考志愿 2）浮点二分AcWing 790. 数的三次方根 1）整数二分有单调性的题目一定可以二分，但是用二分做的题目不一定拥…

【数论】莫比乌斯反演巩固1

文章目录前言洛谷P3455洛谷P1829洛谷P4449 前言这里需要对莫反有一些基础。不会的可以点这里洛谷P3455 题意： 给定 a , b , d a,b,d a,b,d 求 ∑ x 1 a ∑ y 1 b [ gcd ⁡ ( x , y ) d ] \sum_{x1}^a\sum_{y1}^b[\gcd(x,y)d] ∑x1a∑y1b[gcd(x,y)d…

洛谷P3373 [ 模板] 线段树（乘法和加法）

andy的小伙伴acer（WA_哈_哈）已经写好【模板】线段树1啦，但是仅仅支持区间加法和查询，这对于oier们当然是远远不够的，所以本蒟蒻在此奉上线段树的区间加法，乘法的实现，以及对乘法标记的下放&…

洛谷P1005 矩阵取数游戏

也是从这里开始更会写高精度运算了。贪心算法和dp很简单，只是加上了高精度而已。 #include <iostream> #include <algorithm> #include <cstring> #define mem(_x) memset(_x,0,sizeof(_x)) #define fs(_x,_y) for(int _x1;i<_y;_x) #defin…

洛谷P1004 方格取数

双线程dp，前两个维数是第一个人的坐标，后两个维数是第二个人的坐标。 #include <iostream> #include <algorithm> #define f(_x) for(int _x1;_x<n;_x) using namespace std; int dp[10][10][10][10],num[10][10],x,y,number,n; int ma…

洛谷P1003 铺地毯

简单搜索。因为后放的地毯肯定在上面，所以只需要倒着搜索能“接住”点的地毯就行了。如果最后都没能“接住”就输出-1 #include <iostream> using namespace std; struct point{int a,b,g,k; }pt[100005]; int main(){int i,n,x,y,flag1;cin>>n;for(i0…

洛谷P1002 过河卒

貌似是我做的第一道dp题，hh岁月如水，很简单就不说啥了 #include <cstdio> long long step[25][25]; bool map[25][25]; int main(){int b1,b2,m1,m2;scanf("%d%d%d%d",&b1,&b2,&m1,&m2);map[m1][m2]map[m1-1][m22]map[…

洛谷P1000 超级玛丽

想想那时候我还真是无聊呢，好吧现在也很无聊w #include<cstdio> using namespace std; int main() {printf(" ********\n");printf(" ************\n");printf(" ####....#.\n");…

P1042 [NOIP2003 普及组] 乒乓球 Java版最简单题解！

为什么说最简单，因为本人就是一个算法小白，只学过一点数据结构，打算备战蓝桥杯的，网上说备战蓝桥杯就去刷洛谷，早有听闻洛谷很难，今天一看算是真的被打醒了，对于小白是真的太难了。(;༎ຶД༎ຶ…

【万题详解】DFS搜索专题合集（中）

课前C小程序（关机，休眠，注销程序） 有的时候我们需要让电脑在一段时间工作而不能关机，但是工作完成之后不关机会造成用电浪费，那么使用自动关机命令，就不用担心电脑一直开着会浪费电啦。夜里看电…

【洛谷】P1873 [COCI2011-2012#5] EKO / 砍树

原题链接：https://www.luogu.com.cn/problem/P1873 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析整体思路：二分答案设置一个变量highest来记录最高的树的高度，sum记录切下的木头的长度。令左边界l0&#xff0c…

【洛谷】P3853 路标设置

原题链接：https://www.luogu.com.cn/problem/P3853 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析整体思路：二分答案由题意知，公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标&…

蓝桥杯备战数学基础位运算：洛谷【高低位运算】

题目：# 高低位交换## 题目描述给出一个小于 2^{32} 的非负整数。这个数可以用一个 32 位的二进制数表示（不足 $32$ 位用 $0$ 补足）。我们称这个二进制数的前 16 位为“高位”，后 16 位为“低位”。将它的高低位交换，我…

洛谷P1036 [NOIP2002 普及组] 选数【回溯搜索+素数】

P1036 [NOIP2002 普及组] 选数前言题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题目分析注意事项代码后话王婆卖瓜题目来源前言期中考逆天大作业，都快没时间写了。不过还是得抽空写一下题目，今天还是做搜索的题单，一题…

【洛谷】P1102 A-B 数对

原题链接：https://www.luogu.com.cn/problem/P1102 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析将A-BC转化成ABC，然后遍历数组，让数组的每个元素加C，再查找原数组中是否存在对应数组元素C之后的值。…

P3370 【模板】字符串哈希

#include <bits/stdc.h> using namespace std; set<string> se; int main() {int n;cin >> n;for(int i 1;i < n;i){string s;cin >> s;se.insert(s);}cout << se.size() << endl;return 0; }

【LGR-172-Div.4】洛谷入门赛 #19（A—H,c++详解！）

文章目录【LGR-172-Div.4】洛谷入门赛 #19A.分饼干 I题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示样例解释 1样例解释 2数据范围与约定思路: 代码 B.分饼干 II题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样…

洛谷——P1093 [NOIP2007 普及组] 奖学金

文章目录[NOIP2007 普及组] 奖学金题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2测试点信息[NOIP2007 普及组] 奖学金题目描述某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 555 名学生发奖学金。期末…

好题分享--小A的皇室战争卡组

题目描述小 A 很喜欢玩皇室战争这款游戏。皇室战争的卡牌种类共有 3 种，分别为部队、建筑和法术。一个卡组会携带 88 张卡牌，一个合理的卡组会包含 0∼1 张建筑牌、 1∼3 张法术牌，部队牌则没有限制。每张卡牌都有自己独立的等级 ai 和种…

【洛谷】P1163 银行贷款

原题链接：https://www.luogu.com.cn/problem/P1163 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析这题需要注意的是利率按月累计这句话，也就是相当于“利滚利”。我们定义sum变量表示贷款原值，money表示每月支付…

（洛谷 R6765172）八数码问题 DBFS+hash 乱搞

非常经典的一道搜索练手题，各种方法花式求解（虽然目前只搞定了 DBFShash,但是可以说说想法XD)题目描述：在33的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格…

洛谷 P1436 棋盘分割

如图：思路： 这是一个很明显的二维dp题，每一次分割的可以衍生出2种情况：左（上）右（下）2个新矩形所以最优解一定存在于两种新情况中，继续进行递归求解即可； dp[…

排序---P1781 宇宙总统

思路： 当我们要对这些超大数进行比较排序时，如果我们用int或long基本数据类型时，会超出能承载的范围，因此我们选择用引用数据类型：BigDecimal或BigInteger。区别在于基本数据类型直接比较大小，而是调用这…

【洛谷】P2678 跳石头

原题链接：https://www.luogu.com.cn/problem/P2678 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析二分答案。（使用二分需要满足两个条件。一个是有界，一个是单调。这题的题面：使得选手们在比赛过程中…

【洛谷P3374】树状数组模板

题目描述如题，已知一个数列，你需要进行下面两种操作： 1.将某一个数加上x 2.求出某区间每一个数的和输入格式第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中…

洛谷题解 | AT_arc069_b [ABC055D] Menagerie

目录题面翻译题目描述题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示制約Sample Explanation 1Sample Explanation 2 题目思路解法一解法二 AC 代码解法一解法二题面翻译题目描述 Snuke&#…

洛谷 2511 [HAOI2008]木棍分割

题意：如题思路：首先二分枚举最大的长度。 dp[i][j]表示前一个木棍，切了j刀符合条件的方案数。 dp[i][j]dp[k][j-1] (sum[i]-sum[k]<ans) 这个转移可以用前缀和维护。状态总共O(n*m)，转移O（1） #inclu…

洛谷 P2678 [NOIP2015 提高组] 跳石头（二分答案）

前提知识： 二分法往下其实有一些小分支，最常见的是二分查找，然后就是二分答案，浮点数二分等等主要谈谈二分查找和二分答案的具体区别，我们不能光报个菜名随口就来，一问具体也说不出来个所以然。前提&a…

B3668 [语言月赛202210] 应急食品

题目背景派蒙是不是应急食品？不同的旅行者有不同的答案。题目描述派蒙是不是应急食品，是每一个旅行者必须完成的选择题。选项 A 为派蒙是应急食品； 选项 B 为派蒙不是应急食品。旅行者一定是正确的，现在告诉你某个旅行…

【洛谷】P2440 木材加工

原题链接：https://www.luogu.com.cn/problem/P2440 1. 题目描述 2. 思路分析整体思路：二分答案设置一个变量longest来记录最长木头的长度，sum记录切成的小段数量之和。令左边界l0，右边界llongest。写一个bool类型的check…

【洛谷】P2004 领地选择

原题链接：https://www.luogu.com.cn/problem/P2004 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析整体思路：二维前缀和 （模板在这https://blog.csdn.net/m0_62531913/article/details/132712831?spm1001.2014.30…

洛谷题单【入门3】循环结构

1.P5718 【深基4.例2】找最小值 #include <stdio.h>int main() {int min,n;scanf("%d",&n);int a[n];for(int i0;i<n;i){scanf("%d",&a[i]);}mina[0];for(int i0;i<n;i){if(a[i]<min)mina[i];}printf("%d",min);return…

【洛谷】P1678 烦恼的高考志愿

原题链接：https://www.luogu.com.cn/problem/P1678 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析将每个学校的分数线用sort()升序排序，再二分查找每个学校的分数线，通过二分找到每个同学估分附近的分数线。最后…

【洛谷】 P1240 诸侯安置（递推）

洛谷P1240 诸侯安置点击此处去OJ 问题描述很久以前，有一个强大的帝国，它的国土成正方形状（需旋转45来看），图1所示为n3时的情况。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，因此国王准备给他们每…

洛谷 P1873 砍树（二分简单）

【二分答案】是分治的一种，这类问题很经典，接下来几篇文章会关于二分答案相关的文章，希望同学们可以完成10道以上的【二分答案】相关问题，以此来加深对【二分答案】这类问题的个人理解。原公众号链接：分治第二讲&…