A Surface Area
题目描述
There is a cuboid with length a, width b and height c, Your job is to calculate its surface area.
输入描述
The first line of the input is a positive integer T. T is the number of test cases followed.
输出描述
For each test case output the surface area on a single line.
样例输入
2
1 2 3
4 5 6样例输出
22
148java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n= scanner.nextInt();
int [][]a=new int [n+10][4];
int []res=new int[n+1];
for(int i=1;i<=n;i++) {
int sum=0;
a[i][1]=scanner.nextInt();
a[i][2]=scanner.nextInt();
a[i][3]=scanner.nextInt();
sum=sum+(a[i][1]*a[i][2]+a[i][1]*a[i][3]+a[i][2]*a[i][3])*2;
res[i]=sum;
}
for(int i=1;i<=n;i++) {
System.out.println(res[i]);
}
}
}B 矩阵DP
题目描述
给定一个M*N矩阵，其中每个元素都是从-10到10之间的整数。要求所编程序选取一条从（1，1）到（M，N）的路径使路径上数字之和尽可能小的正整数。（只能右下走）
输入描述
第一行是两个整数M,N（2<=M<=10,2<=N<=10），分别表示矩阵的行和列。接下来的M行，每行包括N个整数。M和N都为0时终止程序。
输出描述
输出该路径上数字之和，若不能达成任何正整数，则输出-1。每个测试输出结果一行。
样例输入
2 2
0 2
1 0样例输出
1java代码1
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int m=scanner.nextInt();
int n=scanner.nextInt();
int [][]juzhen=new int[m+5][n+5];
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
juzhen[i][j]=scanner.nextInt();
}
}
int sum=juzhen[1][1];
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if (juzhen [i][j+1]>juzhen[i+1][j]) {
sum=sum+juzhen[i+1][j];
}else {
sum+=juzhen[i][j+1];
}
}
}
System.out.println(sum);
}
}java代码2
package PTA;
import java.util.Scanner;
public class 矩阵DP {
static int a[][] = new int[20][20];
static int m,n;
static int ans =100000000;
static void dfs(int x, int y, int sum) {
sum = sum + a[x][y];
if (x < m)
dfs(x + 1, y, sum);
if(y<n)
dfs(x, y+1, sum);
if (x==m && y==n && sum>0 && sum<ans && sum>0)
ans =sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner( System.in);
m =sc.nextInt();
n =sc.nextInt();
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n ; j++) {
a[i][j]=sc.nextInt();
}
}
dfs(1,1,0);
if (ans==1e9){
ans =-1;
System.out.println(ans);
}else {
System.out.println(ans);
}
}
}本代码1、2都只通过了50%
C Transit search
题目描述
Henry decides to develop a web site, which will provide the service of transit search. But he can only get the transit data of Guangzhou, so his web site can only support the transit search of Guangzhou. We suppose Guangzhou is 10240 meters by 10240 meters. The coordinate of the top-left corner is (0,0). The coordinate of the bottom-right corner is (10240,10240). The X–axis is from top to bottom and the Y-axis is from left to right. At the beginning, four pictures of the size 10cm by 10 cm make up of the whole map of Guangzhou. They are numbered from 0 to 3. It is to say at the beginning the scale of the map is 1cm:512 meters. We call the four pictures are at level 1.
When you double-click on the map using the mouse, the map will zoom in. The pictures at next level will be shown on the screen. For example, when you double-click on the above map, picture 0 will be replaced by four pictures 00, 01, 02, 03, all of whose sizes are 10 cm by 10 cm. and the scale of the map change to 1cm:256 meters. (notice that, pictures 00,01,02,03 together describe the same area as picture 0). When you continue double-click, picture 01 will be replaced by pictures 010,011,012,013, and so on.
Now, a position’s coordinate can be given by(str, x,y). str consists of 8 characters each from 0 to 3. It describes the id of the picture which the position is located at. x and y(0cm<=x,y<=10cm) describe the position’s offset relative to the top-left corner on picture str. Notice that the X–axis is from top to bottom and the Y-axis is from left to right.
Now, the start position and end position are given as (start, sx, sy), (end, ex, ey). And some information about the bus line will be also given. First, each bus stop will be described by (name, x, y), its name and its coordinate. Second, each bus line will be described by (name1, name2, name3…namek) which are the bus stops the bus line travels through. If the distance between the start position and end position is no more than 2000 meters, the web site will suggest walking there. Otherwise, the web site will find a bus stop whose distance is no more than 1000 meters from the start position. You can take buses to a bus stop whose distance is no more than 1000 meters from the end position. Along the way, you can change buses at any bus stop. If you can take buses according the above rules, the web site will find a route with fewest number of changing buses. If you can’t take buses according the above rules, the web site will suggest taking a taxi.
输入描述
The input begins with a line containing an integer T, the number of test cases.
For each case, the first two lines describe the start position and the end position as followed.
Start sx sy
End ex ey
Start and End both contain 8 characters each from 0 to 3. 0cm<=sx,sy,ex,ey<=10cm. Notice that all the numbers in the input are integers.
The next line contains an integer n(0<n<5001), indicating the total number of bus stops in Guangzhou. The following n lines each describe a bus stop in the format:
Name x y
Name contains no more than 20 characters. 0<=x,y<=10240.
Next comes an integer m(0<m<=100), indicating the number of bus lines in Guangzhou.
Then following is the description of the m bus lines.
Each bus line is described as followed:
K
Name1 Name2 Name3 … Namek
K(0<K<=30) is the number of bus stops along the bus line.
Namei is the ith bus stop along the bus line. Notice that the bus line is bidirectional.
输出描述
(1) If the distance between the start position and end position is no more than 2000 meters, print “walk there” in a single line.
(2) If you can take buses according to the above rule, print the fewest number of buses you have to take. For example, if you can take a bus directly to end position without changing bus line, print 1.
(3) Otherwise, print “take a taxi” in a single line.
样例输入
3
00000000 1 1
00001000 3 3
4
a 1 1
b 20 30
c 40 50
d 100 100
2
3
a b c
3
b c d
00000000 1 1
03231130 5 5
5
a 1 1
b 1000 1000
c 3000 3000
d 3000 4000
e 4500 4000
2
3
a b c
3
c d e
00000000 1 1
03231130 5 5
4
a 1 1
b 1000 1000
c 3000 3000
d 3000 4000
2
3
a b c
3
b c d样例输出
walk there
2
take a taxiD 【作业调度方案】
题目描述
我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。
例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。
一方面，每个操作的安排都要满足以下的两个约束条件。
(1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始；
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。
由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。
还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。
例如，取n=3,m=2，已知数据如下：
则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。
当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题 简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条 件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。
显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。
输入描述
第1行为两个正整数，用一个空格隔开：
m n
（其中m（〈20）表示机器数，n（〈20）表示工件数）
第2行： 2n个用空格隔开的数，为给定的安排顺序。
接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。
其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。
后n行依次表示每个工件的每个工序的加工时间。
可以保证，以上各数据都是正确的，不必检验。
输出描述
只有一个正整数，为最少的加工时间。
样例输入
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4样例输出
10java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int m=scanner.nextInt();//机器数
int n=scanner.nextInt();//工件数
int []a= new int[n*m+10];//安排顺序
int [][]b=new int[n+1][m+10];//机器号
int [][]c=new int[n+1][m+10];//加工时间
int [][]d=new int [n+10][n+10];//每个工件的每个工序最早能开始的时间
int []e = new int [n+10];//每个工件已完成的工序数
int [][]l=new int[n+10][n+10];//每个机器空隙的左端点
int [][]r=new int[n+10][n+10];//每个机器空隙的右端点
int []num=new int[n+10];//空隙的个数
for(int i=1;i<=n*m;i++) {//工艺顺序
a[i]=scanner.nextInt();
}
//每件工序使用的机器号
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
b[i][j]=scanner.nextInt();
}
}
//每件工件的每个工序的加工时间
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
c[i][j]=scanner.nextInt();
}
}
//以上为输入完成
//初始化空隙，工作开始之前，定义空隙为1，即空隙的左端点为0，右端点为无穷大
for(int i=1;i<=m;i++) {
num[i]=1;
l[i][1]=0;
r[i][1]=100000000;
}
for(int k=1;k<=n*m;k++) {
int job=a[k]; //当前工作的工件，a数组是安排的顺序
int process= e[job]+1;//已完成工作
int number=b[job][process];//机器编号
//枚举空隙
for(int i=1;i<=num[number];i++) {
if (l[number][i]<d[job][process]&&d[job][process]+c[job][process]<=r[number][i]) {
//空隙需要包含整个过程
num[number]++; //被分成两个空隙
for(int j = num[number]; j > i + 1;j--) {
l[number][j] = l[number][j-1];
r[number][j] = r[number][j-1];
}
//空隙排序
d[job][process + 1] = d[job][process] + c[job][process];
//得出当前工作的下一个工序最早开始时间
l[number][i+1]=d[job][process+1];
r[number][i+1]=r[number][i];
r[number][i]=d[job][process];
//开工时间
break;
}
else if (l[number][i]>=d[job][process] && l[number][i]+c[job][process]<=r[number][i]) {
//空隙的大小得大于等于工作时间
//第二种情况
d[job][process+1]=l[number][i]+c[job][process];
l[number][i]=l[number][i]+c[job][process];//左端点往后挪
break;
}
}
e[job]++;//完成了一个工序
}
int ans = 0;
for(int i=1;i<=m;i++) {
ans=Math.max(ans, l[i][num[i]]);
}
System.out.println(ans);
}
}E 【求[X,Y]内被除3余1并且被除5余3的整数的和】
题目描述
输入两个正整数X,Y,求出[X,Y]内被除3余1并且被除5余3的整数的和
输入描述
输入两个正整数X,Y
输出描述
求所有满足条件的数的和
样例输入
200 800样例输出
20020java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int X=scanner.nextInt();
int Y=scanner.nextInt();
int sum=0;
for(int i=X;i<=Y;i++) {
if (i%3==1&&i%5==3) {
sum+=i;
}
}
System.out.println(sum);
}
}F 众数问题
题目描述
问题描述：
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。
编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
输入描述
第1行多重集S中元素个数n(n<=50000)；接下来的n 行中，每行有一个自然数。
输出描述
输出文件有2 行，第1 行给出众数，第2 行是重数。(如果有多个众数，只输出最小的)
样例输入
6
1
2
2
2
3
5样例输出
2
3java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int []a = new int[n];
for(int i=0;i<n;i++) {//输入数据
a[i]=scanner.nextInt();
}
int max=0;
for(int i=0;i<n;i++) {
int count=0;
for(int j=i;j<n;j++) {
if (a[i]==a[j]) {
count++;
}
}
max=Math.max(max, count);
}
for (int i = 0; i < n; i++) {
int count=0;
for(int j=i;j<n;j++) {
if (a[i]==a[j]) {
count++;
}
}
if (count==max) {
System.out.println(a[i]+"\n"+count);
}
}
}
}G 数列问题
题目描述
已知一个数列的前3个数为3，4，5，以后每个数为前3个数的和，编程序求此数列的第N项
输入描述
输入N(N<=35)
输出描述
求出第N项的值
样例输入
28样例输出
25527448java代码
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
list.add(3);
list.add(4);
list.add(5);
int n=scanner.nextInt();
for(int i=3;i<n;i++) {
int sum=list.get(i-1)+list.get(i-2)+list.get(i-3);
list.add(sum);
}
System.out.println(list.get(n-1));
}
}H 邮局选址问题
题目描述
问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。
居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
编程任务：
给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
输入描述
第1 行是居民点数n，1<10000。< 个整数x 行是居民点的位置，每行2>
输出描述
n个居民点到邮局的距离总和的最小值。
样例输入
5
1 2
2 2
1 3
3 -2
3 3样例输出
10java代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int []x=new int[n];
int []y=new int[n];
for(int i=0;i<n;i++) {
x[i]=scanner.nextInt();
y[i]=scanner.nextInt();
}
Arrays.sort(x);
Arrays.sort(y);
int resx=x[n/2];
int resy=y[n/2];
int sumx=0;
int sumy=0;
for(int i=0;i<n;i++){
sumx+=Math.abs(resx-x[i]);
sumy+=Math.abs(resy-y[i]);
}
System.out.println(sumx+sumy);
}
}