bonism 的个人博客

链接

275

题意：要求构建一颗n个节点的树，每个节点的权值为score[dge[i]-1]，dge[i]是点i的度数，给定score，问最大权值和是多少？n<=50

分析：所有度数之和为2(n-1)，每一个点的dge范围在1到n-1之间。所以DP一下就ok。

450

题意：有一个R*C的01网格，现在给两种描述，描述由"0","1","?"组成，"0"表示这个位置上的数是0，"1"表示这个位置上的数是1，"?"表示这个位置上的数可以是0或1。第一种描述按原网格的顺序给出，第二种描述是打乱了列顺序后的。求一个字典序最小的01网格。R,C<=30

分析：遇到这种字典序最小的问题，一般采取逐位枚举+判断可行性的做法。所以，按从上到下、从左到右的顺序，先尝试填0，判是否可行，如果不行，则这个位置只能填1。

可行性的判断：对于两种描述，可以从第一种描述的各列向第二种描述的各列建立邻接布尔表，布尔表中第i行第j列的元素表示第一种描述的第i列是否可以对应第二种描述的第j列（这里用简单的检查即可）。如果问题可行，则存在一个完备匹配。在逐位枚举的过程中更新布尔表+做二分匹配。

时间复杂度O(N^2*N^3)，即O(N^5)。

1050

题意：给出c1,c2,...,cn（ci<=10^18，n<=40），保证c1=1且当i<j的时候，ci|cj。再给一个10^18范围的整数sum。问c1x1+c2x2+...+cnxn=sum的非负整数解的个数，答案取模输出。

分析：这个题，有点难度，想了挺久的。

题解有个背景：一只小兔子从数轴0跳到数轴sum位置，可选步长集合为c[]，每次跳跃步长不增加（不超过上一次跳跃步长），求方案数。

分析1. 由于c之间的倍数关系，那么有一个很好的性质，可以帮助我们把sum的规模逐渐缩小：假设第一次跳跃步长为X，那么，2X，3X，4X，……这些都是必经点。

分析2. 设solve(len)(i)(j)表示，跳跃总长为len，可选步长集合为c[1..i]，并且最后一步跳跃的步长为c[j]的方案数。那么有solve(A)(i)(k)*solve(B)(k)(j)=solve(A+B)(i)(j)，这就是矩阵乘法啦。

由分析1和分析2，可得出，在0到sum之间，c[n]是一个必经点，求出solve(c[n])这个矩阵，并自乘(sum div c[n])次，这样可以把sum的大小缩减为sum mod c[n]，继续递归求解。所以问题转化为子问题：求所有solve(len)矩阵，满足len∈c[]。

子问题的求法：总长度为len(设len=c[x])，那么可以一步跳到len处，或者选一个小一点的步长。

当一步跳到len时，有solve(len)(i|i>=x)(x)=1。

当选用小一点的步长时，我们知道，在0到len之间，c[x-1]是一个必经点，根据之前的分析，可以由矩阵solve(c[x-1])自乘(c[x]/c[x-1])次得到。

综上：求解子问题的时间复杂度为O(n^4 * log sum)，原问题的时间复杂度为O((n^4+n^3) * log sum)。

某搜索引擎公司Research Intern的面试。

（如果有侵权内容，请告诉我，我将马上删除）

三面

有两个面试官，下面称面试官A和面试官B

面试官A主要问我一些算法问题:

Q1. 我对排序算法的理解

我讲了冒泡排序，选择排序，快速排序，归并排序，Intro-sort.

他接着问了我quick sort为什么可能退化，intro-sort的切换界是怎么得来的，以及比较类排序时间复杂度下限为什么是O(NlogN).一开始我往推公式的方面想，不知道怎么表达，他给我提示说可以用类似描述的方法证明。于是瞬间茅塞顿开，居然还可以这样证明!!

Q2. 整数划分，N超大(longint)，问划分后各数乘积最大的方案有多少种

