湘潭大学OJ-2018年期末考试JAVA版

• Triangle
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 思路
  • 代码：
• Palindrome
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码
• Fraction
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码
• Digit String
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码
• Robots
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码
• Euler's Totient Function
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码
• Maze
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 思路
  • 代码

在单位半径的半圆弧上的一个点C，已知其x坐标，求三角形△ABC的面积。
题目地址

第一行是一个整数T(1≤T≤1000)，表示样例的个数。 以后的每一行是一个浮点数x(−1≤x≤1)，表示点C的x坐标。

每行输出一个样例的结果，保留3位小数。

2 0 0.5

样例输出

简单的数学计算

import java.util.Scanner;

public class P1350 {
    public static void main(String args[]){
        int T;
        Scanner in = new Scanner(System.in);
        T = in.nextInt();
        while (T>0){
            T--;
            double x = in.nextFloat();
            double y = Math.sqrt(1-x*x);
            double s = y;
            System.out.println(String.format("%.3f",s));
        }
    }
}

给你一个只含有英文小写字母的字符串，你可以无限次交换任意相邻的两个字符，请问是否能将字符串变为回文串。 所谓“回文串”，就是字符串从左到右读，和从右到左读是一样的字符串。

存在不超过1000个样例。 每行一个字符串，不超过1000个字符。

每行输出一个样例的结果，如果原串可以变成回文串，输出"Yes"，否则输出"No"。

abcd
aaaa

No
Yes

计算每个字母的个数，根据回文串特点，个数为奇数的字母最多只有一个。

#include
#include
#include
using namespace std;
int main(){
    char str[1001];
    while(scanf("%s",str)!=EOF){
        int nums[1005] = {0};
        int len = strlen(str);
        for(int i=0;i='a'&&str[i]<='z')
            nums[str[i]-'a']++;
        }
        bool flag = false;
        int counts = 0;
        for(int i=0;i<26;i++){
            if(nums[i]%2!=0){
                counts++;
            }
        }
        if(counts<=1){
            printf("Yesn");
        }else{
            printf("Non");
        }
    }
}

埃及人只能理解分子为1的分数，所以他们把分子不为1的分数理解成若干个分母不相同的分数的累加和。 比如23=12+16。

如果存在多个解，我们希望按分母从小到大的排列，然后取字典序最小的一个。 比如35=12+110=13+14+160。 我们按分母从小到大排列，前者为<2,10>,后者为<3,4,60>,显然前者的字典序更小。

现在给你一个分数，请求出符合要求的埃及人能理解的分数。

