Posted 09/16/2019Updated 07/19/2023a few seconds read (About 67 words)

Cracking Java Interview

A list of frequently asked Java questions

Overriding vs overloading

Overriding happens at subclass while overloading happens in the same class. Also, overriding is a runtime activity while overloading is resolved at compile time.
Difference between Hashtable and Hashmap, ArrayList and Vector

Synchronized or not.
Thread-safe and synchronization

Posted 06/29/2016Updated 07/19/2023 Semprathlon / Simfae Dean Servera minute read (About 198 words)

解决jdbc连接SQL Server常见连接错误

错误信息：
通过端口 1433 连接到主机 localhost 的 TCP/IP 连接失败。错误:“connect timed out。请验证连接属性。确保 SQL Server 的实例正在主机上运行，且在此端口接受 TCP/IP 连接，还要确保防火墙没有阻止到此端口的 TCP 连接。”。

重要前提：

确保数据库允许远程连接
确保登录名允许远程连接

检查错误：
打开Sql Server Configuration Manager，选中左栏SQL Server网络配置=>< 服务名>的协议，双击TCP/IP以弹出对话框。

特别注意最下方IPAll项的端口设置。
按图设置，重启SQL Server服务后生效。

telnet 127.0.0.1 1433 可供测试端口。

Posted 05/17/2016Updated 07/19/2023 Semprathlon / Simfae Dean Programinga few seconds read (About 27 words)

Java中一些基本类型的内存占用

你真的知道Java中boolean类型占用多少个字节吗？

Posted 04/29/2016Updated 07/19/2023 Semprathlon / Simfae Dean Programinga few seconds read (About 33 words)

在Eclipse中查看jdk源代码

为了帮助初学Java的同学，现给出查看jdk源代码的提示：

ACM竞赛Java模板[dev-160504]

ACM-ICPC

Java Code Template By Semprathlon

部分理论知识引用自维基百科

Input 输入

An enhanced InputReader supporting keeping reading data until the end of input while the number of input cases is unknown:
一个加强版的输入器 ，支持读到输入文件末尾的方式，用法类似java.util.Scanner但效率显著提高:

Posted 12/02/2015Updated 07/19/2023 Semprathlon / Simfae Dean Programinga few seconds read (About 19 words)

Cannot create generic array of in Java?

See Stackoverflow

Posted 11/16/2015Updated 07/19/2023 Semprathlon / Simfae Dean Programinga few seconds read (About 105 words)

Java代码编译命令的微小而关键的细节

今天室友问我，为什么javac编译源代码完成后，用java执行就报错Error: Could not find or load main class呢？

我习惯性地认为是环境变量的值不合适（百度上很多解答也类同），但检查后并无问题……

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