我不知道N很大怎么做，猜测这个对时限要求还是比较低的，就设计了一个超窘的类似枚举的递推，解释完之后，他提示我可以去掉一些冗余，我反应很慢，他又提示用数学方法，于是我说了一个可行性剪枝。

Q3. 求max{a1x1+a2x2+a3x3}，x必须是整数，且满足不等式组

c11x1+c12x2+c13x3<=b1

c21x1+c22x2+c23x3<=b2

…

cn1x2+cn2x2+cn3x3<=bn

我往空间多面体方面想，描述的时候他让我分析复杂度，并且把变量数加至m，我想了一会儿没啥思路，没法想象m维的情况..然后他告诉我这个复杂度是没法估计的(really?!-O-) 又问了一下无解的情况。

面试官A问我问题的时候旁边来了面试官B，面试官A问完问题，他们俩就离开我讨论了一会儿。面试官B主要和我聊一些职业方面的内容，问了我的动机，然后告诉我，我是直接进入三面，之前的一面和二面都省略了，于是要考察一下我的代码能力。

他先考察了我的代码风格，问一道很简单的字符串匹配，让我手写一个程序来，考虑各种情况.我写完之后程序风格被他”指点”了，我写程序习惯不太好，没有每步都查错，无输出错误日志，居然用全局变量，一些优化，等等。

然后问了智力题，翻硬币问题，21个黑白两面的硬币，10个黑色朝上，11个白色朝上，问在看不见的情况下，如何把这21个硬币分成两堆，使每堆黑色朝上的个数相同? 给我两分钟思考，我不会. 又给了一个2黑1白的简化版，我压力很大还是不会…

总结

从投递简历到面试结束一共用了一个星期，超快！整个面试大概历时1小时30分钟。 神奇的是面试完和面试官的交流中得知自己已经通过面试了。

某搜索引擎公司Research Intern的面试。

（如果有侵权内容，请告诉我，我将马上删除）

一面

先自我介绍。

第一问。

给一个字符串，表示一个数，把它+1后返回一个字符串。

我写代码的过程中把string中高低位的顺序弄反了，自己重新写了一下。通过。

第二问。

给许多按某种顺序排好序的字符串，求字母表顺序。

我想了一会儿开始写代码，面试官让我讲讲算法，我讲完，他没什么表示。过了一会儿，他觉得程序太长，就要求我写其中一个函数：给出一些偏序关系（小于关系）确定整体的顺序。我一开始想了一个O(n^5)的算法，其实可以用传递闭包优化到O(n^3)，面试官提醒我有简单算法，我想了一个有向无环图最长路算法，面试官听懂我的做法以后，问“你学过拓扑排序吧？”顿时发觉我SB了……

第三问。

二分查找，如果有多个一样的，返回最小下标，如果没有，返回-1。

比较简单的题目，我很快写了程序，不过被发现一个小bug，当答案=0时会出错。改了一下改对了，不过面试官怀疑我没改对，他找了很久的反例，然后他失败了。

二面

第一问，比较简单的数学问题。

桌子上有52张扑克牌，大小关系是既定的，现在有包括你在内的三个人，各取一张牌，问你抽到的牌的大小介于另外两个人的牌之间的概率。

一共有6种大小关系，满足条件的有两种，所以答案是1/3。

第二问，股票市场里，每秒钟更新一次数据，现在要求实现一种询问操作，返回最近一小时内的最大价值和最小价值。

我用单调队列实现，交流后，面试官理解了我的做法，叫我写一个完整的类（class）来实现这几个操作。

吸取一面写程序太急的教训，我这回写得比较慢，写完了面试官让我解释给他听，我balabala解释了一下，一些小细节的实现上我们做了进一步讨论，不过对大局没什么影响。

第三问，也许是写程序太久了，所以不用再写了（哈哈），第三问是这样，搜索引擎每天都要处理好多好多查询，面对海量级别的查询，要求设计一个比较快的方法，粗略地求出当天最热门的100个关键词。时间只允许扫描一遍输入。

