花生_TL007

这个屌丝很懒，什么也没留下！

热门标签

java在ACM中的应用_有这样的公式y=d(x1x2...xn)

作者：花生_TL007 | 2024-02-10 19:05:14

踩

有这样的公式y=d(x1x2...xn)

ACM模拟题讲解（1）-高精度

Java中提供了byte、short、int和long表示整数，float和double来表示浮点数，每种类型都有一定的表示范围，当超过了这个范围之后就不能处理了。为了提供对非常大的整数和浮点数的处理，Java提供了BigDecimal和BigInteger。下面的代码演示了BigDecimal和BigInteger的基本用法：

BigDecimal data1 = new BigDecimal("23232123456789.123456789");

BigDecimal data2 = new BigDecimal("23423423123456789.123456789");

BigDecimal data3 = data1.add(data2);

System.out.println(data3.toString());

BigInteger iData1 = new BigInteger("123123123456456789789123456789");

BigInteger iData2 = new BigInteger("12312312323232456456789789123456789");

BigInteger iData3 = iData1.add(iData2);

System.out.println(iData3.toString());

如果不使用这些类库如何实现大整数和大浮点数的计算呢？下面通过ACM模拟题介绍。

1、Exponentiation（不想看英文，可以直接跳到后面的中文部分）

Description

Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.

This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

Input

The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

Output

The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.

Sample Input

95.123 12

0.4321 20

5.1234 15

6.7592 9

98.999 10

1.0100 12

Sample Output

548815620517731830194541.899025343415715973535967221869852721

.00000005148554641076956121994511276767154838481760200726351203835429763013462401

43992025569.928573701266488041146654993318703707511666295476720493953024

29448126.764121021618164430206909037173276672

90429072743629540498.107596019456651774561044010001

1.126825030131969720661201

翻译：题目的含义是计算R（0.0 < R < 99.999）的n（0 < n <= 25）次方。

题目解析：

这个题目的关键是如何表示大的整数或者浮点数。针对本题目，计算n次方。可以单独处理小数的位置，如果R中的包含x位小数，则进行运算后的结果应该包括x*n位小数。可以采用数组表示R，然后进行运算即可。下面的方法供参考。

