BestCoder 百度之星2016

20160523 百度之星初赛第一场

1001 All X

思路：对于m个x组成的数，这个数太大无法直接计算。所以应该从另外的角度考虑问题。

　　首先我们得明确对于乘法和加法的求模运算，可以先乘（加）后模或者先模后乘（加），所得结果是一样的。比如(a*b)%c == ((a%c) * (b%c))%c; (a+b)%c =(a%c+b%c)%c.

　　所以这一题我们可以转化到求m个1组成的数对k的余数，同样的这个数也很大，但是k的范围不大，我们知道余数的个数最多是k个不同的值，所以余数是有周期的或者说从某一个数开始会循环。我们需要找到周期开始和周期结束的位置。假设 a个1对k的余数是 ak，1的个数不断增加，直到b个1对k的余数 bk == ak；就会得出周期开始是a个1，周期结束是b-1个1.此后，无论1的个数增加到多少，都是在a~b-1这个区间内，区间长度为 b-a。

　　当有m个数时，m < b时，余数即第m个；m>b时，余数在(m-b)%(b-a)+a 这个位置。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main{
     public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int t = in.nextInt();
                for (int i = 1; i <= t; i++) {
                    int x = in.nextInt();
                    long m = in.nextLong();
                    int k = in.nextInt();
                    int c = in.nextInt();
                    
                    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
                    int[] ref = new int[k + 1];
                    int allOne = 1;
                    int index = 1;
                    //计算1~index个1对k的余数，余数个数最多为k个，所以肯定从某个位置开始有周期，找出周期
                    //某个余数第二次出现了，这就是周期开始位置
                    while (!map.containsKey(allOne)) {
                        map.put(allOne, index);
                        ref[index++] = allOne;
                        allOne = (allOne * 10 + 1) % k;
                    }
                    int start = map.get(allOne);//周期开始的位置，map的最后一项是周期结束的位置
                    int period = index - start;//周期长度
                    System.out.println("Case #" + i + ":");
                    int res = 0;
                    if (m < index) {
                        res = (ref[(int) m] * x) % k; //转化成m个x的余数
                    } else {
                        res = (ref[(int)((m - index) % period + start)] * x) % k;
                    }
                    System.out.println(res == c ? "Yes" : "No");
                }
            }
     }
}

20160514 百度之星资格赛

Problem A

度熊手上有一本字典存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串。现在麻烦来了，他忘记了原来的字符串都是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到：

$H(s)=prod_{i=1}^{ileq len(s)}(S_{i}-28) (mod 9973)H(s)=∏i=1i≤len(s)(Si−28) (mod 9973)$

$S_{i}Si代表 S[i] 字符的 ASCII 码。$

请帮助度熊计算大字符串中任意一段的哈希值是多少。

6891
9240
88



思路：本题要用到乘法逆元+ 费马小定理+快速模取幂算法，这三个之前都没有接触过，这里总结一下
1.乘法逆元
　　满足 a*k≡1 (mod p)的k值就是a关于p的乘法逆元。也就是a*k mod p = 1。
什么时候要用到乘法逆元呢？
当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。

