2015 ACM-ICPC 上海邀请赛 迭代解决

B.Base64

• Problem Description
  Mike does not want others to view his messages, so he find a encode method Base64.
  Here is an example of the note in Chinese Passport.
  The Ministry of Foreign Affairs of the People’s Republic of China requests all civil and military authorities of foreign countries to allow the bearer of this passport to pass freely and afford assistance in case of need.

When encoded by Base64, it looks as follows

VGhlIE1pbmlzdHJ5IG9mIEZvcmVpZ24gQWZmYWlycyBvZiB0aGUgUGVvcGxlJ3MgUmVwdWJsaWMgb2Yg
Q2hpbmEgcmVxdWVzdHMgYWxsIGNpdmlsIGFuZCBtaWxpdGFyeSBhdXRob3JpdGllcyBvZiBmb3JlaWdu
IGNvdW50cmllcyB0byBhbGxvdyB0aGUgYmVhcmVyIG9mIHRoaXMgcGFzc3BvcnQgdG8gcGFzcyBmcmVl
bHkgYW5kIGFmZm9yZCBhc3Npc3RhbmNlIGluIGNhc2Ugb2YgbmVlZC4=

In the above text, the encoded result of The is VGhl. Encoded in ASCII, the characters T, h, and e are stored as the bytes 84, 104, and 101, which are the 8-bit binary values 01010100, 01101000, and 01100101. These three values are joined together into a 24-bit string, producing 010101000110100001100101.
Groups of 6 bits (6 bits have a maximum of 2^6 = 64 different binary values) are converted into individual numbers from left to right (in this case, there are four numbers in a 24-bit string), which are then converted into their corresponding Base64 encoded characters.
The Base64 index table is

0123456789012345678901234567890123456789012345678901234567890123
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

In the above example, the string 010101000110100001100101 is divided into four parts 010101, 000110, 100001 and 100101, and converted into integers 21, 6, 33 and 37. Then we find them in the table, and get V, G, h, l.
When the number of bytes to encode is not divisible by three (that is, if there are only one or two bytes of input for the last 24-bit block), then the following action is performed:
Add extra bytes with value zero so there are three bytes, and perform the conversion to base64. If there was only one significant input byte, only the first two base64 digits are picked (12 bits), and if there were two significant input bytes, the first three base64 digits are picked (18 bits). ‘=’ characters are added to make the last block contain four base64 characters.
As a result, when the last group contains one bytes, the four least significant bits of the final 6-bit block are set to zero; and when the last group contains two bytes, the two least significant bits of the final 6-bit block are set to zero.
For example, base64(A) = QQ==, base64(AA) = QUE=.
Now, Mike want you to help him encode a string for k times. Can you help him?
For example, when we encode A for two times, we will get base64(base64(A)) = UVE9PQ==.

• Input
  The first line contains an integer T(T≤20) denoting the number of test cases.
  In the following T lines, each line contains a case. In each case, there is a number k(1≤k≤5) and a string s. s only contains characters whose ASCII value are from 33 to 126(all visible characters). The length of s is no larger than 100.

• Output
  For each test case, output Case #t:, to represent this is t-th case. And then output the encoded string.

• Sample Input
  2
  1 Mike
  4 Mike

• Sample Output
  Case #1: TWlrZQ==
  Case #2: Vmtaa2MyTnNjRkpRVkRBOQ==

粗暴的模拟题，但是赛场上的做法简直一根筋；
修正……

