C. C. Blog

Problem

一个字符串t是半回文的条件是，对于所有的奇数𝑖(1≤𝑖≤|𝑡|+12)，𝑡𝑖 = 𝑡|𝑡| − 𝑖 + 1 始终成立，|t|表示字符串t的长度。下标从1开始。例如"abaa", "a", "bb", "abbbaa"都是半回文，而"ab", "bba"和"aaabaa"则不是。

现在有一个字符串s，只由小写字母a,b构成，还有一个数字k。现在要求找出s的半回文子串中字典序排在第k位的串，字符串可以是一样，只要所在的位置不同就是不一样的串。

样例解释：

这个样例中半回文子串是 a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab,bab, bb, bbab, bbabaab (按照字典序排序).

Problem

很久很久以前的一天，一位美男子来到海边，海上狂风大作。美男子希望在海中找到美人鱼，但是很不幸他只找到了章鱼怪。

然而，在世界的另一端，人们正在积极的收集怪物的行为信息，以便研制出强大的武器来对付章鱼怪。由于地震的多发，以及恶劣的天气，使得我们的卫星不能很好的定位怪物，从而不能很好的命中目标。第一次射击的分析结果会反映在一张由n个点和m条边组成的无向图上。现在让我们来确定这张图是不是可以被认为是章鱼怪。

为了简单起见，我们假设章鱼怪的形状是这样，他有一个球形的身体，然后有很多触须连接在他的身上。可以表现为一张无向图，在图中可以被认为由三棵或者更多的树（代表触须）组成，这些树的根在图中处在一个环中（这个环代表球形身体）。

题目保证，在图中没有重复的边，也没有自环。

Problem

每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法，例如：14 = 13 + 1 = 8 + 5 + 1，其中13 + 1是最短的表示（只用了2个斐波那契数）。定义F(n) = n的最短表示中的数字个数，F(14) = 2，F(100) = 3（100 = 3 + 8 + 89），F(16) = 2（16 = 8 + 8 = 13 + 3）。定义G(n) = F(1) + F(2) + F(3) + ...... F(n)，G(6) = 1 + 1 + 1 + 2 + 1 + 2 = 8。给出若干个数字n，求对应的G(n)。

Problem

有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角走到右下角的方案数。（只能向右和向下走）

Problem

现在有两个块巧克力一块大小是𝑎1 × 𝑏1 的，另外一块大小是𝑎2 × 𝑏2 的。

现在要把两块巧克力变成面积一样大小，可以使用下列两种方法：

· 可以沿横向或纵向的网格线分成两等分，然后吃掉其中的一份。

· 可以沿横向或纵向的网格线分成2/3,1/3的两份，吃掉小的那一份。

因此使用第一种方法会留一半巧克力，用第二种方法会留下2/3巧克力。

两种方法并不总是可行的，有些时候两种方法都不能再用了。比如巧克力大小是16 × 23的时候，可以使用第一种方法，但是不能使用第二种方法。当大小是20 × 18的时候，可以使用第一种方法或者第二种方法。如果大小是5 × 7的时候，两种方法都不能使用。

问最少要操作几次才能使得两块巧克力的面积是一样的。

Problem

给出n个正整数，从中挑选若干个，使得他们的和为m。如果存在多个，输出排序后字典序最小的一组。如果没有找到任何一组，输出"No Solution"。

Problem

lyk最近在研究二分答案类的问题。

对于一个有n个互不相同的数且从小到大的正整数数列a（其中最大值不超过n），若要找一个在a中出现过的数字m，一个正确的二分程序是这样子的：

1
2
3
4
5
6
7
8
9
10

l=1; r=n; mid=(l+r)/2;
while (l<=r)
{
    if (a[mid]<=m) 
        l=mid+1; 
    else
        r=mid-1;

    mid=(l+r)/2;
}

最终a[r]一定等于m。

但是这个和谐的程序被熊孩子打乱了。

熊孩子在一开始就将a数组打乱顺序。（共有n!种可能）

lyk想知道最终r=k的期望。

由于小数点非常麻烦，所以你只需输出将答案乘以n!后对1000000007取模就可以了。

在样例中，共有2个数，被熊孩子打乱后的数列共有两种可能(1,2)或者(2,1)，其中(1,2)经过上述操作后r=1，(2,1)经过上述操作后r=0。r=k的期望为0.5，0.5*2!=1，所以输出1。

Problem

一个字符串是非回文的，当且仅当，他只由前p个小写字母构成，而且他不包含长度大于等于2的回文子串。

给出长度为n的非回文串s。请找出字典序比s大的，而且字典序要最小的长度为n的非回文。

Problem

阿P给阿K出了一个难题，他给阿K两个素数A,B，保证A，B的位数相同且为4位或5位。

阿K只能对A作一种操作，即将其中一位数字改成另一个数字，要求每次操作后得到的数还是一个素数，问最少多少次可以从A变到B

Problem

给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示只包含0或1。求最小的M。 例如：N = 4，M = 100。