我一下就想到算法了，不过还是在脑子里酝酿了一下细节，面试官说不必想太清楚，让我说大致思路就ok。我说：我的方法是基于概率论，和一种划归的想法。假设，我根据经验，得出每天Top100的词出现的概率是0.01%，那么其余的词出现概率都比0.01%小。那么对于海量输入，我可以把输入分成好几段，每一段比如说有10万个关键词，我可以用一些算法（比如哈希）来统计出这一段内出现次数最多的几个词，这样每一段我都可以得到几个高频词（划归成了一个规模比较小的问题，再利用这个方法整合起来就好）。

面：“每一段取几个呢？”

“每一段取一两个就好了，因为会有好多段。”

面：“嗯，那你这个算法最坏情况是什么样的呢？”

“当真正的高频词分布很平均，但是每一段里又密集地出现好多局部高频词，balabala”

面：“嗯，这是一个开放性题目，也没有正确算法。”

总结

该公司整个招聘流程还是比较久的，从投简历到开始面试大概过去了两周，两轮面试在三天内糙快猛完成，每一轮面试历时1小时左右，然后又进入半个月漫长的等待。今天中午刚出的结果，心里一块石头落地。

前一段时间写大作业，发现对C++掌握得不够熟练，导致有些时候非常痛苦。所以开始断断续续地看《C++ Primer》这本书，这里是一些读书笔记，主要记录一些对我个人来说印象不是很深刻的东西。

第1章  快速入门
    1.5  类的简介
        标准库头文件用尖括号<>，非标准库的头文件用双引号""
第一部分  基本语言
第2章  变量和基本类型
    2.2  字面值常量
        非打印字符的转义序列
        换行    \n
        回车    \r
        问号    \?
        双引号  \"
        退格    \b
        反斜线  \\
        单引号  \'
        （详见P35）
    2.3  变量
        2.3.3  定义对象
            初始化不是赋值（好神奇）
        2.3.6  名字的作用域
    2.4  const限定符
        const对象默认为文件的局部变量，若要是const变量能在其他文件中访问，必须显式地指定为extern const
    2.5  引用
        相当于多了一个名字
第3章  标准库类型
    3.2  标准库string类型
        3.2.3  string对象的操作
            string的size操作返回的是string::size_type类型，不要把它赋给一个int变量
        3.2.4  string对象中字符的处理
            头文件cctype
            isalnum(c)    是字母or数字
            isalpha(c)    是字母
            isdigit(c)    是数字
            isgraph(c)    非空格
            islower(c)    是小写
            ispunct(c)    是符号
            isspace(c)    是空格
            isupper(c)    是大写
            isxdigit(c)   是十六进制数
            tolower(c)    大写则返回小写，否则返回c
            toupper(c)    小写则返回大写，否则返回c
            （详见P77）
第4章  数组和指针
    4.2  指针的引入
        4.2.5  指针和const限定符
            这里基本上看不懂
    4.3  C风格字符串
        标准库函数
        strlen(s)
        strcmp(s1, s2)      相等返回0，s1>s2返回正数，s1<s2返回负数
        strcat(s1,s2)       把s2接到s1后，返回s1
        strcpy(s1,s2)       s1=s2，返回s1
        strncat(s1,s2,n)    把s2的前n个字符链接到s1后，返回s1
        strncpy(s1,s2,n)    s1=s2[0..n-1]，返回s1

由于我看错题目了，所以原创了一道题。SRM526解题报告请看这里

题意

有一堆石子，共N个。A和B轮流取石子，每一轮至少取1个，至多取K个石子，无法操作的人输。A先手，A每次只能质数个石子，B每次只能取合数个石子。A和B都按最优策略来玩：即，如果赢，则尽量早点赢；如果输，则尽量晚点输。问这个游戏将在哪一轮结束，以及谁赢了。K<=N

