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但效率显著提高:

#Grids

Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 65535/65535 K (Java/Others)

##Problem Description

　　度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去，但是为了使格子看起来优美，他想找到使每行每列都递增的方案。不过画了很久，他发现方案数实在是太多了。度度熊想知道，有多少种放数字的方法能满足上面的条件？

##Input

　　第一行为数据组数T(1< =T<=100000)。
　　然后T行，每行为一个数N(1< =N<=1000000)表示长方形的大小。

##Output

　　对于每组数据，输出符合题意的方案数。由于数字可能非常大，你只需要把最后的结果对1000000007取模即可。

##Sample Input

2
1
3

##Sample Output

Case #1:
1
Case #2:
5

##Hint

对于第二组样例，共5种方案，具体方案为：

##Source

2014年百度之星程序设计大赛 - 初赛（第一轮）

---

引用维基百科的解释：

Cn is the number of standard Young tableaux whose diagram is a 2-by-n rectangle. In other words, it is the number of ways the numbers 1, 2, …, 2n can be arranged in a 2-by-n rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the hook-length formula.

• 除法取模运算、Catalan数计算依赖于不同的推导，分别有多种不同写法，分别有不同的时间复杂度表现。

/**
 * Apr 3, 2016 9:54:01 PM
 * PrjName: hdu4828
 * @semprathlon
 */

import java.io.*;
import java.util.*;

public class Main {
    final static int maxn = 1000010, mod = 1000000007;
    static long inv[] = new long[maxn];
    static long a[] = new long[maxn];
    static long b[] = new long[maxn];
    static long C[] = new long[maxn];
    static long x, y;

    static void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    static void get_inv(int maxn, long mod) {
        inv[1] = 1;
        for (int i = 2; i < maxn; i++) {
            // inv[i] = (mod - mod / i) * inv[(int) (mod % i)] % mod;

            inv[i] = (int) cal_inv(i, mod);
        }
    }

    static long cal_inv(long n, long mod) {
        extgcd(n, mod);
        return x < 0L ? (x + mod) % mod : x % mod;
    }

    static long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
    }

    static long div_mod(long n, long m, long mod) {
        // return n * pow_mod(m, mod - 2, mod) % mod;
        // return n * pow_mod(m, phi(mod) - 1, mod) % mod;
        return n * inv[(int) m] % mod;
    }

    static void get_Catalan(int maxn) {
        a[1] = 2;
        b[1] = 1;
        C[1] = 1;
        for (int i = 2; i < maxn - 1; i++) {
            /*
             * a[i] = a[i - 1] * ((i << 1) - 1) % mod * (i << 1) % mod; a[i] =
             * div_mod(a[i], i, mod); a[i] = div_mod(a[i], i, mod); b[i] = b[i -
             * 1] * ((i << 1) - 1) % mod * (i << 1) % mod; b[i] = div_mod(b[i],
             * i + 1, mod); b[i] = div_mod(b[i], i - 1, mod); C[i] = a[i] -
             * b[i]; if (C[i] < 0) C[i] += mod;
             */
            C[i] = C[i - 1] * ((i << 2) - 2) % mod;
            C[i] = div_mod(C[i], i + 1, mod);
        }
    }

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        get_inv(maxn, mod);
        get_Catalan(maxn);
        int T = in.nextInt(), cas = 0;
        while (T-- > 0) {
            int n = in.nextInt();
            out.println("Case #" + (++cas) + ":");
            out.println(C[n]);
        }
        out.flush();
        out.close();
    }

}

GCD

Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Given 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

You can assume that a = c = 1 in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

Case 1: 9
Case 2: 736427

Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

• 莫比乌斯反演，可比容斥原理节省工作量。
• 所需寻找的二元组中i==j时，仅算1对。