第一行是一个整数T(1≤T≤1000)，表示样例的个数， 每个样例是两个整数a,b(1≤a 输出

每行输出一个样例的结果，为分母从小到大排列，每个分母之间用一个空格隔开。

3
1 2
2 3
3 7

2
2 6
3 11 231

这题感觉更多的是考数学，我是搜埃及分数性质才懂的，整体思路是贪心算法。

import java.util.Arrays;
import java.util.Scanner;

public class P1352 {
    public static void main(String  args[]){
        long T,a,b,common;
        Scanner in = new Scanner(System.in);
        T = in.nextInt();
        while (T>0){
            T--;
            a = in.nextLong();
            b = in.nextLong();
            long up = a,down = b;
            long K = 0;
            int counts = 0;
            long res[] = new long[100001];
            for(;;){
                K = down/up+1;
                if(down%up==0){
                    res[counts++]=down/up;
                    break;
                }else{
                    res[counts++]=K;
                }
                up = K*up-down;
                down = K*down;
                common = gcd(up,down);
                up = up/common;
                down = down/common;
            }
            Arrays.sort(res,0,counts);
            for(int i=0;i 
Digit String 
题目描述 
小明获得了一些密码的片段，包含0∼9,A∼F 这些字符，他猜这些是某个进制下的一个整数的数码串。 小明想知道从2到16进制中，哪些进制下，这个数码串的对应的十进制整数值，等于n?
 
输入 
存在不超过1000个样例，每行一个样例。 每行包括两部分，数码串(串长不超过31)，整数n(1≤n≤109)
 
输出 
每行输出一个样例的结果。 如果存在多个解，输出最小的那个进制。 如果没有满足的进制，输出"Impossible"。
 
样例输入 
F 15
F 14
23 11
25 13
 
样例输出 
16
Impossible
4
Impossible
 
思路 
模拟，懂得进制转换就好做，记得题目中说的，选择最小的一个进制，那么遍历进制的时候肯定是顺序遍历的，还有注意:进制里面的数字<进制的，如:二进制01里面的数只能是比2小的，二进制不能是012。
 
代码 
import java.io.BufferedInputStream;
import java.util.Scanner;

public class P1353 {
    public static void main(String args[]){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        String str=null;
        long num = 0;
        while (in.hasNext()){
            str = in.next();
            num = in.nextLong();
            char chs[] = str.toCharArray();
            int len = chs.length;
            long sum = 0,res = 0;
            boolean flag = false;
            for(int i=2;i<=16;i++){
                sum = 0;
                flag=false;
                long mid = 0;
                for(int j=0;j= '0' && chs[j] <= '9'){
                        mid = chs[j] - '0';
                        if(mid >=i ){
                            break;
                        }
                    }else if(chs[j] >= 'A' && chs[j] <= 'F'){
                        mid = chs[j] - 'A' + 10;
                        if(mid >=i ){
                            break;
                        }
                    }
                    sum = sum * i + mid;
                }
                if(sum==num) {
                    res = i;
                    flag = true;
                    break;
                }
            }
            if(flag)
                System.out.println(res);
            else{
                System.out.println("Impossible");
            }
        }
    }
}
 
Robots 
题目描述 
在一个n×m的格子上，机器人一开始位于左下角，它每次可以沿格子线往上或者往右行走一步。另外它还有一种技能，可以在一个格子中，从左下角跳到右上角。 请问，机器人从左下角到达右上角，一共有多少种不同的方法？
 图片可参照原题
 
输入 
第一行是一个整数T(1≤T≤10000)，表示样例的个数。 以后每行一个样例为两个整数n,m(1≤n,m≤100)。
 
输出 
每行输出一个样例的结果，因为这个数量可能很大，请将结果对109+7取模。
 
样例输入 
3 1 1 2 1 2 2
 
样例输出 
3 5 13
 
思路 
很明显的是动态规划,我们可以用一个数组来存储到达该店的方案数，状态转移方程为:
 
dp[i][j] = dp[i][j]+dp[i-1][j-1]+dp[i-1][j]+dp[i][j-1];
 
这个意思是当前到达该点的方案数等于该点原来的方案数加上上一步的方案数目，这个上一步的方案数目就是当前点向下移一步和向左移一步后得到点的方案数，因为题目中说明了每次可以沿格子线往上或者往右行走一步。
 除此之外，这题还需要打表，不然会超时，还要注意取模，因为数值会很大，会有溢出。
 
代码 
import java.util.Scanner;

public class P1354 {
    static long dp[][] = new long[101][101];
    static long MAX = (long) (1e9+7);
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        record();
        while (T>0){
            T--;
            int m = in.nextInt();
            int n = in.nextInt();
            System.out.println(dp[m][n]);
        }
    }

    public static void record(){
        for(int i = 0;i<=100;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<=100;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                long mid = (dp[i-1][j-1]%MAX+dp[i-1][j]%MAX+dp[i][j-1]%MAX)%MAX;
                dp[i][j]=(dp[i][j]+mid)%MAX;
            }
        }

    }
}
 
Euler’s Totient Function 
题目描述 
对于整数n，定义ϕ(n)为小于或等于n，并与n互质的整数的个数，比如6,比它小的和它互质的数有1,5,所以ϕ(6)=2。 如果n=pk11⋅pk22⋅…⋅pkmm，其中pi为不相同的素数。 那么ϕ(n)=n⋅(1−1p1)⋅…⋅(1−1pm)。
 
我们定义f(a,b)=∑bi=aϕ(i),请你写一个程序求f(a,b)。
 
输入 
第一行是一个整数T(1≤T≤10000)，表示样例的个数。 每个样例是一行，为两个整数a,b(1≤a≤b≤3000000)。
 
输出 
每行输出一个样例的结果。
 
样例输入 
3  
1 6  
1 100  
1 1000000
 
样例输出 
12  
3044  
303963552392
 
思路 
OJ里面最烦人的一种题目了，要学会打表（欧式筛法，埃式筛法等）,
 打表就完事了。打表真的很重要，以空间换时间。
 
代码 
import java.io.BufferedInputStream;
import java.util.Scanner;

public class P1355 {
    private static int MAX = 3000001;
    private static long tmp[] = new long[MAX];
    private static long fi[] = new long[MAX];
    public static void main(String args[]){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        record();
        int T = in.nextInt();
        while ((T--)>0){
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(fi[b]-fi[a-1]);
        }
    }

    public static void record(){
        int i,j;
        for(i = 2;i < MAX;i++){
            if(tmp[i]==0){
                for(j = i;j < MAX;j+=i){
                    if(tmp[j] == 0){
                        tmp[j] = j;
                    }
                    tmp[j] = (tmp[j]/i)*(i-1);
                }
            }
        }

        fi[1]=1;
        for(i = 2;i 
Maze 
题目描述 
一个n∗m格子的迷宫，’.‘表示道路，’*'表示墙，'S’表示起点，'E’表示终点。一个机器人一开始在起点，如果在它的方向前是道路，每次能往前走一格；如果在它的方向前是墙或者迷宫边界，它会右转90∘。请问机器人从起点到终点最少走多少步？
 
输入 
第一行是一个整数T(1≤T≤100)，表示样例的个数。 每个样例第一行是三个整数，为n,m(1≤n,m≤100),d(1≤d≤4)，n,m表示迷宫的行、列大小， d表示机器人一开始的方向，1∼4依次表示"上右下左"。 以后的n行是迷宫的情况，数据保证S和E不重合。
 
输出 
每行输出一个样例的结果，如果无法走出迷宫，输出"Impossible"
 
样例输入 
2
3 4 2
S...
***.
E...
3 4 2
S...
....
E.*.
 
样例输出 
8
Impossible
 
思路 
我想到的是两种写法，一种是队列(超时了，可能是java巨慢的输入)，一种是动态规划。
 具体说明一下动态规划的思路
 用一个数组vis[i][j][d]来存放到达当前位置的步数。
 根据不同的情况对vis进行处理，这里分为了四种大情况，即不同的方向，每一个方向里面也包含两种情况，一种是需要变方向的，一种是不需要变的。
 转移方程：
 方向改变的情况
 
dp[i][j][新的方向] = dp[i][j][旧的方向];
 
这是方向不用改变的情况
 
dp[i][j][d] = dp[m][n][d];//m,n为上一步的坐标，根据情况修改
 
代码 
//dp
import java.io.BufferedInputStream;
import java.util.linkedList;
import java.util.Queue;
import java.util.Scanner;

public class P1356_2 {
    private static int m,n;
    private static int MAX = 99999999;
    public static void main(String args[]){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int T = in.nextInt();
        while (T>0){
            T--;
            n = in.nextInt();
            m = in.nextInt();
            int d = in.nextInt();
            int beginX=0,beginY=0,endX=0,endY=0;
            char maze[][] = new char[n][m];
            int dist[][][] = new int[n][m][5];//represent the min distance of point(i,j)
            boolean vis[][][] = new boolean[n][m][5];
            for(int i = 0;i < n;i++){
                String mid = in.next();//util read /n finish
                for(int j = 0;j < m;j++){
                    maze[i][j] = mid.charAt(j);
                    for(int t = 1;t <= 4;t++){
                        dist[i][j][t]=MAX;//init the max value
                    }
                    if(maze[i][j]=='S'){
                        beginX = i;
                        beginY = j;
                    }
                    if(maze[i][j]=='E'){
                        endX = i;
                        endY = j;
                    }
                }
            }
            if(m == 1 && n == 1){
                System.out.println("Impossible");
                continue;
            }
            //solve by dp
            for(int t = 1;t <= 4;t++){
                dist[beginX][beginY][t] = 0;
            }
            //start imitate the step
            int nx = beginX,ny = beginY;
            while (true){
                if(nx == endX && ny == endY){
                    break;
                }
                if(vis[nx][ny][d]){
                    break;
                }
                vis[nx][ny][d] = true;  //mark the point of the direction has scanned
                if(d == 1){             //up
                    nx--;
                    if(nx < 0 || maze[nx][ny] == '*'){
                        d = 2;          //change direction
                        nx++;
                        dist[nx][ny][2] = dist[nx][ny][1];
                    }else{
                        dist[nx][ny][d] = dist[nx+1][ny][d]+1;
                    }
                }else if(d == 2){       //right
                    ny++;
                    if(ny >= m || maze[nx][ny] == '*'){
                        d = 3;          //change direction
                        ny--;
                        dist[nx][ny][3] = dist[nx][ny][2];
                    }else {
                        dist[nx][ny][d] = dist[nx][ny-1][d]+1;
                    }
                }else if(d == 3){       //down
                    nx++;
                    if(nx >= n || maze[nx][ny] == '*'){
                        d = 4;          //change direction
                        nx--;
                        dist[nx][ny][4] = dist[nx][ny][3];
                    }else {
                        dist[nx][ny][d] = dist[nx-1][ny][d]+1;
                    }
                }else if(d == 4){       //left
                    ny--;
                    if(ny < 0 || maze[nx][ny] == '*'){
                        d = 1;          //change direction
                        ny++;
                        dist[nx][ny][1] = dist[nx][ny][4];
                    }else {
                        dist[nx][ny][d] = dist[nx][ny+1][d]+1;
                    }
                }
            }
            int min = MAX;
            for(int t = 1;t <= 4;t++){
                min = Math.min(min,dist[endX][endY][t]);
            }
            if(min == MAX){
                System.out.println("Impossible");
            }else{
                System.out.println(min);
            }
        }
    }
}