卢卡斯的驱逐者大军已经来到了赫柏的卡诺萨城，赫柏终于下定决心,集结了大军,与驱逐者全面开战。
卢卡斯的手下有6名天之驱逐者，这6名天之驱逐者各赋异能，是卢卡斯的主力。
为了击败卢卡斯，赫柏必须好好考虑如何安排自己的狂战士前去迎战。
狂战士的魔法与一些天之驱逐者的魔法属性是相克的，第i名狂战士的魔法可以克制的天之驱逐者的集合为Si(Si中的每个元素属于[0,5])。
为了公平，两名狂战士不能攻击同一个天之驱逐者。
现在赫柏需要知道共有多少种分派方案。
例：
S1={01},S2={23}，代表编号为0的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者，编号为1的狂战士的魔法可以克制编号为2和编号为3的天之驱逐者，共有四种方案：02,03,12,13。
02---代表第一个狂战士负责编号为0的驱逐者，第二个狂战士负责编号为2的驱逐者；
03---代表第一个狂战士负责编号为0的驱逐者，第二个狂战士负责编号为3的驱逐者；
12---代表第一个狂战士负责编号为1的驱逐者，第二个狂战士负责编号为2的驱逐者;
13---代表第一个狂战士负责编号为1的驱逐者，第二个狂战士负责编号为3的驱逐者;
S1={01},S2={01}，代表编号为0的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者，编号为1的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者，共有两种方案：01,10。
[编程题]兵临城下
- 热度指数：1196 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
多组测试数据，请处理到文件结束。
对于每组测试数据：
第一行为一个整数N，代表狂战士的数量。
第二行为N个字符串，第i个字符串表示第i个狂战士能够克制的天之驱逐者的集合。
保证：
1<=N<=6，1<=每个字符串的长度<=6，且每个字符都是0~5中的一个数字。
输出描述:
输出一个整数，代表分配方案数
示例1
输入
2 01 23 2 01 01 3 3 015 5
输出
4 2 2
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s[6];
int n;
int vis[6];
int ans;
void dfs(int p)
{
if(p == n)
{
ans++;
return;
}
for(inti =0; i < s[p].length(); i++)
{
if(vis[s[p][i]-'0'] == 0)
{
vis[s[p][i]-'0'] = 1;
dfs(p+1);
vis[s[p][i]-'0'] = 0;
}
}
}
int main()
{
while(cin>>n)
{
ans =0;
memset(vis,0,sizeof(vis));
for(inti =0; i < n; i++)
cin>>s[i];
dfs(0);
cout<<ans<<endl;
}
}
编辑于 2016-06-19 10:31:46
回复(7)
/*简单搜索*/
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
private static int ans;
public static int getAns(String[] str, int n) {
ans = 0;
int[] vis = {0, 0, 0, 0, 0, 0};
dfs(str, vis, n, 0);
return ans;
}
public static void dfs(String[] str, int[] vis, int n, int p) {
if (p == n) {
ans++;
return ;
}
for (int i = 0; i < str[p].length(); i++) {
if (vis[str[p].charAt(i) - '0'] == 0) {
vis[str[p].charAt(i) - '0'] = 1;
dfs(str, vis, n, p + 1);
vis[str[p].charAt(i) - '0'] = 0;
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
while (in.hasNext()) {
int n = in.nextInt();
String[] str = new String[n];
for (int i = 0; i < n; i++) {
str[i] = in.next();
}
int ans = getAns(str, n);
System.out.println(ans);
}
in.close();
}
}
发表于 2016-07-06 18:22:29
回复(1)
//非递归解法和递归解法，有兴趣的可以参考下
// letv1.cpp : 定义控制台应用程序的入口点。
//这道题的非递归解法，有兴趣的可以参考一下
//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct node
{
string * ps;
int i;
};
int findNum(vector<string> data)
{
if (data.size() == 1)
{
return data[0].size();
}
vector<struct node *> stk;
vector<struct node *>::iterator it;
struct node * pNode = new struct node;
struct node * pTmp;
pNode->ps = &data[0];
pNode->i = 0;
int j = 1;
string * now = &data[1];
int k = 0;
int num = 0;
stk.push_back(pNode);
int m;
while (true)
{//while1
for (m = k; m < now->size(); m++)
{
bool flag = true;
for (it = stk.begin(); it != stk.end(); it++)
{
if ((*((*it)->ps))[(*it)->i] == (*now)[m])
{
flag = false;
break;
}
}
if (flag == true)
{
pNode = new struct node;
pNode->ps = now;
pNode->i = m;
stk.push_back(pNode);
break;
}
}
if (m < now->size())
{
if (j < data.size() - 1)
{
j++;
k = 0;
now = &data[j];
}
else
{
if (m == now->size() - 1)
{
it = stk.end() - 1;
pTmp = *it;
stk.erase(it);
delete pTmp;
it = stk.end() - 1;
pTmp = *it;
k = (*it)->i + 1;
now = (*it)->ps;
stk.erase(it);
delete pTmp;
j--;
num++;
if (stk.size() == 0 && k==now->size())
{
break;
}
}
else
{
k=m+1;
it = stk.end() - 1;
pTmp = *it;
stk.erase(it);
delete pTmp;
num++;
}
}
}
else
{
it = stk.end() - 1;
pTmp = *it;
now = (*it)->ps;
k = (*it)->i+1;
stk.erase(it);
delete pTmp;
j--;
if (stk.size() == 0 && k == now->size())
{
break;
}
}
}//while
return num;
}
int main()
{
vector<string> data;
int n;
string tmp;
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
string tmp;
cin >> tmp;
data.push_back(tmp);
}
cout << findNum(data) << endl;
data.clear();
}
return 0;
}
//以下是递归的解法
// letv1Recursion.cpp : 定义控制台应用程序的入口点。
//
//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int getNum(vector<string> data, int i, string &s)
{
int num = 0;
int j;
for (j = 0; j < data[i].size(); j++)
{
char a = data[i][j];
if (s.find(a)== string::npos)
{
s.push_back(a);
if (i == data.size() - 1)
{
num++;
s.pop_back();
}
else
{
num+=getNum(data, i + 1, s);
s.pop_back();
}
}
}
//s.pop_back();
return num;
}
int main()
{
vector<string> data;
int n;
while (cin>>n)
{
int i = 0;
string s = "";
int num = 0;
for (int j = 0; j < n; j++)
{
string tmp;
cin >> tmp;
data.push_back(tmp);
}
cout<<getNum(data, i, s)<<endl;
data.clear();
}
return 0;
}
编辑于 2016-06-20 12:37:42
回复(4)
//自己觉得算java版本、递归解法里面比较简单的解法了
//首先用ArrayList<Integer>[N] 数组存储 N 个狂战士的可抵抗对象的list
//其次利用boolean[6] 存储被抵抗者的状态，true代表已被抵抗，false代表未被抵抗
//接着采用 深搜 算法直接返回答案
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int N = scan.nextInt();
//*****存储*******//
ArrayList<Integer>[] S = (ArrayList<Integer>[])(new ArrayList[N]);
for(int i = 0; i < N; i++){
S[i] = new ArrayList<Integer>();
String s = scan.next();
for(int j = 0; j < s.length(); j++){
S[i].add((int)s.charAt(j) - (int)'0' );
}
}
//*****//
//状态bool数组
boolean[] isG = new boolean[6];
int result = 0;
result = count(isG,S,0,N);
System.out.println(result);
}
}
// DFS
private static int count(boolean[] isG,ArrayList<Integer>[] S,int n,int N){
if(n >= N) return 1; // 返回条件 ，每一中分配到最后方案的都是一种解法
int result = 0;
for(int num : S[n]){ // 遍历当前狂战士所能抵抗的对象，num代表每一个结果
if(isG[num]) continue; // 剪枝
else{
isG[num] = true; // 设置状态
result += count(isG,S,n+1,N);
isG[num] = false; // 恢复状态！！！
}
}
return result;
}
}
发表于 2016-08-30 16:11:56
回复(0)
/**java实现的 递归解法与非递归解法，交流学习。**/
package cn.leshi.coding.first;
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
public class Arrangement {
//全部方案的个数
public int allProgramCount = 0;
public static void main(String args[]) {
Arrangement arrangement = new Arrangement();
arrangement.preprocess(2, new String[]{"01","23"});
System.out.println();
arrangement.allProgramCount = 0;
arrangement.preprocess(2, new String[]{"01","01"});
System.out.println();
arrangement.allProgramCount = 0;
arrangement.preprocess(3, new String[]{"3","015","5"});
}
/**
* 预处理 numberOfFighter 代表狂战士的人数。 covers 的长度等于
* numberOfFighter，每一个数组代表[index]的狂战士能克制的 的 天之驱逐者 的组合。
**/
public void preprocess(int numberOfFighter, String covers[]) {
List<Integer[]> emerySet = new ArrayList<Integer[]>();
// 转换成char数组 保存起来。
for (int index = 0; index < numberOfFighter; index++) {
char emery[] = covers[index].toCharArray();
Integer intEmery[] = new Integer[emery.length];
for (int inner = 0; inner < emery.length; inner++) {
intEmery[inner] = (int) emery[inner];
}
emerySet.add(intEmery);
}
// 6-numberOfFighter的部分，用大于5的数字填充一个，不影响总数。
if (numberOfFighter < 6) {
for (int index = numberOfFighter - 1; index < 6; index++) {
char addValue = (char)('6' + index);
emerySet.add(new Integer[]{(int) addValue});
}
}
/*for(int outter = 0;outter < 6;outter++) {
for(int inner = 0;inner < emerySet.get(outter).length;inner++) {
System.out.print(emerySet.get(outter)[inner] + " , ");
}
System.out.println();
}*/
//int totalCount = arrange(emerySet);
// 记录一个分配方案
List<Integer> aProgram = new LinkedList<Integer>();
recursiveArrange(emerySet,0,aProgram);
System.out.println("方案总数 = " + allProgramCount);
}
/**
* 非递归解法。
* 分配方案 List<Integer[]> emerySet 代表每个狂战士魔法所能克制的 敌人的数组集合。
**/
public int arrange(List<Integer[]> emerySet) {
// 统计总的 分配方案
int totalcount = 0;
// 记录一个分配方案
List<Integer> aProgram = new LinkedList<Integer>();
for (int inner1 = 0; inner1 < emerySet.get(0).length; inner1++) {
aProgram.add((int) emerySet.get(0)[inner1]);
for (int inner2 = 0; inner2 < emerySet.get(1).length; inner2++) {
if (!aProgram.contains(emerySet.get(1)[inner2])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(1)[inner2]);
for (int inner3 = 0; inner3 < emerySet.get(2).length; inner3++) {
if (!aProgram.contains(emerySet.get(2)[inner3])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(2)[inner3]);
for (int inner4 = 0; inner4 < emerySet.get(3).length; inner4++) {
if (!aProgram.contains(emerySet.get(3)[inner4])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(3)[inner4]);
for (int inner5 = 0; inner5 < emerySet.get(4).length; inner5++) {
if (!aProgram.contains(emerySet.get(4)[inner5])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(4)[inner5]);
for (int inner6 = 0; inner6 < emerySet.get(5).length; inner6++) {
if (!aProgram.contains(emerySet.get(5)[inner6])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(5)[inner6]);
totalcount++;
System.out.println("组合为 ＝ " + aProgram.toString());
}
if(aProgram.size() > 5) {
aProgram.remove(aProgram.get(5));
}
}//for6
}//if5
if(aProgram.size() > 4) {
aProgram.remove(aProgram.get(4));
}
}// for5
}//if4
if(aProgram.size() > 3) {
aProgram.remove(aProgram.get(3));
}
}// for4
}//if3
if(aProgram.size() > 2) {
aProgram.remove(aProgram.get(2));
}
}// for3
}//if2
if(aProgram.size() > 1) {
aProgram.remove(aProgram.get(1));
}
}// for2
aProgram.remove(aProgram.get(0));
}// for1
return totalcount;
}
//递归解法。
public void recursiveArrange(List<Integer[]> emerySet, int num, List<Integer> aProgram) {
if(num == 6) {
return ;
}
for(int index = 0;index < emerySet.get(num).length;index++) {
if (!aProgram.contains(emerySet.get(num)[index])) {
// 如果数字 未被包含，加入链表中
aProgram.add((int) emerySet.get(num)[index]);
recursiveArrange(emerySet,num+1,aProgram);
}
//满足要求，总数加１
if(aProgram.size() == 6) {
outputValue(aProgram);
allProgramCount++;
}
if(aProgram.size() > num) {
aProgram.remove(aProgram.get(num));
}
}
}
public void outputValue(List<Integer> aProgram) {
for(int index = 0;index < aProgram.size();index++) {
int value = aProgram.get(index);
System.out.print((char)value + " ");
}
System.out.println();
}
}
编辑于 2016-08-10 21:15:09
回复(0)
/*将问题转化为求一棵树第n层有多少叶子节点的问题，所以使用DFS方法，只需要判断有哪些分支有n层即可*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int res;
void getNumDFS(vector<string>,vector<int>,int,int);
int main(){
int n;
while(cin>>n){
res = 0;
vector<int> visit= {0, 0, 0, 0, 0, 0};
vector<string> data;
for(int i=0;i<n;i++){
string tmp;
cin >> tmp;
data.push_back(tmp);
}
getNumDFS(data,visit,n,0);
cout<<res<<endl;
}
return 0;
}
void getNumDFS(vector<string> data,vector<int> visit, int n,int p){
if(n==p){
res++;
return;
}
for(int i =0;i<data[p].size();i++){
if(visit[data[p][i]-'0']==0){
visit[data[p][i]-'0'] = 1;
getNumDFS(data,visit,n,p+1);
visit[data[p][i]-'0']=0;
}
}
}
发表于 2016-07-14 20:48:05
回复(0)
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Main {
// 利用回溯+减枝
static int answer_qty = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
List<String> conquer = new ArrayList<String>();
//用于保存当前的前k个元素的排列
Set<Character> result = new HashSet<Character>();
//以下为初始化过程。
while (in.hasNext()) {
answer_qty = 0;
conquer.clear();
result.clear();
int num = in.nextInt();
for (int i = 0; i < num; ++i) {
conquer.add(in.next());
}
int index = 0;
//问题求解方法
permutation(conquer, index, result);
System.out.println(answer_qty);
}
}
// 减治，将N组元素的排序问题，化简为N-1组元素的排序问题
//利用了经典全排列问题的思想，只不过第i个位置上的元素可选的集合不再是所有元素
//每个位置i的可选元素的集合为 conquer.get(i) //此外还有一个约束条件：选取的元素不能相同
public static void permutation(List<String> conquer, int index, Set<Character> result) {
if (conquer == null)
return;
// 排序完毕
if (index == conquer.size()) {
answer_qty++;
return;
}
String currentRow = conquer.get(index);
for (int i = 0; i < currentRow.length(); ++i) {
//如果这个字符还未被使用，则可以加入到排列中
//如果已经被使用采用，直接跳过，加快速度
if (!result.contains(currentRow.charAt(i))) {
result.add(currentRow.charAt(i));
permutation(conquer, index+1, result);
result.remove(currentRow.charAt(i));
}
}
}
}
编辑于 2017-06-05 11:35:30
回复(0)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
inttime;
intdis[6];
voiddfs(chara[][7],intstep,intn,intend){
inti,j,k;
if(step==end){
time++;
return;
}
for(inti=0;i<n;i++){
if(dis[a[step][i]]==0){
dis[a[step][i]]=1;
dfs(a,step+1,strlen(a[step+1]),end);
dis[a[step][i]]=0;
}
}
}
intmain(){
intn,i,k,p;
longlongsum=0;
intf;
chartemp;
chara[6][7];
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++){
scanf("%s",a[i]);
}
time=0;
memset(dis,0,sizeof(int));
dfs(a,0,strlen(a[0]),n);
printf("%d\n",time);
}
}
发表于 2016-10-25 16:38:23
回复(0)
//动态规划#include<cstdio>#include<cstring>intdp[10][(1<<6)+5];intmain(){intn,a[10],i,j,k;chars[10];while(~scanf("%d",&n)){for(i=1;i<=n;i++){a[i]=0;scanf("%s",s);for(j=0;s[j];j++){a[i]|=(1<<(s[j]-48));}}memset(dp,0,sizeof(dp));dp[0][0]=1;intl=(1<<6);for(i=1;i<=n;i++)for(j=0;j<l;j++){for(k=0;k<6;k++){if(((a[i]>>k)&1)&&((j>>k)&1))dp[i][j]+=dp[i-1][j^(1<<k)];}}intans=0;for(i=0;i<l;i++){intcnt=0;for(j=0;j<6;j++)if((i>>j)&1)cnt++;if(cnt==n)ans+=dp[n][i];}printf("%d\n",ans);}return0;}
发表于 2016-08-14 09:28:11
回复(0)
//利用递归来模拟多重嵌套循环.
import java.util.Scanner;
public class Main{
static String res = "";
static int num = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int xb = 0;
while(in.hasNext()){
int count = in.nextInt();
String[] Si = new String[count];
for(int i=0;i<count;i++)
Si[i] = in.next();
dfs(Si,xb);
System.out.println(num);
res = "";
num = 0;
}
}
private static void dfs(String[] Si,int xb) {
for(int i=0;i<Si[xb].length();i++){
if(!res.contains(Si[xb].charAt(i)+"")){
if(xb == Si.length-1){//到了数组尾
num++;
}
else{
res = res + Si[xb].charAt(i);
dfs(Si, xb+1);
res = res.substring(0,res.length()-1);
}
}
}
}
}
发表于 2016-07-18 21:07:02
回复(0)
#include<iostream>
#include<string>
using namespace std;
bool isnotin(string now, char sij)
{
if(now.length() == 0)
return true;
int index = now.find(sij);
if(index == -1)
return true;
else
return false;
}
int main()
{
int n;
while(cin >> n)
{
if(n > 6 || n < 1)
break;
int i, j, temp, count;
count = 1;
char **s = new char *[n];
for(i = 0; i < n; i++)
{
s[i] = new char [7];
cin >> s[i];
}
string now = "";
for(i = 0; i < n; i++)
{
temp = 0;
for(j = 0;s[i][j] != '\0'; j++)
if(isnotin(now, s[i][j]))
{
now += s[i][j];
temp++;
}
if(temp == 0)
{
count = 0;
break;
}
count *= temp;
}
if(count == 0)
return 0;
cout << count << endl;
for(i = 0; i < n; i++)
delete [] s[i];
delete s;
}
return 0;
}
本地VS2010运行没问题，提交却出现这样的问题，我是循环判断的啊。。
你的代码仅仅处理了一个测试用例，没有循环处理多个测试用例。
比如对于求解A+B的和的题目，需要按照以下代码来处理
正确代码：
#include <stdio.h> int main() { int a,b; while(scanf("%d %d",&a, &b) != EOF)//注意while处理多个case printf("%d",a+b); //根据题目情况是否输出回车 return 0; }
错误代码:
#include <stdio.h> int main() { int a,b; scanf("%d %d",&a, &b);//没有处理多个case printf("%d",a+b); //根据题目情况是否输出回车 return 0; }
发表于 2016-06-22 21:11:00
回复(0)
好坑。
用python在牛客网写算法有个很奇葩的问题，分割字符串如果用line.split()就可以通过，用line.split('
')就失败 为什么呀，我本地测试这两种分割完全一致呀
正确的源码如下
# -*- coding:utf-8 -*-
#step为第step个空格之前，num共有多少个空格，s为字符串，mark为标记序列
def dfs(step,num,s,mark):
global number
if step>=num:
number+=1
else:
sline=s[step]
for i in sline:
if mark[int(i)]==0:
mark[int(i)]=1
dfs(step+1,num,s,mark)
mark[int(i)]=0
try:
while True:
n = int(raw_input())
line = raw_input()
if n == '' or line == '':
break
s=line.split()# list
number=0
mark=[0,0,0,0,0,0]#标记0-5是否已经出现，初始化为未出现
dfs(0,n,s,mark)
print number
except:
pass
如果修改第20行，提示只通过了一个样例，太奇葩了。。。
发表于 2016-06-22 11:34:26
回复(0)
就是一棵树，求叶子节点个数
我直接遍历的
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { //获取输入 int N = in.nextInt(); String[] si = new String[N]; for (int i = 0; i < N; i++) { si[i] = in.next(); } int count = work(si, 0, new ArrayList<Character>(si.length)); System.out.println(count); } } /** * 进行计算的方法 * @param si 输入的字符串数组 * @param i 表示进行到了树的第i层 * @param list 保存根节点到当前节点的路径，用于判断重复 * @return 表示当前树（子树）的可行方案数量 */ public static int work(String[] si, int i, List<Character> list) { if (i != list.size()) return 0; if (i >= si.length) return 0; int count = 0; String layel = si[i]; for (int j = 0; j < layel.length(); j ++ ) { Character sub = layel.charAt(j); if (!list.contains(sub)) { list.add(sub); if (list.size() == si.length) { count ++; list.remove(si.length - 1); continue; } count += work(si, i + 1, list); list.remove(list.size() - 1); } } return count; } }
编辑于 2016-06-16 17:06:01
回复(2)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
int num=cin.nextInt();
String [] si=new String[num];
for(int i=0;i<si.length;i++)
{
si[i]=cin.next();
}
int [] select={0,0,0,0,0,0};//初始化一个标志数组，表示每个是否被选中过，一开始都为0，表示都没被选中过
int ans[]=new int[1];
//Integer ans = new Integer(0);
int n=0;
dfs(n,num,ans,si,select);
//n表示正在搜索第几个字符串,num表示字符串总数，ans表示结果，si表示字符串数组，select表示标志数组
//for(int i=0;i<si.length;i++)
//System.out.println(si[i]);
System.out.println(ans[0]);
}//while
}//main
private static void dfs(int n,int num,int ans[],String [] si,int [] select)
//n表示正在搜索第几个字符串,num表示字符串总数，ans表示结果，si表示字符串数组，select表示标志数组
{
//System.out.println("n="+n);
//System.out.println("num="+num);
if(n==num)
{
ans[0]++;
//System.out.println(ans);//测试到这一步是否正确
return ;
}
for(int i=0;i<si[n].length();i++)
{
if(select[si[n].charAt(i)-'0']==0)//第n个字符串的第i个字符没被使用过
{
select[si[n].charAt(i)-'0']=1;
dfs(n+1,num,ans,si,select);//搜索的第n+1个字符串
//System.out.println("ans:"+ans);
select[si[n].charAt(i)-'0']=0;
}
}
}
}//class
发表于 2016-06-15 19:37:16
回复(2)
import java.util.HashSet;
import java.util.Scanner;
public class Main {
static int sum;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext())
{
sum = 0;
int N = Integer.valueOf(scanner.nextLine().split(" ")[0]);//狂战士的个数
String[] inputarrr = scanner.nextLine().split(" ");//每个狂战士对应克服的天之
HashSet<Character> sets = new HashSet<Character>();
pailie(inputarrr, 0, sets);
System.out.println(sum);
}
}
private static void pailie(String[] input, int target, HashSet<Character> sets)
{
if(target == input.length)
{
sum++;
return;
}
else
{
String str = input[target];
for(int i=0;i<str.length();i++)
{
if(!sets.contains(str.charAt(i)))
{
sets.add(str.charAt(i));
pailie(input, target+1, sets);
sets.remove(str.charAt(i));
}
}
}
}
}
发表于 2016-06-15 15:54:55
回复(1)
简单搜索，用了位运算加速，供参考import java.util.Scanner; public class Main { static Scanner sc; static int n; static int[] a; static int ans; public static void main(String[] args) { sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); a = new int[n]; for (int i=0;i<n;i++) { a[i] = strToBin(sc.next()); } ans = 0; dfs(0, (1 << 6) - 1); System.out.println(ans); } } private static void dfs(int dep, int x) { if (dep == n) { ans++; return; } int t = a[dep]; t &= x; int d = 0; while (t > 0) { while ((t & 1) == 0) { d++; t >>= 1; } x &= ~(1 << d); dfs(dep + 1, x); x |= (1 << d); t >>= 1; d++; } } private static int strToBin(String str) { int x = 0; for (int i=0;i<str.length();i++) { int t = (int)str.charAt(i) - (int)'0'; x = x | (1 << (t)); } return x; } }
编辑于 2016-06-15 14:41:35
回复(1)
问题信息
通过挑战的用户
-
2022-10-05 23:32:22
-
2022-07-31 11:34:03
-
2021-09-12 20:41:08
-
2021-01-11 09:20:15
-
2020-05-07 10:54:31
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
