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)的算法，但总的运行时间还是较短的？