Posted 07/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 240 words)

hdu 4825 Xor Sum 位操作字典树

遇到本题，在对象成员中申请数组空间的话，会不明就里地TLE，而且浪费大量内存。

/**
 * 2015年7月15日 上午11:21:15
 * PrjName:hdu4825
 * @ Semprathlon
 */

import java.io.*;

class Trie {
    private final int maxd = 33;
    private long data;
    private Trie ch0, ch1;

    void insert(long n) {
        Trie rt = this;
        for (int i = maxd - 1; i >= 0; i--) {
            if ((n & (1L << i)) == 0L) {// 0
                if (rt.ch0 == null)
                    rt.ch0 = new Trie();
                rt = rt.ch0;
            } else {// 1
                if (rt.ch1 == null)
                    rt.ch1 = new Trie();
                rt = rt.ch1;
            }
            if (i == 0)
                rt.data = n;
        }
    }

    long query(long n) {
        Trie rt = this;
        for (int i = maxd - 1; i >= 0; i--) {
            if ((n & (1L << i)) > 0L && rt.ch0 != null || rt.ch1 == null)// 0
                rt = rt.ch0;
            else if (rt.ch1 != null)// 1
                rt = rt.ch1;
        }
        return rt.data;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int cas = 0;
        in.nextToken();
        int T = (int) in.nval;
        while (T-- > 0) {
            Trie tr = new Trie();
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                tr.insert((long) in.nval);
            }
            out.println("Case #" + (++cas) + ":");
            for (int i = 1; i <= m; i++) {
                in.nextToken();
                out.println(tr.query((long) in.nval));
            }
        }
        out.flush();
        out.close();
    }

}

Posted 07/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 398 words)

hdu 2604 Queuing 递推/DP 矩阵快速幂 Trie数辅助

过于傻气的递推公式！
状态傻傻分不清楚
写矩阵乘法，混淆了左乘与右乘。

引用一个类比字符串模式匹配的trie树的应用：

/**
 * 2015年7月14日 下午4:51:05
 * PrjName:hdu2604
 * @ Semprathlon
 */
import java.io.*;

class Matrix {
    int n, m, mod;
    int[][] dat;

    Matrix(int n, int m, int mod) {
        this.n = n;
        this.m = m;
        this.mod = mod;
        this.dat = new int[n][m];
    }

    Matrix(Matrix mat) {
        this.n = mat.n;
        this.m = mat.m;
        this.mod = mat.mod;
        this.dat = new int[n][m];
        for (int i = 0; i < mat.n; i++)
            for (int j = 0; j < mat.m; j++)
                this.dat[i][j] = mat.dat[i][j];
    }

    static Matrix one(Matrix mat) {
        Matrix res = new Matrix(mat.n, mat.m, mat.mod);
        for (int i = 0; i < Math.min(mat.n, mat.m); i++)
            res.dat[i][i] = 1;
        return res;
    }

    Matrix add(Matrix c) {
        Matrix res = new Matrix(this);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                res.dat[i][j] += c.dat[i][j];
                res.dat[i][j] %= mod;
            }
        return res;
    }

    Matrix mul(Matrix c) {
        Matrix res = new Matrix(this.n, c.m, mod);
        for (int i = 0; i < this.n; i++)
            for (int j = 0; j < c.m; j++)
                for (int k = 0; k < this.m; k++) {
                    res.dat[i][j] += this.dat[i][k] * c.dat[k][j];
                    res.dat[i][j] %= mod;
                }

        return res;
    }

    Matrix pow(int m) {
        Matrix n = new Matrix(this);
        Matrix res = Matrix.one(n);
        while (m > 0) {
            if ((m & 1) > 0)
                res = res.mul(n);
            n = n.mul(n);
            m >>= 1;
        }
        return res;
    }
}

public class Main {
    static Matrix mat, p;

    static void init(int mod) {
        mat = new Matrix(4, 1, mod);
        mat.dat = new int[][] { { 9 }, { 6 }, { 4 }, { 2 } };
        p = new Matrix(4, 4, mod);
        p.dat = new int[][] { { 1, 0, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 },
                { 0, 0, 1, 0 } };
    }

    static int solve(int l, int m) {
        mat = p.pow(l - 4).mul(mat);
        if (l > 4)
            return mat.dat[0][0];
        else if (l > 0)
            return mat.dat[4 - l][0];
        return 0;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int l = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            init(m);
            out.println(solve(l, m) % m);    
        }
        out.flush();
        out.close();
    }
}

