当前位置：网站首页>图论，二叉树，dfs，bfs，dp，最短路专题
图论，二叉树，dfs，bfs，dp，最短路专题
2022-08-09 06:34:00 【51CTO】
目录
- 1167 逆序数（大数据）
- 1179 Shortest Path
- Problem C 1195 Large Population
- Problem D 1245 Lisa's Puzzle
- Problem E 1250 Bonus
- Problem F 1288 Binary Search Tree
- Problem G 1302 Balance Tree
- Problem H 1369 Black White Chess
- Problem L 1389 二叉查找树
- Problem P 1418 消星星
- Problem R 1433 Swap Digits
1167 逆序数（大数据）
题目描述
给你一个序列x1,x2,…,xn,如果数对< xi,xj >，其中i< j,而xi> xj我们称之为逆序数对。 一个序列的逆序数对的数目，称为这个序列的逆序数。 比如说序列 3 1 2 ,逆序数对为 ️,1>和<3,2>，所以这个序列的逆序数为2。 现在给你一个数字序列，请求其逆序数。
输入
每个样例为两行，第一行为一个整数n(n≤10,000)，表示序列中数字的个数，如果n为0，则表示输入结束，不需要处理。 第二行是n个整数xi，0≤xi≤100,000。输入数据保证序列中没有相同整数。
输出
每行输出一个整数，表示其序列数。
样例输入
3
3 1 2
4
1 2 3 4
0
样例输出
2
0
简单来说，就是直接套用递归算法的模板，进行一些变通。
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
util.
Scanner;
public
class
Main {
public
static
void
main(
String[]
args) {
// TODO Auto-generated method stub
Scanner
in
=
new
Scanner (
System.
in);
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
while(
in.
hasNext()) {
int
n
=
in.
nextInt();
if(
n
==
0)
return;
int []
a
=
new
int [
n];
for(
int
i
=
0;
i
<
n;
i
++) {
a[
i]
=
in.
nextInt();
}
int
ans
=
process(
a,
0,
n
-
1);
pw.
println(
ans);
pw.
flush();
}
}
public
static
int
process(
int[]
arr,
int
l,
int
r){
if(
l
==
r){
return
0;
}
int
mid
=
l
+((
r
-
l)
>>
1);
return
process(
arr,
l,
mid)
+
process(
arr,
mid
+
1,
r)
+
merge(
arr,
l,
mid,
r);
}
public
static
int
merge(
int[]
arr,
int
l,
int
mid,
int
r){
int[]
help
=
new
int[
r
-
l
+
1];
int
p1
=
l;
int
p2
=
mid
+
1;
int
i
=
0;
int
res
=
0;
while(
p1
<=
mid
&&
p2
<=
r){
res
+=
arr[
p1]
>
arr[
p2]
?(
mid
-
p1
+
1):
0;
help[
i
++]
=
arr[
p1]
<=
arr[
p2]
?
arr[
p1
++]:
arr[
p2
++];
}
while(
p1
<=
mid){
help[
i
++]
=
arr[
p1
++];
}
while(
p2
<=
r){
help[
i
++]
=
arr[
p2
++];
}
for(
i
=
0;
i
<
help.
length;
i
++){
arr[
l
+
i]
=
help[
i];
//这个过程中相当于给a排序，调用了a的地址
}
return
res;
}
}
- 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.
1179 Shortest Path
题目描述
N(3≤N≤1,000)个城市（编号从1~N），M(N-1≤M≤10,000)条公路连接这些城市，每条公路都是双向通车的。 你想从1号城市出发，到达N号城市，期间你希望通过按顺序经过K(0≤K≤3)个指定的城市（这K+2个城市只允许达到1次），求最短的里程。
输入
存在多个样例。 每个样例的第一行是三个整数N，M，K。如果N，M，K为0，则表示输入结束。 以后是M行表示M条公路，每行三个整数x(1≤x≤N),y(1≤y≤N),c(1≤c≤1,000),表示城市x与城市y之间有一条距离为c的公路。输入保证任意两座城市之间至少存在一条路。然后的一行包含K个城市的序号，序号属于[2,N-1]。
输出
每行输出一个样例的结果，为一个整数。如果不存在这样的方案，输出“Impossible”。
样例输入
3 3 1
1 2 3
2 3 4
1 3 2
2
0 0 0
样例输出
7
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
util.
Arrays;
import
java.
util.
Scanner;
public
class
Main {
static
int [][]
mmap
=
new
int [
1105][
1105];
static
int
c[]
=
new
int [
20];
static
int
dis[]
=
new
int [
1100];
static
int
vis[]
=
new
int [
1100];
static
int
n,
k;
static
int
inf
=
99999999;
//如果这里写成Integer.MAX_VALUE会wa
public
static
void
main(
String[]
args) {
// TODO Auto-generated method stub
Scanner
in
=
new
Scanner (
System.
in);
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
int
m
=
0;
while(
in.
hasNext()) {
n
=
in.
nextInt();
m
=
in.
nextInt();
k
=
in.
nextInt();
if(
n
==
0
&&
m
==
0
&&
k
==
0) {
return ;
}
for(
int
i
=
1;
i
<=
n;
i
++) {
for(
int
j
=
1;
j
<=
n;
j
++) {
mmap[
i][
j]
=
inf;
}
}
for(
int
i
=
1;
i
<=
n;
i
++) {
mmap[
i][
i]
=
0;
}
for(
int
i
=
0;
i
<
m;
i
++) {
int
aa
=
in.
nextInt();
int
bb
=
in.
nextInt();
int
cc
=
in.
nextInt();
if(
cc
<
mmap[
aa][
bb]) {
mmap[
aa][
bb]
=
mmap[
bb][
aa]
=
cc;
}
}
c[
0]
=
1;
for(
int
i
=
1;
i
<=
k;
i
++) {
c[
i]
=
in.
nextInt();
}
c[
k
+
1]
=
n;
int
ans
=
0,
jud
=
1;
for(
int
i
=
0;
i
<=
k;
i
++) {
dij(
c[
i],
c[
i
+
1]);
if(
dis[
c[
i
+
1]]
>=
inf) {
jud
=
0;
break;
}
ans
+=
dis[
c[
i
+
1]];
}
if(
jud
==
0) {
pw.
println(
"Impossible");
pw.
flush();
}
else {
pw.
println(
ans);
pw.
flush();
}
}
}
static
void
dij(
int
x,
int
y) {
int
mmin
=
0,
pos
=
0;
for(
int
i
=
0;
i
<
1100;
i
++) {
vis[
i]
=
0;
}
for(
int
i
=
1;
i
<=
n;
i
++) {
dis[
i]
=
mmap[
x][
i];
}
for(
int
i
=
0;
i
<=
k
+
1;
i
++) {
if(
c[
i]
!=
x
&&
c[
i]
!=
y) {
vis[
c[
i]]
=
1;
}
}
for(
int
i
=
2;
i
<=
n;
i
++) {
mmin
=
inf;
for(
int
j
=
1;
j
<=
n;
j
++) {
if(
vis[
j]
==
0
&&
dis[
j]
<
mmin) {
mmin
=
dis[
j];
pos
=
j;
}
}
vis[
pos]
=
1;
if(
mmin
>=
inf) {
break;
}
for(
int
j
=
1;
j
<=
n;
j
++) {
if(
vis[
j]
==
0
&&
dis[
pos]
+
mmap[
pos][
j]
<
dis[
j]) {
dis[
j]
=
dis[
pos]
+
mmap[
pos][
j];
}
}
}
}
}
- 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.
Problem C 1195 Large Population
题目描述
很多城市人口众多，政府决定在不同城市之间修建高速公路提高相互之间的交通条件。 但是由于修建费用昂贵，所以政府只要能保证所有城市都可以通过高速公路互联就可以了。 但是政府又想这些公路的容量之和尽可能的大。请你设计一下线路，看最大容量和是多少？
输入
第一行是一个整数K，表示样例数。 每个样例的第一行是两个整数N和M（2≤N≤1000;N-1≤M≤10000）， N表示N个城市，其中城市代号用1到N表示；M表示可以修建的高速公路条数。 以后的M行为每条高速公路的容量情况。 每行为三个整数X，Y，C，其中1≤X,Y≤N,C≤10^6。
输出
每行输出一个样例的结果，为一个整数。
Sample Input
2
2 1
1 2 1
3 3
1 2 1
1 3 2
2 3 3
Sample Output
1
5
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
import
java.
util.
Arrays;
import
java.
util.
Scanner;
public
class
Main {
public
static
int
size
=
510;
//点的个数，多开10个防止越界
public
static
int
INF
=
0x3f3f3f3f;
//可以认为是正无穷
public
static
int
n,
m;
public
static
int[]
dist
=
new
int[
size];
//dist[i]存放i这个点到最小生成树集合的距离
public
static
boolean[]
st
=
new
boolean[
size];
//st[i]表示这个点是否已经加入了集合
public
static
int[][]
map
=
new
int[
size][
size];
//存放图的关系
public
static
void
Init() {
Arrays.
fill(
dist,
INF);
//初始化点到集合的距离为正无穷
for (
int
i
=
0;
i
<=
n;
i
++) {
//初始化各个点之间的距离为正无穷
Arrays.
fill(
map[
i],
INF);
}
}
public
static
int
prim() {
int
result
=
0;
//最小生成树集合大小
for (
int
i
=
0;
i
<
n;
i
++) {
//遍历n次,每次加入一个点
int
temp
=
-
1;
for (
int
j
=
1;
j
<=
n;
j
++) {
//找到还没有加入集合当中距离集合最近的点
if (
st[
j]
==
false
&& (
temp
==
-
1
||
dist[
temp]
>
dist[
j]))
temp
=
j;
}
if (
i
!=
0
&&
dist[
temp]
==
INF)
//如果这个点不是第一个点并且与集合的距离为正无穷，直接返回，因为最小的点距离集合的距离都为正无穷的，其他的点也是一样的
return
INF;
if (
i
!=
0) {
//如果这个点不是第一个点，将这个点到集合的距离加入最小生成树
result
+=
dist[
temp];
}
st[
temp]
=
true;
//将这个点标记为加入集合
for (
int
j
=
1;
j
<=
n;
j
++)
//用上面找到的点来更新其他点到集合的距离
dist[
j]
=
Math.
min(
dist[
j],
map[
temp][
j]);
}
return
result;
//返回结果
}
public
static
void
main(
String[]
args)
throws
IOException {
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
in.
nextToken();
int
k
=(
int)
in.
nval;
while(
k
-->
0) {
in.
nextToken();
n
= (
int)
in.
nval;
in.
nextToken();
m
= (
int)
in.
nval;
Init();
for (
int
i
=
0;
i
<
m;
i
++) {
in.
nextToken();
int
a
= (
int)
in.
nval;
in.
nextToken();
int
b
= (
int)
in.
nval;
in.
nextToken();
int
c
= (
int)
in.
nval;
c
=
c
*(
-
1);
map[
a][
b]
=
Math.
min(
map[
a][
b],
c);
//有重边
map[
b][
a]
=
map[
a][
b];
//两边都打通
}
int
t
=
prim();
if (
t
==
INF) {
//如果返回的结果为正无穷，表示没有生成最小生成树
System.
out.
println(
"impossible");
}
else
System.
out.
println(
t
*(
-
1));
}
}
}
- 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.
Problem D 1245 Lisa’s Puzzle
题目描述
5的二进制是101，13的二进制是1101，所以在二进制上，5是13的后缀。Lisa获得了一个长长的正整数列表，她想知道在列表中每一个数是列表中多少个其他数的后缀?
输入
第一行是一个整数N,1≤N≤100000,表示整数的个数。 以后N行，每行一个正整数，每个都可以使用一个32位int表示，而且所有的数都是唯一的。
输出
每个整数对应的结果输出一行，
样例输入
5
5
13
1
2
3
样例输出
1
0
3
0
0
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
public
class
Main {
static
class
Tree{
int
value;
Tree
left;
Tree
rigth;
public
Tree() {
//默认为0时，这里可以不写
value
=
0;
}
}
public
static
void
main(
String[]
args)
throws
IOException {
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
in.
nextToken();
int
n
=(
int)
in.
nval;
Tree
root
=
new
Tree();
long
a[]
=
new
long[
n];
for(
int
i
=
0;
i
<
n;
i
++) {
in.
nextToken();
a[
i]
=(
long)
in.
nval;
long
t
=
a[
i];
Tree
tree
=
root;
while(
t
!=
0) {
if((
t
&
1)
==
1) {
if(
tree.
rigth
==
null) {
tree.
rigth
=
new
Tree();
}
tree
=
tree.
rigth;
}
else {
if(
tree.
left
==
null) {
tree.
left
=
new
Tree();
}
tree
=
tree.
left;
}
tree.
value
++;
t
=(
t
>>
1);
}
}
for(
int
i
=
0;
i
<
n;
i
++) {
long
t
=
a[
i];
Tree
tree
=
root;
while(
t
!=
0) {
if((
t
&
1)
==
1) {
tree
=
tree.
rigth;
}
else {
tree
=
tree.
left;
}
t
=(
t
>>
1);
}
pw.
println(
tree.
value
-
1);
pw.
flush();
}
}
}
- 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.
Problem E 1250 Bonus
题目描述
要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。
由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。
老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？
输入
第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10000)和m(0≤m≤50000)，分别表示员工的人数以及工作表现记录的数目，员工的编号从1到n。
以后的m行为两个整数a和b(1≤a≠b≤n)，表示员工a的工作表现比b好。
输入数据保证工作表现不会有重复记录。
输出
每个样例先输出一行为奖金总数，然后再输出一行，按员工号的顺序，输出每个员工的奖金数，中间用一个空格隔开。
样例输入
2
3 2
1 2
2 3
3 2
1 2
2 1
样例输出
5664
2888 1888 888
2664
888 888 888
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
import
java.
util.
ArrayList;
import
java.
util.
LinkedList;
import
java.
util.
List;
import
java.
util.
Queue;
public
class
Main{
static
int[]
a;
static
List[]
list;
static
int
n;
static
int []
time;
static
class
Node{
int
x;
int
y;
public
Node(
int
x,
int
y) {
//这里一定要写
this.
x
=
x;
this.
y
=
y;
}
}
static
void
dfs() {
Queue
<
Node
>
qq
=
new
LinkedList
<>();
for(
int
i
=
1;
i
<=
n;
i
++) {
if(
time[
i]
==
0) {
qq.
add(
new
Node(
i,
1));
}
}
while(
!
qq.
isEmpty()) {
Node
node
=
qq.
poll();
a[
node.
x]
=
Math.
max(
node.
y,
a[
node.
x]);
for(
int
i
=
0;
i
<
list[
node.
x].
size();
i
++) {
//当不存在优先级别高的员工时，直接结束循环
int
v
=(
int)
list[
node.
x].
get(
i);
time[
v]
--;
if(
time[
v]
==
0) {
qq.
add(
new
Node(
v,
node.
y
+
1));
}
}
}
}
public
static
void
main(
String[]
args)
throws
IOException {
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
in.
nextToken();
int
k
=(
int)
in.
nval;
while(
k
-->
0) {
in.
nextToken();
n
=(
int)
in.
nval;
in.
nextToken();
int
m
=(
int)
in.
nval;
list
=
new
List[
n
+
1];
//List容器
for(
int
i
=
0;
i
<=
n;
i
++) {
list[
i]
=
new
ArrayList
<
Integer
>();
}
time
=
new
int[
n
+
1];
for(
int
i
=
0;
i
<
m;
i
++) {
in.
nextToken();
int
aa
=(
int)
in.
nval;
in.
nextToken();
int
bb
=(
int)
in.
nval;
list[
bb].
add(
aa);
//在员工b中存放比b优先级高的员工
time[
aa]
++;
//表示记录的员工a的优先次数
}
boolean
flag
=
true;
a
=
new
int [
n
+
1];
dfs();
for(
int
i
=
1;
i
<=
n;
i
++) {
if(
a[
i]
==
0) {
flag
=
false;
}
}
if(
flag) {
long
ans
=
0;
for(
int
i
=
1;
i
<=
n;
i
++) {
a[
i]
=(
a[
i]
-
1)
*
1000
+
888;
ans
+=
a[
i];
}
pw.
println(
ans);
pw.
flush();
for(
int
i
=
1;
i
<
n;
i
++) {
pw.
print(
a[
i]
+
" ");
pw.
flush();
}
pw.
println(
a[
n]);
pw.
flush();
}
else {
pw.
println((
n
*
888));
pw.
flush();
for(
int
i
=
1;
i
<
n;
i
++) {
pw.
print(
"888 ");
pw.
flush();
}
pw.
println(
"888");
pw.
flush();
}
}
}
}
- 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.
Problem F 1288 Binary Search Tree
题目描述
给1∼n的一个排列，把这个排列的数字按顺序依次插入一棵空的二叉查找树，得到一棵由这个排列建立的二叉查找树。 比如第一个样例的第1和2个排列最后得到的二叉查找树分别如下图中的左图和右图。
现在有m+1个排列，请问后m个排列建立的各个二叉查找树和第一个排列建立的二叉查找树是否相同。
输入
第一行是一个整数T(1≤T≤1000)，表示样例的个数。
每个样例的第1行是两个整数n(1≤n≤100),m(1≤m≤min(100,(n−1)!)。 每个样例的第2∼m+2行,每行是n个整数，表示排列。
输出
对于每个样例的后m每个序列的结果，先输出序列的序号，从1开始，然后输出一个英文冒号和空格，再输出结果，如果相同输出“Yes”，否则输出“No”。 每个样例最后输出一个空行。
样例输入
2
5 5
3 2 5 1 4
3 1 2 5 4
3 2 1 5 4
3 5 2 1 4
3 5 4 2 1
3 2 4 5 1
3 2
1 2 3
1 3 2
3 2 1
样例输出
1: No
2: Yes
3: Yes
4: Yes
5: No
1: No
2: No
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
public
class
Main {
static
int
n;
static
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
static
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
static
class
Tree{
int
x;
Tree
left;
Tree
right;
public
Tree(
int
v) {
x
=
v;
}
/*
* 等同于
* public Tree(int x){
* this.x=x;
* }
*/
}
static
void
f(
Tree
root)
throws
IOException {
for(
int
i
=
1;
i
<
n;
i
++) {
Tree
tree
=
root;
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
true) {
if(
t
<
tree.
x) {
if(
tree.
left
==
null) {
tree.
left
=
new
Tree(
t);
break;
}
else {
tree
=
tree.
left;
}
}
else {
if(
tree.
right
==
null) {
tree.
right
=
new
Tree(
t);
break;
}
else {
tree
=
tree.
right;
}
}
}
}
}
public
static
void
main(
String[]
args)
throws
IOException {
// TODO Auto-generated method stub
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
t
-->
0) {
in.
nextToken();
n
=(
int)
in.
nval;
in.
nextToken();
int
m
=(
int)
in.
nval;
in.
nextToken();
Tree
head
=
new
Tree((
int)
in.
nval);
/*
* head 是第一个二叉树的头肩点，即对照二叉树
* root 是后m个排序建立的各个二叉树的头节点
*/
f(
head);
for(
int
i
=
1;
i
<=
m;
i
++) {
in.
nextToken();
Tree
root
=
new
Tree((
int)
in.
nval);
f(
root);
if(
!
dfs(
root,
head)) {
pw.
println(
i
+
": No");
pw.
flush();
}
else {
pw.
println(
i
+
": Yes");
pw.
flush();
}
}
pw.
println();
pw.
flush();
}
}
static
boolean
dfs(
Tree
root,
Tree
head) {
if(
root
==
null
&&
head
==
null) {
return
true;
}
if(
root
==
null
||
head
==
null) {
return
false;
}
if(
root.
x
!=
head.
x) {
return
false;
}
else {
return
dfs(
root.
left,
head.
left)
&&
dfs(
root.
right,
head.
right);
}
}
}
- 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.
Problem G 1302 Balance Tree
题目描述
我们将数字序列按顺序依次插入一棵空的二叉查找树，得到一棵由这个序列建立的二叉查找树。
如果对于任何节点，其左右子树的高度相差不超过1，那么我们称其是平衡的。
请你写一个程序，判断一下，对于一个数字序列得到的二叉排序树是否是平衡的？
输入
第一行是一个整数T(1≤T≤1000)，表示样例的个数。
每个样例的第一行是一个整数n(1≤n≤1000)，表示数字序列的长度。
每个样例的第二行是n个互不相同的整数ai(1≤ai≤109)。
输出
每行输出一个样例的结果，如果是平衡的，输出Yes，否则输出No。
样例输入
3
5
4 3 2 1 5
5
3 4 2 1 5
5
4 2 1 3 5
样例输出
No
Yes
Yes
提示
第一个样例：
/
1
第二个样例:
第三个样例:
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStream;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
import
java.
util.
StringTokenizer;
public
class
Main {
static
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
static
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
static
int
n;
static
void
read(
Tree
head) {
for(
int
i
=
1;
i
<
n;
i
++) {
Tree
tmp1
=
head;
int
tmp
=(
int)
in.
nval;
while(
true) {
if(
tmp
<
tmp1.
value) {
if(
tmp1.
left
==
null) {
tmp1.
left
=
new
Tree(
tmp,
tmp1.
deep
+
1);
break;
}
else {
tmp1
=
tmp1.
left;
}
}
else {
if(
tmp1.
right
==
null) {
tmp1.
right
=
new
Tree(
tmp,
tmp1.
deep
+
1);
break;
}
else {
tmp1
=
tmp1.
right;
}
}
}
}
}
public
static
void
main(
String[]
args)
throws
IOException {
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
t
--!=
0) {
in.
nextToken();
n
=(
int)
in.
nval;
in.
nextToken();
Tree
head
=
new
Tree((
int)
in.
nval,
0);
read(
head);
boolean
flag
=
max(
head,
true).
flag;
if(
!
flag) {
pw.
println(
"No");
pw.
flush();
}
else {
pw.
println(
"Yes");
pw.
flush();
}
}
}
private
static
aa
max(
Tree
head,
boolean
flag) {
// TODO Auto-generated method stub
if(
head.
left
==
null
&&
head.
right
==
null) {
return
new
aa(
true,
head.
deep);
}
if(
head.
left
==
null) {
aa
r
=
max(
head.
right,
flag);
if(
flag
&&
r.
deep
-
head.
deep
>
1) {
return
new
aa(
false,
r.
deep);
}
return
new
aa(
flag,
r.
deep);
}
if(
head.
right
==
null) {
aa
l
=
max(
head.
left,
flag);
if(
flag
&&
l.
deep
-
head.
deep
>
1) {
return
new
aa(
false,
l.
deep);
}
return
new
aa(
flag,
l.
deep);
}
else {
aa
left1
=
max(
head.
left,
flag);
aa
right1
=
max(
head.
right,
flag);
if(
!
left1.
flag
||!
right1.
flag) {
flag
=
false;
}
int
left
=
left1.
deep;
int
right
=
right1.
deep;
if(
flag
&&
Math.
abs(
right
-
left)
>
1) {
flag
=
false;
}
return
new
aa(
flag,
Math.
max(
left,
right));
}
}
public
static
class
aa{
boolean
flag;
int
deep;
public
aa(
boolean
flag,
int
deep) {
this.
deep
=
deep;
this.
flag
=
flag;
}
}
public
static
class
Tree{
int
value;
Tree
left;
Tree
right;
int
deep;
public
Tree(
int
val,
int
deep) {
value
=
val;
this.
deep
=
deep;
}
}
}
- 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.
Problem H 1369 Black White Chess
题目描述
一个4×4的格子棋盘，每个格子上有白棋或者黑棋，我们可以做下面三种操作：
把同一行的棋子翻转（白变成黑，黑变成白）
把同一列的棋子翻转
把一个2×2的格子里的棋子翻转
求最少多少步操作，我们可以得到全部是黑的或者全部是白的棋局。
输入
第一行是一个整数T(1≤T≤100000)，表示样例的个数。 以后每行一个样例，每行是一个16位的二进制码，依次表示从第1行到第4行的棋局。
输出
每行输出一个样例的结果，如果无法达到目标，输出“-1”。
样例输入
5
0000000000000000
1111111111111111
0000111100001111
1000000000000000
1100000000000011
样例输出
0
0
2
-1
4
样例解释
第三个样例棋局如下
0000
1111
0000
1111
此时，翻转第1,3行可以得到全白；或者翻转第2,4行可以得到全黑。
第五个样例棋局如下
1100
0000
0000
0011
此时，依次翻转左上角在(1,1),(2,1),(3,1)的2×2的块，再翻转第4行，可以得到全白。
import
java.
io.
IOException;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
util.
HashSet;
import
java.
util.
Scanner;
public
class
Main {
private
static
String
bb(
String
s,
int
t) {
// TODO Auto-generated method stub
if(
t
<
4) {
//列变换
char[]
st
=
s.
toCharArray();
for(
int
i
=
0;
i
<
4;
i
++) {
if(
st[
i
*
4
+
t]
==
'1') {
st[
i
*
4
+
t]
=
'0';
}
else {
st[
i
*
4
+
t]
=
'1';
}
}
return
new
String (
st);
}
else
if(
t
<
8) {
t
-=
4;
char[]
st
=
s.
toCharArray();
for(
int
i
=
0;
i
<
4;
i
++) {
if(
st[
t
*
4
+
i]
==
'1') {
st[
t
*
4
+
i]
=
'0';
}
else {
st[
t
*
4
+
i]
=
'1';
}
}
return
new
String (
st);
}
else {
t
-=
8;
int
x
=
t
/
3;
int
y
=
t
%
3;
char[]
st
=
s.
toCharArray();
if(
st[
x
*
4
+
y]
==
'1') {
st[
x
*
4
+
y]
=
'0';
}
else {
st[
x
*
4
+
y]
=
'1';
}
x
=
x
+
1;
if(
st[
x
*
4
+
y]
==
'1') {
st[
x
*
4
+
y]
=
'0';
}
else {
st[
x
*
4
+
y]
=
'1';
}
x
=
x
-
1;
y
=
y
+
1;
if(
st[
x
*
4
+
y]
==
'1') {
st[
x
*
4
+
y]
=
'0';
}
else {
st[
x
*
4
+
y]
=
'1';
}
x
=
x
+
1;
if(
st[
x
*
4
+
y]
==
'1') {
st[
x
*
4
+
y]
=
'0';
}
else {
st[
x
*
4
+
y]
=
'1';
}
return
new
String (
st);
}
}
//这道题的思路就是先预处理出，从初始状态到最终状态的所有情况，所需的步数
//之后就进行字符串的读入，直接出答案
public
static
void
main(
String[]
args)
throws
IOException {
Scanner
in
=
new
Scanner(
System.
in);
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
int
t
=
in.
nextInt();
HashSet
<
String
>[]
pre
=
new
HashSet[
8];
for(
int
j
=
0;
j
<
8;
j
++) {
//初始化
pre[
j]
=
new
HashSet
<
String
>();
}
pre[
0].
add(
"0000000000000000");
pre[
0].
add(
"1111111111111111");
for(
int
i
=
0;
i
<
7;
i
++) {
for (
String
s :
pre[
i]) {
for(
int
j
=
0;
j
<
17;
j
++) {
String
tmp
=
bb(
s,
j);
boolean
flag
=
false;
for(
int
k
=
0;
k
<=
i;
k
++) {
if(
pre[
k].
contains(
tmp)) {
flag
=
true;
break;
}
}
if(
!
flag)
pre[
i
+
1].
add(
tmp);
}
}
}
while(
t
-->
0) {
int
f
=
0;
String
s
=
in.
next();
for(
int
i
=
0;
i
<
8;
i
++) {
if(
pre[
i].
contains(
s)) {
pw.
println(
i);
pw.
flush();
f
=
1;
break;
}
}
if(
f
==
0) {
pw.
println(
-
1);
pw.
flush();
}
}
}
}
- 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.
Problem L 1389 二叉查找树
题目描述
n个元素，依次插入一颗初始为空的二叉查找树。对于第i个元素，其所在二叉查找书的左右子树深度差的绝对值为di，求max{di}。
输入格式
第一行是一个整数T (1≤T≤1000)，表示样例的个数。 每个样例的第一行是一个整数n (1≤n≤1000)，表示元素的个数。 第二行是n个整数ai,(1≤ai≤109)，表示第i个元素的值，所有元素的值是唯一的。
输出格式
依次每行输出一个样例的结果，为一个整数。
样例输入
2
5
3 2 1 4 5
5
4 5 3 2 1
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
public
class
Main{
static
long
max
=
0;
static
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
static
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
static
int
n;
public
static
class
Tree{
int
value;
Tree
l;
Tree
r;
int
height;
public
Tree(
int
val,
int
deep) {
value
=
val;
this.
height
=
deep;
}
}
static
void
read(
Tree
head)
throws
IOException {
for(
int
i
=
1;
i
<
n;
i
++) {
Tree
tree
=
head;
in.
nextToken();
int
tmp
=(
int)
in.
nval;
while(
true) {
if(
tmp
<
tree.
value) {
if(
tree.
l
==
null) {
tree.
l
=
new
Tree(
tmp,
tree.
height
+
1);
break;
}
else {
tree
=
tree.
l;
}
}
else {
if(
tree.
r
==
null) {
tree.
r
=
new
Tree(
tmp,
tree.
height
+
1);
break;
}
else {
tree
=
tree.
r;
}
}
}
}
}
public
static
void
main(
String[]
args)
throws
IOException {
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
t
-->
0) {
max
=
0;
in.
nextToken();
n
=(
int)
in.
nval;
in.
nextToken();
Tree
head
=
new
Tree((
int)
in.
nval,
0);
read(
head);
f(
head);
pw.
println(
max);
pw.
flush();
}
}
private
static
long
f(
Tree
root) {
if(
root.
l
==
null
&&
root.
r
==
null) {
return
root.
height;
}
if(
root.
l
==
null) {
long
r
=
f(
root.
r);
max
=
Math.
max(
r
-
root.
height,
max);
return
r;
}
if(
root.
r
==
null) {
long
l
=
f(
root.
l);
max
=
Math.
max(
l
-
root.
height,
max);
return
l;
}
else {
long
left1
=
f(
root.
l);
long
right1
=
f(
root.
r);
max
=
Math.
max(
max,
Math.
abs(
right1
-
left1));
return
Math.
max(
left1,
right1);
}
}
public
static
class
Node{
boolean
flag;
int
deep;
public
Node(
boolean
flag,
int
deep) {
this.
deep
=
deep;
this.
flag
=
flag;
}
}
}
- 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.
Problem P 1418 消星星
题目描述
小代最近迷上了消灭星星，所以没时间给程设考试出题了。消灭星星游戏规则介绍：
初始有一个n×m大小的格子矩阵，每个格子里都有一个a到z的字符，表示一种颜色的星星。
两个格子如果有共同的边，则认为是相邻的。
当你点击一个星星，与它相邻的所有同颜色星星都会被消除，顺带着，所有与它相邻的同颜色星星相邻的同颜色星星也会被消除，以此类推。
点击一次星星，需要消耗1点能量。
假设你已经得到n×m的初始地图，你能判断你需要消耗多少能量消除所有星星吗？
输入
第一行一个t(1≤t≤10)，表示样例个数；
接下来每个样例的第一行是正整数n,m(1≤n,m≤103)，表示矩阵的大小。
接下来n行m列字符，表示地图，其中所有的字符都是小写字母。
输出
对于每个样例，每行输出一个答案，表示消灭所有星星至少需要多少能量。
样例输入
2
2 2
ab
ba
3 3
aab
cab
ccb
样例输出
4
3
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
public
class
Main {
static
int
n,
m;
static
char
a[][];
static
boolean [][]
flag;
static
void
dfs(
int
i,
int
j) {
flag[
i][
j]
=
true;
if(
i
>
0
&&!
flag[
i
-
1][
j]
&&
a[
i][
j]
==
a[
i
-
1][
j]) {
dfs(
i
-
1,
j);
}
if(
j
>
0
&&!
flag[
i][
j
-
1]
&&
a[
i][
j]
==
a[
i][
j
-
1]) {
dfs(
i,
j
-
1);
}
if(
i
<
n
-
1
&&!
flag[
i
+
1][
j]
&&
a[
i][
j]
==
a[
i
+
1][
j]) {
dfs(
i
+
1,
j);
}
if(
j
<
m
-
1
&&!
flag[
i][
j
+
1]
&&
a[
i][
j]
==
a[
i][
j
+
1]) {
dfs(
i,
j
+
1);
}
}
public
static
void
main(
String[]
args)
throws
IOException {
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
t
-->
0) {
int
ans
=
0;
in.
nextToken();
n
=(
int)
in.
nval;
in.
nextToken();
m
=(
int)
in.
nval;
a
=
new
char[
n][];
flag
=
new
boolean [
n][
m];
for(
int
i
=
0;
i
<
n;
i
++) {
in.
nextToken();
a[
i]
=
in.
sval.
toCharArray();
}
for(
int
i
=
0;
i
<
n;
i
++) {
for(
int
j
=
0;
j
<
m;
j
++) {
if(
!
flag[
i][
j]) {
dfs(
i,
j);
ans
++;
}
}
}
pw.
println(
ans);
pw.
flush();
}
}
}
- 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.
Problem R 1433 Swap Digits
题目描述
一个十进制整数n，你最多可以任意交换相邻的两个数码k次，请问能得到多少个不同的无前导0的数？
输入
第一行是一个整数T(1≤T≤200)。 以后每行一个样例，为两个整数n(1≤n≤109),k(1≤k≤20)
输出
每行输出一个样例的结果。
样例输入
2
10 1
123 2
样例输出
1
5
样例解释
第一个样例只能得到10;第二个样例可以得到123,132,213,312,231。
import
java.
io.
BufferedReader;
import
java.
io.
IOException;
import
java.
io.
InputStream;
import
java.
io.
InputStreamReader;
import
java.
io.
OutputStreamWriter;
import
java.
io.
PrintWriter;
import
java.
io.
StreamTokenizer;
import
java.
util.
HashSet;
import
java.
util.
LinkedList;
import
java.
util.
Queue;
import
java.
util.
StringTokenizer;
public
class
Main {
static
HashSet
<
Integer
>
set;
private
static
void
f(
int[]
a,
int
k) {
// TODO Auto-generated method stub
set.
add(
zhengshu(
a));
Queue
<
int[]
>
queue
=
new
LinkedList
<>();
queue.
add(
a);
while(
k
--!=
0) {
Queue
<
int[]
>
t
=
new
LinkedList
<>(
queue);
queue.
clear();
while(
!
t.
isEmpty()) {
int[]
tem
=
t.
poll();
for(
int
i
=
0;
i
<
tem.
length
-
1;
i
++) {
int
tt
=
tem[
i];
tem[
i]
=
tem[
i
+
1];
tem[
i
+
1]
=
tt;
if(
tem[
0]
!=
0) {
int
tem3
=
zhengshu(
tem);
if(
!
set.
contains(
tem3)) {
set.
add(
tem3);
queue.
add(
tem.
clone());
}
}
tt
=
tem[
i];
tem[
i]
=
tem[
i
+
1];
tem[
i
+
1]
=
tt;
}
}
}
}
public
static
void
main(
String[]
args)
throws
IOException {
StreamTokenizer
in
=
new
StreamTokenizer(
new
BufferedReader(
new
InputStreamReader(
System.
in)));
PrintWriter
pw
=
new
PrintWriter(
new
OutputStreamWriter(
System.
out));
in.
nextToken();
int
t
=(
int)
in.
nval;
while(
t
-->
0) {
in.
nextToken();
int
n
=(
int)
in.
nval;
in.
nextToken();
int
k
=(
int)
in.
nval;
int
tt
=
n;
int
len
=
0;
while(
tt
!=
0) {
len
++;
tt
/=
10;
}
int []
a
=
new
int[
len];
tt
=
n;
int
i
=
len
-
1;
while(
tt
!=
0) {
a[
i]
=
tt
%
10;
i
--;
tt
/=
10;
}
set
=
new
HashSet
<>();
f(
a,
k);
pw.
println(
set.
size());
pw.
flush();
}
}
private
static
int
zhengshu(
int[]
a) {
// TODO Auto-generated method stub
int
zhengshu
=
0;
for(
int
i
=
0;
i
<
a.
length;
i
++) {
zhengshu
=
zhengshu
*
10
+
a[
i];
}
return
zhengshu;
}
}
- 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.
边栏推荐
猜你喜欢
随机推荐
直接用的zip包 缺少很多依赖，pip没有，感觉用anaconda create一个环境会方便点
leetcode 之盛水问题
GNNExplainer applied to node classification task
sql problem solving statement to create a table
Explain the wait() function and waitpid() function in C language in detail
P6阿里机试题之2020 斐波那契数
The Integer thread safe
cut命令的使用实例
TCP segment of a reassembled PDU
idea中PlantUML插件使用
AD画PCB板教程 20分钟讲清楚操作流程 铺铜 网络标号
pycharm环境包导入到另外一个环境
Web APIs BOM- 操作浏览器：本地存储
INSTALL_RPATH and BUILD_RPATH problem in CMake
网络学习总结
Thread Pool Summary
Unity backgammon game design and simple AI implementation (1)
Go lang1.18入门精炼教程——第一章：环境搭建
无重复的字符的最长子串
mongo+ycsb性能测试及线程数分析