方法一

暴力方法，时间复杂度O(N^2)。设F[i]表示有i个石子，A先手时，游戏结束时的轮数（若A胜，则F[i]为正，否则F[i]为负），再设G[i]表示有i个石子，B先手时，游戏的轮数（B胜，则G[i]为正，否则G[i]为负），状态转移时枚举所有决策即可。

方法二

求必败态方法，时间复杂度为O(L*prime(N))，L是必败态个数，prime(N)是N以内质数个数。

这种博弈问题可以直接求必败态，假设已经求出了所有下标不超过P的F和G的必败态，他们是F[f1]，F[f2]，...，F[ft]以及G[g1]，G[g2]，...，G[gs]（1<=f1<f2<...<ft<=P，1<=g1<g2<...<gs<=P）。接下来要求下标在P以后的第一个必败态F[f_t+1]和G[g_s+1]，那么如下约束条件成立：

1.( (f_t+1) - 任何质数) 不属于{g1,g2,...,gs} ，即f_t+1与任意gi的差为合数。

2.( (g_s+1) - 任何合数) 不属于{f1,f2,...,ft}，即g_s+1与任意fi的差为质数。

那么，当我们求出一个gi的时候，枚举所有质数pr，F[gi+pr]肯定不是必败态，这里额外开一个布尔表即可。

当我们求出一个fi的时候，枚举所有质数pr，额外开一个整型表，把整型表的fi+pr位置加1。因为G[g_s+1]是必败态当且仅当所有fi+某个质数=g_s+1，所以只有当整型表中的值达到t时，g_s+1才是下一个必败态。

所以，可以用当前的必败态推出下一个必败态。直到推出所有N以内的必败态，最后枚举一下A的第一步即可求出原问题的答案 。

小结

博弈类问题最普通的方法是递推，当n达到一定规模以后，可能必败态很少（或者必胜态很少），这种情况下，可以直接求必败态（或必胜态），通过当前已经求出来的必败态推下一个必败态。这样状态数会少很多。

作者注

如果你有更好的解法，殷切期望你能和我交流。

链接http://apps.topcoder.com/wiki/display/tc/SRM+526

250

题意：给一个矩形网格，网格的每一行、每一列至多含一只鸭子，每次操作可以让一只鸭子向四面走一格。问把这些鸭子移动到同一行或同一列的最少步数。边长<=50

分析：方法一、暴力枚举最后聚集到哪一行或列。方法二、分别对行列求中位数，再移动。

500

题意：有一堆石子，共N个。A和B轮流取石子，每一轮至少取1个，至多取K个石子，无法操作的人输。A先手，A取完后必须剩下质数个石子，B取完后必须剩下合数个石子。A和B都按最优策略来玩：即，如果赢，则尽量早点赢；如果输，则尽量晚点输。问这个游戏将在哪一轮结束，以及谁赢了。K<=N<=474747

分析：先考虑最暴力的方法，设F[i]表示有i个石子，A先手时，游戏结束时的轮数（若A胜，则F[i]为正，否则F[i]为负），再设G[i]表示有i个石子，B先手时，游戏的轮数（B胜，则G[i]为正，否则G[i]为负）。则不难得出状态转移方程

如果A可以赢，则F[i] = - max{ G[pr] | i-K<=pr<i且G[pr]<=0 } +1

如果A赢不了，则F[i] = - max{ G[pr] | i-K<=pr<i且G[pr]>0 } - 1

其中pr是一个质数。G的状态转移类似，所以就不讨论了。时间复杂度是O(N^2)。

下面来优化一下这个算法：

与F[i]有关的G[pr]满足i-K<=pr<i，如果下面的关系均成立

1. i-K<=a<b<i（在转移的范围内有两个决策，决策a和决策b）

2.G[a]<0且G[b]<0（A可以赢）

3.|G[a]|>|G[b]|（决策a的轮数比决策b的轮数多）