Posted 07/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 537 words)

hdu 4185 Oil Skimming 二分图匹配

Oil Skimming

/** Aug 24, 2015 11:15:57 AM
 * PrjName:hdu4185
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static char[][] mp;
    //static int[][] adj;
    static int[] match;
    static boolean[] vis;
    static int n,cnt,sum;
    final static int[][] dir={ {-1,0},{1,0},{0,-1},{0,1}};
    final static int maxn=605;
    static Vector<Integer>[] adj=new Vector[maxn*maxn>>1];
    static HashMap<Integer, Integer> sta=new HashMap<Integer,Integer>();
    static HashMap<Integer, Integer> stb=new HashMap<Integer,Integer>();
    static int geta(Pt p){
        int hash=p.hashCode();
        if (sta.containsKey(hash))
            return sta.get(hash);
        else{
            sta.put(hash, ++cnt);
            return cnt;
        }
    }
    static int getb(Pt p){
        int hash=p.hashCode();
        if (stb.containsKey(hash))
            return stb.get(hash);
        else{
            stb.put(hash, ++sum);
            return sum;
        }
    }
    static boolean cango(int x,int y){
        if (x<0||x>=n||y<0||y>=n||mp[x][y]!='#') return false;
        return true;
    }
    static boolean dfs(int u){
        for(int v:adj[u]){
            if (vis[v]) continue;
            vis[v]=true;
            if (match[v]<0||dfs(match[v])){
                match[v]=u;
                return true;
            }
        }
        return false;
    }
    static int maxmatch(){
        int res=0;
        Arrays.fill(match, -1);
        for(int i=1;i<=cnt;i++){
            Arrays.fill(vis, false);
            if (dfs(i)) res++;
        }
        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);
        for(int i=0;i<maxn*maxn>>1;i++) adj[i]=new Vector<Integer>();
        int T=in.nextInt(),cas=0;
        
        while(T-->0){
            n=in.nextInt();
            mp=new char[n][n];
            for(int i=0;i<n*n>>1;i++) adj[i].clear();
            sta.clear();stb.clear();cnt=sum=0;
            for(int i=0;i<n;i++){
                String s=in.next();
                for(int j=0;j<n;j++)
                    mp[i][j]=s.charAt(j);
            }
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if (mp[i][j]=='#'){
                        Pt p=new Pt(i, j,n);
                        for(int k=0;k<4;k++){
                            int x=i+dir[k][0];
                            int y=j+dir[k][1];
                            if (((x+y)&1)>0&&cango(x,y)){
                                Pt q=new Pt(x, y,n);
                                adj[geta(p)].add(getb(q));
                                //adj[q.hashCode()].add(p);
                            }
                        }
                    }
            match=new int[sum+1];
            vis=new boolean[sum+1];
            out.println("Case "+(++cas)+": "+maxmatch());
        }
        out.flush();
        out.close();
    }

}
class Pt{
    int x,y,n;
    Pt(int _x,int _y,int _n){
        x=_x;y=_y;n=_n;
    }
    Pt(int hash,int _n){
        n=_n;
        y=hash%n;
        x=hash/n;
    }
    public int hashCode(){
        return x*n+y;
    }
}
class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;
 
    public InputReader(InputStream stream){
           reader = new BufferedReader(new InputStreamReader(stream), 32768);
           tokenizer = null;
    }
 
    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
     
    public long nextLong() {
        return Long.parseLong(next());
    }
 
}

折腾了过长的时间，原因：
这不是通常意义上的可随意匹配的二分图。
既然是二分图，就有把节点分为两类的依据。
由题中给定的结合规则，一定是一个(x+y)为偶数的点与一个(x+y)为奇数的点相匹配，且是相邻点的匹配。
所以会将两类点分别加入两个表中，并进行hash操作节约存储空间。
“奇”的点总是不少于“偶”的点？

Posted 07/14/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 634 words)

poj 3253 Fence Repair 最小堆优先队列哈夫曼树

Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn’t own a saw with which to cut the wood, so he mosies over to Farmer Don’s Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn’t lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

Input
Line 1: One integer N, the number of planks
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank

Output
Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts

Sample Input
3
8
5
8

Sample Output
34

Hint
He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8.
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).

犯过以下错误：
误用二分
元素删除后未完成堆的调整操作
最小堆写成了最大堆
long类型的res用了int类型

import java.io.*;

class Heap {
	private final int maxn = 50010;
	int[] data;
	int r;

	Heap() {
		data = new int[maxn];
		r = 0;
	}

	public int size() {
		return r;
	}

	void swap(int a, int b) {
		int tmp = data[a];
		data[a] = data[b];
		data[b] = tmp;
	}

	void up(int p) {
		if (!(p > 0))
			return;
		int q = p >> 1;
		if (data[p] < data[q]) {
			swap(p, q);
			up(q);
		}
	}

	void down(int p) {
		int q;
		if ((p << 1) >= r)
			return;
		else if ((p << 1) == r - 1) {
			q = p << 1;
		} else {
			q = (data[p << 1] < data[p << 1 | 1] ? p << 1 : p << 1 | 1);
		}
		if (data[p] > data[q]) {
			swap(p, q);
			down(q);
		}
	}

	void push(int n) {
		data[r++] = n;
		up(r - 1);
	}

	int pop() {
		int res = data[0];
		swap(0, r - 1);
		r--;
		down(0);
		return res;
	}

	int top() {
		return data[0];
	}

}

public class Main {
	private static long solve(int[] a) {
		Heap hp = new Heap();
		int n = a[0], l1, l2;
		long res = 0;
		for (int i = 1; i <= n; i++)
			hp.push(a[i]);
		// hp.print();
		while (hp.size() > 1) {
			l1 = hp.pop();
			l2 = hp.pop();
			res += (long) (l1 + l2);
			hp.push(l1 + l2);
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(
				new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(System.out);
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) in.nval;
			int[] a = new int[n + 1];
			a[0] = n;
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				a[i] = (int) in.nval;
			}

			if (n > 1)
				out.println(solve(a));
			else
				out.println(a[1]);
			out.flush();
		}
		out.close();
	}
}

Posted 07/14/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing10 minutes read (About 1531 words)

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==

0123456789012345678901234567890123456789012345678901234567890123
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

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

/**
 * 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();
    }
}

Posted 07/08/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 242 words)

hdu 2894 DFS 欧拉回路

这应该是《离散数学》教材中关于欧拉回路的一道例题，模型很经典。
不要拘泥于过去邻接矩阵存储形式的做法！
从效率角度上着想，能得到更佳的解决方案

struct Edge
{
    int to,next,ve;
    Edge(){}
    Edge(int v,int w,int x):to(v),next(w),ve(x){}
} edge[maxn];
int head[maxn],cnt;

void addedge(int u,int v)
{
    if (u==v) return;
    edge[cnt]=Edge(v,head[u],v);
    head[u]=cnt++;

    /*edge[head[0]]=Edge(u,head[v]);
    head[v]=head[0]++;*/
}

