做男人不容易系列：是男人就过8题--loutiancheng题课件

一、前言性格是人类行为和心理活动的总和，它影响着一个人的思维方式、情感表达、人际关系等方面。

男性作为社会的重要组成部分，其性格特点也备受关注。

本篇高智商测试题旨在通过一系列心理测试题，帮助您了解男性性格的各个方面，从而更好地认识自己和他人。

二、测试题1. 你在日常生活中，以下哪种情况更符合你的行为？A. 喜欢独立思考，不太依赖他人B. 乐于与人沟通，善于倾听他人意见C. 倾向于内敛，不太表露自己的情感2. 当你遇到困难时，以下哪种应对方式更符合你的性格？A. 主动寻求解决方案，不轻易放弃B. 虽然感到困扰，但会尽量保持乐观C. 容易感到沮丧，倾向于逃避问题3. 在团队协作中，以下哪种角色更符合你的性格？A. 担任领导，带领团队完成任务B. 扮演协调者，促进团队成员间的沟通C. 专注于个人职责，不太关心团队整体4. 当你面对失败时，以下哪种态度更符合你的性格？A. 认真总结经验教训，不断改进B. 虽然失落，但会尽快调整心态，继续前行C. 容易陷入自我怀疑，对未来的信心不足5. 你认为以下哪种特质在男性性格中最为重要？B. 坚韧C. 温柔6. 你在以下哪种场合下更容易感到焦虑？A. 公众场合发言B. 与陌生人交往C. 独自一人时7. 你认为以下哪种行为更能体现男性魅力？A. 谦逊有礼B. 挺身而出，保护他人C. 独立自主，不依赖他人8. 在以下情境中，你更倾向于哪种行为？A. 帮助他人解决问题B. 专注于自己的事情，不过问他人C. 在他人需要帮助时，选择旁观9. 你认为以下哪种特质在男性性格中最为关键？A. 责任感B. 胆识C. 情感丰富10. 在以下情境中，你更倾向于哪种决策方式？A. 根据自身经验和直觉做出决策B. 经过充分调研，权衡利弊后做出决策C. 依赖他人的意见和决策三、性格解析1. 选择A的男性：这类男性性格独立，善于独立思考，具有较强的自我意识。

他们在面对问题时，往往能够迅速找到解决方案，不易受他人影响。

《男人不易做》第二期剧本CAST路放：阿春何仲亭：苏榭【裔美声社】路恺：乘风归去【水岸聆音】何方：轩轩【裔美声社】琅寰宇：水易冬华严肃：Forsaken【昆仑班】车行师傅：李逍遥【声声Melody】何妈妈：苏清颜【优声由色】何爸爸：大象龙套：买车女：Monkey【含笑半步颠】买车男：清影轩阳【蓝颜倾音】同学：考拉符号含义：【方括号】为人物感情【红色字体】后期标注底纹为内心戏第一幕：宿舍【欢快音乐，砰的一声门被踢开】方方【撅嘴娇嗔】：“爸爸，你怎么一回来就偷菜。

”严肃：“哈哈哈哈！”【狂笑不止】“我严汉三又回来啦！”何方【安慰自己】：“不怕不怕……是严叔叔……”严肃【吊儿郎当】：“哟！方方也在，来送你老子上学？”何仲亭【吼】：“严肃，别教坏我家方方！打今儿起，方方常住315！”严肃【表情严肃】：“家庭政变？”何仲亭【伪神情悲惨】：“父母离异，母亲卖房出国，单亲爸爸独自养大三岁孩童！这是为哪般啊为哪般！”严肃【伪同情】：“嗯！今年的十大悲情人物就是你了。

”何仲亭：“我是十大杰出人物！”【强调】“不对，重点是后半句！我含辛茹苦养大三岁孩童！”严肃【吐槽】：“那得等方方长大了再说，或者……等你作古了，让方方写回忆录顺带提及提及你？【路恺回来，开门进屋】路恺：“哟，严肃，你可回来了，这几天干嘛呢？”严肃【无奈】：还能干嘛，泡图书馆呗。

路恺【同情】：“我说兄弟，你至于这么刻苦么？”严肃：“呸！不刻苦我能考上么？”路恺【顺口】：“那就不考呗。

