10.31 普及

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了(表示感觉原来的方式没毛病).

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

Day 2

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

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

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

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

第三题,枚举最大和最小……(不懂得细讲)

第四题,多重背包问题。

赛前集训2

第一题 三角形    枚举三角形的顶点,再枚举边长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])。

10.31心得

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

题目描述

小红学姐手头上的电话号码太多了,于是她决定要做一个电话簿。她所在地区的电话号码都是四位数字并且第一位不会是0或者8。
小红学姐稍微有一点点强迫症,她的电话簿前两页一定要写一点有趣的笑话,不然她绝对不想打开这个无聊的电话簿。所以,电话号码会从第三页开始记录。为了格式的美观(以及满足他的强迫症),每页最多可以记录k个号码并且一定要是同一个数字开头的。同一页中的号码需要按字典序从小到大排序。
现在,小红学姐嘿嘿一笑,问你:他的电话簿有多少页?

题目解析

水题,略。

题目描述

题目解析

乘法分配律完,还用说什么?

题目描述

 一个公司有n个编号为1到n的员工。每个员工或者没有直接主管要么恰有一个编号不同的直接主管。如果一个员工A满足以下至少一个条件,那么他被称为另一个员工B的上司:
1.员工A是员工B的直接主管
2.员工B的直接主管是员工C且员工A是员工C的上司。
这家公司没有管理上的环。即,不存在一个员工是他/她直接主管的上司。
今天这家公司将安排一场聚会。这需要将所有n个员工分成几组:每个员工必须恰属于一个组。而且,在任何一个单独的组中,必不存在两个员工A和B满足A是B的上司。

题目解析

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

题目描述

zjc是一只喜欢探险的猴子。有一次,她在森林里迷路了(不仅仅是去探险,还要去找香蕉和桃子),森林里的每个地方都有一个编号1~n。幸好她所在的森林有路标,这些路标会告诉她从她所在的地方可以到达哪里,以及到达另一个地方的时间。zjc所在的地方为s地,他想去k地玩,这个森林的出口是t地。但是zjc找了一天的香蕉和桃子,很累了,更重要的是她也很饿……她必须在m时间内到达k地再出森林。所有的路标的起点终点值均包含上文的s,k和t。

题目解析

首尾呼应,现在开始。这题最优解是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];
            }
        }    
    }

 

【2017NOIP】复赛集训 DAY-2

BY 苏弘烨

写blog前必吐槽

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


1. 小红的电话簿

 

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

题目描述

小红学姐手头上的电话号码太多了,于是她决定要做一个电话簿。她所在地区的电话号码都是四位数字并且第一位不会是0或者8。
小红学姐稍微有一点点强迫症,她的电话簿前两页一定要写一点有趣的笑话,不然她绝对不想打开这个无聊的电话簿。所以,电话号码会从第三页开始记录。为了格式的美观(以及满足他的强迫症),每页最多可以记录k个号码并且一定要是同一个数字开头的。同一页中的号码需要按字典序从小到大排序。
现在,小红学姐嘿嘿一笑,问你:他的电话簿有多少页? 

输入

  第一行包含一个自然数K(0 < K < 255),表示每页最多可以有多少号码。
第二行包含一个自然数N(0 < N < 8000),表示号码的数量。
接下来N行,每行包含一个含有4个数码的数字(就是手机号码啦),以某种规则排序,并且不会重复。

输出

  输出一行一个自然数,表示有多少页。

临场思路

首先,题目有个不得不说的槽点:

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


好的,继续。

这题就是纯模拟。

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

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

1372. 神奇数

 

Warning!Chronosphere ready!

1372. 神奇数

题目描述

输入

 一个正整数n。

输出

n的最小神奇数。

临场思路

根据乘法分配律,可得:

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,变量居然还要初始化才不会挂,毁我青春


3. 聚会

~~~下界传送门~~~

题目描述

 一个公司有n个编号为1到n的员工。每个员工或者没有直接主管要么恰有一个编号不同的直接主管。如果一个员工A满足以下至少一个条件,那么他被称为另一个员工B的上司:
1.员工A是员工B的直接主管
2.员工B的直接主管是员工C且员工A是员工C的上司。
这家公司没有管理上的环。即,不存在一个员工是他/她直接主管的上司。
今天这家公司将安排一场聚会。这需要将所有n个员工分成几组:每个员工必须恰属于一个组。而且,在任何一个单独的组中,必不存在两个员工A和B满足A是B的上司。

输入

输入文件party.in第一行包含整数n(1≤n≤2000)代表员工数。
接下来n行包含整数pi(1≤pi≤n或pi=-1)。每一个pi表示第i个员工的直接主管。如果pi是-1,则表示第i个员工没有一位直接主管。
数据保证没有员工是他自己的直接主管(pi≠i)。同样,不存在管理上的环。

输出

 输出文件party.out包含一个单独的整数代表这个聚会中组成的最少组数。

临场思路

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

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

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

正解

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

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

如图所示:

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


1374. 森林探险

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

题目描述

zjc是一只喜欢探险的猴子。有一次,她在森林里迷路了(不仅仅是去探险,还要去找香蕉和桃子),森林里的每个地方都有一个编号1~n。幸好她所在的森林有路标,这些路标会告诉她从她所在的地方可以到达哪里,以及到达另一个地方的时间。zjc所在的地方为s地,他想去k地玩,这个森林的出口是t地。但是zjc找了一天的香蕉和桃子,很累了,更重要的是她也很饿……她必须在m时间内到达k地再出森林。所有的路标的起点终点值均包含上文的s,k和t。

输入

第一行是n,s,t,k,m,其中n≤1000;
第二行是bian,代表边的数目,bian≤200000;
接下来bian行,每行3个数,分别为ui,vi,ri,表示从ui地到vi地需要ri个单位时间。(ri≤maxlongint)

输出

如果zjc可以在规定时间内走出森林,则第一行输出‘Yes’,否则输出‘No’;第二行输出zjc走出森林的最少时间。

临场思路

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

这猴子真TM无聊。

因为n≤1000,m≤200000。

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

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

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

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


感悟:

今天题好水啊。

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

集训Day2

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

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

 

我包容六月清泉结冰

包容暮老的生命

包容世界的迟疑

没包容你

Y.W.    东海集训

2017.10.31题解与心得

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]}。

Day2

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


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

(题解什么的没意义(我还没改完。。。。。))

2017.10.31

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

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

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

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

Noip2017 – 赛前集训Day2

写在前面

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

Cys啊,连读入优化都打错!

总之就是好菜好菜

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

                                                          ????

正文

Task1. 小红的电话薄

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

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

Task2. 神奇数

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

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

Task3. 聚会

考察算法:深搜建树
思路:

  • 第一眼以为要是一个裸的并查集。后来仔细分析了一下发现如果打并查集在处理一些关系上有很多坑点..
  • 于是就考虑到是不是能直接根据关系构建一棵搜索树(或者亲切地说关系树?),那么很容易可以证明他们的组合数就是这个树的深度.

Task4. 森林探险

考察算法:最短路/Bfs
思路:

  • 估计全场我最有把握的一题
  • 裸的最短路。
  • 考虑到N比较大,那么Floyd的N^3的复杂度显然难以解决问题
  • 那么这时候我们就可以使用SPFA或者Dij
  • 鉴于我Dij打得很烂于是我打了SPFA
  • 唯一坑点就是去重边(然鹅这不是显而易见?)
  • 然后考完Csz说还可以打一个Bfs

关于这题引发的几个思考:

  1. 看一下我不会的邻接表
  2. 熟悉一下Dij
  3. 学Dij+堆的优化