/**
 * 2015年7月14日 下午2:56:01
 * PrjName:hdu5237
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

	final static String code = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

	static String encode(String str) {
		String res = new String();
		int ch1 = 0, ch0, pos = 0;
		for (int i = 0; i < str.length(); i++) {
			ch0 = ch1;
			ch1 = str.charAt(i);

			switch (i % 3) {
			case 0:
				pos = ch1 >> 2;
				res += code.charAt(pos);
				break;
			case 1:
				pos = ((ch0 & 3) << 4) + ((ch1 & ~3) >> 4);
				res += code.charAt(pos);
				break;
			case 2:
				pos = ((ch0 & 15) << 2) + ((ch1 & ~15) >> 6);
				res += code.charAt(pos);
				pos = ch1 & 63;
				res += code.charAt(pos);
				break;
			}
		}
		if (str.length() % 3 == 2) {
			ch1 = str.charAt(str.length() - 1);
			pos = (ch1 & 15) << 2;
			res += code.charAt(pos);
			res += '=';
		} else if (str.length() % 3 == 1) {
			ch1 = str.charAt(str.length() - 1);
			pos = (ch1 & 3) << 4;
			res += code.charAt(pos);
			res += "==";
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		int T = in.nextInt(), cas = 0;
		while (T-- > 0) {
			int k = in.nextInt();
			String s = new String(in.next());
			for (int i = 1; i <= k; i++)
				s = encode(s);
			out.println("Case #" + (++cas) + ": " + s);

		}
		out.flush();
		out.close();
	}

}

#D.Doom
本题的唯一（赛场上难以发现的）突破口就是，输入数据任给的正整数，经过不超过30次“平方再取模”操作后都成为某一定值。
也有特别的卡long long边界而不卡unsigned long long的现象，Java中不存在无符号类型因而无法实现。

#E.Exam
贪心。。。

/** Sep 6, 2015 8:40:50 PM
 * PrjName:hdu5240
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    /**
     * @param args
     */
    static ArrayList<Data> vec=new ArrayList<Data>();
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int n=in.nextInt();
            int s=0,last=0;
            boolean ans=true;
            vec.clear();
            for(int i=1;i<=n;i++){
                int r=in.nextInt();
                int e=in.nextInt();
                int l=in.nextInt();
                vec.add(new Data(r, e, l));
            }
            vec.sort(new DataComp());
            for(int i=0;i<vec.size();i++){
                int r=vec.get(i).r;
                int e=vec.get(i).e;
                int l=vec.get(i).l;
                //out.println(r+" "+e+" "+l);
                s+=r;
                if (s>e){
                    ans=false;break;
                }
                s+=l;
            }
            out.println("Case #"+(++cas)+": "+(ans?"YES":"NO"));
        }
        out.flush();
        out.close();
    }
}
class Data{
    int r,e,l;
    Data(int _r,int _e,int _l){
        r=_r;
        e=_e;
        l=_l;
    }
}
class DataComp implements Comparator<Data>{
    @Override
    public int compare(Data d1,Data d2){
        return Integer.compare(d1.e, d2.e);
    }
}

#F.Friends
必须及时通过必要的暴力模拟来找出这个千呼万唤不出来的规律

/**
 * 2015年7月27日 上午11:25:38
 * PrjName:hdu5241
 * @ Semprathlon
 */
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
	static BigInteger TWO=new BigInteger("2");
	public static void main(String[] args) {
		InputReader in=new InputReader(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int T=in.nextInt(),cas=0;
		while(T-->0){
			int n=in.nextInt();
			out.println("Case #"+(++cas)+": "+TWO.pow(n*5));
		}
		out.flush();
		out.close();
	}

}

#J.Joyful
赛场上耗费不少精力的题。。。
我无论是赛中还是赛后都没明白一点：对一个矩形区域涂色次数的期望，就是对该区域各点涂色期望之和。
写代码时轻视了多个int类型值相乘越界的问题

/** Sep 6, 2015 9:26:29 PM
 * PrjName:hdu5245
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    /**
     * @param args
     */
    static double pow(double n, int m) {
        double res = 1;
        while (m > 0) {
            if ((m & 1) > 0)
                res = res * n;
            n = n * n;
            m >>= 1;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int m=in.nextInt();
            int n=in.nextInt();
            int k=in.nextInt();
            double ans=0;
            for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++){
                    double s=0;
                    s+=(double)(i-1)*(i-1)*n*n;
                    s+=(double)(m-i)*(m-i)*n*n;
                    s+=(double)m*m*(j-1)*(j-1);
                    s+=(double)m*m*(n-j)*(n-j);
                    s-=(double)(i-1)*(i-1)*(j-1)*(j-1);
                    s-=(double)(i-1)*(i-1)*(n-j)*(n-j);
                    s-=(double)(m-i)*(m-i)*(j-1)*(j-1);
                    s-=(double)(m-i)*(m-i)*(n-j)*(n-j);
                    ans+=1.0-pow(s/n/n/m/m, k);
                }
            out.println("Case #"+(++cas)+": "+Math.round(ans));
        }
        out.flush();
        out.close();
    }
}

#A.Article
赛中没有耐心读完的题。。。赛后还读错了题意……
原来按“保存”键是不存在失败率的，这大大简化了问题模型（即可列出状态转移方程）。

/** Sep 7, 2015 6:37:43 PM
 * PrjName:hdu5236
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static double[] f;
    static int n,x;
    static double solve(int k){
        double res=k*x;
        if (n%k>0)
            //res+=f[n/k]*(k-1)+f[n%k];
            res+=f[n/k+1]*(n%k)+f[n/k]*(k-n%k);
        else
            res+=f[n/k]*k;
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            n=in.nextInt();
            double p=in.nextDouble();
            x=in.nextInt();
            f=new double[n+1];
            for(int i=1;i<=n;i++)
                f[i]=(f[i-1]+1)/(1-p);
            double ans=f[n]+x;
            for(int i=2;i<=n;i++)
                ans=Math.min(ans, solve(i));
            out.println("Case #"+(++cas)+": "+String.format("%.6f", ans));
        }
        out.flush();
        out.close();
    }
}