bool vis[maxn];
int n,N;
vector<int> vec;

void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;

    for(int i=0;i<N;i++)
    {
        //cout<<i<<':'<<(i<<1)%N<<' '<<((i<<1)|1)%N<<' '<<((N|i)>>1)<<' '<<(i>>1)<<endl;
        /*mp[i][(i<<1)%N]++;
        mp[i][((i<<1)|1)%N]++;
        mp[i][(N|i)>>1]++;
        mp[i][i>>1]++;
        mp[i][i]=0;*/
        addedge(i+1,(i<<1)%N+1);
        addedge(i+1,((i<<1)|1)%N+1);
        //addedge(i,(N|i)>>1);
        //addedge(i,i>>1);
    }
}

void dfs(int u)
{

    for(int i=head[u];i>-1;i=edge[i].next)
    {
        int v=edge[i].to;
        //cout<<u<<' '<<v<<endl;
        if (vis[edge[i].ve]) continue;
        vis[edge[i].ve]=1;
        vec.push_back(edge[i].ve);
        dfs(v);
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        N=1<<n;
        init();
        vec.clear();

        CLEAR(vis,maxn);
        dfs(1);
        cout<<N<<' ';
        //cout<<vec[0];
        for(int i=0;i<vec.size();i++) cout<<(vec[i]&1);//cout<<vec[i]<<' ';
        cout<<endl;
    }
    return 0;
}

Posted 07/07/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 287 words)

（迟到的）湖南湘潭程序设计邀请赛后感想

