1371.小红的电话簿

数据全部整除1000，对应的数组num【1~9】++，然后%k，如果有余数就total（页数）+=num【i】/k+1，否则total(页数)+=num【i】/k,这里要注意一下，total（初始值）要定义为2；

1372.神奇数

定义一个长长的各个位数都为一的long long(假设为step，反正要比n的取值范围大)，然后n%step，如果不为0，即不能整除，step/=10；如果为0，即能整除，跳出循环，直接输出n%step（一定记得要开long long）;

1373.聚会

本来是不会的，后来画了一个图，发现其实就是求最长那一条上下属关系链，最后用递归的方式解出来了；即枚举每个点，用递归分别求出以他们各自为起点到达最高上司所经过的点，再在这之中取最大的输出；

1374.森林探险

分别求s到k和k到t的耗费时间最少的路径，然后相加和时限相比<=就输出‘Yes’否则输出‘No’，最后输出所需的最少时间（注意不管‘Yes’或‘No’都要输出）；我用的是今天早上学的SPFA，记录某一条边的起点.终点和耗费时间是用三个数组，再进行两遍的SPFA分别算出s到k和k到t的耗费时间最少的路径，这里要注意在两次计算中间要进行一定步骤的数据处理，例如记录到达每个点最后更新的最少耗费时间要初始为最大；错了一个点，没有重边问题，到现在也不知道为什么错，难受；后来换了一种记录某一条边的起点.终点和耗费时间的方式，用邻接矩阵（即f[i][j]，对于一条边，i表示起点，j表示终点，f[i][j]表示耗费时间），其它没变，然后出现了重边问题，然后处理了一下就AK了（表示感觉原来的方式没毛病）.

不过今天考了这么高分还是很开心的!~(^_^)~!

今天的题目和昨天完全是两个级别的！！

今天第一题打暴力没处理好，崩了，剩余时间全给了第二题，幸亏想到了。

第一题三角形：模拟+优化，一些边长大等于2k的三角形，实际上可以拆分成若干个边长为k~2k−1的三角形。

第二题，我用DP+滚动数组，但好像有别的转移方程可以不用滚动数组。

第三题，枚举最大和最小……（不懂得细讲）

第四题，多重背包问题。

第一题 三角形    枚举三角形的顶点，再枚举边长1~2K，用前缀和来求解，当边长为2K时，可以看出这个三角形可以分成4个边长K的三角形，而且小三角形的最大值>=大三角形……

第二题 小 Y 包汤圆    dp，滚动数组f[i][j][k]表示到第 i 个位置，前一个汤圆在i-j，再前一个汤圆在i-k。f[i][j][k] = f[i - 1][j - 1][k-1]。f[i][0][j] = f[i - 1][j-1][k] + a[i]……

第三题 邮差    排序海拔，枚举最大最小用区间[i,j],用bfs判断是否合法，合法i++，不合法j++……

第四题 背包    顺序多重背包f[i][j]，逆序多重背包f2[i][j],对于每个询问ans=max(f1[i-1][j] + f2[i+1][m-j])。

我穿过高山与大海，也穿过人山人海，当我蓦然回首，却发现——DJ比SPFA还好用！

题目描述

题目解析

水题，略。

题目描述

题目解析

乘法分配律完，还用说什么？

题目描述

题目解析

题目讲得天马行空，就是一个员工的上司是他的上司，上司的上司也是他的上司。深搜一下就能过了。

题目描述

题目解析

首尾呼应，现在开始。这题最优解是DJ，其实DJ不管是复杂度，还是空间都比SPFA好，但我受了早上讲座的蛊惑（气得我屁滚尿流），花两个小时打后者，结果啊不要。现在郑重地附上DJ算法关键部分——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(i=1;i<=n-1;i++)

    {

        //找到离1号顶点最近的顶点

        min=inf;

        for(j=1;j<=n;j++)

        {

            if(book[j]==0 && dis[j]<min)

            {

                min=dis[j];

                u=j;

            }

        }

        book[u]=1;

        for(v=1;v<=n;v++)

        {

            if(e[u][v]<inf)

            {

                if(dis[v]>dis[u]+e[u][v]) 

                    dis[v]=dis[u]+e[u][v];

            }

        }    

    }

BY 苏弘烨

写blog前必吐槽

今天第2题莫名其妙的挂了一个点，经本机测试，发现无误。由cys大佬处得知，OJ的变量都要初始化才能用，不然会莫名其妙的挂。真TM个破OJ！

1. 小红的电话簿

~~~超时空传送仪已就绪~~~

题目描述

临场思路

首先，题目有个不得不说的槽点：

现在，小红学姐嘿嘿一笑，问你:他的电话簿有多少页？

好的，继续。

这题就是纯模拟。

因为每页最多可以记录k个号码并且一定要是同一个数字开头的。所以我们可以用book数组标记每个读入的号码的开头。然后遍历book数组，对于每个数字开头出现的次数都令sum加上出现次数除以k，有余数的情况加1。

什么垃圾题目，一个不男不女的，还嘿嘿一笑，看着老有毒的。

1372. 神奇数

Warning！Chronosphere ready！

1372. 神奇数

临场思路

根据乘法分配律，可得：

n=a*10^0+a*10^1+a*10^2+...+a*10^k

=a*(10^0+10^1+10^2+...+10^k)

=a*(111...111)

那我们就可以枚举111...111，通过判断n能不能整除111...111得出a。

垃圾OJ，变量居然还要初始化才不会挂，毁我青春

临场思路

每一个员工顶多只有一个直接上司，这是一个树的结构。

考虑并查集，代码实现不好，只拿了10分。

原先考虑将所有人的上司关系组成树，再两两枚举。但是时间复杂度太高，实现又很乱。所以没有完成。

