http://hihocoder.com/contest/ntest2016spring1/problem/1
提交已经关闭,也不知道做的对不对,花了一晚上,测试过了用例
import java.util.HashMap;
import java.util.Scanner;
/**
* @author jun
* */
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
//编码表
int[][] table=new int[][]
{
{1,1,1,0,1,1,1},
{0,0,1,0,0,1,0},
{1,0,1,1,1,0,1},
{1,0,1,1,0,1,1},
{0,1,1,1,0,1,0},
{1,1,0,1,0,1,1},
{1,1,0,1,1,1,1},
{1,0,1,0,0,1,0},
{1,1,1,1,1,1,1},
{1,1,1,1,0,1,1}
};
int S=input.nextInt();
for(int i=0;i<S;i++){
int K=input.nextInt();
String N=input.next();
input.nextLine();
//对应位总共有多少种可能
int[] total=new int[K+1];
total[K]=1;
//是否存在与equal相等的可能
int[] equal=new int[K];
//对应位比N的对应位小的可能
int[] min=new int[K];
// min[K]=0;
while(N.length()<K){
//N补0
N="0"+N;
}
//获取每一位的可能
for(int j=0;j<K;j++){
String tmp=input.nextLine();
int label=0;
HashMap<Integer,Integer> map = new HashMap<Integer ,Integer>();
for(int l=0;l<10;l++){
map.put(l, 0);
}
// System.out.println(tmp);
for(int l=0;l<tmp.length();l++){
if(tmp.charAt(l)!=' '){
label++;
int n=tmp.charAt(l)-'1';
for(int m=0;m<10;m++){
if(table[m][n]==1){
map.put(m,map.get(m)+1);
}
}
}
}
for(int l=0;l<10;l++){
if(map.get(l)==label){
total[j]++;
if(l<(N.charAt(j)-'0')){
min[j]++;
}
if(l==(N.charAt(j)-'0')){
equal[j]++;
}
}
}
}
int result=0;
//主要思想就是按位比较
for(int j=0;j<K;j++){
if(j==0){
int tmp=min[0];
int l=1;
while(l<=K){ tmp=tmp*total[l];l++; }
result+=tmp;
}
else{
int l=j;
int tmp=min[j];
l--;
while(l>=0) {tmp=tmp*equal[l];l--;};
l=j+1;
while(l<=K) {tmp=tmp*total[l];l++;};
result+=tmp;
}
}
System.out.println(result);
}
input.close();
}
}
网友评论