public static String exponentiation(String data,int n){

// 找小数点

int index = data.indexOf(".");

// 去掉小数点

String temp = data.replace(".","");

// 用数组表示输入的数据

byte[] inputData=new byte[temp.length()];

// 表示计算结果

byte[] result = new byte[160];

// 表示进位

byte pre=0;

// 初始化

for(int i=0;i<inputData.length;i++){

result[i] = Byte.parseByte(temp.substring(temp.length()-i-1,temp.length()-i));

inputData[i] = result[i];

}

// 计算n-1遍

for(int i=0;i<n-1;i++){

// 表示上一次的计算结果

byte[] tempResult = Arrays.copyOf(result,result.length);

// 对result初始化

Arrays.fill(result,0,result.length,(byte)0);

// 用上一次的计算结果与输入的数据相乘

for(int k=0;k<inputData.length;k++){

for(int j=0;j<150;j++){

// 两位相乘

byte tempMul = (byte)(tempResult[j]*inputData[k]+result[j+k]);

// 处理个位

result[j+k]=(byte)(tempMul%10);

// 处理进位

pre=(byte)(tempMul/10);

// 表示进到第几位

int pp=1;

// 处理进位

while(pre>0){

tempMul=(byte)(pre+result[j+k+pp]);

result[j+k+pp]=(byte)(tempMul%10);

pre=(byte)(tempMul/10);

pp++;

}

// 计算小数位

int digits;

if(index==-1)

digits = 0 ;

else

digits = n*(data.substring(index+1).length());

StringBuffer stringResult = new StringBuffer();

if(index==-1){ // 没有小数点

boolean b=false;

for(int i=result.length-1;i>=0;i--){

if(!b){ //前面都是0

if(result[i]==0)

continue;

else

b=true;

}

stringResult.append(result[i]);

}

}else{ // 有小数点

boolean b=false;

// 处理小数点之前

for(int i=result.length-1;i>=digits;i--){

if(!b){ //前面都是0

if(result[i]==0)

continue;

else

b=true;

}

stringResult.append(result[i]);

}

stringResult.append(".");

for(int i=digits-1;i>=0;i--){

stringResult.append(result[i]);

}

return stringResult.toString();

}

2、A + B Problem

Problem Description

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

Sample Input

1 2

112233445566778899 998877665544332211

Sample Output

Case 1:

1 + 2 = 3

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

翻译：题目要求就算两个大的整数的和。

题目解析：两个整数分别使用数组表示，然后每一位相加，并对进位处理即可。上一题的内容已经包含这个过程。这里不再给出参考代码。

ACM模拟题详解（2）——简单数论

有很多与数字相关的题目，主要考察基本的编程能力，如果数学比较好，丢与解决这些问题有比较好的帮助。下面的题目是学生收集的题目，我进行了讲解。

1、Self Numbers

Description

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.

Input

No input for this problem.

Output

Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.

Sample Input

Sample Output

| <-- a lot more numbers

9903

9914

9925

9927

9938

9949

9960

9971

9982

9993

题目翻译：有这样的公式y=d(x1x2…xn)=x1+x2+…+xn+ x1x2…xn，例如：

d(123) = 123+1+2+3=129

d(55)=55+5+5=65

这里把x1x2…xn称为y的生成子，例如123是129的生成子，55是65的生成子。题目要求列出10000以内没有生成子的整数。

题目详解：对1到10000的生成子进行遍历，看能够生成哪些数字，然后把不能生成的输出即可，下面的代码供参考。

public static void setNumbers(){

int[] numbers=new int[10000];

Arrays.fill(numbers, 0);

for(int i=1;i<10000;i++){

int temp = i+i%10+(i/10)%10+(i/100)%10+i/1000;

if(temp<10000)

numbers[temp-1]=1;

}

for(int i=0;i<9999;i++){

if(numbers[i]==0)

System.out.println(i+1);

}

2、Goldbach's Conjecture

Description

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can be written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.

20 = 3 + 17 = 7 + 13.

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)

Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

Input

The input will contain one or more test cases.Each test case consists of one even integer n with 6 <= n < 1000000. Input will be terminated by a value of 0 for n.

Output

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

Sample Input

Sample Output

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

翻译：据推测大于4的偶数都可以写成两个质数（素数）的和。让我们编写程序进行验证，如果有写出表达式，如果没有则输出“Goldbach's conjecture is wrong.”。如果能够写成的式子多于1个，则写出两个数字差比较大的那对。例如：

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23

输出42 = 5 + 37即可。因为37-5最大。

题目详解：题目比较简单，只要测试两个数是否为质数即可。下面的代码供参考。

* 8 = 3 + 5

* 20 = 3 + 17

* 42 = 5 + 37

public static void test(int x){

if(6<=x && x < 1000000){

if(x%2!=0){

System.out.println("输入数据不是偶数！");

}else{

boolean b=false;

for(int i=3;i+i<x;i++){

if(isPrime(i) && isPrime(x-i)){

System.out.println(x+" = "+i+" + "+(x-i));

b = true;

break;

}

if(!b)

System.out.println("Goldbach's conjecture is wrong.");

}

}else{

System.out.println("输入数据范围不对");

}

* 判断某个数是否为质数，如果是返回true

public static boolean isPrime(int x){

for(int i=2;i*i<=x;i++){

if(x%i==0)

return false;

}

return true;

}

3、Sum of Consecutive Prime Numbers

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

666

Sample Output

翻译：有些整数可以表示为多个连续质数的和，例如53 = 5 + 7 + 11 + 13 + 17，有的数字有多中表示方法，例如41可以表示为2+3+5+7+11+13, 11+13+17, and 41。题目要求计算给定的某个数有多少种表示方法。

题目详解：对于给定的某个数，先从2开始，然后找下一个质数，然后累加直到他们的和等于或者大于给定的数，如果等于说明是一组解，如果大于说明不是接，然后找下一个接，直到结束。下面的代码供参考。

* Sum of Consecutive Prime Numbers

public static int test2(int x){

int count=0;

for(int i=2;i+i<x;i++){

int sum = 0;

if(!isPrime(i)){

continue;

}

for(int j=i;j<x;j++){

// 判断是否为质数

if(!isPrime(j))

continue;

sum = sum+j;

// 判断是否满足条件

if(sum>=x){

if(sum==x){

count++;

}

break;

}

if(isPrime(x))

count++;

return count;

}

* 判断某个数是否为质数，如果是返回true

public static boolean isPrime(int x){

for(int i=2;i*i<=x;i++){

if(x%i==0)

return false;

}

return true;

}

4、Binomial Coefficients

Description

The binomial coefficient C(n, k) has been extensively studied for its importance in combinatorics. Binomial coefficients can be recursively defined as follows:

C(n, 0) = C(n, n) = 1 for all n > 0;

C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.

Given n and k, you are to determine the parity of C(n, k).

Input

The input contains multiple test cases. Each test case consists of a pair of integers n and k (0 ≤ k ≤ n < 231, n > 0) on a separate line.

End of file (EOF) indicates the end of input.

Output

For each test case, output one line containing either a “0” or a “1”, which is the remainder of C(n, k) divided by two.

Sample Input

1 1

1 0

2 1

Sample Output

翻译：二项式系数（可能翻译的不好）C(n, k)满足下面的要求：

C(n, 0) = C(n, n) = 1 for all n > 0;

C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.

题目要求根据给定的n和k(0 ≤ k ≤ n < 231, n > 0)计算C(n,k)，典型的递归问题。但是如果采用递归，当n的值比较大的时候，会堆栈益处。而上面的表达式应该有相应的公式。如果采用公式计算就会变的简单了。公式自己找吧。

ACM模拟题详解（3）——数论（续）

5、Prime Ring Problem

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input

n (0 < n < 20).

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input

Sample Output

Case 1:

1 4 3 2 5 6

1 6 5 2 3 4

Case 2:

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

翻译：n个数字（1,2,3...n）围成一个圈，要求相邻的两个数字之和是质数。题目要求根据给出的n，计算所有能够组成满足条件的圈的数字序列。

解题思路：

首先选择1，然后选择和1相加等于质数的数字，可能有很多种情况，例如（n=6的情况）：

1+2

1+4

1+6

然后针对每种情况，再选择与第二个数的和为质数的数字，得到下面的序列

1+2+3

1+2+5

1+4+3

1+6+5

直到所有的数字都选择完，把所有的组合列出即可。计算的过程就是构造下面的树的过程。

从图中可以看出1-4-3-2-5-6 和 1-6-5-2-3-4是两个合法的解。

对于树的遍历可以采用深度优先，也可以采用广度优先，如果采用广度优先占用的内存比较大，所以解空间比较大的时候不宜采用。

下面是采用广度优先实现的（当n=18和n=20的时候内存不够用）

* Prime Ring Problem

public static void test4(int n){

int values[] = new int[n];

// 初始化

for(int i=0;i<n;i++){

values[i] = i+1;

}

// 表示遍历过程中可能的解

List list = new ArrayList();

list.add(values);

// 处理后面的n-1个数字，1永远是第一个

for(int i=1;i<n;i++){

List temp = list;

list = new ArrayList();

// 对于每个可能的解，得到下一层节点

for(int j=0;j<temp.size();j++){

int tempValues[]=(int[])temp.get(j);

// 考虑所有可能的组合

for(int k=i;k<n;k++){

if(isPrime(tempValues[i-1]+tempValues[k])){

// 创建新的状态，并复制原来的值

int[] newValues = Arrays.copyOf(tempValues, tempValues.length);

// 交换i和k处的值

if(i!=k){

int change = newValues[i];

newValues[i] = newValues[k];

newValues[k] = change;

}

// 把新状态添加到列表中

list.add(newValues);

}

// 输出结果

for(int i=0;i<list.size();i++){

int[] tempValues = (int[])list.get(i);

if(isPrime(tempValues[0]+tempValues[n-1])){

for(int j=0;j<n;j++){

System.out.print(tempValues[j]+" ");

}

System.out.println();

}

System.out.println(list.size());

}

下面是深度优先的算法。

* Prime Ring Problem（深度优先）

public static void test5(int n){

// 数组的前n个元素表示环中的数字，第n+1个数据表示数组中前n+1个元素是满足条件的

int values[] = new int[n+1];

// 初始化

for(int i=0;i<n;i++){

values[i] = i+1;

}

values[n]=1;

// 表示遍历过程中可能的解

List list = new ArrayList();

list.add(values);

StringBuffer sb = new StringBuffer();

while(list.size()>0){

// 取出第一个元素

int tempValues[]=(int[])list.get(0);

// 表示处理到第几层，第一层用0表示

int index=tempValues[n];

// 遍历并生成所有可能的下一层节点

for(int k=tempValues[n];k<n;k++){

if(isPrime(tempValues[index-1]+tempValues[k])){

// 如果是最后一层并且，最后一个数和第一个数的和

// 也是质数，则输出结果

if(index==n-1 && isPrime(tempValues[index]+1)){

for(int j=0;j<n;j++){

sb.append(tempValues[j]+" ");

}

sb.append("\n");

// 分批输出

if(sb.length()>10000){

System.out.print(sb.toString());

sb=new StringBuffer();

}

continue;

}

// 创建新的状态，并复制原来的值

int[] newValues = Arrays.copyOf(tempValues, tempValues.length);

// 交换i和k处的值

if(index!=k){

int change = newValues[index];

newValues[index] = newValues[k];

newValues[k] = change;

}

newValues[n] = newValues[n]+1;

// 把新状态添加到列表中,放在最前面，深度优先，

// 如果采用广度优先，则应该放到最后面

list.add(0,newValues);

}

// 从list中删除当前的节点

list.remove(tempValues);

}

System.out.print(sb.toString());

}

6、人见人爱A^B

Problem Description

求A^B的最后三位数表示的整数。

说明：A^B的含义是“A的B次方”

Input

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

Output

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Input

2 3

12 6

6789 10000

0 0

Sample Output

984

解题思路：要求67**10000次方，使用Java语言提供的数据类型肯定要越界，可以使用之前介绍的大数解决方案，但是计算量会非常大。仔细看这道题会发现要求求结果的后3位，所以6789*6789与789*7**结果的后3位是相同的，所以在处理的时候只需要考虑后3位即可，这样处理解简单了。下面的代码供参考：

* A的B次方的后3位

public static int test6(int a,int b){

// 保留后3位

int temp = a%1000;

int result = temp;

for(int i=1;i<b;i++){

result = (result*temp)%1000;

}

return result;

}

ACM详解（4）——递归

递归在解决一些问题的时候非常直观，但是在是使用递归的时候要注意递归的深度，如果深度太深，可能会造成堆栈溢出。下面通过实例介绍如何使用。

题目：超级楼梯

Problem Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

Sample Output

解题思路：这类题目首先要找到规律，可以试着写出M比较少的情况，然后从中找规律。例如：

M 走法

2 1-2

3 1-3（从1走两级）1-2-3（从2走一级）

4 1-2-4（从2走两级） 1-2-3-4 1-3-4（从3走一级）

5 1-2-3-5 1-3-5（从3走两级） 1-2-3-4-5 1-2-4-5 1-3-4-5（从4走一级）

6 1-2-4-6 1-2-3-4-6 1-3-4-6（从4走两级）

1-2-3-5-6 1-3-5-6 1-2-3-4-5-6 1-2-4-5-6 1-3-4-5-6（从5走一级）

…

n n-2层的所有走法走两级可以到达n层，n-1层的所有走法走一级可以到达n层

n层的走法可以表示为f(n)，则f(n)=f(n-1)+f(n-2)，n>4

这样就可以用递归计算了。参考代码如下：

* 超级楼梯

public static int test7(int n){

switch(n){

case 1:return 0;

case 2:return 1;

case 3:return 2;

default:return test7(n-1)+test7(n-2);

}

对于这种题目来说，使用递归速度并不快，并且递归太深的话会溢出，可以采用循环来处理，可以参考下面的代码：

* 超级楼梯

public static int test7(int n){

int[] result = new int[40];

result[0] = 0;

result[1] = 1;

result[2] = 2;

for(int i=3;i<n;i++){

result[i] = result[i-1]+result[i-2];

}

return result[n-1];

}

ACM详解（5）——排序

有些ACM题需要使用一些基本的数据结构，下面首先介绍与排序相关的内容。

1、基本排序

Problem Description

These days, I am thinking about a question, how can I get a problem as easy as A+B? It is fairly difficulty to do such a thing. Of course, I got it after many waking nights.

Give you some integers, your task is to sort these number ascending (升序).

You should know how easy the problem is now!

Good luck!

Input

Input contains multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case contains an integer N (1<=N<=1000 the number of integers to be sorted) and then N integers follow in the same line.

It is guarantied that all integers are in the range of 32-int.

Output

For each case, print the sorting result, and one line one case.

Sample Input

3 2 1 3

9 1 4 7 2 5 8 3 6 9

Sample Output

1 2 3

1 2 3 4 5 6 7 8 9

翻译：对给定的数字序列进行排序。使用数据结构的基本排序算法即可。可以使用各种排序算法实现。另外在Java中提供了排序方法，可以使用Arrays.sort方法，参考下面的代码：

Arrays.sort(a);

其中a是需要排序的数组。

下面给出了冒泡排序的代码供参考：

* 冒泡排序

public static int[] sort(int[] a){

// Arrays.sort(a);

for(int i=0;i<a.length-1;i++){

for(int j=a.length-1;j>i;j--){

if(a[j]<a[j-1]){

int temp = a[j];

a[j] = a[j-1];

a[j-1] = temp;

}

return a;

}

2、DNA Sorting

Description

One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6

AACATGAAGG

TTTTGGCCAA

TTTGGCCAAA

GATCAGATTT

CCCGGGGGGA

ATCGATGCAT

Sample Output

CCCGGGGGGA

AACATGAAGG

GATCAGATTT

ATCGATGCAT

TTTTGGCCAA

TTTGGCCAAA

翻译：对于一个序列的无序性可以使用相互之间无序的元素组的个数表示，例如字母序列DAABEC的无序性是５，Ｄ大于后面的ＡＡＢＣ，Ｅ大于后面的Ｃ。而AACEDGG的无序性是１，因为只有Ｅ和Ｄ之间的顺序是乱的。

题目要求：对于给定的多个字符串（长度相同，由A, C, G和T组成），从最有序到最无序进行排列。

解题思路：计算每个字符串的无序性，然后进行排序即可。参考下面的代码：

* DNA sorting

public static void test3(String[] dnas){

Map invertions = new HashMap();

// 计算每个字符串的乱序数量

for(int i=0;i<dnas.length;i++){

invertions.put(dnas[i], count(dnas[i]));

}

// 排序

for(int i=0;i<dnas.length-1;i++){

for(int j=dnas.length-1;j>i;j--){

if((Integer)(invertions.get(dnas[j]))<(Integer)(invertions.get(dnas[j-1]))){

String temp = dnas[j];

dnas[j] = dnas[j-1];

dnas[j-1] = temp;

}

// 输出

for(String temp:dnas){

System.out.println(temp+invertions.get(temp));

}

// 计算无序性

public static int count(String dna){

int sum=0;

for(int i=0;i<dna.length()-1;i++){

char temp = dna.charAt(i);

for(int j=i+1;j<dna.length();j++){

if(temp>dna.charAt(j))

sum++;

}

return sum;

}

上面计算无序性的代码是通过遍历字符串中的每个元素，然后判断后续的每个字符和它之间是否有序，需要遍历两次。如果字符串不是很长，这种算法还可以接受。如果字符串很长，计算将很耗时。下面的方法进行了改进。

* 计算无序性（改进算法）

publicstaticint count2(String dna){

int count[] = newint[4];

Arrays.fill(count,0);

int sum=0;

for(int i=dna.length()-1;i>=0;i--){

char temp = dna.charAt(i);

switch(temp){

case'A':

count[0]++;

break;

case'C':

count[1]++;

sum = sum+count[0]; // 加上C后面的A的个数

break;

case'G':

count[2]++;

sum = sum+count[0]+count[1]; // 加上G后面的A和C的数量

break;

case'T':

count[3]++;

sum = sum+count[0]+count[1]+count[2]; // 加上G后面的A、C和G的数量

break;

}

return sum;

}

另外在代码中，对序列进行排序是自己编写的排序算法。也可以使用系统提供的排序功能，需要编写一个类，参考代码如下：

class DNA implements Comparable{

String content;

int unsortness;

DNA(String content,int unsortness){

this.content = content;

this.unsortness = unsortness;

}

@Override

public int compareTo(Object o) {

return unsortness-((DNA)o).unsortness;

}

修改后的代码如下：

* DNA sorting

publicstaticvoid test3(String[] dnas){

DNA newDnas[] = new DNA[dnas.length];

for(int i=0;i<dnas.length;i++){

newDnas[i] = new DNA(dnas[i],count(dnas[i]));

}

Arrays.sort(newDnas); // 替换了原来的排序算法

// 输出

for(DNA temp:newDnas){

System.out.println(temp.content+temp.unsortness);

}

ACM详解（6）——栈

堆栈是一种特殊的线性结构，后进先出，只能对栈顶元素操作，典型的操作入栈和出站。下面通过例子介绍基本用法。

题目：Train Problem

Problem Description

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.

Input

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

Output

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.

Sample Input

3 123 321

3 123 312

Sample Output

Yes.

out

FINISH

No.

FINISH

题目翻译：火车站非常繁忙，火车A先进站，如果火车B在火车A出站之前进站，则或者A只能等或者B出站之后再出站（后进先出）。题目要求有n(n最大为9，编号从1到n)列火车，给出火车进站的序列，并给出火车出站的序列，让你判断这个要求能否实现，如果能实现写出进站(in)、出站(out)的操作序列。

解题思路：基本原则就是后进先出，但是对于特定的火车来说是先进后出。所以首先考虑入栈的序列，在入栈的过程根据出栈序列判断是否需要出栈，如果不需要出栈，则继续进栈，如果需要出栈则进行出栈操作。如果要出栈的元素不在栈顶则表示序列不合法。下面以入栈序列1234和出栈序列1423进行分析。

考虑入栈：1进栈，栈顶元素为1；

考虑出栈：因为栈顶元素与出栈序列中的第一个元素相同，1出栈，出栈后栈中无元素；

考虑出栈：栈中无元素，所以不用出栈；

考虑入栈：2进栈，栈顶元素为2；

考虑出栈：因为栈顶元素是2，而要出栈的元素是4，所以不能出栈；

考虑入栈：3进栈，栈顶元素为3，栈中包括2和3；

考虑出栈：因为栈顶元素是3，而要出栈的元素是4，所以不能出栈；

考虑入栈：4进栈，栈顶元素为4，栈中包括2、3和4；

考虑出栈：因为栈顶元素是4，而要出栈的元素是4，所以4出栈，出栈后栈中元素为2和3,3为栈顶元素。

考虑出栈：因为栈顶元素是3，而要出栈的元素是2，所以不能出栈；

考虑入栈：所有元素已经入栈，所以不能出栈；

无法入栈也无法出栈，而栈中有元素，所以序列不合法。

下面是参考代码：

* Train Problem I

public static String test2(int n,String s1,String s2){

// 记录操作结果

StringBuffer sb = new StringBuffer();

// 表示栈

int[] a=new int[9];

// 表示栈顶元素

int index=-1;

// 入栈元素序号

int index1=0;

// 出栈元素序号

int index2=0;

// 把第一个元素放到栈中

index++;

a[index]=s1.charAt(index1);

index1++;

sb.append("in\n");

// 只要栈中有元素，则处理

while(index1<s1.length() || index2<s2.length()){

// 如果栈顶元素是与s2中的元素一致，则出栈

if(index>-1 && s2.charAt(index2)==a[index]){

index--;

sb.append("out\n");

index2++;

}else if(index1==s1.length()){ // 不能实现

break;

}else{ // 如果否则把s1中的下一个元素加入到栈中

index++;

a[index] = s1.charAt(index1);

index1++;

sb.append("in\n");

}

if(index!=-1){

return "No.\nFINISH\n";

}else{

sb.insert(0,"Yes.\n");

sb.append("FINISH\n");

return sb.toString();

}

有些题目会给出一些简单的压缩方法或者编码方法，让你实现具体的算法。下面通过题目分析。

1、Parencodings

Description

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:

By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).

By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

S (((()()())))

P-sequence 4 5 6666

W-sequence 1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

4 5 6 6 6 6

4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6

1 1 2 4 5 1 1 3 9

翻译：S = s1 s2...s2n是结构正确的（有左括号和右括号组成，并且数量相等，并且对应关系正确）小括号序列，他可以使用两种方式编码：

正整数序列P = p1 p2...pn，pi表示第i个右括号之前的左括号的数量（P序列）；

正整数序列W = w1 w2...wn，wi表示第i个右括号对应的左括号的位置（从右向左数，1,2,3）（w序列）。

题目要求根据p序列求出w序列。

解题思路：

对于p序列中的每个元素pi：

循环判断之前的左括号，对于遇到的每个左括号：

判断是否已经与其他右括号配对，如果已经配对，继续向左判断；

如果没有，则记录它是第几个左括号。

以4 5 6 6 6 6为例分析，首先创建数组a表示左括号，1表示没有配对的左括号，0表示已经配对的左括号。初始情况a的值为1 1 1 1 1 1

读取p序列中的信息

P1=4 从a[3]开始判断左括号，a[3]=1，所以与a[3]括号对应，所以w1=1，a的值1 1 1 0 1 1

P2=5 从a[4]开始判断左括号，a[4]=1，所以与a[4]括号对应，所以w2=1，a的值1 1 1 0 0 1

P3=6 从a[5]开始判断左括号，a[5]=1，所以与a[5]括号对应，所以w3=1，a的值1 1 1 0 0 0

P4=6 从a[5]开始判断左括号，a[5]=0，a[4]=0,a[3]=0,a[2]=1,所以与a[2]括号对应，所以w4=4，a的值1 1 0 0 0 0

同理得到w5=5 w6=6

最后的w序列为：111456

参考代码略。

2、Encoding

描述

Given a string containing only 'A' - 'Z', we could encode it using the following method:

1. Each sub-string containing k same characters should be encoded to "kX" where "X" is the only character in this sub-string.

2. If the length of the sub-string is 1, '1' should be ignored.

输入

The first line contains an integer N (1 <= N <= 100) which indicates the number of test cases. The next N lines contain N strings. Each string consists of only 'A' - 'Z' and the length is less than 10000.

输出

For each test case, output the encoded string in a line

样例输入

ABC

ABBCCC

样例输出

ABC

A2B3C

翻译：把字符串中出现的连续相同的多个字符使用该字符以及出现的次数表示，例如ABBCCC中的BB可以使用2B表示，可以使用3C表示。题目要求对给定的字符串编码。

解题思路：遍历字符串，取出每个字符与之前的字符进行比较，如果相等计数加1，不相同，则从新计数。例如ABBCCC，可以处理如下。

先初始化，c表示前一个字符，count表示统计次数。c=’0’,count=0。

对于A，之前没有字符，count=1，c=’A’;

对于B，之前的字符是’A’，输出A，count=1，c=’A’；

对于B，之前的字符是’B’，count=2；

对于C，之前的字符是’B’，输出2B，count=1，c=’C’;

对于C，之前的字符是’C’，count=2;

对于C，之前的字符是’C’，count=3;

最后输出3C。

输出的结果是A2B3C

参考代码如下：

* 字符串编码

public static void test5(String str){

int count=1;

char c=str.charAt(0);

for(int i=1;i<str.length();i++){

if(str.charAt(i)==c){

count++;

}else{

if(count!=1)

System.out.print(count);

System.out.print(c);

count=1;

c=str.charAt(i);

}

if(count!=1)

System.out.print(count);

System.out.print(c);

比赛的时候告诉你简单的加密算法，让你完成加密或者解密操作，下面通过几个简单例子介绍。

1、Message Decowding

Description

The cows are thrilled because they've just learned about encrypting messages. They think they will be able to use secret messages to plot meetings with cows on other farms.

Cows are not known for their intelligence. Their encryption method is nothing like DES or BlowFish or any of those really good secret coding methods. No, they are using a simple substitution cipher.

The cows have a decryption key and a secret message. Help them decode it. The key looks like this:

yrwhsoujgcxqbativndfezmlpk

Which means that an 'a' in the secret message really means 'y'; a 'b' in the secret message really means 'r'; a 'c' decrypts to 'w'; and so on. Blanks are not encrypted; they are simply kept in place.

Input text is in upper or lower case, both decrypt using the same decryption key, keeping the appropriate case, of course.

Input

* Line 1: 26 lower case characters representing the decryption key

* Line 2: As many as 80 characters that are the message to be decoded

Output

* Line 1: A single line that is the decoded message. It should have the same length as the second line of input.

Sample Input

eydbkmiqugjxlvtzpnwohracsf

Kifq oua zarxa suar bti yaagrj fa xtfgrj

Sample Output

Jump the fence when you seeing me coming

翻译：简单的加密算法，把字符串中的字符替换成另外的字符，只有对方知道如何替换就可以解密。题目要求根据给定的加密方法和密文，得到原始消息。

解题思路：

第一行eydbkmiqugjxlvtzpnwohracsf相当于密钥，含义是

a对应e

b对于y

c对应d

…

只要把密文序列中的相应字符替换为后面的字符即可。

Kifq oua zarxa suar bti yaagrj fa xtfgrj

把K替换成J

把i替换成u

把f替换成m

…

(注意大小写)

编程的时候：可以定义数组表示密钥。然后对密文进行遍历得到原始信息。不再给出参考代码。

2、Ancient Cipher

Description

Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping. The most popular ciphers in those times were so called substitution cipher and permutation cipher.

Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from 'A' to 'Y' to the next ones in the alphabet, and changes 'Z' to 'A', to the message "VICTORIOUS" one gets the message "WJDUPSJPVT".

Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation <2, 1, 5, 4, 3, 7, 6, 10, 9, 8> to the message "VICTORIOUS" one gets the message "IVOTCIRSUO".

It was quickly noticed that being applied separately, both substitution cipher and permutation cipher were rather weak. But when being combined, they were strong enough for those times. Thus, the most important messages were first encrypted using substitution cipher, and then the result was encrypted using permutation cipher. Encrypting the message "VICTORIOUS" with the combination of the ciphers described above one gets the message "JWPUDJSTVP".

Archeologists have recently found the message engraved on a stone plate. At the first glance it seemed completely meaningless, so it was suggested that the message was encrypted with some substitution and permutation ciphers. They have conjectured the possible text of the original message that was encrypted, and now they want to check their conjecture. They need a computer program to do it, so you have to write one.

Input

Input contains two lines. The first line contains the message engraved on the plate. Before encrypting, all spaces and punctuation marks were removed, so the encrypted message contains only capital letters of the English alphabet. The second line contains the original message that is conjectured to be encrypted in the message on the first line. It also contains only capital letters of the English alphabet.

The lengths of both lines of the input are equal and do not exceed 100.

Output

Output "YES" if the message on the first line of the input file could be the result of encrypting the message on the second line, or "NO" in the other case.

Sample Input

JWPUDJSTVP

VICTORIOUS

Sample Output

YES

翻译：古罗马帝国有两种简单的加密算法，第一种按照顺序替换，例如把a-y分别替换成b-z，把z替换成a，这样可以把VICTORIOUS替换成WJDUPSJPVT。

第二种是打乱顺序消息的顺序，例如<2, 1, 5, 4, 3, 7, 6, 10, 9, 8>的含义就是把第二个字符放在第一位，而把第一位的字符放到第二位，然后是第5个字符，第4个字符，…，可以把VICTORIOUS替换成IVOTCIRSUO。

后来发现同时使用两种算法，加密效果更好。可以把VICTORIOUS替换成JWPUDJSTVP。

题目要求：能不能把第二行中的原文转换为第一行的密文。

解题思路：首先要找出规律，第二种算法只会改变每个字符的位置，但是不会影响每个字符在字符串中出现的次数。例如A在原来的字符串中出现3次，那么通过第二种算法它出现的次数还是3次。第一种算法虽然改变了字符串的内容，但是有些东西没有变化，例如原来字符串中的a、b、c出现的次数分别n1、n2、n3，假设abc替换def，则d、e、f出现的次数应该是n1、n2、n3。所以只要保证相对位置上的字符出现的次数相同即可实现转换。

算法：

统计输入信息第一行中每个字符出现的次数。使用长度为26的数组表示，分别表示字母A到字母Z出现的次数，使用int[] a表示。

统计输入信息第二行中的每个字符出现的次数。使用长度为26的数组表示，分别表示字母A到字母Z出现的次数，使用int[] b表示。

循环26次：

第j次循环中，再循环比较a[(i+j)%26]与b[i]是否相同，如果都相同则说明能够转换，输出YES即可，退出外层循环，否则继续循环。

如果26次循环完之后，没有得到结果，输出NO。

有时候会考一些锻炼基本能力的题目，下面使用几个例子进行简单分析。

1、IP Address

Description

Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:

27 26 25 24 23 22 21 20

128 64 32 16 8 4 2 1

Input

The input will have a number N (1<=N<=9) in its first line representing the number of streams to convert. N lines will follow.

Output

The output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.

Sample Input

00000000000000000000000000000000

00000011100000001111111111111111

11001011100001001110010110000000

01010000000100000000000000000001

Sample Output

0.0.0.0

3.128.255.255

203.132.229.128

80.16.0.1

翻译：23位的0/1序列表示可以用来表示一个IP地址，题目要求把给定的32位序列转换为IP地址。例如序列00000011100000001111111111111111可以转换为3.128.255.255。

解题思路：把序列分成8个一组，然后把二进制序列转换为十进制的数，然后把4个数用“.”连接即可。题目比较简单，不再给出参考代码。

2、Elevator

描述

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.

For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

输入

There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.

输出

Print the total time on a single line for each test case.

样例输入

1 2

3 2 3 1

样例输出

翻译：大楼中只有一个电梯，请求序列有N个正整数组成，数字表示电梯将在哪里停，按照顺序。电梯向上一层需要6秒，向下一层需要4秒，每层停5秒。题目要求根据给定的请求序列求出电梯完成所有任务需要的时间。电梯刚开始在0层。

解题思路：使用sum表示总时间，初始值为0。对于每个请求序列，取出每个请求的楼层，如果是请求序列中第一个，计算上楼需要的时间（n*6），然后再加上电梯停留的时间（5），sum=sum+n*6+5。如果不是第一个请求，看上次请求的位置m，如果小于当前位置，计算上楼的时间（n-m）*6，电梯停留时间5，sum=sum+(n-m)*6+5，如果大于当前位置，计算下楼时间(m-n)*4，电梯停留时间5，sum=sum+(m-n)*4+5。

参考代码如下：

* 电梯运行时间

public static void test4(int[] datas){

// 表示原来的楼层

int m = 0;

// 表示总时间

int sum = 0;

for(int i=1;i<=datas[0];i++){

int n = datas[i];

if(n>m){

sum = sum+(n-m)*6+5;

}else{

sum = sum+(m-n)*4+5;

}

m = n;

}

System.out.println(sum);

}

3、集合的减法运算

Problem Description

集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）。

Input

每组输入数据占1行,每行数据的开始是2个整数n(0<n<=100)和m(0<m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.

如果n=0并且m=0表示输入的结束，不做处理。

Output

针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

Sample Input

3 3 1 2 3 1 4 7

3 7 2 5 8 2 3 4 5 6 7 8

0 0

Sample Output

2 3

NULL

集体思路：没有难度，就是锻炼基本功。从每个测试用例中分别得到A集合和B集合，遍历A集合中的所有元素，如果不在B集合中，则输出该元素。不再给出参考代码。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/75142