来到如此遥远的地域挑战未知，少有惊喜却多有险阻。
第一个签到题D题的疏忽几乎引起我的疯狂WA。实际上只是简单的边界问题的处理（分数值等于0）胡牛和张学长的仔细列举检验奏效了。
我个人花大量精力为F题写的线段树惨烈地挂了。Lazy标记未能体现出应有的使用价值。多种不同的修改操作与统计操作的优先级，必是平时练习时漏洞密布之处。
E题简单的计算几何遭遇了一些磕绊。张学长所归纳的方程是正确的，只是计算过程中变量范围的设置不甚合理。
相比之下，A题递推的实现较为顺利。
I题和J题是既面熟又陌生的题型。尽管全队坚持到了最后一刻，却未能再争取关键的突破。
赛后听解题报告会，发现原题无不存在破解的可能性？

Posted 06/04/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 750 words)

Cylinder Candy - The 15th Zhejiang University Programming Contest 求积分

原题地址
比赛时卡在这种题上，很是要命

Edward the confectioner is making a new batch of chocolate covered candy. Each candy center is shaped as a cylinder with radius r mm and height h mm.

The candy center needs to be covered with a uniform coat of chocolate. The uniform coat of chocolate is d mm thick.

You are asked to calcualte the volume and the surface of the chocolate covered candy.

Input

There are multiple test cases. The first line of input contains an integer T(1≤ T≤ 1000) indicating the number of test cases. For each test case:

There are three integers r, h, d in one line. (1≤ r, h, d ≤ 100)

Output

For each case, print the volume and surface area of the candy in one line. The relative error should be less than 10^-8.

Sample Input

2
1 1 1
1 3 5

Sample Output

32.907950527415 51.155135338077
1141.046818749128 532.235830206285

Author: ZHOU, Yuchen Source: The 15th Zhejiang University Programming Contest

在底面半径r mm，高h mm的圆柱体糖块外裹上一层厚度均匀的壳，求它的体积和表面积。
设外壳厚度为$ a $ mm(只是为了避免与微分符号混淆，原题中用d表示)，

求体积

(1)糖果顶上和底下的各一个侧面圆滑的类台体
$ z^2+{(y-r)}^2=a^2(y\ge r),y=\sqrt {a^2-z^2} +r.$
$$
\begin{array}
\newline
V_{台体}=\int_0^a{\pi (\sqrt {a^2-z^2} +r)^2 {\rm d}z}
\newline\left( 或V_{台体}=\int_0^a {\rm d}z\int_0^{2\pi}{\rm d}\theta \int_0^{r+a\sqrt{1-\frac{z^2}{a^2}}}r{\rm d}r \right)
\newline=\int_0^a \pi \left(r+a\sqrt{1-\frac{z^2}{a^2}}\right)^2 {\rm d}z
\newline=\int_0^a \left( \pi r^2+\pi a^2\left(1-\frac{z^2}{a^2}\right)+2\pi ar\sqrt{1-\frac{z^2}{a^2}} \right) {\rm d}z
\newline=\int_0^a \left( \pi r^2+\pi a^2 \right) {\rm d}z-\int_0^a \pi z^2{\rm d}z + \int_0^a 2\pi r\sqrt{a^2-z^2}{\rm d}z
\newline=\pi a^3+\pi ar^2-\frac{\pi a^3}{3}+\frac{\pi^2 a^2r}{2}\newline
\end{array}
$$
(2)糖果中部的圆柱体
$ V_{圆柱}=Sh=\pi r^2h=\pi(r+a)^2h$
(3)总体积
$ V=2V_{台体}+V_{圆柱}=\frac{4\pi a^3}{3}+2\pi ar^2+\pi^2a^2r+\pi(r+a)^2h $

求表面积

