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类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/**
 * 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
贪心。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/** 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
必须及时通过必要的暴力模拟来找出这个千呼万唤不出来的规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * 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类型值相乘越界的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/** 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
赛中没有耐心读完的题。。。赛后还读错了题意……
原来按“保存”键是不存在失败率的，这大大简化了问题模型（即可列出状态转移方程）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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

ACM-ICPC Live Archive Regionals 2014 >> Asia - Bangkok
6844 - Combination
=====

原题页面
PDF题面
Vjudge提交地址

艰辛坎坷的探索历程

设 $ {f(n)=C_{n}^{r}(n∈N^{ * },r∈[0,n])} $中奇数的个数。
题意是说，求出 $ \sum f(k),k∈[low,high] $
庞大的数据， $ n≤16\times{10^{11}}. $

step1

判断给定 $ n∈N^{ * } $时 $ C_n^r(r∈[0,n]) $的奇偶性。 不难往n,r的二进制表示方向考虑。
查阅他人博客获得结论： $ n{ & }r==r $时 $ C_n^r $为奇数。 然而本题中无需直接应用这一“定理”，所要做的是统计。
拿出纸笔推算发现，若n的二进制表示中有d个1，则 $ C_n^r(r∈[0,n]) $中存在 $ 2^d $个奇数。

step2

研究 $ f(n) $ 的递推关系及通项。 编写暴力程序 $ O(n^2) $ ，打表观察 $ n∈[0,64) $ 时 $ f(n) $ 的取值：
1
2
2 4
2 4 4 8
2 4 4 8 4 8 8 16
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 4 8 8 16 8 16 16 32 8 16 16 32 16 32 32 64
第一行 $ f(0)=1 $ 作为边界条件， 第二行 $ f(1)=2 $ ，随后各行的第k行的 $ 2^{k-2} $ 个数分别表示 $ f(2^{k-2}),f(2^{k-2}+1),…,f(2^{k-1}-1) $ 。
通过不懈的努力，观察发现从第3行开始，每行的前半部分与前一行完全一致，每行的后半部分的各个f值恰为前半部分对应位置的f值的2倍。

step3

出于数列直觉，我们尝试求解各行的和构成的数列的递推以及通项。
$ a_1=1 $
$ a_2=2 $
$ a_3=a_2+2\times{a_2}=3\times{a_2}=6 $
…
$ a_n=a_{n-1}+2\times{a_{n-1}}=3\times{a_{n-1}}(n\geq 3) $（递推公式）
通项公式:
$$
\begin{equation} a_n= \begin{cases} 1 &\mbox{$n=1$}\newline 2 &\mbox{$n=2$}\newline 2\times3^{n-2} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
\begin{equation} S_n=\sum\limits_{i=1}^{n} {a_i}= \begin{cases} 1 &\mbox{$n=1$}\newline 3 &\mbox{$n=2$}\newline 3+6\times\frac{1-3^{n-2}}{1-3}=3+3\times{(3^{n-2}-1)}=3^{n-1} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
S_n=3^{n-1}（a_n的前n项和的公式）
$$
化简后上面这个公式样子够好看了吧？

step4

再看一下第2步发现的规律，应用“二分”手段高效地求解，而且真的可以二分求解。
具体地说，就是先置求解区间 $ [l,r) $ (左闭右开)的端点于每行的头尾( $ l=2^{i-2},r=2^{i-1} $ )，利用上一步所得公式计算该区间的 $ 左端点前缀和U=\sum\limits_{k=1}^{2^{i-2}} {f(k)} $ 与 $ 右端点前缀和V=\sum\limits_{k=1}^{2^{i-1}-1} {f(k)} $ 后，不断地对区间折半，总可以确定新区间的左端点前缀和与右端点前缀和。
当区间缩至一点时， $ U==V==f(k) $，即能得到我们所求，而无需计算出[1..n]的每个函数值。

step5

以上所解决的并不是最终答案，而是前缀和 $ \sum\limits_{k=1}^{n} {f(k)} $ ；
不过走到这一步已经很好办了， $ ans=\sum\limits_{k=low}^{high} {f(k)}=\sum\limits_{k=1}^{high} {f(k)}-\sum\limits_{k=1}^{low-1} {f(k)} $

PS:写完代码后，用极大的n值测试一下，事实上 $ \sum\limits_{k=1}^{n} {f(k)} $已经超出了int64的范围。其他的细节不必多说了。

1.319s AC java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

/**
 * @date 2015-05-31
 * @author Semprathlon
 */
import java.math.*;
import java.io.*;

public class Main {
    static int maxn=42;
    static BigInteger[] sum=new BigInteger[maxn];
    static long[] Pow2=new long[maxn];
    final static BigInteger TWO=BigInteger.valueOf(2);
    final static BigInteger THREE=BigInteger.valueOf(3);
    
    static int found_pow2(long n){
        return (int)(Math.log((double)n)/Math.log(2.0));
    }

    static void init(){
        for(int i=0;i<maxn;i++)
        {
            sum[i]=THREE.pow(i);
            Pow2[i]=1L<<i;
        }
            
    }
    static BigInteger Bisearch(long l,long r,BigInteger ls,BigInteger rs,long key){
        while(l+1L<r){
            long mid=(l+r)>>1;
            if(key<mid){
                r=mid;
                rs=ls.add(rs.subtract(ls).divide(THREE));
            }
            else{
                l=mid;
                ls=ls.add(rs.subtract(ls).divide(THREE));
            }
        }
        return ls;
    }
    static BigInteger solve(long n){
        if (n<0L) return BigInteger.ZERO;
        if (n==0L) return BigInteger.ONE;
        int k=found_pow2(n+1);
        BigInteger ls=sum[k];
        BigInteger rs=sum[k+1];
        return Bisearch(Pow2[k],Pow2[k+1],ls,rs,n+1);
    }
    public static void main(String[] args) throws IOException{
        init();
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n=0,m=0;
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n=(long)in.nval;
            in.nextToken();
            m=(long)in.nval;
            if (n==0L&&m==0L) break;
            out.println(solve(m).subtract(solve(n-1)));
        }
        out.flush();
        out.close();
    }
}