证：（其实很简单。。。）
根据b*k≡1 (mod p)有b*k=p*x+1。
k=(p*x+1)/b。
把k代入(a*k) mod p，得：
(a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//p*[(a*x)/b] mod p=0
所以原式等于：(a/b) mod p

这一题中就是要求（a/b） mod p （p = 9973），那么怎么去求这个乘法逆元呢，这里就要用到费马小定理。
2.费马小定理
--百度百科（http://baike.baidu.com/link?url=L9XOakOsc-s9IK8cnRHJCh060JnJYbIDhkNpVqnIynK1b8_lC3pDALOoSiUa4CRsz9ZXHp2xKp_tVD9IEn9BSa）
费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a(p-1)≡1（mod p）。
即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
这里p = 9973，所以a的乘法逆元也就是 a^(p-2),所以我们要求这个（同时也要mod 9973）。

3.要求 a^b % c的时候，当然可以直接循环然后每一步都mod c，这样的复杂度就是O(b)了，但是快速模取幂算法可以降低复杂度。


描述如下：

可以把b按二进制展开为：b = p(n)*2^n + p(n-1)*2^(n-1) +…+ p(1)*2 + p(0)

　　其中p(i) (0<=i<=n)为 0 或 1

　　样 a^b = a^ (p(n)*2^n + p(n-1)*2^(n-1) +...+ p(1)*2 + p(0))
= a^(p(n)*2^n) * a^(p(n-1)*2^(n-1)) *...* a^(p(1)*2) * a^p(0)
　　对于p(i)=0的情况, a^（p(i) * 2^(i-1) ） = a^0 = 1,不用处理
　　我们要考虑的仅仅是p(i)=1的情况
　　化简：a^(2^i) = a^(2^(i-1) * 2) = ( a^( p(i) * 2^(i-1) ) )^2
　　（这里很重要！！具体请参阅秦九韶算法：http://baike.baidu.com/view/1431260.htm）

　　利用这一点，我们可以递推地算出所有的a^(2^i)
　　当然由算法1的结论，我们加上取模运算：
　　a^(2^i)%c = ( (a^(2^(i-1))%c) * a^(2^(i-1))) %c

相应的算法将在这道题的AC代码中写出。

import java.util.Scanner;

public class Main {
    
    static int[] H =  new int[100001];
    static int mods = 9973;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int N = sc.nextInt();
            String str = sc.next();
            
            getHashFactor(str);
            for (int i = 0; i < N; i++) {
                int begin = sc.nextInt() -1;
                int end = sc.nextInt() ;
                System.out.println(getHashCode(begin,end));
            }
        }
    } 
    //保存从开始到当前位置前面字符串的hash值
    private static void getHashFactor(String ss) {
        int len = ss.length();
        H[0] = 1;
        for(int i = 1;i <= len;i ++){
            H[i] = H[i - 1] * (ss.charAt(i-1) - 28) % mods;
        }
    }
    //利用费马小定理和乘法逆元
    private static int getHashCode(int begin,int end) {
        return (int) (H[end]*mod_pow(H[begin], mods-2, mods)%mods);
    }
    //快速模取幂算法
    private static long mod_pow(long x, long n, long mod) {
        long res = 1;
        while(n > 0) {
            if((n & 1) != 0) res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
}

Problem D

度熊所居住的 D 国，是一个完全尊重人权的国度。以至于这个国家的所有人命名自己的名字都非常奇怪。一个人的名字由若干个字符组成，同样的，这些字符的全排列的结果中的每一个字符串，也都是这个人的名字。例如，如果一个人名字是 ACM，那么 AMC， CAM， MAC， MCA，等也都是这个人的名字。在这个国家中，没有两个名字相同的人。

度熊想统计这个国家的人口数量，请帮助度熊设计一个程序，用来统计每一个人在之前被统计过多少次。

0
1
0
2
1


思路：关键要想到java里面Arrays.sort()函数可以将字符数组按照ascii码排序。排序之后，同一个名字所组成的字符串就相同了，
再利用HashMap，键记录名字，值记录当前已出现的次数，每遇到一次就把值加一，更新map里的值部分。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String args[]) throws IOException{
        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(is);
        String str = "";
        while ((str = br.readLine()) != null) {
            int n = Integer.valueOf(str);
            Map<String,Integer> m = new HashMap<String,Integer>();            
            for (int i = 0; i < n; i++) {
                char[] sa = br.readLine().toCharArray();
                Arrays.sort(sa);
                String sorted = new String(sa); 
                if (m.containsKey(sorted)) {
                    m.put(sorted, m.get(sorted)+1);
                    System.out.println(m.get(sorted));
                } else {
                    m.put(sorted, 0);
                    System.out.println(0);
                }
            }
        }
    }
}

需要注意的是 Map里面存储的是对象，所以在将排序好的字符数组put进map的时候，需要 新建String对象，而不能直接put，要不然无法判断是否相等，
在利用equals函数判断时，也是如此。看下面的代码即可。

public class Main {
    public static void main(String args[]) throws IOException{
        String a = "ss";
        String b = "ss";
        char[] arr = {'s','s'};
        String c = arr.toString();
        String d = new String(arr);
        if (a.equals(b))
            System.out.println("a == b");
        else 
            System.out.println("a != b");
        if (a.equals(c))
            System.out.println("a == c");
        else
            System.out.println("a != c");
        if (a.equals(d))
            System.out.println("a == d");
        else 
            System.out.println("a != d");
        if (c.equals(d))
            System.out.println("c == d");
        else
            System.out.println("c != d");
        if ("ss".equals("ss"))
            System.out.println("ss == ss");
        else
            System.out.println("ss != ss");        
    }
}

打印结果是：

a == b
a != c
a == d
c != d
ss == ss

Problem B

