web analytics

20170923 NOIP模拟赛 解析报告

总的来说.出错的都是小问题.细节还是没有处理到位.

Problem 2 : pair
无序字母对

问题描述
给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入数据
第一行输入一个正整数n。
以下n行每行两个字母,表示这两个字母需要相邻。

输出数据
输出满足要求的字符串。
如果没有满足要求的字符串,请输出“No Solution”。
如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案

样例输入
4
aZ
tZ
Xt
aX

样例输出
XaZtX

时间限制
各测试点1秒

内存限制
你的程序将被分配32MB的运行空间

数据规模
不同的无序字母对个数有限,n的规模可以通过计算得到。

分析:

此题就是欧拉回路.
考试的时候没有看出来是失误.

其实就是判断每个点的度的奇偶性.
如果奇数点超过2个。那这个图肯定一笔走不完。

如果奇数点为2个。那选最小的那个为起点。

之后就是DFS贪小的遍历整个图。

Problem 3 : transfer
数字转换

问题描述
如果一个数x的约数和(不包括它本身,下同)比它本身小,那么x可以变成它的约数和;如果对于某个y>x且y的约数和为x,那么x也可以变成y。例如,4可以变为3,1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行,求不断进行数字变换且没有重复数字出现的最多变换步数。

输入数据
输入一个正整数n。

输出数据
输出最少需要花费的时间。

样例输入
7

样例输出
3

样例说明
一种方案为:4→3→1→7。

时间限制
各测试点1秒

内存限制
你的程序将被分配32MB的运行空间

数据范围
n<=50 000。

分析:

 

考试的时候想到树的直径了。但是由于算约数和的时候用O(n^2)的算法就最后几个点就GG了。

 

约数和定理:

 

一个数为n我们可以将这个数分解成n= \sum_{i=1}^{k}{p_i ^{a^i} }

其中p为质数a为正整数.

 

根据乘法原理.

 

这个数的约数和就为n=\prod_{i=1}^{k}{ \sum_{j=0}^{a_i}{p_i ^j}}

 

之后先用欧拉筛O(n)预处理一下。就好啦

One Trackback

  1. By fornhamhall on 五月 28, 2018 at 8:34 上午

    fornhamhall

    air max flyknit vapormax,mens salomon speed cross 3 yellow,nike mercurial superfly ea sports limited edition,nike zoom pegasus 33 grey black,air jordan pe,adidas zx vulc rodrigo

Post a Comment

You must be logged in to post a comment.