正解

这题其实就是个没有路径压缩的并查集。

遍历一遍到每个人的最高上司，求出所在的树的深度。分组数即是每棵树的最大深度。

如图所示：

在不同的树中，同深度的所有节点都可以为一组，所以总组数就为所有树的最大深度。

1374. 森林探险

通往天堂的......传送门？不存在的。让这玩意送你去吧！

临场思路

很明显，zjc 走出森林的最少时间即从 s 到 k 再到 t 的最短路。

这猴子真TM无聊。

因为n≤1000，m≤200000。

所以Floyd可能超时，可以考虑Dijkstra或SPFA。

当然SPFA是O(NM)，Dijkstra是O（N^2）。相比之下SPFA时间复杂度比较高，还是有点悬（容易卡常），还是用Dijkstra好点。

PS:临场无聊把两种都打了一遍。

注意：这题可能有重边，所以读入时一定要注意，读入路径最短的边即可。

感悟:

今天题好水啊。

我们一定要认真仔细，考虑所有情况。

T1

求一个大三角形的子三角形的平均值的最大值，要求边长大于等于k。枚举顶点，不断扩展长度，每行用前缀和优化即可。
可以发现长度不会多于 2*k。当长度为 2*k 时，肯定可以分成 4 个长度为 k 的三角形，根据最大值一定大于等于平均值，所以肯定存在一个子三角形平均值更优。

T2

动态规划，f[i][j]表示第i位取且上一个取的位置为i-j的最小代价。分类讨论i<m 和 i>=m的情况即可。

也可用三维表示。

f[i][j][k]表示到第 i 个位置，前一个汤圆在 i – j，再前一个汤圆在 i-k。
f[i][j][k] = f[i - 1][j - 1][k-1]。f[i][0][j] = f[i - 1][j-1][k] + a[i]。

T3

枚举最大最小值，然后用bfs判断经过路径是否能够满足最大最小值在区间内，可以则l++，否则r++。

T4

预处理出背包，考虑用 f[i][j]表示 0-i 玩偶用 j 的价钱（不需全用）获得的最大价值。g[i][j]表示
i-n 玩偶用 j 价钱（不需全用）获得的最大价值。两遍背包即可。
去掉第 i 个玩偶，相当于 1-i-1 玩偶和 i+1-n 玩偶。ans=max(f[i-1][j] + g[i+1][m-j])。

传送门：https://2017.noi.team/oj/#contest/problems/39

题目需要多想，要有更强的发散性思维。

1、三角形

70/60分：枚举三角形的每个顶点，再不断扩大边长，用前缀和优化。

100分优化：通过观察可发现，边长为2x的大三角形可分为4个边长为x的小三角形，大三角形的平均数一定小于等于4个小三角形中的最大平均数。因此枚举边长时只需枚举到2k-1。

2、小Y包汤圆

动态规划。f[i][j][k]表示前i个汤圆中，前两个有馅汤圆的位置分别在i-j和i-k的最小代价，f[i][j][k]=f[i-1][j-1][k-1]，f[i][0][j]=max{f[i-1][j-1][k]}+a[i]。由于空间过大，应用滚动数组。

3、邮差

用h[i]表示矩阵中第i小的海拔高度，用区间[l,r]表示最小值为h[l]，最大值为h[r]，宽搜判断是否满足，若满足则l++，否则r++。

4、背包

两遍背包，f[i][j]表示前i件物品花费j元的最大价值，g[i][j]表示i-n件物品花费j元的最大价值，则答案为min{f[d-1][k]+g[d+1][e-k]}。

想问问，今天是不是和纪中不小心拿错题了，纪中的前两题那么水，这四题却这么难，还是四题。。。。。

其实，嗯。。。。今天比昨天更气。。。 第三题自信一个宽搜加标记。。。然后第三题，完全错。。。然后第四题，和正解完全一眼的思路，几乎一模一样，所有点我都想到了，但是。。为什么3E的复杂度不会炸。真鸡儿气气，真的一堆奇奇gaygay的错误。该正视自己的高度了，谦虚学习。

（题解什么的没意义（我还没改完。。。。。））

T1 小红的电话簿
纯模拟没什么好说的吧。。

T2 神奇数
就是提取一个因数a然后打表1111111好多个1。再从后往前枚举可以整除就输出停止运行。

T3 聚会
递归搜索。找最长的那串。然后输出。就是答案。因为不可以有上下司所以找最长的就是答案。

T4 森林探险
spfa算法。要用俩次。就是判断重边需要特判一下其他都一样了。

写在前面

普及组好难啊，我都不会啊

Cys好菜啊，连读入优化都打错!

总之就是好菜好菜啊

所以今天奶死自己明天就要爆炸了啊.

                                                          ？？？？

正文

Task1. 小红的电话薄

考察算法：模拟
思路： 用桶的思想计数一下每一个电话号码的开头，由于每页能出现的号码数有限，所以需要做一下除法统计一下出现次数，如果有余数+1即可

然后吐槽一下题目给了一堆没啥用的条件是来迷惑我这种不自信的老年人选手的吗???然后这个小红学姐到底是她还是他??

Task2. 神奇数

考察算法：数学方法?
思路： 听说这题是什么乘法分配律??可能是我数学比较差吧...看不出来什么goushi分配律..但是看到数据10^12然后又只读入一个数

• 不用看了，呵呵肯定是玄学
• 然后我就打了几个表，发现把一个数/最小神奇数=1 11 111 1111……
• 于是很高兴地以为就我一个人发现这个规律，然后很开心的按照规律打了出来。
• 考完发现他们都用乘法分配律打出来??
• 最坑爹的是开了LL然后读入优化忘记改了
• 上一次历史好像是在长乐？？也是因为LL然后Wa了20没AK?