课件参考全国赛01.mytest

1、-青少年信息学中国国家队训练2010-2011竞赛时间：待定提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关。对于 Pascal 语言paspaspas对于 C语言ccc对于 C+ 语言cppcppcpp题目名称稳定排队目录marriagequeuegift可执行文件名marriagequeuegift输入文件名标准输入标准输入标准输入输出文件名标准输出标准输出标准输出每个测试点时限0.2s0.4s1s测试点数目202020每个测试点分值555是否有部分分无无无题目类型传统型传统型传统型稳定【问题描述】我国的离婚率连续 7 年上升，今年的头两季，平均每天有近 5000 对夫

2、妇离婚，大城市的离婚率上升最快，有续有关。问题的认为，是与简化离婚手25 岁的和男友谈恋爱半年就结婚，结婚不到两个月就离婚，是典型的“闪婚闪离”例子，而离婚的导火线是两个人争玩电脑电脑炸烂。，丈夫一气之下，把有社会工作者就表示，80 后求助个案越来越多，有些是与父母过多干预有关。而根据的统计，中国离婚五大城市首位是，其次是、深分析圳，广州和厦门，那么到底是什么原因导致我国成为离婚大国呢?有说，中国经济急速发展，加上女性越来越来越独立，另外，近年来简化离婚手续是其中一大原因。以上内容摘自第一门户现活给人们施加的压力越来越大，离婚率的不断升高已成为现代社会的一大问题。而其中有许许多多的个案是由中的

3、“不安定”引起的。妻子与丈夫吵架如绞痛，于是寻求前男友的安慰，进而夫妻激化，最终以离婚收场，类似上述的案例数不胜数。已知 n 对夫妻的状况，称第 i 对夫妻的为 Bi，女方为 Gi。若某男 Bi 与某女 Gj 曾经交往过（无论是大学，高中，亦或是阶段，ij），则当某方与其配偶（即 Bi 与 Gi 或 Bj 与 Gj）感情出现问题时，他们有私奔的可能性。不妨设 Bi 和其配偶 Gi 感情不和，于是 Bi 和 Gj 旧情复燃，进而 Bj 因被戴绿帽而感到不爽，联系上了他的初恋Gk一串串的离婚事件像多米诺骨牌一般接踵而至。若在 Bi 和 Gi 离婚的前提下，这 2n 个人最终依n 对情侣，那么i 为

4、不安全的，否则i 就是安全然能够结的。称给定所需信息，你的任务是判断每对是否安全。【输入格式】第一行为一个正整数 n，表示夫妻的对数；以下 n 行，每行包含两个字符串，表示这 n 对夫妻的由一个空格隔开；（先女后男），第 n+2 行包含一个正整数 m，表示曾经相互喜欢过的情侣对数；以下 m 行，每行包含两个字符串，表示这 m 对相互喜欢过的情侣女后男），由一个空格隔开。（先【输出格式】输出文件共包含 n 行，第 i 行为“Safe”（如果i 是安全的）或“Unsafe”（如果i 是不安全的）。【样例输入 1】2Melanie Ashley Scarlett Charles 1Scarlett

5、Ashley【样例输出 1】Safe Safe【样例输入 2】2Melanie Ashley Scarlett Charles 2Scarlett Ashley Melanie Charles【样例输出 2】Unsafe Unsafe【数据规模和约定】对于 20%的数据，n20；对于 40%的数据，n100，m400；对于 100%的数据，所有字符串中只包含英文大小写字母，大小写敏感，长度不大于 8，保证每对关系只在输入文件中出现一次，输入文件的最后m 行不会出现未在之前出现过的1n4000，0m20000。，这 2n 个人的各不相同，【解题】本题主要强连通分量。选手对图论与运用，主要涉及知识

