[题解]P1083[NOIP2012提高组]借教室解法\(1\)：线段树-\(O((n+m)\logn)\)比较直观的一种做法，但是可能需要卡一下输入（这里没卡也过了，但要注意输入是\(10^6\)级的，为了保险一定要加）。#include<bits/stdc++.h>#definelc(x<<1)#definerc((x<<1)|1)#defineintlonglong

[NOIP2012提高组]开车旅行题目描述小\(\text{A}\)和小\(\text{B}\)决定利用假期外出旅行，他们将想去的城市从$1$到\(n\)编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市\(i\)的海拔高度为\(h_i\)，城市\(i\)和城市\(j\)之间的距

原题链接：https://www.luogu.com.cn/problem/P1078题意解读：1~n个国家，每个国家有自己的文化，不同国家文化可以相同，要从起点遍历到终点，已经学习过的文化不能重复学习，已经学习过的文化被某个文化歧视的国家也不能遍历，且不同国家之间有边，边有不同的距离，计算从起点到终点的最短路径。解

原题链接：https://www.luogu.com.cn/problem/P1075题意解读：求n的两个素因子中较大的一个。解题思路：数论的简单题，关键在于要知道一定有一个素因子不超过sqrt(n)，而另一个素因子必然大于或等于sqrt(n)，这样才能减少枚举时间。100分代码：#include<bits/stdc++.h>usingnamespaces

P1077[NOIP2012普及组]摆花题目描述小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过a[i]盆，摆花时同一种花放在一起，且不同种类的花需按标号的

嗨嗨嗨！又是我想写这道题，我们就需要掌握：拓展欧几里得顾名思义，它就是欧几里得算法（人话：辗转相除法）的proMax版本别告诉我你不会辗转相除法拓展欧几里得的作用是求对于方程\[a*x+b*y=gcd（a，b）\]解出x，y的值。让我们一步步分析！贴个辗转相除板子先：voidojld(inta,intb){ i

原题链接：https://www.luogu.com.cn/problem/P1077题意解读：n种花选m个的选法，每种花数量为ai。解题思路：设dp[i][j]表示前i种花选j个的选法对于第i种花，可以选0,1,2...min(ai,j)个则有递推式：dp[i][j]=∑dp[i-1][j-k]，k取0,1,2...min(ai,j)初始化dp[0][0]=1100分代码：#incl

题目：链接：https://www.luogu.com.cn/problem/P1077总的来说就是和上题差不多？记dp[i][j]为前i种花塞进了j的背包的种类，那么状态转移方程：就是：dp[i][j]=dp[i-1][j]+dp[i-1]j-k贴代码：#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<ss

P1075[NOIP2012普及组]质因数分解[NOIP2012普及组]质因数分解题目描述已知正整数\(n\)是两个不同的质数的乘积，试求出两者中较大的那个质数。输入格式输入一个正整数\(n\)。输出格式输出一个正整数\(p\)，即较大的那个质数。样例#1样例输入#121样例输出#1

题目链接：本题由于是对某一段区间的数统一进行删除某个数的操作，很容易想到差分。对于能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。在本题中，由于随着订单数量的增加，每天可用教室的数量一定单调下降。也即，如果前一份订单都不满足，那么之后的所

原题链接：https://www.luogu.com.cn/problem/P1080题意解读：通过不同的排队方式，让获得最多奖赏的大臣金额尽可能的少。此题如果没有思路，用全排列枚举可以“骗”分，更好的做法直觉上是某种贪心策略，另外基于数据规模考虑，要拿满分，需要上高精度。下面就由浅入深一步一步的解决。解题思

原题链接扩展欧几里得算法的应用，关于原理性的讲解这里就略去了，这边给出学习链接即模板。intexgcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returnx;}intd=exgcd(b,a%b,x,y);x=y;y=d-a/b*y;returnx;}文

