Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 416 words)

Bestcoder

Protest一时爽，final test全爆零 QwQ

1001 wyh2000 and a string problem

1
out.println(str.matches(".*w.*y.*h.*")||str.matches(".*v{2,}.*y.*h.*")?"Yes":"No");

偷懒着用正则表达式，华丽地TLE……
后来就醉了一样的胡乱的写了个匹配也不太行……

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
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.*;
import com.sun.org.apache.xalan.internal.xsltc.compiler.Pattern;
public class Main {
    static boolean check(String str){
        int res=0;
        int i,len=str.length();
        for(i=0;i<len-1;i++)
            if (str.charAt(i)=='w'||str.charAt(i)=='v'&&str.charAt(i+1)=='v'){
                res|=1;break;
            }
        for(;i<len;i++)
            if (str.charAt(i)=='y'){
                res|=2;break;
            }
        for(;i<len;i++)
            if (str.charAt(i)=='h'){
                res|=4;break;
            }
        return res==7;
    }
    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();
         while(T-->0){
             String str=in.next();
             out.println(check(str)?"Yes":"No");
             out.flush();
         }
         out.close();
    }
}

1002 wyh2000 and pupil

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
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

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

short col[maxn];
int s[2];

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

void addedge(int u,int v)
{
    edge[head[0]]=Edge(v,head[u]);
    head[u]=head[0]++;
}

void init()
{
    fill(head,head+maxn,-1);
    head[0]=1;
}

int bfs(int u)
{
    queue<int> q;
    q.push(u);
    col[u]=0;
    while(!q.empty())
    {
        int p=q.front();
        s[col[p]]++;
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (col[v]>=0)
            {
                if (col[v]==col[p]) return -1;
            }
            else
            {
                col[v]=1^col[p];
                q.push(v);
            }

        }
    }
    return 0;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }

        int sum=0;
        fill(col+1,col+n+1,-1);
        for(int i=1;i<=n;i++)
            if (col[i]<0)
        {
            s[0]=s[1]=0;
            if (bfs(i)<0)
            {
                sum=-1;break;
            }
            else sum+=max(s[0],s[1]);
        }
        if (n==sum) sum--;
        if (sum<1||n-sum<1)
            puts("Poor wyh");
        else
            printf("%d %d\n",sum,n-sum);
    }
    return 0;
}

事实证明这并不是二分图匹配；并没有什么典型的算法让两个集合中的一个最大……
用DFS或BFS都可实现填色。

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 277 words)

hdu 5115 Dire Wolf 区间DP

2014ACM/ICPC亚洲区北京站
Dire Wolf

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
/**
 * 2015年7月18日 上午9:55:52
 * PrjName:hdu5115
 * @ Semprathlon
 */
import java.io.*;
public class Main {
    final static long inf=0x7FFFFFFFFFFFFFFFL;
    static long min(long a,long b){
        return Math.min(a, b);
    }
    public static void main(String[] args)  throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T=(int)in.nval,cas=0;
        int[] a,b;
        long[][] f;
        while(T-->0){
            in.nextToken();
            int n=(int)in.nval;
            a=new int[n+2];
            b=new int[n+2];
            f=new long[n+2][n+2];
            for(int i=1;i<=n;i++){
                in.nextToken();
                a[i]=(int)in.nval;
            }
            for(int i=1;i<=n;i++){
                in.nextToken();
                b[i]=(int)in.nval;
            }
            f[1][1]=a[1]+b[2];
            f[n][n]=a[n]+b[n-1];
            for(int i=2;i<n;i++)
                f[i][i]=a[i]+b[i-1]+b[i+1];
            for(int i=1;i<=n;i++)
                for(int j=i+1;j<=n;j++)
                    f[i][j]=inf;
            for(int j=0;j<=n;j++)
                for(int i=1;i+j<n+1;i++)
                    for(int k=i;k<=i+j;k++){
                        f[i][i+j]=min(f[i][i+j],f[i][k-1]+f[k+1][i+j]+a[k]+b[i-1]+b[i+j+1]);
                        //out.print(f[i][i+j]+" ");
                    }
            /*for(int i=0;i<=n+1;i++){out.println();
                for(int j=0;j<=n+1;j++)
                    out.print(f[i][j]+"\t");    
            }*/
                        
            
            /*for(int i=0;i<n;i++)
                for(int j=1;j<n-i;j++){
                    if (j==1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]);
                    if (j>1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]+b[j-1]);
                    if (i+j<n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]+b[j+i+1]);
                    if (i+j==n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]);
                    for(int k=j+1;k<j+i;k++)
                        min(f[j][j+i],f[j][k-1]+a[k]+f[k+1][j+i]);
                }*/
            out.println("Case #"+(++cas)+": "+f[1][n]);
            out.flush();
        }
        
        out.close();
    }
}

贪心真的是要贪婪死了。。。
已消除区段。。。其实对后续操作没有影响，符合无后效性。

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 229 words)