那么在以后的决策中，决策b肯定比决策a优，决策a可以删掉了。这样就可以用一个单调队列维护一下所有负的G。对于A输的情况，另开一个单调队列维护一下所有正的G即可。

优化后的时间复杂度为O(N)。

PS.

1.官方报告没有用单调队列而用set，我觉得可以再优化一下。

2.我一开始题目意思理解错了，YY出了另一道题，用的是博弈中的另一种经典方法，详见这里。

1000

题意：给定N（N<=50）个pieces串，每个pieces串长度<=50，再给定一个“好串”（长度<=500）。现用随机方法生成一个含K（K<=10^12）个pieces的目标串，一个目标串的权值为：“好串”在该目标串中出现的次数（允许重叠）。问目标串的期望权值。

分析：这题我想了好久看题解的，题解的思路是分情况求期望后相加。

设好串的长为L，当K很大时，设f[x]为好串的末端落在目标串的第x个piece中的期望次数，则f[x]=(∑s[x,i])/n，其中，s[x,i]表示好串的末端落在目标串的第x个piece中，并且这个piece的编号是i，共有多少种情况。因为好串最多长L个pieces，所以f[L+1]=f[L+2]=...=F[K]，只需计算前L个f值，即可得出answer=f[1]+f[2]+...+f[K]。

