原题链接：https://www.luogu.com.cn/problem/P1982题意解读：特征值：第i个同学的特征值是1~i中最大子段和，分数：第i个同学分数是前1~i-1个同学的分数+特征值最大值，求最大分数。解题思路：第一步：先计算特征值f[i]，f[i]等于1~i中所有数的最大子段和，所以借助最大子段和的DP方法，每次计算以i

原题链接：https://www.luogu.com.cn/problem/P1981题意解读：中缀表达式求值，只有+，*，没有括号，保留后4位。解题思路：中缀表达式求值的典型应用，采用两个栈：符号栈、数字栈，对于没有括号的情况，只需要如下步骤：1、遍历表达式每一个字符2、如果遇到数字，则持续提取数字，保存整数到数字栈3、

原题链接：https://www.luogu.com.cn/record/160821231题意解读：统计1~n中x的个数。解题思路：枚举每个数，提取每一位，判断是否等于x。100分代码：#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)

P1969[NOIP2013提高组]积木大赛题目春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦，大厦可以看成由\(n\)块宽度为\(1\)的积木组成，第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前，没有任何积木（可以看成\(n\)块高度为

原题链接：https://www.luogu.com.cn/problem/P1983题意解读：由于“如果这趟车次停靠了火车站x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠”。因此，在始发站和终点站之间，能停靠的车站都是级别较高的，没有停靠的车站都是级别较低的，计算最少有多少个不同级别。解题思路：

B组都说看不懂……我也解释不清啊……只能写这么详细了ac自动机ac自动机上dp怎么才能判定一个母串是否包含几个模式串？我们可以想到ac自动机，考虑对模式串建ac自动机，如果我们跑到了一个标记为tail的节点，说明我们的母串包含了这一个模式串。所以我们设\(f[i][s][

显然只选峰或者谷，所以记录当前走势是向上还是向下，出现转折时答案加一即可。因为存在相同的元素，所以开头的走势要特判，把最前面连续相同的一段看成一个元素，因为不确定会转变成哪种走势。后面遇到相同则可以正常做，因为前面走势已经确定了，相当于自动忽略了相同的元素。

原题链接题解已经讲的足够好了，我想来补充一点我在思考过程中遇到的“小石子”（此处dalao可以跳过）1.逆序对和线性代数里的逆序数有点不一样，逆序数是指一段排列中所有逆序对的数量（蒟蒻当时卡在这里好久）2.每进行一次交换，最多能消除一个逆序对所以为了消除所有的逆序对，最少交换次

[NOIP2013普及组]计数问题题目描述试计算在区间到的所有整数中，数字（）共出现了多少次？例如，在到中，即在中，数字出现了次。输入格式个整数，之间用一个空格隔开。输出格式个整数，表示出现的次数。样例#1样例输入#1111样例输出#14提示对于的数据，，。思路求每个数字的

P1967[NOIP2013提高组]货车运输https://www.luogu.com.cn/problem/P1967首先有些边是没用的（比较小的边），比如两个点之间的两条（并行的）路，只有较大的会被走到，小的不会被走，因此可以直接去除小的边，即求最大生成树。接着做求任意两点经过的边的最小值就演变成求树上任意两点的最小树

洛谷P1969[NOIP2013提高组]积木大赛[NOIP2013提高组]积木大赛题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦，大厦可以看成由\(n\)块宽度为\(1\)的积木组成，第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前

P1967[NOIP2013提高组]货车运输因为可能成环，这样可能导致到达点的最小权值不一，所以用最小生成树的方法重新建图然后我是利用倍增的思想建立从i点开始，到上面点的距离ff和最小权值ww因为最小权值不好直接建立，所以不如最后统一建立最后就是寻找最近公共祖先的模板了一组hack

1.错误原因：想的太复杂正解：10^k轮，会使x号小伙伴变到(x+m*10^k)%n号，直接套用公式代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lln,m,k,x;llquickPow(lla,llb,llmod){ llans=1; while(b){ if(b&1)ans=((ans%mod)*(a%mod))%mod; a=((

7. 正解：可以画出递归树，画出后应该是这样子的 画出递归树，就可以得出答案时间复杂度为O(Fn) 15. 正解：2T(n/2)=O(logn)T(n)=2*T(n/2)+2*n=O(nlogn)三.2. 错误原因：蒙的正解：通过观察，可以找到递推关系式，f[n]=1/n*(n+f[1]+f[2]+...+f[n]),f[1]=0,f[2]=2,经过计算

「NOIP2013」货车运输前言这道题算是一个稍有思维难度的MST+LCA题目了。稍微卡了一会（0-88-88-88-100（打表）-100（打表）-100（正解）），开始是打了表过了，后面在DCZ的帮助下正解通过（下面注释提到的一个坑）。题目大意给出一张无向图\(G\)，有\(n\)个点和\(m\)个边\((x,y)=z\)，找到一

本文章主要是为了不想卷题的时候不是特别颓废而准备本文章是为了总结NOIP最近的题目（为了今年NOIP做准备），目前还没写完，尽量做的全面一些。2013积木大赛给定一个长度为\(n\)的序列\(h_i\)，初始有一个全为\(0\)的序列，每次操作可以任意选择\(L,R\)，使得\([L,R]\)这段区

题目链接题目题目描述A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入描述第一行有两个用一个空格隔开的整数n,m，表示A国

Link→很容易想到一个暴力做法，就是跑一遍Floyd，\(F_{i,j}\)表示\(i\)到\(j\)最大载重量，转移\(F_{i,j}=\max\{F_{i,j},\min\{F_{i,k},F_{k,j}\}\}\)。显然时间复杂度\(O(n^3)\)是过不了的。我们发现，因为是求两点路径中使得最小值最大，实际上有一些较小的路径是不会走

[NOIP2013普及组]表达式求值题目描述给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。输入格式一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“\(+\)”和乘法运算符“$\times$”，且没有括号，所有参与运算的数字均为\(0\)到\(2^{31}-1\)之

P1983[NOIP2013普及组]车站分级https://www.luogu.com.cn/problem/P1983 思路https://www.cnblogs.com/tomori/p/14331510.html   Codehttps://www.luo

题目链接：https://www.luogu.com.cn/problem/P1980术语以下的英文术语均可以翻译为数字。digit:一个数字字符，十进制就是0-9之间的一个字符；numeral:用来表示数字的

套路题了。根据和角公式\(\mathrm{\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\cos\beta,\cos(\alpha+\beta)=\cos\alpha\cos\beta-\si

题目链接题目题目描述一条单向的铁路线上，依次有编号为1,2,…,n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下

[NOIP2013提高组]货车运输题解本题解介绍一种最大生成树+并查集+启发式合并离线的做法。想法题目要多次求两点之间的最大瓶颈路长度，所以可以先参照最小瓶颈路的通

[NOIP2013普及组]小朋友的数字思路题中“特征值”是指前面最大的一段数字之和，即以该数结尾的序列的最大子段和，用\(DP\)解决。至于得分，可以从左往右扫一遍，扫的过程中维