import java.io.*;
import java.util.*;
public class Main {
    final static int maxn=100010;
    static int[] pri,phi,fstp,miu;
    static void get_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        phi=new int[maxn];
        miu=new int[maxn];
        phi[1]=1;
        miu[1]=1;
        for(int i=2;i0){
            in.nextInt();
            int n=in.nextInt();
            in.nextInt();
            int m=in.nextInt();
            int k=in.nextInt();
            if (k==0){
                out.println("Case "+(++cas)+": 0");
                continue;
            }
            n/=k;m/=k;
            if (n>m){
                int t=n;n=m;m=t;
            }
            long ans=0;
            for(int i=1;i<=n;i++)
                ans-=(long)miu[i]*(n/i)*(n/i);
            ans/=2;
            for(int i=1;i<=n;i++)
                ans+=(long)miu[i]*(n/i)*(m/i);
            out.println("Case "+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

#Junk-Mail Filter

Time Limit: 15000/8000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

##Problem Description

Recognizing junk mails is a tough task. The method used here consists of two steps:

1. Extract the common characteristics from the incoming email.
2. Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.

   We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:

a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, so
relationships (other than the one between X and Y) need to be created if they are not present at the moment.

b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.

Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
Please help us keep track of any necessary information to solve our problem.

##Input

There are multiple test cases in the input file.
Each test case starts with two integers, N and M (1 ≤ N ≤ 10^5 , 1 ≤ M ≤ 10^6), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

##Output

For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.

##Sample Input

5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3

3 1
M 1 2

0 0

##Sample Output

Case #1: 3
Case #2: 2

#Source

2008 Asia Regional Hangzhou

• 要删除结点时，原结点的编号作废但保留位置，再给该结点新分配一个“马甲”。

/**
 * Mar 28, 2016 8:25:14 PM
 * PrjName: fzu2155
 * @semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
    final static int maxn = 2000010;
    static int[] f = new int[maxn];
    static int[] g = new int[maxn];

    static int n, m, cnt;
    static Set st = new HashSet();

    static int getf(int x) {
        if (f[x] == x)
            return x;
        f[x] = getf(f[x]);
        return f[x];
    }

    static boolean unite(int x, int y) {
        int a = getf(g[x]);
        int b = getf(g[y]);
        if (a == b)
            return false;
        f[a] = b;
        return true;
    }

    static void init() {
        cnt = n;
        for (int i = 0; i < n + m; i++)
            f[i] = i;
        for (int i = 0; i < n; i++)
            g[i] = i;
    }

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int cas = 0;
        while (in.nextLine() != null) {
            n = in.nextInt();
            m = in.nextInt();
            if (n == 0 && m == 0)
                break;
            init();
            for (int i = 1; i <= m; i++) {
                String s = in.next();
                if (s.charAt(0) == 'M') {
                    int x = in.nextInt();
                    int y = in.nextInt();
                    unite(x, y);
                } else if (s.charAt(0) == 'S') {
                    int x = in.nextInt();
                    g[x] = cnt++;
                }
            }
            st.clear();
            for (int i = 0; i < n; i++)
                st.add(getf(g[i]));

            out.println("Case #" + (++cas) + ": " + st.size());
        }
        out.flush();
        out.close();
    }

}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String nextLine() {
        String tmp = null;
        try {
            tmp = reader.readLine();
            tokenizer = new StringTokenizer(tmp);
        } catch (IOException e) {
            throw new RuntimeException(e);
        } catch (NullPointerException e) {
            return null;
        }
        return tmp;
    }

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

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Turing Tree

Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…

Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.

Input

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:

• Line 1: N (1 ≤ N ≤ 30,000).
• Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
• Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
• Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

Output

For each Query, print the sum of distinct values of the specified subsequence in one line.

Sample Input

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

1
5
6
3
6

Author

3xian@GDUT

• 离线化
• 从左到右处理原数列
• 对询问排序

不再是难题。

/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on March 25, 2016, 4:02 PM
 */
#include 
#include 
#include 
#include 
#include 

• Run an existing MySQL-dump script

source [filename]

• switch Ubuntu mirror source

(take an eye on the version)

sudo cp /etc/apt/sources.list /etc/apt/sources.list_backup
(editing /etc/apt/sources.list)
sudo apt-get update
sudo apt-get upgrade

http://askubuntu.com/questions/645236/command-to-list-all-users-with-their-uid