当K很小时，设dp[k][len]表示已经构造了目标串的前k个pieces，当前串的长为len的后缀可以匹配好串长为len的前缀，它可以转移到dp[k+1][len']，转移时枚举第k+1个piece的编号，更新len，并且加上完整出现好串的次数。

这样一来，K很大时，f[i]=dp[i][0]-dp[i-1][0]，answer = (f[1]+f[2]+...+f[L]) + (f[L+1)*(K-L) = dp[L][0] + (dp[L+1][0]-dp[L][0])*(K-L)。整个问题解决，复杂度为O(L^2 *N)。

小结：第一次遇到这种分情况求期望最后相加的问题，有点收获哈。

链接http://apps.topcoder.com/wiki/display/tc/SRM+525

300

题意：在一个长方形网格中，某些格子里有硬币。每次操作可以把所有硬币统一往上（下、左、右四个方向中的某一方向）移动一格，超出边界的硬币消失。问最少多少次操作使网格中恰好剩下K枚硬币。网格边长l<=30

分析：显然最后那K个硬币处于某一个子矩形内，枚举所有恰含K枚硬币的子矩形。那么上下方向和左右方向各有两种移动方案，选最优的即可。复杂度O(l^4)

525

题意：有N只兔子和两个rumor，初始时，每只兔子要么两只rumor都不认识，要么两只rumor都认识。每天伊始，如果一只兔子至少认识一个rumor，那么它在它所认识的rumor中选一个，并花一天的时间，把这个rumor介绍给所有信任它的兔子。给出兔子间的信任关系（单向的），问最少多少天后，所有兔子都认识两个rumor，或返回无解。N<=16

分析：从比较简单的观察入手，

0.如果一只兔子在第t天谁都不认识，那么它在t+1天啥都不做。

1.如果一只兔子在第t天认识了rumorA，但是不认识rumorB，那么它肯定会在t+1天把rumorA介绍给所有信任它的兔子（反之亦然）。

2.如果一只在第t天认识了两个rumor，那么它在t+1天的决策就比较复杂了。

因为N的规模比较小，所以可以枚举每只兔子遇到同时认识了两个rumor的第二天，优先选择介绍哪个rumor。然后模拟一下。复杂度O(2^n*n^2).

950

题意：给一个n*n的黑白网格，行列的下标都从0到n-1，每次操作是选择两个数i和j，交换第i行和第j行，再交换第i列和第j列。问最少多少次操作到达目标状态或输出无解。n<=50，目标状态满足if |i-j|=1 or i+j=N-1 or {i,j}={0,N/2-1} or {i,j}={N/2, N-1} then 格子(i,j)是黑色，否则为白色

分析：首先，行列操作是相互独立的，不妨先只考虑行操作，调整成目标状态的话，相当于对行下标的一个置换。其次，由操作的行列对称性，可得，对列下标的置换与对行下标的置换相同。也就是说要求一组坐标映射关系。

然后来观察目标状态，看看有没有特殊的地方可以下手。（看左边的图）

可以看到

0.主对角线全白，副对角线全黑，主对角线两侧的对角线全黑。

1.在每条边的中间有4个特殊格子。

2.每行每列恰好3个黑格。

3.关于主对角线对称

上面的条件可以初步判断无解。

若问题是有解的，那么对于某一行的中的3个黑格的坐标映射关系，如果已经确定了其中两个的坐标映射，那么剩下一个的坐标映射可以轻松得出。于是我尝试先枚举一些映射关系，然后看看能不能由图的特殊性逐步得出所有映射关系。

第一步，我枚举在每条边的中间4个特殊格子所在行列的映射，见图中绿色部分。这一步复杂度为O(n^2*3^2)

第二步，为了使某行或某列有两个格子，我枚举了副对角线两端的格子所在行列的映射，见图中紫色部分。这一步复杂度为O(2^2)

这么一来，左上角和右下角位于紫色区域内的格子(0,1),(1,0),(n-1,n-2),(n-2,n-1)的坐标映射可以求出。也就相当于求出了下标1和下标n-2的映射，这样就，有一些黑格的坐标映射就自动确定了。又可以推出下标2和下标n-3的映射……相继推出所有下标的映射关系。这一步复杂度为O(n)

最后，求出了所有映射关系，可以通过统计置换的循环节个数求得最少操作次数，这一步复杂度为O(n)

总时间复杂度O(n^3)。

链接：http://apps.topcoder.com/wiki/display/tc/SRM+524

250

题意：把n分解成合数的和，问最少可以分成多少个？1属于合数，n<=10^12

分析：对于这种题目，一般是先尝试一些特殊的分法，然后看看能不能找到规律。首先，n为合数时答案为1，否则，可以分成n个1，说明问题必然有解。然后，想到n可以分解为若干2的幂之和，于是规律出现了！！！把所有大于1的2的幂全部加起来变成一个新的数，这个数有因数2！把这个数和1相加可以得到n。这样似乎就解出来了，n为合数时输出1，n为质数时输出2。但是，这种题目一般在n范围很小时有trick，验证一下果然n=3时，只能分解为1+1+1。加上这一个特判即可。

500

题意：问满足约束条件的最长序列有多长？约束条件形式为

1.连续c[i]个数之和为正   c[i]>0

2.连续-c[i]个数之和为负   c[i]<0

最多50个约束,|c[i]|<=1000

分析：先来个转化，设构造序列的前i个数之和为sum[i]，这下约束条件的转化就爽多了。为了方便叙述，假设c中有许许多多-a和+b，那么约束条件可以转化成这样：

1.sum[i+a]-sum[i]<0，即sum[i]>sum[i+a]

2.sum[i+b]-sum[i]>0，即sum[i]<sum[i+b]

上面有一些不等式，若把sum[i]看成一个点，大于关系看成有向边，那么合法序列对应无环有向图（差分约束系统）。又因为序列长度大于某个阈值以后肯定非法（满足单调性），所以可以用二分+构图+判断是否无环的方法来。至于二分的上界，可以证明如果答案是有限的，那么答案<=min{a+b-1}<2000。

1000

题意：在一个n*m网格基座上，堆砌了一些单位立方体。给出正视图和侧视图，问有多少种满足条件的堆砌方法。n,m<=50

分析：（汗，图像不能隐身。。。）这个题我没想出来。。。某人发现改变正视图各个height的顺序，左视图不变；改变左视图的顺序，正视图不变。于是可以调整成正视图height递减，左视图height也递减的形式，这下规律了很多。

举官方题解上的例子，heightsOfLeftView = {0, 1, 2, 4, 5} ，heightsOfFrontView = {1, 1, 4, 5}，如左图。可以看到有好多不同的L型（或退化的L型）区域，每块区域里的约束条件本质上是一样的，都是每行每列至少要有一个高度为h。

链接http://apps.topcoder.com/wiki/display/tc/SRM+523

250

题意：给定a, b, c, d和upperbound，统计1到upperbound范围内可以表示成ax+b或c*d^y的数的个数（x和y是非负整数）。a,b,c, upperbound<=10^12, d<=10^5。

分析：对于ax+b的形式，直接枚举。对于c*d^y的形式，当d=1时特殊处理，d>1时，d^y<=upperbound，非负整数y的个数不多，可以枚举，顺便判断一下是否在ax+b形式中已经统计过。

500

题意：有1*1*i(1<=i<=k)k种积木，以及一个1*1*w的基座，要求积木必须完全搭在其他积木之上，不能悬空。问高度不超过h的方案数。w,h<=50

分析：比较简单的DP，可以化为二维来看。对于一行中连续l个都被积木覆盖的情况，设g[l]为方案数，可递推求出。再设G[i][l]为第i~h层底部不超过l的方案数，则G[i][l]=∑g[k]*G[i+1][k]*G[i][l-k-1]

1000

题意：给一个棋盘，由21个字母（A B C D E F Z H I K L M N O P Q R S T V X）和“.”组成，问有多少条长度为21的不自交的有向路径，恰好包含这21中字母各一次？棋盘长w/宽h<=21

分析：一开始我想了各种状压DP，发现都浮云了。只好搜索，裸搜的复杂度大概是O(w*h*(3^20))，稳TLE。显然可以折半搜一搜，枚举一个中间点，搜两条半路径，两条路径上各含10个字母。具体来说，搜10步，得到若干条路径，记录下路上出现了哪些字母（保证路径合法），搜完枚举一下字母集合S1和S2，使它们互补且大小相同，统计一下即可。时间复杂度O(w*h*(3^10+2^20))。

链接http://apps.topcoder.com/wiki/display/tc/SRM+522

250

水，答案与A和B的段数有关，直接判断头尾即可。

500

题目大意：给定a，b，c，求A*B=C，使得修改量|A-a|+|B-b|+|C-c|最小。

分析：一个最简单的办法就是A=B=C=1，修改量为a+b+c-3。有了这个前提，c的改变量|C-c|肯定不超过a+b+c-3，所以，考虑A*B=C这个式子，最优解必然满足A*A<=C或B*B<=C，这样就可以枚举A和B中小一点的那个数（假设为A），那么修改b肯定比修改c优（因为修改b的话，c-A*b改变量为A，修改c的话，c-A*b该变量为1），所以可以求出最终B∈[c/A-1, c/A+1]，相应地算出C=A*B，再求当前该变量，取最优该变量即可。总复杂度O(sqrt(C))，C是输入数字的范围。

1000

题目大意：给平面上N个点，坐标为(x, y[x])，x={0, 1, 2, ..., n-1}。某人玩这样一个游戏：取两个点（未被擦去），以这两点为对角线画一个平行坐标轴的长方形，擦去严格在长方形内部的点。如此往复，直到无法再擦去任何一个点。问最终剩余点数的所有可能性。N<=50

分析：首先，最上、最下、最左和最右的点是绝对无法删除的（设最左和最右的点编号为L和R，最上和最下的点编号为U和D）。以这些边界点为对角线的矩形可以删掉除了x<min{x[U],x[D]}且y=y[L]和x>max{x[U],x[D]}且y=y[R]之外的所有点。于是问题转化为这样一个子问题：给一条直线上的一些点，以及一些擦除区间，问可能剩余多少个点未被擦除。子问题的解法可以用DP，F[i][j]表示第i个点之前保留j个点，枚举一下擦除区间。总复杂度O(N^3)。