ACM-ICPC 2014 Beijing Regional / hdu 5115 区间DP

贪心？走进死胡同了吧

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
/**
 * 2015年7月18日 上午9:55:52
 * PrjName:hdu5115
 * @ Semprathlon
 */
import java.io.*;
public class Main {
	final static long inf=0x7FFFFFFFFFFFFFFFL;
	static long min(long a,long b){
		return Math.min(a, b);
	}
	public static void main(String[] args)  throws IOException{
		// TODO Auto-generated method stub
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int T=(int)in.nval,cas=0;
		int[] a,b;
		long[][] f;
		while(T-->0){
			in.nextToken();
			int n=(int)in.nval;
			a=new int[n+2];
			b=new int[n+2];
			f=new long[n+2][n+2];
			for(int i=1;i<=n;i++){
				in.nextToken();
				a[i]=(int)in.nval;
			}
			for(int i=1;i<=n;i++){
				in.nextToken();
				b[i]=(int)in.nval;
			}
			f[1][1]=a[1]+b[2];
			f[n][n]=a[n]+b[n-1];
			for(int i=2;i<n;i++)
				f[i][i]=a[i]+b[i-1]+b[i+1];
			for(int i=1;i<=n;i++)
				for(int j=i+1;j<=n;j++)
					f[i][j]=inf;
			for(int j=0;j<=n;j++)
				for(int i=1;i+j<n+1;i++)
					for(int k=i;k<=i+j;k++){
						f[i][i+j]=min(f[i][i+j],f[i][k-1]+f[k+1][i+j]+a[k]+b[i-1]+b[i+j+1]);
						//out.print(f[i][i+j]+" ");
					}
			/*for(int i=0;i<=n+1;i++){out.println();
				for(int j=0;j<=n+1;j++)
					out.print(f[i][j]+"\t");	
			}*/
						
			
			/*for(int i=0;i<n;i++)
				for(int j=1;j<n-i;j++){
					if (j==1)
						min(f[j][j+i],f[j+1][j+i]+a[j]);
					if (j>1)
						min(f[j][j+i],f[j+1][j+i]+a[j]+b[j-1]);
					if (i+j<n)
						min(f[j][j+i],f[j][j+i-1]+a[j+i]+b[j+i+1]);
					if (i+j==n)
						min(f[j][j+i],f[j][j+i-1]+a[j+i]);
					for(int k=j+1;k<j+i;k++)
						min(f[j][j+i],f[j][k-1]+a[k]+f[k+1][j+i]);
				}*/
			out.println("Case #"+(++cas)+": "+f[1][n]);
			out.flush();
		}
		
		out.close();
	}

}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 225 words)

ACdreamOJ 1726 hash 二进制表示下的枚举

http://acdream.info/problem?pid=1726
Problem Description

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],……,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.

Input

There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],……,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.

Output

If Losanto could win the game, output “Yes” in a line. Else output “No” in a line.

Sample Input

10 87
2 3 4 5 7 9 10 11 12 13
10 38
2 3 4 5 7 9 10 11 12 13

Sample Output

No
Yes

最大的n值为40，需枚举的状态略多；于是折成两半枚举。前后两段合拼时，不是正向地求和，而是逆向查询，节约了时间 

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
/**
 * 2015年7月17日 下午5:41:50
 * PrjName:acd1726
 * @ Semprathlon
**/
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer cin = new StreamTokenizer(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		HashSet<Long> map = new HashSet<Long>();
		while (cin.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) cin.nval;
			cin.nextToken();
			int m = (int) cin.nval;
			map.clear();
			int[] num = new int[n];
			for (int i = 0; i < n; i++) {
				cin.nextToken();
				num[i] = (int) cin.nval;
			}
			int t = (n + 1) / 2;
			for (int i = 0; i < (1 << t); i++) {
				long sum = 0;
				for (int j = 0; j < t; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[j];
				}
				if (sum > m)
					continue;
				map.add(sum);
			}
			int tt = n - t;
			boolean flag = map.contains(m);
			for (int i = 0; i < (1 << tt); i++) {
				long sum = 0;
				for (int j = 0; j < tt; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[t + j];
				}
				if (sum > m)
					continue;
				if (map.contains(m - sum)) {
					flag = true;
					break;
				}
			}
			if (flag)
				out.println("Yes");
			else
				out.println("No");
			// out.flush();
		}
		out.flush();
	}
}
Posted Updated  Semprathlon / Simfae Dean a few seconds read (About 0 words)

我的动态

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 232 words)

hdu 4810 Wall Painting 位操作

本题题意甚是费解。
找到合适的位操作，再运用组合数，是关键。

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
/**
 * 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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 240 words)

hdu 4825 Xor Sum 位操作 字典树

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

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
/**
 * 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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 398 words)

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

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

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

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
/**
 * 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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 537 words)

hdu 4185 Oil Skimming 二分图匹配

Oil Skimming

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
/** 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 Updated  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类型 

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

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview4
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python11
RMQ1
React2
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
TypeScript2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×