0.279s AC cpp代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 42;
const LL mod = 1e8;
const int digit = 8;
struct LongInt
{
    LL data[3];
    LongInt()
    {
        data[0] = data[1] = data[2] = 0;
    }
    LongInt(LL n)
    {
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
    }
    LongInt operator= (const LL num)
    {
        LL n = num;
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
        return *this;
    }
    LongInt operator+ (const LL& num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] += n;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator+ (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] += b.data[0];
        tmp.data[1] += b.data[1];
        tmp.data[2] += b.data[2];
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator- (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] -= b.data[0];
        if (tmp.data[0] < 0)
        {
            tmp.data[1]--;
            tmp.data[0] += mod;
        }
        tmp.data[1] -= b.data[1];
        if (tmp.data[1] < 0)
        {
            tmp.data[2]--;
            tmp.data[1] += mod;
        }
        tmp.data[2] -= b.data[2];
        return tmp;
    }
    LongInt operator* (const LL num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] *= num;
        tmp.data[1] *= num;
        tmp.data[2] *= num;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator*= (const LL num)
    {
        *this = *this * num;
        return *this;
    }
    LongInt operator/ (const LL num)
    {
        LongInt tmp = *this;
        tmp.data[1] += tmp.data[2] % num * mod;
        tmp.data[2] /= num;
        tmp.data[0] += tmp.data[1] % num * mod;
        tmp.data[1] /= num;
        tmp.data[0] /= num;
        return tmp;
    }
    void fillzero(int n)
    {
        char str[digit * 2];
        sprintf(str, "%d", n);
        for (int i = 1; i <= digit - strlen(str); i++)
        {
            printf("%d", 0);
        }
        printf("%s", str);
    }
    void print()
    {
        if (data[2] > 0)
        {
            printf("%d", data[2]);
            fillzero(data[1]);
            fillzero(data[0]);
        }
        else if (data[1] > 0)
        {
            printf("%d", data[1]);
            fillzero(data[0]);
        }
        else
        {
            printf("%d", data[0]);
        }
    }
};

const LL pow2[maxn] = {1, 2, 4, 8, 16, 32, 64, 128,
                       256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
                       65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
                       16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
                       4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888,
                       1099511627776, 2199023255552
                      };
/*const ULL sum[maxn] = {3, 5, 11, 29, 83, 245, 731, 2189,
                       6563, 19685, 59051, 177149, 531443, 1594325, 4782971, 14348909,
                       43046723, 129140165, 387420491, 1162261469, 3486784403, 10460353205, 31381059611, 94143178829,
                       282429536483, 847288609445, 2541865828331, 7625597484989, 22876792454963, 68630377364885, 205891132094651, 617673396283949,
                       1853020188851843, 5559060566555525, 16677181699666571, 50031545098999709, 150094635296999123, 450283905890997365, 1350851717672992091, 4052555153018976269,
                       12157665459056928803
                      };*/
LongInt sum[maxn];

int found_pow2(ULL n)
{
    return int(log(n) / log(2));
}

LongInt Bisearch(LL l, LL r, LongInt ls, LongInt rs, LL key) // [ l , r ) 
{
    while (l + 1 < r)
    {
        ULL mid = (l + r) >> 1;
        if (key < mid)
        {
            r = mid;
            rs = (rs - ls) / 3 + ls;
        }
        else
        {
            l = mid;
            ls = (rs - ls) / 3 + ls;
        }
    }
    return ls;
}

LongInt solve(LL n)
{
    if (n < 0)
    {
        return 0;
    }
    if (!n)
    {
        return 1;
    }
    int k = found_pow2(n + 1);
    LongInt ls = sum[k];
    LongInt rs = sum[k + 1];
    return Bisearch(pow2[k], pow2[k + 1], ls, rs, n + 1);
}

void init()
{
    LongInt tmp = 1;
    for (int i = 0; i < maxn; i++)
    {
        sum[i] = tmp;
        tmp *= 3;
    }
}

int main()
{
    init();
    LL n, m;
    while (cin >> n >> m)
    {
        if (!n && !m)
        {
            break;
        }
        LongInt ans = solve(m) - solve(n - 1);
        ans.print();
        puts("");
    }
    return 0;
}

参见：转载前页面

怎么读题时就没发现“每行每列各有一个水阀”？这是把问题转化成二分图模型的关键啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int MAXN = 110;
char graph[MAXN][MAXN];
bool visited[MAXN];
int nCase, cCase, use[MAXN], m, n;
 
void init() {
    memset(use, -1, sizeof(use));
}
 
void input() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%s", graph[i]);
    }
}
 
bool find(int x) {
    for (int j = 0; j < n; j++) {
        if (graph[x][j] == '1' && !visited[j]) {
            visited[j] = true;
 
            if (use[j] == -1 || find(use[j])) {
                use[j] = x;
                return true;
            }
        }
    }
    return false;
}
 
int match() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        if (find(i)) count++;
    }
    return count;
}
 
void solve() {
    printf("Case #%d: %d\n", ++cCase, match());
}
 
int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
 
    }
    return 0;
}