(1)求上下各一个环状曲面的面积
这个曲面（轮胎面）的参数方程为
$$
\begin{cases}
x = (r+a {\rm cos}\varphi) {\rm cos}\theta \newline
y = (r+a {\rm cos}\varphi) {\rm sin}\theta \newline
z = a {\rm sin}\varphi
\end{cases}
$$
用向量值函数表示为：$ \vec{f}(\theta,\varphi)=x(\theta,\varphi)\vec{i}+y(\theta,\varphi)\vec{j}+z(\theta,\varphi)\vec{k}$
该曲面上某一点(x,y,z)处的基本法向量
$$
\vec{n}=(-\frac{\partial z}{\partial x},-\frac{\partial z}{\partial y},1)=\frac{\partial \vec{f}}{\partial \theta}\times\frac{\partial \vec{f}}{\partial \varphi}
$$
积分区域$ \Sigma=$ { $ \left(\theta,\varphi \right) | 0\le \theta \le 2\pi,0\le \varphi \le\frac{\pi}{2} $ }
$$
\begin{array}
\newline
S_{环}=\iint_\Sigma {\rm d}S=\iint_\Sigma |\vec{n}| {\rm d}x{\rm d}y\newline
=\iint_\Sigma \sqrt{\left(-\frac{\partial z}{\partial x}\right)^2+\left(-\frac{\partial z}{\partial y}\right)^2+1}{\rm d}x{\rm d}y\newline
=\iint_\Sigma \left|\frac{\partial \vec{f}}{\partial \theta}\times\frac{\partial \vec{f}}{\partial \varphi}\right| {\rm d}x{\rm d}y\newline
=\int_0^\frac{\pi}{2} {\rm d}\varphi \int_0^{2\pi} a(r+a {\rm cos}\varphi) {\rm d}\theta\newline
=\int_0^\frac{\pi}{2} 2\pi a(r+a {\rm cos}\varphi){\rm d}\varphi\newline
=2\pi a\left.(r+a {\rm cos}\varphi)\right|_0^\frac{\pi}{2}=\pi^2 ar+2\pi a^2\newline
\end{array}
$$
(2)求侧面积
$$
S_{侧}=2 \pi(r+a)h
$$
(3)求底面积
$$
S_{底}=\pi r^2
$$
(4)总表面积
$$
S=S_{环}+S_{侧}+2S_{底}=\pi^2 ar+2\pi a^2+2 \pi(r+a)h+2 \pi r^2
$$

Posted 05/31/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 191 words)

Java 输入输出效率优化黑科技get

刚开始，用最常规的输入输出：

import java.util.*;
Scanner scan=new Scanner(System.in);
System.out.println("...");

面对海量输入输出数据，TLE妥妥的

接着有了下面这种姿势（输入流？）：

import java.util.*;
import java.io.*;
Scanner scan=new Scanner(new BufferedInputStream(System.in));

效果不太理想。
最后查阅大神用于处理水题的代码，获得以下终极模板：

import java.io.*;
/*...*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while(in.nextToken() != StreamTokenizer.TT_EOF){
    n=(long)in.nval;
    in.nextToken();
    m=(long)in.nval;
    out.println(n+" "+m);
}
out.flush();//刷新。若本行放循环体内，则毎输入一组数据即输出一组答案，但是效率降低
out.close();
}

Posted 05/30/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 245 words)

2015 ACM-ICPC 上海5 24 现场状态

比赛过程中忘了写chs函数导致无论如何都调试不成
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define CLEAR(a,n) memset((a),0,n*sizeof((a)[0]))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1010;
const int inf=0x7fffffff;
const double eps=1e-3;

const int m1=0x00fc0000;
const int m2=0x0003f000;
const int m3=0x00000fc0;
const int m4=0x0000003f;

char str[maxn];

char chs(char ch)
{
if (ch>=0&&ch<26) return ch+’A’;
else if (ch>=26&&ch<52) return ch-26+’a’;
else if (ch>=52&&ch<62) return ch-52+’0’;
else if (ch==62) return ‘+’;
else if (ch==63) return ‘/‘;
}

void solve(char str[maxn])
{
char s[maxn]={‘\0’};
int len=strlen(str);
int tmp=0;
int pos=0;
for(int i=0;i<len;i++)
{
tmp<<=8;tmp+=int(str[i]);
if (!((i+1)%3))
{
s[pos++]=chs((tmp&m1)>>18);
s[pos++]=chs(((tmp&m2)>>12));
s[pos++]=chs(((tmp&m3)>>6));
s[pos++]=chs((tmp&m4));
tmp=0;
}
}
if (len%3)
{
tmp<<=(3-len%3)*8;
if ((tmp&m1)>0) s[pos++]=chs((tmp&m1)>>18);
if ((tmp&m2)>0) s[pos++]=chs(((tmp&m2)>>12));
if ((tmp&m3)>0) s[pos++]=chs(((tmp&m3)>>6));
if ((tmp&m4)>0) s[pos++]=chs((tmp&m4));
}
int sum=4-strlen(s)%4;
char *t=s+strlen(s);
if (sum<4)
for(int j=1;j<=sum;j++) *t++=’=’;
*t=’\0’;
strcpy(str,s);
}

int main()
{
int T;
scanf(“%d”,&T);
while(T–)
{
int k;
scanf(“%d%s”,&k,str);
for(int i=1;i<=k;i++) solve(str);
printf(“%s\n”,str);
}
return 0;
}
[/cpp]