当前位置：文档之家› java编程例题

java编程例题

[题目大意]:

在平面上给出的n个点中，判断最多可以组成多少个正方形。

[输入]

每个案例的第一行是点的个数n,接下来的n行是各点的坐标(x,y) ，当n=0时,结束.

[输出]:

对每个案例输出这n个点可以组成的正方形个数.

[样例]:

Sample Input

1 0

0 1

1 1

0 0

1 0

2 0

0 2

1 2

2 2

0 1

1 1

2 1

-2 5

3 7

0 0

5 2

Sample Output

[解题分析]:

枚举两个点，然后把这两个点的连线作为正方形的一边，然后找能与这两个点构成正方形的另外两个点是否存在在给出的点集里面。在一个集合里面找点的方法有很多，比如二分搜索和hash都可以。

如何求正方形的另外两个点呢,如图:

用已知两个点做出两个全等三角形。之后就得出结论(x1+|y1-y2|,

y1+|x1-x2|),(x2+|y1-y2|,y2+|x1-x2|)。当然这只是一种情况，其他情况类似。

[代码]：

import java.util.Scanner;

import java.util.HashSet;

public class Main{

private int n;

private Point p[];

private HashSet< Point> pset=new HashSet< Point>();

private int sum;

public Main(int n,Point p[]){

this.n=n;

this.p=p;

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

pset.add(p[i]);

}

public int getSum(){

return sum;

}

public void doIt(){

int bound;

int a1, a2, b1, b2, ab1, ab2, x1, y1, x2, y2, x3, y3, x4, y4;

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

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

a1 = p[i].getX();

a2 = p[i].getY();

b1 = p[j].getX();

b2 = p[j].getY();

ab1 = a1 - b1;

ab2 = a2 - b2;

x1 = a1 + ab2;

y1 = a2 - ab1;

x2 = b1 + ab2;

y2 = b2 - ab1;

if (pset.contains(new Point(x1, y1)) && pset.contains(new Point(x2, y2))) sum++;

x3 = a1 - ab2;

y3 = a2 + ab1;

x4 = b1 - ab2;

y4 = b2 + ab1;

if (pset.contains(new Point(x3, y3)) && pset.contains(new Point(x4, y4))) sum++;

}

public static void main(String args[]){

Scanner in=new Scanner(System.in);

int x=0;

int y=0;

while(true){

int n=in.nextInt();

if(n==0) break;

Point p[]=new Point[n];

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

x=in.nextInt();

y=in.nextInt();

p[i]=new Point(x,y);

//System.out.println(p[i]);

}

Main m=new Main(n,p);

m.doIt();

System.out.println(m.getSum()/4);

}

class Point

{

private int x;

private int y;

public Point(int x,int y)

{

this.x = x;

this.y = y;

}

public void setX(int x){

this.x=x;

}

public void setY(int y){

this.y=y;

}

public int getX(){

return this.x;

}

public int getY(){

return this.y;

}

public boolean equals(Object o)

{

if (this == o)

{

return true;

}

if (o.getClass() == Point.class)

{

Point p = (Point)o;

return (p.x==x) && (p.y==y); }

return false;

}

public int hashCode() {

long bits = getX();

bits ^= getY() * 31;

return (((int) bits) ^ ((int) (bits >>

32)));

}

public String toString()

{

return "Point[" +x+"," +y+ "]";

}

2．

[题目大意]:

翻转游戏是在4*4的正方形里进行的，每个小正方形放有拥有黑白两面的棋子。每一轮你翻转3-5个棋子，把它从白变黑或从黑变白。翻转的规则如下：

1. 选择任意一个棋子。

2. 翻转选择的棋子和与它相临的前后左右的棋子（如果有的话）

参考如下例子：

bwbw

wwww

bbwb

bwwb

b表示黑色在上面，w表示白色在上面。如果选择第三行第一个棋子进行翻转结果如下：

bwbw

bwww

wwwb

游戏的目标在于使所有白色或所有黑色朝上，你的任务是计算完成目标所需要的最少步数。

[输入]

输入4行，每行4单词w或b,表示游戏初始格局。

[输出]:

输出完成目标所需最小步数。如果最初格局及达到目标，输出0；不能达到目标输出“Impossible”(不用引号)。

[样例]:

Sample Input

bwwb

bbwb

bwwb

bwww

Sample Output

[解题分析]:

实际上我们完全可以只枚举第一行的操作,第一行有（翻，翻，翻，翻）（翻，翻，翻，不翻）。。。（不翻，不翻，不翻，不翻）16种，如果我们想把棋子全部翻成一种颜色的话，那么第二行的操作就是固定的了（因为第一行的棋子的状态对第二行棋子的翻转进行了约束，如果想把第一行的棋子变成白色，那么第二行中位于第一行黑色棋子下方的位置必须翻转，反之亦然），那么第三行、第四行的操作显然也是固定的了。

[代码]：

import java.util.Scanner;

public class Main{

static int steps=Integer.MAX_VALUE;

//(x,y)坐标合起来就是中心点及上下左右坐标啦！

static int[] dx={0,0,0,1,-1};

static int[] dy={0,1,-1,0,0};

* 把每一行的状态和整个状态都以2进制表示，四个2进制数排成一行，组成整个状态。

* 1010

* 0000

* 1101

* 1001

*如图的状态表示为：1010000011011001

* @param x横坐标点(注意：坐标系右下为(0,0)左上为（3,3））

* @param y纵坐标点

* @param source(整个状态如上面的1010000011011001）

* @return 改变确定位置的状态，如1变成0或者0变成1

* */

public static int flip(int x, int y, int source){

if(x >= 0 && x < 4 && y >= 0 && y < 4)

source ^= 1 << (x * 4 + y);

return source;

}

* @param current当前行

* @param num 回合数

* @param source 原数据，比如：1010000011011001

* @param flag 标志如果数据源当前位的状态不为flag，则翻动

* */

public static void dfs(int current,int num,int source,int flag){ //如果最后一行已经翻完

if(current==4){

if(source==0xffff||source==0){

//已经完成了任务

steps=num< steps?num:steps;

}

return;

}

//把当前行都翻成同种颜色

int x,y;

for (int i = current-1,j=0; j < 4; j++) {//每行有四个，翻或者不翻，所以需要四次

if( (((source& (1<< (i*4+j) ))>>(i*4+j)) ^ flag)==1 ){ /*source& (1<< (i*4+j) )>>(i*4+j) :把source中的(i,j)的状态取出来*/

for (int k = 0; k <5; k++) {//当前，上下左右都得翻动 x=current+dx[k];

y=j+dy[k];

source=flip(x, y, source);

}

num++;

}

//翻下一行

dfs(current+1, num, source, flag);

}

/* 第一行共有16种翻法（翻，翻，翻，翻）（翻，翻，翻，不翻）。。。（不翻，不翻，不翻，不翻）

* */

public static int solve(int source){

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

int num=0,temp=source,x,y;

for (int j = 0; j < 4; j++) { // 这个循环是翻第一行

if((i&(1<< j))>0){

for (int k = 0; k <5; k++) {//当前，上下左右都得翻动

x=0+dx[k];

y=j+dy[k];

temp=flip(x, y, temp);

}

num++;

}

dfs(1, num, temp, 0); //全部翻成白色

dfs(1, num, temp, 1); //全部翻成黑色

}

return steps==Integer.MAX_VALUE?-1:steps;

}

public static void main(String[] args) {

Scanner scanner=new Scanner(System.in);

int source=0;

String string="";

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

string+=scanner.nextLine().trim();

}

// System.out.println(string);

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

source=(source<<1)+(string.substring(i,

i+1).equals("b")?1:0);

}

// System.out.println(Integer.toBinaryString(source));

if(solve(source)!=-1){

System.out.println(steps);

}else {

System.out.println("Impossible");

}

其具体实现思想是这样的：首先把字符转化成int ，而且以二进制的方式操作。dx,dy是这样工作的：

把字符转化成相对应的0,1数字。以四个为一组存入int型内。dx,dy就是需要改变的点的上、下、左、右点的相对位置。设需要改变点的坐标为（0，0）。这样就好理解了！第二点就是solve方法中的循环16次，开始也看不明白，后来才发现0-15变成2进制数，分别与 1，10，100，1000（if(i&(1<

3．

[题目大意]:

给出N台电脑和K辆卡车，要求每辆卡车至少放一台电脑。问共有多少种放法运走这些电脑？

数据范围N (1<=N<=200) and K(1<=K<=N)。

[输入输出]:

输入的每一行是空格隔开的电脑数n和卡车数k ，输出对应的运法总数。[样例]:

Sample Input

7 3

0 0

Sample Output

[解题分析]:

分析：典型dp，状态转移方程dp[i][j]=dp[i-1][j-1]+dp[i][j-i]；dp[i][j]表示i辆卡车装j台电脑的方法数。

例如：8台电脑3台车

[代码]：

import java.util.*;

public class Main{

private long dp[][]=new long[201][201];

public Main(){

init();

}

private void init(){

for(int i=1;i< 201;i++)

{

dp[i][i]=dp[1][i]=dp[i][0]=dp[0][i]=1;

}

for(int i=2;i< 201;i++)

{

for(int j=i+1;j< 201;j++)

{

dp[i][j]=dp[i-1][j-1]+dp[i][j-i];

}

public long dp(int k,int n){

return dp[k][n];

}

public static void main(String args[]){

Scanner in=new Scanner(System.in);

Main m=new Main();

while(true){

int n=in.nextInt();

int k=in.nextInt();

if(n==0 && k==0) break;

System.out.println(m.dp(k,n));

}

4．

题目大意]:

有N头牛，每头牛有两个参数T和D。把第i头牛送到目的地要2*Ti的时间，在这期间其他牛会吃掉2*Ti*Di的花，问如何排送牛的顺序使得被牛吃到的花最少。（牛只能一头一头的送，送完一头后再送另一头）

[输入输出]:

第一行是牛的头数n。接下来的n行是每一头牛的两个参数T和D。输出整个送牛期间被牛吃掉的最少的花。

[样例]:

Sample Input

3 1

2 5

2 3

3 2

4 1

1 6

Sample Output

[解题分析]:

策略很简单，就是按每分钟吃掉的花（单位时间内吃掉的花）从大到小排序，大的先运走。。。

[代码]：

import java.util.*;

class Cow implements Comparable{ //代表一头牛

private long t;

private long d;

public long getT(){

return this.t;

}

public long getD(){

return this.d;

}

public Cow(long t,long d){

this.t=t;

this.d=d;

}

public int compareTo(Object o){

Cow b = (Cow)o;

double diff=1.0 * this.d / this.t - 1.0 * b.d / b.t;

if (diff > 0)

return -1;

else if (diff == 0)

return 0;

else

return 1;

}

public String toString(){

return ("("+t+" "+d+")");

}

public class Main{

public static void main(String args[]){

long ans=0,sum=0;//吃掉的花和总用时

Scanner in=new Scanner(System.in);

int n=in.nextInt();

Cow cow[]=new Cow[n];

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

cow[i]=new Cow(in.nextLong(),in.nextLong());

}

Arrays.sort(cow);//将牛按单位时间内吃掉的花从大到小排序

sum = 2 * cow[ 0 ].getT();//送第一头牛的用时

ans = 0;

for(int i = 1; i < n; i ++ )//从第二头牛起计算每头牛吃掉的花。

{

ans = ans + sum * cow[ i ].getD();//送牛时间内每一头牛吃掉的花 sum = sum + cow[ i ].getT() * 2;//时间迭加

}

System.out.println(ans);

}

5．

题目大意]:

有n(1~10)种不同颜色的衣服总共m (1~100)件，Dearboy和她的girlfriend 两个人要一起洗完全部衣服，

两个人洗衣速度相同，并且已知每件衣服需要的时间<1000)。两个人可以同时洗衣。为了预防色彩混合，必须一种颜色的衣服洗完之后，两个人才能开工洗下一种颜色的衣服，问两个人洗完所有的衣服需要的最短时间。

[输入输出]:

输入的第一行是n和m,空格分开。第二行是衣服的所有颜色。按下来的m行是m 件要洗的衣服，每一行有这件衣服的洗衣时间和颜色。最后输入0 0结束。

输出两个人洗完所有的衣服需要的最短时间

[样例]:

Sample Input

3 4

red blue yellow

2 red

3 blue

4 blue

6 red

0 0

Sample Output

[解题分析]:

每种颜色的衣服可以分开来考虑，算出每种颜色的衣服所需要的最短时间，最后加起来即可。

然后再来考虑单一一种颜色的衣服该怎么洗，考虑到可能一个人要多洗一会儿，一个人要少洗一会儿，两个人所花的时间越接近一个人洗时总时间的一半，肯定是越好的方案，所以，用一个人洗时总时间的一半做容量，所有的衣服所花的时间做容量与价值（容量等于价值），转化成n个01背包，用01背包求出最大价值就是花时间少的那个人所用的时间了，然后用总时间减去这个花时间少的人的用时，就得到了用时多的人的用时了。

[代码]：

import java.util.*;

class Cloth{//表示一件要洗的衣服

int time;//洗这件衣服的时间

String color;//这件衣服的颜色

public Cloth(){

this.time=0;

this.color=null;

}

public Cloth(int tiem,String color){

this.time=time;

this.color=color;

}

public class Main{

private int n;//颜色种类数

private int m;//衣服件数

private String colors[];//颜色数组，保存所有的颜色

private Cloth cloths[];//衣服数组，保存所有要洗的衣服

private int res;//洗完全部衣服所需的最少时间

public Main(int n,int m,String colors[],Cloth cloths[]){

this.n=n;

this.m=m;

this.colors=colors;

this.cloths=cloths;

res=0;

}

public void dp(){//动态规划

int r[]=new int[n];//r[j]表示一个人洗colors[j]这种颜色的衣服的总的洗衣时间

int dp[]=new int[50000];

dp[j]表示在时间j内, 一个人洗某种颜色的衣服，一件件的洗. 最大洗衣时间。

总的衣服数< 100,每件衣服的洗衣时间< 1000，100*1000/2=50000

for(int i=0;i< m;i++){//对每一件衣服

for(int j=0;j< n;j++){//看它是哪一种的颜色

if(cloths[i].color.equals(colors[j])){

r[j]+=cloths[i].time;//计算这种颜色的衣服总的洗衣时间

break;

}

for(int i=0;i< n;i++){//对每一种颜色（n个01背包问题）for(int j=0;j<=r[i]/2;j++)

dp[j]=0;

for(int j=0;j< m;j++){//在所有衣服中找这种颜色的衣服

if(cloths[j].color.equals(colors[i])){

for(int k=r[i]/2;k>=cloths[j].time;k--){

if(dp[k]< dp[k-cloths[j].time]+cloths[j].time)

dp[k]=dp[k-cloths[j].time]+cloths[j].time;

}

res+=r[i]-dp[r[i]/2];//洗完全部衣服所需的最少时间=洗各种颜色衣服所需最少时间的和。

}

System.out.println(res);

}

public static void main(String args[]){

String colors[];

Cloth cloths[];

Scanner in=new Scanner(System.in);

while(true){

int n=in.nextInt();

int m=in.nextInt();

if(n==0&&m==0) break;

colors=new String[n];

cloths=new Cloth[m];

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

colors[i]=in.next();

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

cloths[i]=new Cloth();

cloths[i].time=in.nextInt();

cloths[i].color=in.next();

}

Main mm=new Main(n,m,colors,cloths);

mm.dp();

}

6．

[题目大意]:

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L 的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

[输入输出]:

输入

输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L 代表马路的长度，M代表区域的数目，

L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

[样例]:

样例输入

500 3

150 300

100 200

470 471

样例输出

298

[解题分析]:

先输入路线长度L，将他定义成一个数组的长度，即 l=input.nextInt(); int a[]=new int [l+1];将数组的每个元素都赋值成数字1，表示在这个点有一棵树，然后输入区间的个数和区间的两个端点，对应区间的起点和终点把数组中的这一段元素赋值成数字0。最后统计数组中1的个数。注意：

1.数组长度是l+1.

2.若输入的区间是 100,200.那么对应数组的起止位置是a[100]和a[200].画数轴看看就明白了。

[代码]：

import java.util.*;

import java.io.*;

public class Main {

public static void main(String []args)throws Exception{

Scanner input=new Scanner(System.in);

int l=0,m=0,c,b,s=0;

l=input.nextInt();

m=input.nextInt();

int a[]=new int [l+1];

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

a[i]=1;

}

while(m>0){

b=input.nextInt();

c=input.nextInt();

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

a[i]=0;

}

m--;

}

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

if(a[i]==1){

s++;

}

System.out.println(s);

}

7．

[题目大意]:

给你一个N * M（1 ≤ N, M ≤ 20）的地图，'.'表示空位，'*'表示垃圾，'o'表示机器人的初始位置，'x'表示墙。请你计算机器人清理完所有的垃圾至少要走多少步。机器人一旦走到垃圾上，垃圾就被清掉了。输入数据保证垃圾不多于10个。

[输入]

第一行：地图的宽和高，以下各行为地图数据，最后一行输入0，0结束。

[输出]:

机器人清理完所有的垃圾至少要走的步数。如果不能全部清理则输出 -1

[样例]:

Sample Input

7 5

.......

.o...*.

.......

.*...*.

.......

15 13

.......x.......

...o...x....*..

.......x.......

...............

xxxxx (xxxxx)

...............

.......x.......

..*....x....*..

.......x.......

10 10

..........

..o.......

..........

(xxxxx)

.....x....

.....x.*..

.....x....

0 0

Sample Output

-1

[解题分析]:(来自：

https://www.doczj.com/doc/6c1784026.html,/mark063_ai/blog/static/1776540812011212111358148/）

大概思路：

1）先对每两个点之间A*算出最短距离

2）转化成类似哈密顿问题，求从机器人所在的点到几个点的最短距离。

A*的话启发函数(g+h)直接是到达此点已经走的路程+当前点到目标点的直线距离。

记忆化搜索时需要用到状态压缩来记录已经走过的点。记录状态和判重的时候加一个二进制数s来表示就行了。类似于状态压缩。二进制数的第k位上如果是1，说明第k个垃圾清理过了（垃圾请自行编号）。各个位上都是1就表示垃圾清理完毕。

dp[now][s]表示最后一个到达的点为now，已经到达的点集为s的最短距离

(s & (1 << i)) != 0用来检查是否到过i，如果是的话，表达式为真

[代码]：

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.PriorityQueue;

class P {

int x, y, id;

P(){}

P(int x, int y, int id) {

this.x = x;

this.y = y;

this.id = id;

}

class A implements Comparable {// 优先级队列要用comparable接口

int x, y, step, score;

A(){};

A(int x, int y, int step, int score) {// 方便直接赋值

this.x = x;

this.y = y;

this.step = step;

this.score = score;

}

public int compareTo(A arg0) {

return (score - arg0.score);

}

public class Main {

char[][] g = new char[25][25];//地图

int[][] mat = new int[12][12];//机器人、垃圾点每两个点之间最短距离(步数）

int[][] dp = new int[11][1<<11];

int w, h, n ;

int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

boolean[][] mark = new boolean[25][25];

boolean[][] ok = new boolean[11][1<<11];

int dis(int x1, int y1, int x2, int y2) {

return (int) Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

int min(int a, int b) {return a > b ? b : a;}