题目1
维护一个累加数组，sum[i]表示，从1到i的元素之和。从而当sum[i]-sum[j]为k的倍数的时候，从i到j就是一个满足条件的序列。用双层循环跑一遍就可以了。注意当i-j<=max的时候，已经不可能获取到比max大的序列了，直接break；
#include <stdio.h>
int main(){
long sum[10005];
int n,i,j,k;
long p;
scanf("%d",&n);
sum[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&p);
sum[i] = sum[i-1]+p;
}
scanf("%d",&k);
int max=0;
for(i=n;i>=1;i--){
for(j=0;j<i;j++){
if(i-j<=max) break;
if((sum[i]-sum[j])%k==0) {
max=i-j;
break;
}
}
if(max>=i) break;
}
printf("%d",max);
return 0;
}
题目2
老师不想自己改试卷，于是让大家互相改试卷。
把全班同学分为k组，每组有s(k)个同学，
老师先选择一个组i，将这个组的所有试卷s(i)份都收上来放在讲台上
然后再选择一个组j，从讲台上拿s(j)份试卷随机分给j组的同学，然后把j组的所有试卷收上来，放在讲台上试卷的最下方
……重复上述过程，
最后把剩余的试卷随机分给i组的s(i)个同学。
但是这样分配试卷是有缺陷的，比如：
1.有可能出现讲台上试卷不够的的情况
2.可能出现有的同学改到自己试卷的情况
题目给出k个组每个组同学的数量，请问是否可以找到一种策略使得不会出现缺陷
如果可以找到，输出"Yes"
否则输出"No"
对于这个题，我们先分析一下，
1.首先，老师选择的第一个组必须是数量最大的组；
假如我们选的第一组不是数量最大的组，对于接下来的每一个组，我们的操作都是先把讲台上的试卷减少s(i)份，然后再增加s(i)份，讲台上的试卷数量稳定是第一组的数量，当我们碰到数量比第一组大的组时，会出现缺少试卷的缺陷，所以老师选择的第一个组必须是数量最大的组；
2.第一组的数量必须小于等于剩下各组的和
如果第一组的数量大于剩下各组的和，那么把第一组的试卷分给剩下的每个组中的同学后，还有剩余，剩余的试卷再分给第一组，就会出现自己改自己试卷的情况，出现缺陷。
3.只要第一组是数量最大的组，那么剩下各组分试卷的顺序是无所谓的
因为我们选择的第一组是数量最大的组，所以讲台上试卷数量始终都会大于等于各组的数量，必然不会出现缺少试卷的情况
综上：这个题的焦点就在于最大数量的组是否小于等于剩下各组的和，那么这个问题就很简单了。题目太简单就不给代码了。
题目3
圆桌上放了一圈红包形成环形，每个红包金额不同，围绕圆桌走一圈选择若干红包，规则是不能拿相邻的红包，请问拿到红包最多的总金额是多少？
输入：
整数T，表示T组数据
T行数组，每行表示一组红包
输出：
最多的总金额
样例输入：
2
1，2
1，3，4
样例输出：
2
4
解题思路：
1.将环状结构转化为线性结构；
2.运用动态规划求解最优解决方案；
解析：
将环状结构转化为线性结构：对于第一个和最后一个，两个不可能同时取，所以问题可以转化为不取第一个和不取最后一个的最大值，即f(0,len-1) = f(1,len-1)+f(0,len-2);
动态规划：假设起点相同，对于f(n) = max{ f(n-2),f(n-3) } + a[n] (n>3)。因为对于任何一个位置的红包，假设前面有大于等于三个的红包没有取，那么这些红包得中间可以多取至少一个红色，则这时候就不是最大值。所以要取n位置的红包，它的前面只可能是一个红包没取，或者两个红包没取，就是f(n-2)和f(n-3)的状态。
代码示例如下：
import java.util.Scanner;
public class RedBag {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
for(int i = 0; i < n; i++){
String s = sc.next();
String[] ss = s.split(",");
int[] arr = new int[ss.length];
for(int j = 0; j < ss.length; j++)
arr[j] = Integer.parseInt(ss[j]);
System.out.println(redBag(arr));
}
}
}
public static int redBag(int[] arr){
if(arr.length == 1) return arr[0];
return Math.max(search(arr, 0,arr.length - 2), search(arr, 1, arr.length - 1));
}
public static int search(int[] a,int start,int j){
if(j<start)return 0;
return Math.max(search(a, start, j-2),search(a, start, j-3))+a[j];
}
}
题目4-求所有能被7整除的数
分析：
方法一：采用暴力解法，即两两数字都组合一遍对7取余判断的方法，算法复杂度O(n2),会超时，提交成功率为70%。
方法二：求一个数A前面拼接上什么数能够被7整除，只需进行以下操作即可：
①数A前面依次拼上0~6,变为0A，1A，2A···6A。
②依次判断这7个数能否被7整除
③以1A为例，若1A等被7整除，则A前面拼的数B，只要满足B%7==1，则BA能被7整除，因为B%7==1，所以BA总能转化为1A，即BA也能被7整除。
于是，解题过程：
首先，记录一个数组sum[7]，用sum[i]来记录这些数中余数为i的个数
然后，遍历一遍这些数，对于每一个数A，判断0A，1A，2A···6A是否能够被7整除，例如iA能够整除，总个数total+=sum[i]；
最后，输出total；
题目5
n个灯泡，从左排到右排成一行，初始时，有些灯泡是亮的，有些是熄灭的。接下来，Alice和Bob轮流进行操作，Alice先开始。每次操作中，轮到操作的人需要选择一个点亮的灯泡，然后把它以及它之后的所有灯泡的状态都变换一次。如果在某个人操作之后，所有的灯泡都熄灭了，那么这个人就赢得了游戏。Alice和Bob都想赢得这个游戏，在他们足够聪明的情况下，最后谁会赢？
输入：
第一行包含一个整数n，表示灯泡的个数。1<=n<=10^5
第二行包含n个0或1，表示初始时灯泡的状态，0表示熄灭，1表示点亮
输出：
如果Alice赢，则输出Alice，或则输出Bob
事实上，不管Alice还是Bob做了什么操作，最后一个灯泡肯定是要来回切换的，用0、1分别代表熄灭和亮起的状态，则为0、1来回变换；所以只有能把1变为0的人，才能赢。也就是只需要判断最后一位输入是1，就是Alice赢，是0就是Bob赢。
题目6-字符串距离
给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符的数量。如串”aab”与串”aba”的距离为 2；串”ba”与串”aa”的距离为 1；串”baa”和串”baa”的距离为 0。下面给出两个字符串 S 与 T，其中 S 的长度不小于 T 的长度。我们用|S|代表 S 的长度，|T|代表 T 的长度，那么在 S 中一共有|S|-|T|+1 个与T长度相同的子串，现在你需要计算 T 串与这些|S|-|T|+1 个子串的距离的和。
输入描述：
第一行包含一个字符串 S。第二行包含一个字符串 T。S 和 T 均由字符 a 和 b 组成，1 ≤ |T| ≤ |S| ≤105 。
输出描述：
输出对应的答案。
样例：
in:
aab
aba
out:
2
in:
aaabb
bab
out:
5
#include <stdio.h>
#include <string.h>
int main(){
char s[200],t[200];
scanf("%s%s",s,t);
int lens = strlen(s),lent = strlen(t),i;
int a=0,b=0;
for(i=0;i<lens-lent+1;i++)
s[i]=='a'?a++:b++;
int ans = 0;
for(i=0;i<lent;i++){
ans+=t[i]=='a'?b:a;
s[i]=='a'?--a:--b;
s[lens-lent+1+i]==a?++a:++b;
}
printf("%d",ans);
return 0;
}
题目7-数字字符
在十进制表示中，任意一个正整数都可以用字符‘0’-‘9’表示出来。但是当‘0’-‘9’这些字符每种字符的数量有限时，可能有些正整数就无法表示出来了。比如你有两个‘1’，一个‘2’ ，那么你能表示出 11，12，121 等等，但是无法表示出 10，122，200 等数。
现在你手上拥有一些字符，它们都是‘0’-‘9’的字符。你可以选出其中一些字符然后将它们组合成一个数字，那么你所无法组成的最小的正整数是多少？
输入描述：
第一行包含一个由字符’0’-‘9’组成的字符串，表示你可以使用的字符。1 ≤ 字符串长度 ≤ 1000
输出描述：
输出你所无法组成的最小正整数。
样例：
in:
55
out:
1
in:
123456789
out:
10
先统计1 - 9的个数，然后找出里面的最小值，最小值表示这些数字至少能凑出几位数(这里还没有考虑字符0)，然后看下0字符的个数是不是大于等于最小值减一，这里举个例子说明后面的步骤，比如1 - 9每个字母都有3个，0有3个，1111和10000都是不可以凑出来的，答案就是1111；比如1 - 9每个字母都有3个，0只有2个，那么1111和1000都是不可以凑出来的，答案就是1000。
#include <stdio.h>
#include <string.h>
int num[10];
int main(){
char str[200];
scanf("%s",&str);
int i;
for(i=0;i<strlen(str);i++){
num[str[i]-'0']++;
}
int index=1;
int min = num[1];
for(i=2;i<10;i++){
if(num[i]<min){
min = num[i];
index = i;
}
}
int ans = 0;
if(num[0]>=min) {
ans = index;
for(i=1;i<=min;i++){
ans = ans*10+index;
}
}else{
ans = 1;
for(i=0;i<=num[0];i++){
ans = ans*10;
}
}
printf("%d",ans);
return 0;
}