思路：找规律发现就是求斐波那契数列的值。陷阱在于如果使用long类型来保存结果会越界，所以要用BigInteger，还要注意保存之前的结果，就像测试赛的第一题。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int max = 1;
        System.out.println(Long.MAX_VALUE);
        BigInteger[] bi = new BigInteger[201];
        bi[0] = new BigInteger("1");
        bi[1] = new BigInteger("1");
        while (sc.hasNext()) {
            int n = sc.nextInt();
            while (n > max) {
                bi[max+1] = bi[max].add(bi[max-1]);
                max++;
            }
            System.out.println(bi[n]);
        }
    }
}

2016 0510 百度之星测试赛

1004 放盘子

小度熊喜欢恶作剧。今天他向来访者们提出一个恶俗的游戏。他和来访者们轮流往一个正多边形内放盘子。最后放盘子的是获胜者，会赢得失败者的一个吻。玩了两次以后，小度熊发现来访者们都知道游戏的必胜策略。现在小度熊永远是先手，他想知道他是否能获胜。

注意盘子不能相交也不能和多边形相交也不能放在多边形外。就是说，盘子内的点不能在多边形外或者别的盘子内。

思路：不得不说最后的Hint至关重要，差点就蒙了。想通了之后非常简单，就是判断所给圆半径是否不大于正多边形的内切圆半径，不大于的话就会赢，反之则会输。

　　因为不大于的时候，先手总是可以把盘子放在中心，然后在对称位置放置盘子就好了。反之，则一个盘子也放不进去，所以就会输。

import java.util.Scanner;

public class Main {
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();
            for (int i = 1; i <= t; i++) {
                int n = sc.nextInt();
                double a = sc.nextDouble();
                double r = sc.nextDouble();
                double ra = a/2 * 1/Math.tan(Math.PI/n);
                System.out.println("Case #"+i+":");
                if(ra >= r)
                    System.out.println("Give me a kiss!");
                else
                    System.out.println("I want to kiss you!");
            }
        }
    }
}

1003 IP聚合

第一行包含一个整数

接下来

第一行两个正整数

再接下来

Case #1:
3
2
Case #2:
3
4

其实是一个很简单的题，但是容易掉进思维陷阱（当然可能是我太笨了）。一开始想的是将ip分段与掩码按位与，再分段比较。
　　　　再将前一段相同的ip再去比较下一段，思考了半天，这样太复杂，估计会超时，实现起来也有难度。
正确的思路：将每一个ip和子网掩码组合成int类型，int类型也是32位，ip和子网掩码都是32位，所以通过移位操作刚好能组合成int，
再将组合之后的int类型的ip与子网掩码按位与，结果放入set里面，set的大小即结果了。

import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String []args) throws IOException{
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();
            for (int i = 1; i <= t; i++) {
                int n = sc.nextInt();
                int m = sc.nextInt();
                sc.nextLine();
                String[] ips = new String[4];
                String[] masks = new String[4];
                int[] ipToInt = new int[n];
                for (int j = 0; j < n; j++) {
                    ips = sc.nextLine().split("\.");
                    //这种写法比较好
                    for (String ip : ips) {
                        ipToInt[j] = (ipToInt[j]<<8) + Integer.valueOf(ip);
                    }
                }
                System.out.println("Case #"+i+":");
                int[] ans = new int[m]; 
                for (int j = 0; j < m; j++) {
                    masks = sc.nextLine().split("\.");
                    //这种写法必须加括号
                    int maskToInt =  (Integer.valueOf(masks[0])<<24) + 
                            (Integer.valueOf(masks[1])<<16) +
                            (Integer.valueOf(masks[2])<<8) +
                            (Integer.valueOf(masks[3]));
                    Set<Integer> set = new HashSet<Integer>();
                    for (int k = 0; k < n; k++) {
                        set.add(ipToInt[k] & maskToInt);
                    }
                    ans[j] = set.size();                
                }
                for (int j = 0; j < m; j++) {
                    System.out.println(ans[j]);
                }
            }
        }
    }    
}

代码中需要注意的就是　　1.ip组合成int时的写法，代码中有两种方式，第二种方式必须加括号，要不然结果不正确。

　　　　　　　　　　　　2.split函数分割点时，记得加上转义符“\”。

1002 列变位法解密

列变位法是古典密码算法中变位加密的一种方法，具体过程如下将明文字符分割成个数固定的分组（如5个一组，5即为密钥），按一组一行的次序整齐排列，最后不足一组不放置任何字符，完成后按列读取即成密文。

比如：

原文：123456789

密钥：4

变换后的矩阵：

1234

5678

9xxx

（最后的几个x表示无任何字符，不是空格，不是制表符，就没有任何字符，下同）

密文：159263748

再比如：

原文：Hello, welcome to my dream world!