6、点为二分图和算法 1：枚举每对后，依次搜索每对的女方对应的，判断是否存在可行解。时间复杂度：O(n*n!)，期望得分：1015。算法 2：状态压缩动态规划。枚举每对后，设 count(x)表示以二进制的形式写出 mask 时，所有数位中 1 的个数。令 fx表示前 count(x)位已配对，并且配对的男生集合为 x 的（fx=true 表示合法，fx=false 表示不合法），配对的男生即可。时间复杂度：O(n2*2n)，期望得转移时枚举当前分：15。算法 3：二分图匹配。枚举每对后，将相应边从原图中去掉，对新图做一次二分图匹配（匈牙利算法、Hopcraft、网络流等均可），若存在完美匹配，则

7、该婚姻是不安全的，否则该是安全的。时间复杂度：O(n*Match(n,m)，其中Match(n,m)表示对 2n 个点（左右两侧各 n 个）和 m 条边的二分图做最大匹配的时间复杂度，期望得分：3040。算法 4：寻找增广路。对算法 3 的改进。枚举每对后，发现其实没有必要对新图重新做一次二分图匹配，只需要寻找一次增广路即可。时间复杂度：O(n*m)，期望得分：4050。算法 5：求解强分量。上述四种算法都是枚举每对后才进行判断的，如果每次判断的时间为 O(m)，那么 O(n*m)已为下限，不会有更优的算法了。因此若想得到更优的算法，就必须在一次扫描图的过程中将所有出。的计算考虑算法 4，在枚

8、举到i 时，发现增广路都是这种形式的：Gp1-Bp2-Gp2-Bp3-Gp3-Bpt-1-Gpt-1-Bpt其中 p1=pt=i，pi 互不相同（2it-1），并且（1it-1）。GpiBpi+1和间有边相连建立新图，新图中的点 Ci 对应着原图中的点 Gi 和 Bi，新图中的边 Ci-Cj对应着原图中的边 Gi-Bj。新图是有向图，因为新图中的边 Cj-Ci 对应着原图中的边 Gj-Bi，这与 Ci-Cj 所对应的边不同。于是在新图中，上述增广路变为如下形式：Cp1-Cp2-Cp3-Cpt-1-Cpt于是出如下结论：i 不安全当且仅当新图中存在从 Ci 出发的路径，最终回到 Ci。如果枚，d

9、fs 或 bfs 判断是否存在从 Ci 出发最终又回到 Ci 的路径，时间复举每对杂度依然为 O(n*m)，与算法 4 本质无区别，无法通过本题的所有测试点，因此需要更高效的判断。回顾上述判断条件，“存在从 Ci 出发最终又回到Ci 的路径”等同于“存在包含 Ci 长度大于 1 的环”，也就是要求 Ci 所处的强连通分量包含的点的个数大于 1。于是得到最终算法：首先将旧图按照上述方法转化为新图，再在新图上求解强连通分量（Tarjan 或 Kosaraju 均可），再依次判断每对对应的强连通分量的点的个数是否大于 1，若大于 1 则输出“Unsafe”，否则输出“Safe”，总时间复杂度 O(n

10、+m)，期望得分：90100。至此本题已被完美解决。排队【问题描述】排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第 i 个小朋友的身高为 hi，定义一个序列的杂乱程度为：满足 ihj 的(i,j)数量。阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便该输出该序列的杂乱程度。阿姨统计，在未进行任何交换操作时，你也应【输入格式】第一行为一个正整数 n，表示小朋友的数量；第二行包含 n 个

11、由空格分隔的正整数 h1,h2,hn，依次表示初始队列中小朋友的身高；第三行为一个正整数 m，表示交换操作的次数；以下 m 行每行包含两个正整数 ai 和 bi，表示交换位置 ai 与位置 bi 的小朋友。【输出格式】输出文件共 m 行，第 i 行一个正整数表示交换操作 i 结束后，序列的杂乱程度。【样例输入】331 3【样例输出】103【样例说明】未进行任何操作时，(2,3)满足条件；操作 1 结束后，序列为 130 140 150，不存在满足 ihj 的(i,j)对；操作 2 结束后，序列为 150 140 130,(1,2)，(1,3)，(2,3)共 3 对满足条件的(i,j)。【数据规

12、模和约定】对于 15%的数据，n,m15；对于 30%的数据，n,m200；在剩下的 70%数据中：存在 15%的数据，hi 各不相同；存在 15%的数据，110hi160；以上两类数据不存在交集。对于 100% 的数据， 1m2*103，1n2*104，1hi109，aibi，1ai,bin。【解题】本题主要选手对数据结构的应用。设每次操作时交换的元素下标为 lID 和 rID，lIDrID，因为如果 lIDrID 那么可以将 lID 和 rID 互换而不影响结果。算法 1：下数组 h，每次操作时直接交换 hlID和 hrID，统计结果时枚举每对 i 和 j 判断是否满足条件，若满足 ihj

13、则结果+1。时间复杂度： O(mn2)，期望得分：15。算法 2：下数组 h，每次操作时直接交换 hlID和 hrID。统计结果时，考虑数对(p,q),phq 则需要计入结果。发现只有p=lID,q=lID,p=rID,q=rID 四个条件中满足至少一个时，才会在本次操作中对结果产生贡献，与 lID 和 rID 无关的 p 和 q 可直接继承操作前的结果。于是每次操作只需要枚举 O(n)级别的数组下标。时间复杂度：O(mn)，期望得分： 30。算法 3：初始状态下（即还没有进行任何交换操作时）的逆序对数量可用归并排序或扫描+高级数据结构解决，在此不再详细展开，预处理时间复杂度 O(nlogn)

14、。对于每个操作交换 lID 和 rID，若 hlID=hrID，则可忽略本次操作（数列并没有改变），否则分类如下：1、所有 prID 产生的(lID,p)和(rID,p)都不会对结果产生任何贡献，类似于情况 1。3、所有 lIDprID 且 hpmin(hlID,hrID)产生的(lID,p)和(p,rID)都不会对结果产生任何贡献。设 x 表示交换操作前 hlID的值，y 表示交换操作前 hrID的值。那么在交换操作前，由 hphp，又因为 lIDp，所以数对(lID,p)对结果产生了 1 的贡献。同理，由于 hpy 且 prID，所以数对(p,rID)不对结果产生贡献。在交换操作后，由于

15、hphp，即 hlIDhp，又因为lIDp，所以对结果产生 1 的贡献。又由 hpx=hrID得数对(p,rID)不对结果产生贡献。由于在交换操作前后均对结果产生 1 的贡献，因此不会改变结果。4、所有 lIDpmax(hlID,hrID)产生的(lID,p)和(p,rID)都不会对结果产生任何贡献。证明方法与情况 3 相似，不再重述。5、当 hlIDhrID时，所有 lIDprID 且 hlIDhphrID产生的数对对结果产生+2 的贡献。在交换操作前，因为 hlIDhphrID，所以与 p 相关的数对没有对结果产生贡献。在交换操作后，(lID,p)和(p,rID)从不合法解变成了合法解，因

16、此对结果产生+2 的贡献。6、当 hlIDhrID时，所有 lIDprID 且 hlID=hp产生的数对对结果产生+1 的贡献。在交换操作前，与 p 相关的数对没有对结果产生贡献。在交换操作后，(lID,p)从不合法解变成了合法解，因此对结果产生了+1 的贡献。7、当 hlIDhrID时，所有 IDphrID时，所有 lIDprID 且 hrIDhphrID时，所有 lIDphrID时，所有 IDprID 且 hlID=hp产生的数对对结果产生了-1 的贡献。证明方法与情况 7 类似。另外，如果 hlIDhrID，那么数对(lID,rID)从合法变为不合法，因此于是需要额外-1。需要一个数据结

17、构，支持查询 lIDprID 且 lefthpright 的 p 的数量（查询 hp=hlID可视为 left=right 的特殊情况）。线段树套平衡树能够在O(log2n)的时间内处理每个询问，其中线段树以数组下标为 key，平衡树以 hi为 key，平衡树的每个节点需key 域、count 域（表示当前下标范围内，满足 hi=key 的 i 的数量）和 size 域（表示当前来举个例子（h = 3, 4, 5, 2, 8, 6, 1, 7）：所有节点 count 域的和）。让其中每个方框内的数字序列表示以这些数字为 key 建立一棵平衡二叉树。每个查询区间可以分解为 O(logn)条线段，

18、在每条线段对应的平衡二叉树中查找满足 lefthpright 的 p 的数量可在 O(logn)时间内得到结果。每个修改操作可段树每一层的对应区间中修改平衡树的对应节点，线段树共 O(logn)层，修改平衡树对应节点可在 O(logn)时间内完成。因此完成单次交换操作的时间复杂度为 O(log2n)，总时间复杂度 O(mlog2n)，期望得分：100。【问题描述】一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多，当然他也会送出许多。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的会越多。小 E 从商店中了 n 件，打算送给的方案数m 个人，其中送给第 i

19、个人数量为 wi。请你帮忙计算出送（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的不同）。由于方案数可能会很大，你只需要输出模 P 后的结果。【输入格式】输入的第一行包含一个正整数 P，表示模；第二行包含两个整整数 n 和 m，分别表示小 E 从商店的人数；的数和接受以下 m 行每行仅包含一个正整数 wi，表示小 E 要送给第 i 个人的量。数【输出格式】若不存在可行方案，则输出“Im的方案数。sible”，否则输出一个整数，表示模P 后【样例输入 1】1004 212【样例输出 1】12【样例输入 2】1002 212【样例输出 2】Imsible【样例说明】下面是对样例 1

20、 的说明。以“/”分割，“/”前后分别表示送给第一个人和第二个人的案详情如下：1/23 1/24 1/342/13 2/14 2/343/12 3/14 3/244/12 4/13 4/23。12 种方【数据规模和约定】设 P=p1c1 * p2c2 * p3c3 * *pt ct，pi 为质数。对于 15%的数据，n15，m5，pici105；在剩下的 85%数据中，约有 60%的数据满足 t2，ci=1，pi105，约有 30%的数据满足 pi200。对于 100%的数据，1n109，1m5，1pici105。【解题】本题主要选手对数论与运用，涉及到组合数学、求、中国剩余定理等知识点。通过

21、简单的计算，得出：如果 sigma(wi) n，则输出“Im ans =C(n, w1) *C(n w1, w2) *C(n w1 w2, w3) *. *sible”，否则C(n w1 w2 w3 - - wm 2 wm 1, wm)=算法 1：按照以上公式进行模拟计算，最后输出模 P 后的值即可。时间复杂度：O(n)，期望得分：15。算法 2：对于剩下 85%的数据，n 达到 109 数量级，因此如此的模拟计算是无法得到好分数的。在算法 2 中只考虑 P 为质数的情况，P 为合数的情况留到下面再。发现 n! mod P 的计算过程是以 P 为周期的的，举例如下：n = 10, P = 3n

22、! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10= 1 * 2 *4 * 5 *7 * 8 *10 *3 * 6 * 9= (1 * 2)3 *33 * (1 * 2 * 3)最后一步中的 1 * 2 *3 可递归处理。因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入，应当用一个计数器变量 cnt 来保存中因子 P 的个数。提前预处理出 faci = 1 * 2 * 3 * * (i 1) * i mod P，函数 calcfac(n)返回 n! mod P 的值， er(a, b, c)返回 ab mod c 的值，可用快速幂在 O(logb)的时间内完成。typedef long long LL; LL calcfac(LL n)if (n P) return facn;LL seg = n / P, rem = n % P;LL ret =er(facP - 1, seg, P); /facP - 1重复出现了 seg 次ret = ret * facrem % P; /除去 seg 次 facP 1外，剩下的零头 cnt += n / P; /提出 n / P 个因子 Pret = ret * calcfac(n / P) % P; /递归处理 return ret;于是分子中 n!的计算可在 O(logn