”严肃【神情夸张】：“公务员！铁饭碗啊！！等我有了铁饭碗，我就买上百八十个瓷碗，用一个cei（卒瓦，合在一起的，输入法打不出= =）一个！我看谁还敢让我洗碗！”路恺【内心】：“哎，好好的孩子，怎么大一被人骗去洗了一个月的盘子就洗出心理阴影了呢？【惋惜】【混响】【欢快BGM淡出】【一天过去了，音乐，早晨，闹铃】何仲亭：“方方起床了，昨晚没睡好？”何方【扁嘴抱怨】“这个路叔叔坏！吵得方方昨晚都不能睡觉觉。

性心理成熟测试题及答案导语：性心理成熟是指一个人在性知识、性认知、性体验和性行为等方面逐渐达到一个成熟的状态。

本文将提供一系列性心理成熟测试题目，并附上相应的答案解析，帮助读者了解自身性心理成熟程度，并提供一些建议。

题目一：性知识测试1. 人类的性别特征分为男性和女性，两者主要通过什么生理特征区分？答案：男性主要通过生殖器官外部特征如阴茎，女性主要通过生殖器官外部特征如阴道和乳房。

2. 性别认同是指一个人对自己的性别偏好和认同感，以下哪个选项表达了性别认同的含义？a. 个人对性别特征的自我观察和比较b. 个人对性别特征的喜好和接受程度c. 个人对社会认可的性别角色的适应d. 个人对他人性别特征的评价和比较答案：b. 个人对性别特征的喜好和接受程度题目二：性体验测试1. 以下哪种陈述最贴近您的性体验？a. 性行为是一种自然而美妙的体验，让人感到愉悦和满足b. 性行为是一种需要克制和压抑的欲望，很难得到满足c. 性行为是一种可有可无的生理需求，对我来说并不重要d. 我对性行为感到困惑和抵触，不愿意主动参与答案：a. 性行为是一种自然而美妙的体验，让人感到愉悦和满足题目三：性信念测试1. 以下哪个陈述更符合您对性的信念？a. 性行为只应该在婚姻或者长期稳定的伴侣关系中进行b. 性行为无需受到特定关系的限制，只要双方关系良好即可c. 性行为不一定需要伴侣，可以通过自慰等方式满足自己的需要d. 性行为是一种危险和不健康的行为，应该尽量避免答案：b. 性行为无需受到特定关系的限制，只要双方关系良好即可题目四：性行为态度测试1. 对于性行为中的安全措施（如避孕和防止性病传播）以下哪种陈述最能反映您的态度？a. 性行为中使用安全措施是保护双方健康的责任b. 性行为中使用安全措施是不必要的，我相信对方c. 性行为中避孕和防病是女方的责任，男方不需要承担d. 性行为中使用安全措施是破坏情感和信任的表现答案：a. 性行为中使用安全措施是保护双方健康的责任答案解析：题目一：性知识测试1. 通过生殖器官外部特征如阴茎和阴道来区分男性和女性。

•男生女生生理特征•男生女生的心理发展•男生女生的社会行为•男生女生的教育问题•男生女生的自我保护目录010203男女生生理特征的差异男性骨骼较粗壮，肌肉较发达，女性骨骼较轻盈，肌肉较柔和。

男性有睾丸，女性无。

男性生殖系统为射精，女性生殖系统为排卵。

男性以雄性激素为主，女性以雌性激素为主。

男生的心理发展认知能力男生的社交能力在青春期开始逐渐发展，包括合作、交流和领导能力等方面。

社交能力情感能力社交能力女生的社交能力在青春期开始逐渐发展，包括建立友谊、表达情感和合作能力等方面。

认知能力女生的认知能力在青春期开始逐渐发展，包括语言能力、音乐能力和艺术能力等方面。

情感能力女生的情感能力在青春期开始逐渐发展，包括情感理解、情感表达和情感管理等方面。

女生的心理发展男女生心理发展的差异社交能力的差异情感能力的差异认知能力的差异男生的社会行为03照顾他人女生的社会行为01情感表达02社交技巧1男女生社会行为的差异23男生和女生的沟通方式存在差异。

男生通常更注重解决问题，而女生更注重情感交流和情感理解。

沟通方式男生和女生的决策方式也存在差异。

