ACM DIY第一届群赛解题报告
取自 Hang Hang's Wiki
目录 |
[编辑] 1001 Turing Tree
- 这个题目不需要动用图灵树，只需一棵线段树来离线处理。
- 首先计算出每一个数出现的位置，通过这些位置来划分一些区间，区间的值x表示“x在这一区间只出现一次”。考虑到数据范围，这一部要离散化一下。
- 接下来，把这些区间按照左端点或者右端点排一下序，问题就转化为了简单的区间加法问题。
- 如此做法时间复杂度是O(NlogN + QlogQ)。
[编辑] 1002 Matrix Puzzle
- 容易知道：
- 假设A的行列式|A|,那么我们可以得到集合
- T1 = {x| |A| ^ x = |B| mod C}
- 那么对于所求集合
- T2 = {x| A^x = B mod C} 必然有
- T2 为T1的子集,于是只需要求出T1的循环周期并枚举
- 由于C是素数，所以T1的循环周期为C-1的因子，枚举
[编辑] 1003 Divisibility
- 根据gcj一道题解题报告改编
- 围观地址 http://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2
- 首先去除重复的数
- 任意两个数，如果A是B的倍数，那么AB连边，就是一个最大独立集的问题
- 数据范围显然是不行的
- 换种考虑方法，如果如果A是B的倍数，那么B->A连边，就形成了一个DAG。
- 那么最大独立集转化成了最大反链
- 根据Dilworth's theorem，最大反链等于最小的链的划分(概念参照以上链接)
- 最小的链的划分可以用最小路径覆盖求得
- ps:随机数据弱 很多贪心的错误方法也过了
- 试试
- 10
- 2 3 5 7 770 910 1190 1330 870 690 这组数据
- 答案是6
[编辑] 1004 Count the string
- 大致思路:kmp+dp
- 首先对串做kmp，获得next函数
- next[i]的真正意义所在 s[i-next[i]+1,i]==s[0,next[i]-1]
- 那么我们可以从后往前，不断回溯，把后面出现的模式往前累加
- 即dp[next[i]-1]+=dp[i];初始dp值全设为1，因为从开始到i都是自身一个匹配
- 复杂度o(n)
[编辑] 1005 Guess the number
- 本题属于非正常题，纯属娱乐。因为本题最多只有16个字符，所以可以用X分提交法来套取输入数据，可以利用的返回结果至少有6种（RE,TLE,WA,OLE,MLE,DIVIDE_BY_ZERO具体看[1]里的What are the meanings of the judge's replies），把字符先统一转化成小写后，基本上两次提交可以确定一个字符，因此可以在期望时间内得到解。
[编辑] 1006 Kakuro Extension
- 原题要求每个run数字都不一样，是搜索+剪枝。但是这题没有这个限制，正确解法是网络流。
- 由于每个格子只能填1~9，有上下限制，那么可以用有上下限的网络流求解，但再想想既然每个数字都至少有1，那么我们可以处理每个run，减去对应的格子的个数后，每个格子的范围就变成了0~8，这样就可以把下界去掉。
- 建图如下：可以想象成从左边流入，上边流出，那么只要加一个源点，连到所有左边的run，流量为run的值，然后加一个汇点，所有上边的run连到汇点，流量为run的值，然后各个格子分别和自己对应的run连接，流量为8，左进上出，然后用sap求解，建图的时候要顺便把每个格子对应的流记录下来以便输出。
[编辑] 1007 In Action
- 这道题原本作为难度比较容易的上手题，不过开赛之后，估计大家是被那幅核武爆炸的图给吓到了，直到比赛过了近两小时才被纷纷发现其水性。
- 题目要求利用尽量少的油耗关闭一半以上的电力来阻止邪恶的AC主人公发动的核战争。因为油耗与距离同单位，则可以先求出从基地到达各电站所需的路程，即使用最短路径算法作一次预处理，那么问题就转化为距离为容量，电厂提供电量为价值的0-1背包问题，只要在所有的价值中线性查找正好比总电量一半要大的那个背包容量，就是所求的解，如果查找不到，那么可以打出impossible。
- 在求最短路上可以使用现今可行的任意算法，程序总复杂度为O(max(背包，最短路))。
[编辑] 1008 Rain in ACStar
- 题目给出两种操作：1.掉下多边形；2.查询一个区间当前所容纳的多边形的面积。操作规模是2.5万级别，因此普通的暴力是不行。
- 由于输入的数都是属于[1,1000000000]的，因此看完并看懂题目之后第一反应应该就是离散化，按照所有出现的横坐标离散化。接 着所面临的问题就是如何处理多边形，这只是一个简单的几何问题。
- 我们过每一个出现的横坐标做和y轴平行的竖直线，那么天上掉下来的多边形就被切割成一个一个的梯形（三角形可以看做是特殊的 梯形），因此这个问题可以简化为掉下梯形的情况。
- 试想，在一个区间如果掉下的不是梯形，而是数字，然后查询的是求区间掉下的数字的和，这样的问题该怎么做？
- 对，线段树或平衡树！Rain in ACStar也可以用同样的方法解决。
- 问题可以转化为这样的形式：实现动态往区间中插入梯形以及查询区间梯形面积和的操作。
- 可以注意到，这棵线段树中插入的是一条斜线。解决的方法很简单，在树中维护一个高度和斜率即可。
- 最后说明一点，给出的多边形并不需要用每一条竖直线切割。
[编辑] 1009 Lost's revenge
- 题解：自动机+DP。设主串有na个A、nc个C、ng个G、nt个T，于是题意转化为用na个A、nc个C、ng个G、nt个T生成一个新串，使模式串匹配次数最大。先将模式串生成自动机〔trie图〕，然后在这上面进行DP，状态可表示为dp[d,s]，d为自动机状态，s表示由ma个A、mc个C、mg个G、mt个T的生成串〔s可表示为ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt〕，转移为O(4)，总复杂度O(500*11^4*4)
[编辑] 1010 Legal or Not
- 本题水题。。发现过一个题的基本都是本题。。
- 题意即为判断所给数据是否构成一个环。
- 本意是拓扑排序 不过因为数据很小 Floyd也可以过