密钥：7

变换后的矩阵：

Hello,

welcome

to my

dream w

orld!xx

密文：

Hw doeetrrlloellc adoomm!,my e w

实现一个利用列变位法的加密器对Bob来说轻而易举，可是，对Bob来说，想清楚如何写一个相应的解密器似乎有点困难，你能帮帮他吗？

思路：属于一看题就知道大概的思路的，但是bug-free对于我来说写起来还有难度。调试了好多遍才成功，边界情况处理的不是很好，暂时不想再研究了，好歹也是过了。
值得注意的地方是StringBuilder的使用，如果是直接新建一个String的话，会超时。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String str = "";
        while ((str = br.readLine()) != null) {
            int t = Integer.parseInt(str);
            for (int i = 1; i <= t; i++) {
                String s = br.readLine();
                int k = Integer.parseInt(br.readLine());
                if (k >= s.length() || k == 1) {
                    System.out.println("Case #"+i+":");
                    System.out.println(s);
                } else {
                    int mod = s.length() % k;
                    int row = s.length() / k;
                    if (mod != 0) {
                        row++;                        
                    } else {
                        mod = k;
                    }                        
                    int j = 0,p = 0,l = 0;
                    StringBuilder sb = new StringBuilder();
                    while ( p < row) {
                        l = 0;
                        while (l <= mod) {
                            sb.append(s.charAt(l*row+p));
                            j = l*row+p;
                            l++;
                            if (l == mod && (p == row-1 || mod == k))
                                break;                            
                        }
                        if (sb.length() == s.length())
                            break;
                        while ((j+row-1 < s.length()) && (mod != k)) {
                            sb.append(s.charAt(j+row-1));
                            j = j+row-1;
                        }
                        p++;
                    }
                    System.out.println("Case #"+i+":");
                    System.out.println(sb.toString());
                }                
            }
        }
    }    
}

1001 大搬家

近期B厂组织了一次大搬家，所有人都要按照指示换到指定的座位上。指示的内容是坐在位置

在第一次搬家后，度度熊由于疏忽，又要求大家按照原指示进行了一次搬家。于是，机智的它想到：再按这个指示搬一次家不就可以恢复第一次搬家的样子了。于是，B厂史无前例的进行了连续三次搬家。

虽然我们都知道度度熊的“机智”常常令人堪忧，但是不可思议的是，这回真的应验了。第三次搬家后的结果和第一次的结果完全相同。

那么，有多少种指示会让这种事情发生呢？如果两种指示中至少有一个人的目标位置不同，就认为这两种指示是不相同的。

Case #1:
1
Case #2:
4

思路：直接想的可能是怎么才能搬家三次的结果和搬家一次的结果相同，但是实际上可以简化为搬家两次的结果和搬家之前相同。
要出现这样的情况，那第一次搬家i-j必须满足i==j或者i-j&&j-i(i!=j).
当给定为N个人搬家时有ans[N]种满足条件的可能，假设第一个人是1-1，也就是位置不变，那么剩下的人可能的情况就是ans[N-1]种。
当第一个人是1-j(j!=1)时，那么必定有j-1。所以还剩下N-2个人，所以就是ans[N-2]，又因为此时j有N-1(2-N)种可能。
可得出dp公式 ans[N] = ans[N-1] + (N-1)*ans[N-2];
初始值ans[1] = 1；ans[2] = 2;利用递归或者dp即可解决，但是递归会超时，dp才是正道。

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();            
            long[] ans = new long[1000001];
            long mod = 1000000007l;
            ans[1] = 1;
            ans[2] = 2;
            int m = 3;
            for (int i = 1; i <= t; i++) {
                int n = sc.nextInt();                
                while (m <= n) {
                    ans[m] = mod(ans[m-1] + (m-1)*ans[m-2]); //用mod函数会稍微快点，但是不影响结果
                    m++;
                }
                System.out.println("Case #"+i+":");
                System.out.println(ans[n]);
//     　　　　    System.out.println("Case #"+i+":
"+ans[n]);//这种形式会报格式错误
            }
        }
    }
    public static long mod(long i) {
        return i%1000000007;
    }
}

/**TLE 递归影响时间,改成dp

public static int find(int n) {
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    else 
        return mod(find(n-1))+mod((n-1)*find(n-2));            
}
*/

代码中的斜体部分应该放到for循环外，这样就可以保存ans[]数组的结果，在下一个测试用例时就可以直接利用了，如果放在for循环内，就会超时。

ps：最后的打印换成代码中的另一种形式就会格式错误Presentation Error，不知道为什么。