男生通常更注重逻辑和分析，而女生更注重情感和直觉。

决策方式男生和女生的领导风格也存在差异。

男生通常更注重权力和控制，而女生更注重合作和协调。

领导风格教育中性别歧视的表现性别刻板印象认为男性和女性有着固定的性格、兴趣和能力，并以此作为教育评价的标准。

性别偏见对男性和女性的能力和表现抱有偏见和歧视，认为某些职业或领域更适合某一性别。

性别隔离在教育系统中，将男性和女性分隔开，限制了他们的学习机会和职业发展。

破坏社会公平降低教育质量阻碍个人发展教育中性别歧视的危害消除教育中性别歧视的措施教育工作者应该具备性别平等意识，认识到性别不应该成为评价学生能力和表现的标准。

树立性别平等意识推广多元文化教育建立公平的评价机制加强法律保障教育应该注重培养学生的多元文化意识和跨性别交流的能力，消除性别刻板印象。

做男人不容易系列SolutionsAmber2 years ago, I trained in Fudan University in Shanghai and attended this contest hold by Lou Tiancheng. The title of this contest is “hard to be a man”and the subtitle is “If you are a man, pass all 8 problems”. I got only 1 problem accepted at that time. Actually, no one can be “a man” except LTC himself at that time. Now there is still only3 guys who finished all problems except the problemsetter LTC. They are timgreen, geworm, Savior. How I admire them!Well, I decide to be a man before my 18th birthday. For my foreign friends, I decide to write the English version in the description and the solution with my poor English.Problem A (POJ 1737): Connected Graph[Description]Find the number of connected labeled undirected graphs with n nodes.找出有标号的n 个点的无向连通图的个数.[Solution]If we do not considered whether the graph is connected, there exists 2^C(n, 2) graphs in total. Let G(n) = 2^C(n, 2). If we know the number of unconnected ones, we will know the answer indirectly. Let F(n) is the answer. Consider the connected component C that contains node 1 and with the size k, namely |C| = k. Because C is unconnected, k < n. So there exists C(n – 1, k - 1) ways to choose another k - 1 nodes to make up connected component C. So there exists C(n – 1, k – 1) * F(k) different connected component C. Any graphs G(n-k) for remaining nodes are okay. So the answer is:111()()()()1n k n F n G n F k G n k k -=-⎛⎫=-- ⎪-⎝⎭∑It takes O(n^2) to calculate this formula.利用补集转化思想, 若不考虑连通性,则有n 个点的任意图有G(n)=2^C(n, 2)个. 只要求出不连通图的个数就知道答案F(n). 考虑含结点1的连通块C, |C| = k. 由于不连通,有k < n 成立. 则有C(n - 1, k – 1)种方法选择另k-1个结点与结点1组成C. 所以有C(n - 1, k – 1) * F(k)种方法组成C. 剩下的结点组成一个任意图即可. 答案为:111()()()()1n k n F n G n F k G n k k -=-⎛⎫=-- ⎪-⎝⎭∑ 复杂度为O(n^2).[Reference][1]The information from the On-Line Encyclopedia of Integer Sequences: A001187 Number of connected labeled graphs with n nodes.[2]杨俊, <<PKU 1737 解题报告>>, IOI2005国家集训队报告Problem B (POJ 1738): An old Stone Game[Description]There are n(n<=50000) piles of stones in a line. Each time we can merge two adjoining piles to a new pile until there is only one pile. Minimize the summation of the number of stones in the new pile after merging.在开始有n(n<=50000)堆的石头堆排成一行.每次可以合并相邻的两个石头堆成为一个新堆,可以得到这个新堆的石头数的分数.直到剩下一堆.找出一种合并计划,使分数最小,求这个最小分数.[Solution]This problem is equivalent to construct an Optimal Alphabetic Binary Search Tree (OABST).As the same As Huffman tree, minimize the summation of the weighted paths lengths of the external nodes(leaves). The difference is that the external nodes in OABST must be in order (alphabetic), namely merge the only adjoining piles each time. It can be solved in O(n^2) by dynamic programming after optimizing by the quadrilateral inequation. But it is not fast enough for this problem. The Hu-Tucker algorithm with the complexity O(nlogn) will be introduced in the following. This algorithm has 3 phases. Because this problem does not need to output the merging method, just to implement the Phase 1 is okay.Phase 1, Combination:The goal of this phase is to build an optimal binary tree in which the depths of the external nodes are the same as the final OABST.The work sequence is a sequence which consists of the internal or external nodes.The initial work sequence of nodes consists of all the external nodes in order....During each iteration of this phase a new working sequence is produced by combining two nodes wi and wj in the previous working sequence into one internal node wi+wj which replaces the leftmost node wi of the two and removing the rightmost one wj from the current sequence.We call the pair of the nodes wi, wj which is combined in each iteration the Local Minimum Compatible Pairs (LMCP). In each iteration, LMCP is unique. It satisfies the following 4 rules: Rule(1): In the current working sequence no external nodes occur between wi and wj.Rule(2): The combined weight w = wi + wj is minimum.Rule(3): If in case of tie, the subscript i of the leftmost nodes wi needs minimized.Rule(4): If still in case of tie, the subscript j of the rightmost nodes wj needs minimized.We use the rectangle to denote an external node and the circle to denote an internal node in the following.For example, n = 5, w = (5, 2, 2, 3, 6). Notice that in Step (2), LMCP (5, 3) spans the internal node (2+2).(1)(3)(2)(5)(4)The implementing of this phase is the most complex and the most important also. We can find that the order of the continuous internal nodes does not matter . Namely the internal nodes between the two adjoining external nodes are similar to be executed the greedy algorithm of Huffman tree in part. In other words, external nodes divide the work sequence into some segments, the internal nodes between the two adjoining external nodes builds a set of the internal nodes (use the dashedcircle to denote).............Because the external node and the set of the internal nodes occurs alternately, we use a block (use the big rectangle to denote) to contain the external node and the set of the internal nodes in the right. We use two-directed links to link them up....List the case of the occurring of the LMCPLet B be the current block.Case 1: The LMCP is the external node in B and the minimum internal node in B.After combining the LMCP, put the new node into the set of internal nodes in A and unite the set of internal nodes in B into A's.Case 2: The LMCP is the external node in B and the external node in C.After combining the LMCP, put the new node into the set of internal nodes in A and unite the set of internal nodes in B and C into A's.Case 3: The LMCP is the minimum and second minimum internal node in B.After combining the LMCP, put the new node into the set of internal nodes in B.Case 4: The LMCP is the minimum internal node in B and the external node in C.After combining the LMCP, put the new node into the set of internal nodes in B and unite the set of internal nodes in C into B's.The set of internal nodes needs the operation of finding the minimum and second minimum element and uniting. The normal mergable heap such as Leftist Tree and Pair Heap and Fibonacci Heap are okay.In each iteration, it is needed to find the LMCP. Because the block can be merged, there exists the large number of the inserting and deleting operation. So we use a deletable priority queue to maintain the pairs of the nodes. The relation of the pairs of the nodes is that the weight summation of the pairs as the first key, the block ID as the second key and the number of the case as the third key.So the maintaining of any case can be done in O(logn).The total time of this phase is O(nlogn).Phase 2, Level Assignment:The goal of this phase is to get the depth of all the external nodes in the optimal tree which is constructed in Phase 1. In Phase 1, record the children information of each node (both internal and external nodes). Travel the tree by recursion can get the depths.The total time of this phase is O(n).Phase 3, Recombination:The internal nodes in Phase 1 and Phase 2 is not used in this phase. This phase builds an OABST from the initial sequence of external nodes and their depths calculated in Phase 2.We arrange the external nodes and their depths to the work sequence....During each iteration of this phase, the pair of adjacent nodes which are at the same maximum depth d are combined to produce a node at depth d – 1 and replace the leftmost one of the two and removing the rightmost one. Exactly, the pair (wi, wj) satisfies:Rule(1): The nodes wi and wj must be adjoining in the work sequence.Rule(2): The depths di and dj must be maximized among all the remaining nodes.Rule(3): If in case of tie, the subscript i of the node wi must be minimized.According to the rules above, the depths in the pair (wi, wj) must be the same. Actually, only the depths produced by Phase 1, 2 can be executed the Phase 3 correctly. Not any depths assignment can be done.Use one queue and one stack to implement this algorithm:1. Put the whole work sequence to the queue in order. The stack is empty.2. If the 2 elements at the top of stack have equal depths d, then pop the two, push the new nodes at depth d – 1 produced by combining the two, and turn Step 2; else turn Step3.3. If the queue is non-empty, pop the head of the queue and push it into the stack; else finish the algorithm.The total time of this phase is O(n).“石子归并”问题等价于构造一棵Optimal Alphabetic Binary Search Tree (OABST). 和Huffman树最优性要求一样, 都是最小化外部结点(叶子)到根的带权路径总长. 区别是OABST的外部结点要求有序. 即每次合并要求石子是相邻的. 可以用四边形优化后的动态规划在O(n^2)内解决, 但对于本题来说是不够快的. 下面介绍O(nlogn)的Hu-Tucker算法, 该算法分为三个阶段, 由于本题不要求输出路径, 就是说执行阶段1即可.阶段1, 组合:先不考虑有序性, 构造一棵最优树, 使得所有叶子的深度和最终所求的OABST 的叶子的深度一样且最优性一样.定义工作序列是一个可以包含内部或外部结点的序列.开始时, 把所有外部结点按顺序放在工作序列内....在每次的迭代中,选出两个结点wi, wj 合并为一个内部结点w=wi+wj, 来替换结点wi, 从工作序列中删去原来的wj, 形成一个新序列.称每次的迭代被组合的点对(wi, wj), 为Local Minimum Compatible Pairs (LMCP). 每次迭代的选择的LMCP 是唯一的, 它满足如下4条规则:规则(1): 在工作序列中, 结点wi 到结点wj 之间没有外部结点(最重要的规则);规则(2): 它们的权和w=wi+wj 要最小;规则(3): 在满足(1)(2)后,下标i 要最小;规则(4): 在满足(1)(2)(3)后, 下标j 要最小.以后统一用方框表示外部结点, 用圆圈表示内部结点.下面举例, n = 5, w = (5, 2, 2, 3, 6). 注意: 在第(2)步时, LMCP(5, 3)跨越了内部结点(2+2).(1)(3)(2)(5)(4)本阶段的实现最为复杂, 也最为重要, 下面介绍实现. 观察算法, 发现连续的内部结点之间的顺序没有意义. 即两个相邻外部结点间的内部结点, 相当于做局部的Huffman 树的贪心. 可以看成, 外部结点将整个工作序列划分为若干的段, 两个相邻外部结点间的内部结点, 组成一个内部结点集合(用虚圆圈表示内部结点集合).............由于外部结点与内部结点集合交替出现, 可以用一个块结构(用外框表示)把外部结点与其右方的内部结点集合包含进来. 再将这些块结构用双向链表串起来....下面讨论, LMCP 可能出现的情况:设图中的块结构B 为当前块结构.情况(1): 在当前块结构中, 外部结点与最小内部结点.合并LMCP 后, 放入A 的内部结点集合, 同时将B 的内部结点集合合并到A 中.情况(2): 在当前块结构中的外部结点, 与右边块结构中的外部结点.合并LMCP 后,放入A 的内部结点集合, 同时将B, C 的内部结点集合合并到A 中.情况(3): 在当前块结构的内部结点集合中, 最小与次小的内部结点.合并LMCP 后,放入B 的内部结点集合.情况(4): 在当前块结构中的最小内部结点, 与右边块结构中的外部结点.合并LMCP 后,放入B 的内部结点集合, 同时将C 的内部结点集合合并到B 中.内部结点集合需要支持找最小和次小元素与合并操作的数据结构来维护. 常见的可并优先队列: 左偏树Leftist Tree, 配对堆Pair Heap, Fibonacci Heap 均可胜任.每次要找一个全局最小的点对LMCP, 则需要用一个总的优先队列来维护这些点对. 由于块结构的合并,会造成大量合法的点对的改变, 这要求总的优先队列支持插入删除操作. 在点对优先级上, 点对之间的比较关系为: 以点对权值和为第1关键字, 以当前结构的编号作为第2关键字, 最后以情况的编号做为第3关键字.这样每种情况的维护都可以在O(logn)的时间内解决.整个阶段用时O(nlogn)阶段2, 深度的确定:遍历求出执行第1阶段后的所有外部结点的在最优树中的深度. 实现时, 记录下阶段1中每个结点(外部结点和内部结点都有)的儿子,递规遍历一遍, 即可求得.整个阶段用时O(n)阶段3, 重新组合: 抛弃阶段1和阶段2的内部结点, 重新构造树, 得到OABST.经过阶段1和阶段2, 可得到一个有深度标号的工作序列....不断地选出两个最大相同深度d 的相邻结点wi, wj 合并成一个深度d-1的结点,并替换wi 的位置. 严格地说, 选择的点对满足:规则(1): wi, wj 在工作序列中要相邻;规则(2): di, dj 在所有剩下结点中是最大的;规则(3): 在满足(1)(2)后,下标i 要最小.以上选择的结点, 深度必相同即di = dj. 实际上, 通过阶段1,2产生的深度标号, 才能正确的执行阶段3, 不是任意一种深度标号都可以.实现上, 使用一个队列和一个栈, 按如下算法执行即可.1. 将工作序列按顺序存入队列. 栈清空.2. 若2个栈顶元素有同样的深度标号d, 将它们出栈, 合并成一个深度为d-1的内部结点, 入栈, 转2; 否则, 转3.3. 若队列非空, 将队列头入栈, 转2; 否则, 结束.整个阶段用时O(n)[Experiment]在Discuss里有一个Knuth的源代码, 不用任何高级数据结构. 我随机生成了100个极限数据, Knuth 运行34.60s, 我运行27.94s. 但在POJ上显示Knuth用时0.250s,我用时2.062s. 相差甚远. 怀疑POJ数据太弱.[Reference][1]frkstyc, <<石子归并、OABST和Hu-Tucker算法>>, frkstyc's blog,/user2/frkstyc/archives/2006/1164187.shtml[2]Sashka T. Davis, <<Hu-Tucker Algorithm for Building Optimal Alphabetic Binary Search Trees>>, /~std3246/thesis/thesis.html[3]Donald E. Knuth, <<The Art of Computer Programming>>, Volume 3, Section 6.2.2[Thanks]This problem jammed me for years. When I got accepted, how happy I am!Gelin Zhou(cmdButtons) from Changjun Middle School, who introduced the algorithm to me in QQ. That's my first time to know the detail of this O(nlogn) algorithm.frkstyc, tN from PKU, who helped me for searching some helpful code and thesis.Problem C (POJ 1739): Tony's Tour[Description]Given an n * m gird that has some blocked cells. Find how many paths visit each unblocked cell exactly once from the left low cell to the right low cell in that map.有个n行,m列的网格,有的格子有障碍物,其他的则可以行走.问有多少条从左下角到右下角的路满足:路经过了所有的可以行走的格子恰好一次.[Solution]#0654321Because the answer is the large number (e.g. n = m = 8, answer = 8934996), we have to use dynamic programming to solve this problem.[Reference]Rujia Liu(SRbGa), <<算法艺术与信息学竞赛>>, p140-142, p184-186Problem D (POJ 1740): A New Stone Game[Description]Given n piles of stones (n<=10), two players play in turn. Each time a player can choose a pile, and removed at least one stone from this pile and can move any number of stones from this pile to any other piles (can move to multiple piles). The one who can not operate loses. Who will win?[Solution]It's easy to find the balanced state is that all piles can divided into pairs, which two piles in one pair have the same stone number. If one player do some operation in one pile A, on the next turn the other player can do the same operation in the pile that is corresponding to A, namely A and B is in one pair. In other words, the second player can always imitate the thing the first player did in the last step. Because the game ends in limited step, the balanced state is a lose state. The following show how to use only one step to convert any unbalanced state to a balanced state.Suppose no two piles have the same stone, because they are already balanced. Sort all piles. If the number of piles is odd number, then use the highest pile to fill up the lower pile in the pair right to make the same height with the higher one in the pair left for each pair. The stone for filling in highest pile is disjoint, so it is enough for filling and removing one stone at least.(Figure Left) If the number of piles is even number, then use highest pile to fill up the lower pile in each pair like it is in odd number's case. At last, remove stones in the highest pile to reach the height of the lowest pile and make the lowest pile and the highest pile a pair.(Figure Right)[Thanks]Discussion in Fudan University after this contestProblem E (POJ 1741): Tree[Description]Given a weighted tree with n nodes (n<=10000). Find the number of pair (u, v) that the distance between u and v is not more than k.给出一个有n个节点的树, 一个整数k. 定义dist(u, v)为节点u, v间的距离. 求这棵树中有多少节点对(u, v)满足dist(u, v)<=k.[Solution]Divide and Conquer.Each iteration, we should choose an edge (u, v) and divide the tree into two parts disjoined by the edge. Due to avoid from degenerating, that partition edge should be chosen to divide two parts as equally as possible. Then we should merge two parts and count the valid pairs between them. It can be implemented by two sorted list that denotes the distances between u and the posterities of u and the distances between u and the posterities of v respectively. And like merge sort, use two scan line l, r in two list and maintain the property d(u, l) + d(v, r) <= k. [Thanks]Yuqian Li(Spaceflyer), from Zhejiang Province, who gave me codes for referenceI discussed with Yangmu, from Fuzhou No.3 Middle School and Chenxue, from Yali Middle School.Problem F (POJ 1742): Coins[Description]Given n kinds of coins whose value is Wi and whose number is Ci. Find how many k (1<=k<=m) can be reached by combining coins.有面值为Ai的硬币Ci个,有n种硬币.问价值在1到m的整数范围内, 有多少个价值能通过现有硬币的组合达到.[Solution]It is a classical knapsack problem. The algorithm is as following.For each i in CoinsFor each j in ValuesIf F[i - 1, j] is true, M[i, j] = Ci. Else M[i, j] = -1For each jIf M[i, j + Ai] = -1 and M[i, j] > 0F[i, j + Ai] = trueM[i, j + Ai] = M[i, j] – 1It runs in O(nm).Problem G (POJ 1743): Musical Theme[Description]Given the integer sequence A with length n (n <= 20000). Find the longest consecutive subsequence B in A so that the length of B is not less than 5 at least, there exists the same length consecutive subsequence C in A, the subsequence B and C is non-overlapping, and {Ci –Bi} is a constant sequence.给出长度为n(1<=n<=20000)的数列A.在这个数列中找出一个最长的至少含有5个数的子数列B, 满足在A中还存在一个同样长度子数列C, 子数列B与子数列C没有交叠部分, 且{Ci - Bi}为常数数列.[Solution]Because {Ci – Bi} should a constant sequence, let S[i] = A[i] –A[i - 1]. Then the problem is equivalent to find the non-overlapping longest repeated sequence in S.Calculate the sorted Suffix Array (SA) of the sequence S by doubling algorithm within O(nlogn) time. And then get the Height array. Here Height[i] denotes the longest common prefix (LCP) of SA[i - 1] and SA[i].If suppose the length of the longest repeated sequence is not more than the limit L and there exists the solution, then for any limit L'<L, there must exist the solution. It denotes the continuity of the solutions. So use Binary Search to search for the answer L.There exists the theorem LCP(SA[i], SA[j]) = RMQ(Height[i+1..j]). So if there exists k that Height[k] < L, then LCP(SA[i], SA[j]) < L for all i, j that i < k < j. Namely, the two suffixes whose common length is L at least must not span the valley k whose Height is less than L. So we can get many consecutive segments in SA array after removing all valley k that Height[k] < L. If in the certain consecutive segment there exists i, j that SA[i] + L < SA[j], then there exists two non-overlapping subsequences with the common prefix with length L at least. For implementing, just record the minimum and the maximum of SA in each consecutive segment.因为{Ci - Bi}为常数列, 所以令S[i] = A[i] – A[i-1]. 问题就转化为在序列S中, 找最长的不相交重复子串.用倍增算法在O(nlogn)时间内, 计算将序列S的所有后缀排序后的后缀数组SA. 之后, 求出高度数组Height. 这里Height[i]表示SA[i - 1]与SA[i]的最长公共前缀(LCP).若在假设重复子串的长度最多为L的限制下有解, 则对于任意一个比L小的限制L'<L, 也一定有解. 这就说明存在解的连续性, 这样就可以用二分查找答案长度L.给出一个关于LCP的定理LCP(SA[i], SA[j]) = RMQ(Height[i+1..j]). 由此, 若存在k, 满足Height[k] < L, 则对于所有i, j 满足i < k < j, 有LCP(SA[i], SA[j]) < L. 即公共长度至少为L的两个后缀, 不会跨过一个小于L的Height低谷k, 所以我们可以得到一些由这些低谷划分开的连续的段.在某段内, 若存在i, j 满足SA[i]+L<SA[j], 则存在一个长度至少为L的2个相同不交迭子串. 实现时只要记录在每段内, 最大和最小的SA值即可.[Reference][1]许智磊, <<后缀数组>>, IOI2004国家集训队论文Problem H (POJ 1744): Elevator Stopping Plan[Description]There is only one elevator in the building. The elevator costs 4s to go up a floor. If the elevator stops on some floor except the first and the last floor, it takes 10s. It takes person 20s to go up or down a floor. Given Fi (1<=i<=n) that is the number of the floor the i-th person needs to reach. Make a plan for reducing the last time that all persons get the floors they want. (n<=30000).有一栋楼, 里面只有一架电梯. 电梯上一层需4s,电梯在一层停下需等10s(1层和最后一层的等待不计时),人走上或走下一层需20s.给出Fi(1<=i<=n)层有人要到达, 求一个安排计划,使最后到达自己目的地的人的用时最短. (n<=30000)[Solution]Use Binary Search to search for the answer L. And try to stop the elevator as high as possible greedily each time. It’s like to set the service stations.[Thanks]Linxi Xie(198808xc), from Fuzhou No.1 Middle SchoolDiscussion in Fudan University after this contest。

