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

2013 ACM/ICPC Asia Regional Chengdu Online

1007 F(x)数位DP

/** Aug 22, 2015 5:23:42 PM
 * PrjName:hdu4734
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[][] f;
    static int[] digit;
    final static int maxm=4600;
    static int fun(int n){
        int res=0,tmp=1;
        while(n>0){
            res+=n%10*tmp;
            tmp<<=1;
            n/=10;
        }
        return res;
    }
    static void init(){
        int tmp=1;
        f=new int[10][maxm+1];
        f[0][0]=1;
        for(int i=1;i<10;i++){
            for(int j=0;j<=maxm;j++)
                for(int k=0;k<=9;k++)
                    if (j+tmp*k<=maxm)
                        f[i][j+tmp*k]+=f[i-1][j];
            tmp<<=1;
        }
        for(int i=0;i<10;i++)
            for(int j=1;j<=maxm;j++) f[i][j]+=f[i][j-1];
    }
    static int[] getdg(int n){
        int[] res=new int[10];
        while(n>0){
            res[++res[0]]=n%10;
            n/=10;
        }
        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);
        init();
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int A=in.nextInt();
            int B=in.nextInt();
            int m=fun(A);
            digit=getdg(B);
            int ans=0,tmp=1<<digit[0];
            for(int i=digit[0];i>=1;i--){
                tmp>>=1;
                for(int k=0;k<digit[i];k++){
                    
                    if (m-k*tmp>=0){
                        ans+=f[i-1][m-k*tmp];
                    }
                }
                m-=digit[i]*tmp;
                if (m<0) break;
                
            }
            if (m>=0) ans++;
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

磕磕绊绊的，到底有几大难？
期初是有过转化为背包问题的尝试，但是忽视了数位DP的处理手段；可先扩大枚举范围，再从中筛选。
预处理的两套循环不能杂糅在一起，因为先通过递推求了第i位、限制F(x)==j的解，然后才相加得到第i位、限制F(x)≤j的解。
筛选时注意“小于”的枚举方式。
最后还应留意B为可行解的条件。

1010 A Bit Fun

/** Aug 22, 2015 4:28:18 PM
 * PrjName:hdu4737
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[] a;
    static Queue<Integer> que=new LinkedList<Integer>();
    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 m=in.nextInt();
            a=new int[n+1];
            que.clear();
            int ans=0;
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                int k=que.size();
                for(int j=0;j<k;j++){
                    int tmp=que.poll()|a[i];
                    if (tmp<m) que.add(tmp);
                }
                if (a[i]<m) que.add(a[i]);
                ans+=que.size();
            }
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

并没有实现有些题解中所说的O(nlogn)或O(30n)的算法，但总的运行时间还是较短的？

Posted 07/18/2015Updated 07/19/2023 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，需枚举的状态略多；于是折成两半枚举。前后两段合拼时，不是正向地求和，而是逆向查询，节约了时间

/**
 * 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 07/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 232 words)

hdu 4810 Wall Painting 位操作

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

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

}

2013 ACM/ICPC Asia Regional Chengdu Online

1007 F(x)数位DP

1010 A Bit Fun

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

Input

Output

Sample Input

Sample Output

hdu 4810 Wall Painting 位操作

Categories

Tags

Subscribe for updates

Links