题目1

image.png

维护一个累加数组，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整除的数

image.png

分析：
方法一：采用暴力解法，即两两数字都组合一遍对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;
}