男生女生习题（含答案)一、单选题1．班级大扫除时，班主任让男生提水拖地、清理垃圾、擦洗灯具，女生擦玻璃、清理装饰品。

这种做法的合理性在于①男生比女生更优秀，可以承担重要的工作②男女体能有别，男生更适宜干体力型工作③男女生各有优势，扬长避短，发挥所长④男女技巧有别，女生更适宜干脑力型工作A．①②B．③④C．②③D．①④【答案】C【解析】【详解】本题考查男生女生的相关知识理解。

对材料进行深入分析，从而做出正确选择。

分析题干信息，男女生分工不同为男女体能有别，男生更适宜干体力型工作；男女生各有优势，扬长避短，发挥所长。

所以②③说法符合题意；①④说法错误，男女生在性格特征、兴趣爱好、思维方式等方面，表现自己的特点。

故选C。

2．上了八年级后，小文悄悄喜欢上了班里的一个男生。

今天她收到了这位男生的纸条，约她周末去郊游，她既高兴又不安。

她不敢告诉父母和老师，又不知该如何处理。

假如你是小文的好朋友，你会告诉她A．答应这位男生的邀请，避开家长和老师B．慎重对待，理智处理，注意交往的尺度和原则C．要自尊自爱，最好是拒绝异性的一切邀请D．与这位男生断绝交往【答案】B【解析】【详解】本题考查正确对待男女同学之间情感问题。

根据教材知识，男女生之间产生爱慕之情是正常的，但是我们要冷静对待，理智处理，所以题文中的小文要注意交往的尺度和原则，B符合题意。

A做法是错误的，会影响自己的学习。

C D说法太绝对，男女生应正常交往。

故选B。

3．新学期开始,“全国中小学校园集体舞”在全国中小学全面推广。

跳集体舞需要男女生之间的默契配合,不少同学对此议论纷纷。

下列说法中,你比较赞同的是A．男女有别,手拉手在一起跳舞很别扭,很难为情B．男女生在一起跳舞久了,肯定会引发早恋C．中小学谈什么男女有别,怎么跳都没关系D．跳舞既能锻炼身体,又能增加男女生之间的友情【答案】D【解析】【详解】此题旨在考查学生对异性交往的认识，根据所学，异性之间正常的交往，有利于身心健康，可以相互学习，取长补短，共同进步等；题文中“全国中小学校园集体舞”需要男女同学默契配合，属于异性之间正常的交往，既能锻炼身体，也能增加男女同学之间的友情，A没有认识到异性之间正常交往的重要性，观点错误；B观点绝对化，是错误的；C没有认识到男女同学之间过密交往的危害，观点错误，所以正确答案选D。