原题链接一道二分+差分的题目，作为学习前缀和和差分的引入题目非常合适。首先检验其单调性，如果一个申请人订单不用修改，那么其前面的申请人也不用修改，符合单调性。接着，这道题暴力的思路就很简单，但是看到运算量（n，m高达1e6），暴力的时间复杂度为O（n*m）显然超时。那么就是运用差分思想

[NOIP2012提高组]借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来天的借教室

求关于\(x\)的同余方程\(ax\equiv1(\bmodb)\)的最小正整数解。根据取模的性质，这个方程相当于\(ax+by=1\)，其中\(y\)为负数，形式类似于扩展欧几里得的经典形式\(ax+by=\gcd(a,b)\)。方程\(ax+by=m\)有整数解的必要条件是\(\gcd(a,b)|m\)，此处\(m=1\)，所以有\(\gcd(a,

题意：H国有$n$个城市，这\(n\)个城市用$n-1$条双向道路相互连通构成一棵树，$1$号城市是首都，也是树中的根节点。H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境

首先军队可以原地不动，时间越多越容易合法，先套上二分。在不回到根的情况下，军队深度肯定越小越好。所以军队能往上移就移，如果能回到根就暂时在根对应的儿子那里驻扎。这个过程用树上倍增优化。做完这一步后，我们找出需要军队驻扎的根的儿子（向下不经过军队就能到达叶子），现在就是要让

题目有点长，一步一步来。预处理出每座城市两人分别会选择的下一座城市用set即可实现。倍增优化DP令\(f_{i,j}\)表示从城市\(j\)出发，行驶\(2^i\)天会到达的城市。令\(ga_{i,j}\)表示从城市\(j\)出发，行驶\(2^i\)天，小A行驶的路程。\(gb_{i,j}\)同理。答案枚

题目描述小AA和小BB决定利用假期外出旅行，他们将想去的城市从11到nn编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市ii的海拔高度为hihi​，城市ii和城市jj之间的距离di,jdi,j​恰好是这两个城市海拔高度之差的绝对值，即di,j=∣h

因为n是两个质数的乘积，所以直接暴力枚举，只要能被整除，直接输出因为是要求大的那个，所以从小到大枚举，输出商即可点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongintmain(){ LLn; cin>>n; for(inti=2;1LL*i*i<=n;i++){ if

算法一根据唯一分解定理，小于\(n\)的最大的能整除\(n\)的整数一定就是答案，可以暴力枚举。时间复杂度\(O(n)\)，实际得分\(60\)。算法二发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。而较小的那个质数一定小于等于\(\sqrtn\)，我们枚举它即可。时间复

[NOIP2012普及组]摆花[NOIP2012普及组]摆花题意有\(n\)个数，每种可以选\(0\lex_i\lea_i\)个，问有多少种方法可以使得\(\sum_{i=1}^nx_i=m\)。Solution1.深搜\(dfs\)显然可以先暴力深搜。#include"bits/stdc++.h"usingnamespacestd;constintmaxn=

转载自这里问题转化题目问的是满足\(ax\bmodb=1\)的最小正整数\(x\)。（a,b是正整数）但是不能暴力枚举\(x\)，会超时。把问题转化一下。观察\(ax\bmodb=1\)，它的实质是\(ax+by=1\)：这里\(y\)是我们新引入的某个整数，并且似乎是个负数才对。这样表示是为了用扩展欧几里

视频链接： LuoguP1080[NOIP2012提高组]国王游戏#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;structnode{inta,b;booloperator<(node&t){returna*b<t.a*t.b;}}

一.3. 错误原因：忘记了解析：Intel是全球最大的CPU厂商，AMD是世界上首个研发出7纳米CPU的厂商 6.错误原因：忘记了解析：ENIAC是世界上首台计算机，属于第一代计算机，即电子管计算机 10.错误原因：选项理解错误解析：A由蝙蝠，发明雷达是正确的，B因特网的发明与蜘蛛网无关，只是形