赢球票
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片（上面写着 1~N 的数字），打乱顺序，排成一个圆圈。
你可以从任意一张卡片开始顺时针数数: 1,2,3.....
如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。
直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。
比如：
卡片排列是：1 2 3
我们从1号卡开始数，就把1号卡拿走。再从2号卡开始，但数的数字无法与卡片对上，
很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了1张球票。
还不算太坏！如果我们开始就傻傻地从2或3号卡片数起，那就一张卡片都拿不到了。
如果运气好，卡片排列是 2 1 3
那我们可以顺利拿到所有的卡片！
本题的目标就是：已知顺时针卡片序列。
随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）
输入数据：
第一行一个整数N(N<100)，表示卡片数目
第二行 N 个整数，表示顺时针排列的卡片
输出数据：
一行，一个整数，表示最好情况下能赢得多少张球票
比如：
用户输入：
3
1 2 3
程序应该输出：
1
比如：
用户输入：
3
2 1 3
程序应该输出：
6
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
package action; import java.util.Scanner; public class demo { public static int n; public static int max = 0; public static int[] value; public static void getResult() { for (int i = 0; i < n; i++) { int[] temp = new int[n]; for (int k = 0; k < n; k++) temp[k] = value[k]; int sum = 0; int count = 1; int start = i; while (true) { boolean judge = true; for (int k = 0; k < n; k++) if (temp[k] >= count) { judge = false; break; } if (judge) break; int j = start % n; if (temp[j] == count) { sum = sum + count; temp[j] = -1; count = 1; } else if (temp[j] != -1) count++; start++; } max = Math.max(max, sum); } System.out.println(max); } public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); value = new int[n]; for (int i = 0; i < n; i++) value[i] = in.nextInt(); getResult(); } }
E、路径之谜
小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入：
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出：
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....
比如，图1.png中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
示例：
用户输入：
4
2 4 3 4
4 3 3 3
程序应该输出：
0 4 5 1 2 3 7 11 10 9 13 14 15
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
碱基
生物学家正在对n个物种进行研究。
其中第i个物种的DNA序列为s[i]，其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。
生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组(i1,p1,i2,p2....im,pm)表示，
满足:
1<=i1<i2<....<im<=n;
且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=....=s[im][pm+q]。
现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。
【输入格式】
输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，意义如题目所述。
接下来n行，每行一个字符串表示一种生物的DNA序列。
DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，不同的生物的DNA序列长度可能不同。
【输出格式】
输出一个整数，表示关注的元组个数。
答案可能很大，你需要输出答案除以1000000007的余数。
【样例输入】
3 2 2
ATC
TCG
ACG
【样例输出】
2
再例如：
【样例输入】
4 3 3
AAA
AAAA
AAA
AAA
【样例输出】
7
【数据规模与约定】
对于20%的数据，k<=5,所有字符串总长L满足L <=100
对于30%的数据，L<=10000
对于60%的数据，L<=30000
对于100%的数据，n<=5,m<=5,1<=k<=L<=100000
保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
package action; import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; public class demo { public static int n, m, k; public static String[] S; public static String[] num; public static int[] start; public static long MOD = 1000000007; public static long count = 0; public static HashSet<String> result = new HashSet<String>(); public static void dfs(int step, int sum) { if (step == n || sum >= m) { if (sum >= m) { ArrayList<String> set = new ArrayList<String>(); StringBuffer[] s = new StringBuffer[sum]; for (int i = 0; i < sum; i++) s[i] = new StringBuffer(""); for (int i = 0; i < n; i++) { if (!num[i].equals("-")) { if (!set.contains(num[i])) { set.add(num[i]); s[set.size() - 1].append(i); s[set.size() - 1].append(start[i]); } else { int j = set.indexOf(num[i]); s[j].append(i); s[j].append(start[i]); } } } if (set.size() == sum - m + 1) { for (int i = 0; i < sum; i++) { if (s[i].toString().length() == k * 2) { if (!result.contains(s[i].toString())) count = (count + 1) % MOD; result.add(s[i].toString()); break; } } } } return; } else { for (int i = 0; i < S[step].length(); i++) { if (i + k <= S[step].length()) { num[step] = S[step].substring(i, i + k); start[step] = i; dfs(step + 1, sum + 1); num[step] = "-"; } dfs(step + 1, sum); } } } public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); k = in.nextInt(); S = new String[n]; for (int i = 0; i < n; i++) S[i] = in.next(); num = new String[n + 1]; start = new int[n + 1]; for (int i = 0; i <= n; i++) num[i] = "-"; dfs(0, 0); System.out.println(count); } }
