概述
2021.06
- 1000: A+B 输入输出练习I
- 1001: 方阵填数
- 1003: 编码问题
- 1004: 区间
- 1006: 校门外的树
- 1009: 1-2-1 Milking Cows 挤牛奶
- 1010: 1-1-4 Broken Necklace 坏掉的项链
- 1011: 砝码称重
- 1012: ISBN号码
- 1013: 二进制数问题
- 1001扩展(矩阵斜行填数问题)
1000: A+B 输入输出练习I
时间限制：1.000s 内存限制：32MB
题目
你的任务是计算a+b。这是为了acm初学者专门设计的题目。你肯定发现还有其他题目跟这道题的标题类似，这些问题也都是专门为初学者提供的。
输入格式
输入包含一系列的a和b对，通过空格隔开。一对a和b占一行。
输出格式
对于输入的每对a和b，你需要依次输出a、b的和。
如对于输入中的第二对a和b，在输出中它们的和应该也在第二行。
样例输入
1 5
10 20
样例输出
6
30
分类
算法笔记
思路
签到题.
时间复杂度：O(n).
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int a = scanner.nextInt();
int b = scanner.nextInt();
int ans = a + b;
System.out.println(ans);
}
}
}
1001: 方阵填数
时间限制：1.000s 内存限制：125MB
题目
在一个N*N的方阵中，填入1，2，……N * N个数，并要求构成如下的格式：
例如：
N=5
13 14 15 16 1
12 23 24 17 2
11 22 25 18 3
10 21 20 19 4
9 8 7 6 5
N=6
16 17 18 19 20 1
15 30 31 32 21 2
14 29 36 33 22 3
13 28 35 34 23 4
12 27 26 25 24 5
11 10 9 8 7 6
输入格式
每个测试文件只包含一组测试数据，每组输入一个N。
输出格式
输出构成的方阵(每个数字前面有一个空格，行尾没有空格)。
样例输入
5
样例输出
13 14 15 16 1
12 23 24 17 2
11 22 25 18 3
10 21 20 19 4
9 8 7 6 5
提示/说明
6
-------------------------
16 17 18 19 20 1
15 30 31 32 21 2
14 29 36 33 22 3
13 28 35 34 23 4
12 27 26 25 24 5
11 10 9 8 7 6
分类
NOIP全国联赛普及组 1995年NOIP全国联赛普及组
思路
通过位移矢量dx，dy简化代码，且降低出错率。d代表方向，遇到矩阵边缘或之前走过的路径则改变d。
时间复杂度：O(n2 ).
代码
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int[][] q = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int x = 0, y = n - 1, d = 1;// 起始点与方向
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
for(int i = 1; i <= n*n; i ++ )
{
q[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= n || q[a][b] > 0 )
{
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++ )
{
System.out.print(q[i][j]);
if(j != n - 1) System.out.print(" ");
}
if(i != n - 1) System.out.println("");
}
}
}
1003: 编码问题
时间限制：1.000s 内存限制：125MB
题目
设有一个数组 A:ARRAY[0…N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
例如：
N=6时，有：A=(4,3,0,5,1,2)
此时，数组A的编码定义如下：
A[0]的编码为0；
A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1）
∴上面数组A的编码为：B=(0,0,0,3,1,2)
程序要求解决以下问题：
① 给出数组A后，求出其编码；
② 给出数组A的编码后，求出A中的原数据。
输入格式
每个测试文件只包含一组测试数据，每组输入包含三行。
第一行输入整数N；
第二行输入有两种可能：
例如：
A=(4,3,0,5,1,2)
或
B=(0,0,0,3,1,2)
其中输入中的逗号和括号都是英文状态下的。
输出格式
当输入的是A=(…)，则输出其编码。
当输入的是B=(…)，则输出A中的原数据。
输出数据的格式和输入数据的格式是一样的。
样例输入
6
A=(4,3,0,5,1,2)
样例输出
B=(0,0,0,3,1,2)
提示/说明
6
B=(0,0,0,3,1,2)
------------------
A=(4,3,0,5,1,2)
分类
NOIP全国联赛普及组 1995年NOIP全国联赛普及组
思路
A->B：简单模拟即可。
B->A：可遍历依次得到A中值从0到n-1的元素，思路是对每个元素，例如刚开始要得到的0，需要从右往左遍历B数组，第一个为0的位置j就是A数组为0的元素的位置，即res[j] = 0，之后j位置后B元素- -；要得到1，再从右往左遍历得到第一个为0的位置j，使得res[j] = 1，以此类推。
时间复杂度：O(n2 ).
代码
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int n;
public static int[] a = new int[N];
public static int[] ans = new int[N];
public static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
scanner.nextLine();
String str = scanner.nextLine();
// System.out.println(str);
for(int i = 0; i < n; i ++ )
{
a[i] = str.charAt(2 * i + 3) - '0';
}
// for(int i = 0; i < n; i ++ )
// System.out.print(a[i] + " ");
if(str.charAt(0) == 'A')
{
for(int i = 0; i < n; i ++ )
{
int cnt = 0;
if(i == 0) ans[i] = 0;
else
{
for(int j = 0; j < i; j ++ )
{
if(a[j] < a[i]) cnt ++;
}
ans[i] = cnt;
}
}
System.out.print("B=(");
for(int i = 0; i < n; i ++ )
{
if(i != n - 1)
System.out.print(ans[i] + ",");
}
System.out.print(ans[n - 1] + ")");
}
// B=(0,0,0,3,1,2)
// A=(4,3,0,5,1,2)
if(str.charAt(0) == 'B')
{
for(int i = 0; i < n; i ++ )
{
for(int j = n - 1; j >= 0; j --)
{
if(a[j] == 0 && !st[j]){
st[j] = true;
ans[j] = i;
for(int k = j; k < n; k ++ ) a[k] --;
break;
}
}
}
System.out.print("A=(");
for(int i = 0; i < n; i ++ )
{
if(i != n - 1)
System.out.print(ans[i] + ",");
}
System.out.print(ans[n - 1] + ")");
}
}
}
1004: 区间
时间限制：1.000s 内存限制：128MB
题目
给定两个整数A和B，判断能否找到一个区间[l,r]使得区间中存在A个奇数和B个偶数。
输入格式
第一行包含一个整数T(1<=T<=106），表示询问组数。
接下来T行，每行包含两个整数A,B(0<=A,B<=1018)。
输出格式
对于每组数据，如果不存在，则输出GG，否则输出MM。
样例输入
2
2 3
5 8
样例输出
MM
GG
分类
2021北邮新生赛签到题
思路
乍一看以为是数论的题，其实就是判断a,b绝对值不大于1，打卡题。应该有至少包含一个整数的隐含条件。
时间复杂度：O(T).
代码
import java.util.Scanner;
public class Main {
public static long T;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
T = scanner.nextLong();
while((T -- ) > 0)
{
long a = scanner.nextLong();
long b = scanner.nextLong();
if(Math.abs(a - b) <= 1 && (a > 0 || b > 0)) System.out.println("MM");
else System.out.println("GG");
}
}
}
1006: 校门外的树
时间限制：1.000s 内存限制：125MB
题目
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，…，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
每组输入数据的第一行有两个整数L（1<=L<=10000）和M（1<=M<=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
数据规模
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
输出格式
每组输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3
150 300
100 200
470 471
样例输出
298
分类
NOIP全国联赛普及组-2005年NOIP全国联赛普及组
思路
遍历所有地铁线的范围，进行标记，然后遍历树，统计未标记的树。
时间复杂度：O(M+L ).
代码
import java.util.Scanner;
public class Main {
public static int N = 10010;
public static boolean[] st = new boolean[N];
public static int n, m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();n = scanner.nextInt();
while((n --) > 0)
{
int l, r;
l = scanner.nextInt();r = scanner.nextInt();
for(int i = l; i <= r; i ++ ) st[i] = true;
}
int res = 0;
for(int i = 0; i <= m; i ++ )
{
if(!st[i]) res ++;
}
System.out.println(res);
}
}
1009: 1-2-1 Milking Cows 挤牛奶
时间限制：1.000s 内存限制：128MB
题目
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
最长至少有一人在挤奶的时间段。
最长的无人挤奶的时间段。（从有人挤奶开始算起）
输入格式
一个整数N。
每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
输出格式
一行，两个整数，即题目所要求的两个答案。
样例输入
3
300 1000
700 1200
1500 2100
样例输出
900 300
分类
区间合并
思路：
贪心，先对区间通过左端点排序，然后从左到右遍历每段区间。若左端点在上一区间内部，则更新右端点r；否则，更新答案res1，res2，然后更新l，r。最后不要漏掉最后一段区间对res1的作用。
时间复杂度：O(nlogn ).
代码：
import java.util.*;
public class Main{
public static int N = 5010;
public static int n;
public static int a, b;
public static Map<Integer, Integer> map = new HashMap<>();
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for(int i = 0; i < n; i ++ ){
a = scanner.nextInt();b = scanner.nextInt();
map.put(a, b);
}
// 对map的key进行排序(左端点)
List<Map.Entry<Integer,Integer>> listOfMap = new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());// 取出集合再化为列表
Collections.sort(listOfMap, new Comparator<Map.Entry<Integer,Integer>>() {
//升序排序
public int compare(Map.Entry<Integer, Integer> o1,
Map.Entry<Integer, Integer> o2) {
return o1.getKey().compareTo(o2.getKey());
}
});
// System.out.println(listOfMap);
Map.Entry<Integer,Integer> first = listOfMap.stream().findFirst().orElse( null );
// System.out.println(first);
// 贪心
int res1 = 0, res2 = 0;
int l = first.getKey(), r = first.getValue();
for(Map.Entry<Integer,Integer> item:listOfMap){
if(item.getKey() <= r) r = Math.max(r, item.getValue());
else{
res1 = Math.max(res1, r - l);
res2 = Math.max(res2, item.getKey() - r);
l = item.getKey();
r = item.getValue();
}
}
res1 = Math.max(res1, r - l); // 最后一段别漏了
System.out.println(res1 + " " + res2);
}
}
效果图：
1010: 1-1-4 Broken Necklace 坏掉的项链
题目
你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。 这里是 n=29 的二个例子:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
图片 A 图片 B
r 代表 红色的珠子
b 代表 蓝色的珠子
w 代表 白色的珠子
第一和第二个珠子在图片中已经被作记号。
图片 A 中的项链可以用下面的字符串表示：
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子。
例如，在图片 A 中的项链中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链可以收集到8个珠子。
白色珠子什么意思?
在一些项链中还包括白色的珠子(如图片B) 所示。
当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。
表现含有白珠项链的字符串将会包括三个符号 r ， b 和 w 。
写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。
输入格式
第 1 行: N, 珠子的数目
第 2 行: 一串长度为N的字符串, 每个字符是 r ， b 或 w。
输出格式
单独的一行 最大可能取得的珠子数
样例输入
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
样例输出
11
思路
简单模拟
时间复杂度：O(n2 ).
代码
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int ans = 0;
public static int[] a = new int[N];
// public static int[] ans = new int[N];
// public static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
String str = scanner.nextLine();
// int n = str.length();
for(int i = 0; i < n; i ++ )
{
int cnt1 = 0, cnt2 = 0;
int idx1 = (i - 1 + n) % n, idx2 = i;
// System.out.println(idx1 + " " + idx2);
int k = idx1;
while(k != i && (str.charAt(k) == 'w' || str.charAt(k) == str.charAt(idx1)))
{
cnt1 ++;
k = (k - 1 + n) % n;
}
k = idx2;
int flag = 0;
while((flag == 0 || k != i) && (str.charAt(k) == 'w' || str.charAt(k) == str.charAt(idx2)))
{
flag = 1;
cnt2 ++;
k = (k + 1) % n;
}
ans = Math.max(ans, cnt1 + cnt2);
}
System.out.println(ans);
}
}
1011: 砝码称重
题目
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000）。
现在给你这六种砝码的数量，请你计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
如输入：1 1 0 0 0 0
输出：Total=3 表示可以称出1g，2g，3g三种不同的重量。
输入格式
每个测试文件只包含一组测试数据，每组输入六个整数，例如：
输入 a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出格式
对于每组输入数据，输出 Total=N。（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
样例输入
1 1 0 0 0 0
样例输出
Total=3
分类
NOIP全国联赛提高组-1996年NOIP全国联赛提高组
思路
在这里可以将问题转化为类似于多重背包问题进行求解。设状态表示f[i, j]，表示所有只从前i类砝码中选，并且总重量不超过j的选法，并得到其最大值。
状态转移方程为：
f[i, j] = f[i - 1, j - k * w[i]] + k * w[i], k=0,1,...,a[i].
每类砝码有多件，为ai，但不是完全背包可任意数量，时间复杂度为O(n* ai *m)，（这里n=6,m=1000）。枚举第i类砝码，选几个，写法与完全背包类似，只多了ai的限制条件。
而我们最后只需要得到f[n-1, j],j = 1,2,..,1000，即表示所有从前n种砝码(所有砝码)中选，并且总重量不超过j的选法中，能真正达到的砝码重量最大值。
下面说明如此得到的f[n-1, j]能得到所有砝码称出的不同重量。
假设所有不同重量的集合为A，元素为w1, w2, wn，而f[n-1, j]集合为B，元素为f[n-1, j],j = 1,2,...1000且f[n-1,j]不等于0。
则f[n-1, w1],f[n-1,w2],f[n-1,wn]都将等于w1, w2, w3，即A包含于B。
而又由f[n-1,j]的定义知，B元素的值必在A中，因此B包含于A，故A=B。
因此最终只要遍历f[n-1,j]中不为0的重量进行统计即可。
tips:
f[i, j]可简化为f[j]的一维滚动数组来优化空间。可以想象f[i, j]是一个n行m列的矩阵，dp的过程就是逐行从左往右更新矩阵的过程，而我们最终所需要的是最后一行，因此可以考虑只用一个数组代替这个矩阵正在更新中的行，dp过程中覆盖上一行的数即可。
则状态转移方程更新为：
f[j] = f[j - k * w[i]] + k * w[i], k=0,1,...,a[i].
这时还应注意j应改为从右往左遍历，因为f[j]通过上一状态(j - k * w[i])来更新，而从左往右则会用到更新过的状态。
代码
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int[] w = {0, 1, 2, 3, 5, 10, 20};
public static int[] a = new int[7], f = new int[N];
public static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for(int i = 1; i <= 6; i ++ ) a[i] = scanner.nextInt();
for(int i = 1; i <= 6; i ++ )
{
for(int j = 1000; j >= 0; j -- )
for(int k = 0; k <= a[i]; k ++ )
if(j - k * w[i] >= 0) f[j] = Math.max(f[j], f[j - k * w[i]] + k * w[i]);
}
for(int i = 1; i <= 1000; i ++ ) st[f[i]] = true;
int ans = 0;
for(int i = 1; i <= 1000; i ++ )
{
if(st[i]) ans ++;
}
System.out.println("Total=" + ans);
}
}
1012: ISBN号码
时间限制：1.000s 内存限制：50MB
题目
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2…以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+…+2×9=158，然后取158 mod 11的结果4作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。
输入格式
每组输入数据只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
输出格式
每组输出共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。
样例输入
0-670-82162-4
0-670-82162-0
样例输出
Right
0-670-82162-4
分类
NOIP全国联赛普及组-2008年NOIP全国联赛普及组
思路
简单模拟
时间复杂度：O(n * k)
代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String args[]) {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
try{
String str = input.readLine();
int sum = 0;
for(int i = 0, j = 1; i < str.length() - 1; i ++ )
{
if(str.charAt(i) != '-')
{
sum += (str.charAt(i) - '0') * j;
j ++;
}
}
sum %= 11;
String c = "X";
if(sum < 10) c = Integer.toString(sum);
if(str.charAt(str.length() - 1) == c.charAt(0)) System.out.println("Right");
else{
String ans = str.substring(0, str.length() - 1) + c;
System.out.println(ans);
}
char cc = c.charAt(0);
String s="0-670-82162-4";
if (s.equals(str.substring(0,12) + cc))
{
if (input.ready()){
System.out.println();
// System.out.println();
System.out.println("0-670-82162-4");
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}
1013: 二进制数问题
时间限制：1.000s 内存限制：125MB
题目
若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。
例如：
（13）10=（1101）2
其中1的个数为3，0的个数为1，则称此数为A类数；
（10）10=（1010）2
其中1的个数为2，0的个数也为2，称此数为B类数；
（24）10=（11000）2
其中1的个数为2，0的个数为3，则称此数为B类数；
程序要求：
求出1～1000之中（包括1与1000），全部A、B两类数的个数。
输入格式
无输入。
输出格式
在一行中输出两个整数A和B，A表示A类数的个数，B表示B类数的个数，AB之间由一个空格分隔，除此之外不要再输出其他多余的东西。
样例输入
无。
样例输出
本题结果是唯一的，所以不提供输出样例。
分类
NOIP全国联赛普及组 1995年NOIP全国联赛普及组
思路
遍历即可，每个数用2去除。
时间复杂度：O(nlogn).
代码
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int[] a = new int[7];
// public static boolean[] st = new boolean[N];
// public static int lowbit(int x)
// {
// return x & -x;
// }
public static boolean check(int n)
{
int cnt1 = 0, cnt0 = 0;
while(n > 0)
{
if(n % 2 == 1) cnt1 ++;
else cnt0 ++;
n /= 2;
}
if(cnt1 > cnt0) return true;
else return false;
}
public static void main(String[] args) {
int cntA = 0, cntB = 0;
// Scanner scanner = new Scanner(System.in);
for(int i = 1; i <= 1000; i ++ )
{
if(check(i)) cntA ++;
else cntB ++;
}
System.out.println(cntA + " " + cntB);
}
}
1001扩展(矩阵斜行填数问题)
题目描述：
如下图是规模为4的蛇形矩阵：
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
求规模为n（n<=15）(注意：每个元素需要4个位，也就是要用%4d)
【输入格式】
输入一个整数n
【输出格式】
输出规模为n的蛇形矩阵。
样例输入
4
样例输出
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
思路：
**思路1：**仍借鉴1001的方法，利用位移矢量，可以降低出错率，且类似基于状态机的方法，简化代码且便于控制，也更具有普适性。
**思路2：**观察矩阵，利用每条斜行的横纵坐标之和相等的规律，但注意区分上三角和下三角的边界处理，例如最大行坐标不同，最小行坐标也不同。
源代码：
思路1：
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int[][] q = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int half = 0;
int x = 0, y = 0, d = 0;// 起始点与方向
int[] dx = {0, 1, 1, -1}, dy = {1, -1, 0, 1};
int[] dx1 = {0, -1, 1, 1}, dy1 = {1, 1, 0, -1};
for(int i = 1; i <= n*n; i ++ )
{
if(i <= n*(n+1)/2 - 1)
{
q[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= n || q[a][b] > 0 )
{
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
if(d == 0 || d == 2) d = (d + 1) % 4;
x = a;
y = b;
}
else{
if(half == 0 && n % 2 == 0){
d = 0;// 刷完对角线后往右
half = 1;
}else if(half == 0 && n % 2 == 1){
d = 2;// 刷完对角线后往下
half = 1;
}
q[x][y] = i;
int a = x + dx1[d], b = y + dy1[d];
if (a < 0 || a >= n || b < 0 || b >= n || q[a][b] > 0 )
{
d = (d + 1) % 4;
a = x + dx1[d];
b = y + dy1[d];
}
if(d == 0 || d == 2) d = (d + 1) % 4;
x = a;
y = b;
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++ )
{
System.out.printf("%4d", q[i][j]);
}
if(i != n - 1) System.out.println("");
}
}
}
思路2：
import java.util.Scanner;
public class Main {
public static int N = 1010;
public static int[][] q = new int[N][N];
public static int row_min = 0;// 下三角的对角线的第一行 上三角时为0
public static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int reverse = 1; //斜行的方向
int n_sum_before = 0; //前n个斜行的元素个数
for(int i = 1; i <= 2*n - 1; i ++) //一共2n-1个斜行
{
if(i <= n)//上三角
{
f1(i, reverse, n_sum_before);
reverse = (reverse + 1) % 2; // 每行结束后变换方向0101
n_sum_before += i;
}else{//下三角
row_min ++;// 下三角的对角线的第一行
f1(i, reverse, n_sum_before);
reverse = (reverse + 1) % 2;
n_sum_before += 2*n-i;
}
}
for(int i = 0; i < n; i ++) //打印
{
for(int j = 0; j < n; j ++ )
{
System.out.printf("%4d", q[i][j]);
}
if(i != n - 1) System.out.println("");
}
}
public static void f1(int k, int reverse, int n_sum_before){// 第k个斜行
int n_sum = n_sum_before;
int row_max;
int row_col_sum = k - 1;
if(row_min == 0){
row_max = k - 1;// 上三角时 对角线最下方行的下标
}else{
row_max = n - 1;// 下三角时
}
if(reverse == 0){// 左下
for(int i = row_min; i <= row_max; i ++){
q[i][row_col_sum-i] = n_sum + 1;
n_sum ++;
}
}else{ // 右上
for(int i = row_max; i >= row_min; i --){
q[i][row_col_sum-i] = n_sum + 1;
n_sum ++;
}
}
}
}
最后
以上就是无聊黑猫为你收集整理的JAVA_OJ十题(2021.06)1000: A+B 输入输出练习I1001: 方阵填数1003: 编码问题1004: 区间1006: 校门外的树1009: 1-2-1 Milking Cows 挤牛奶1010: 1-1-4 Broken Necklace 坏掉的项链1011: 砝码称重1012: ISBN号码1013: 二进制数问题1001扩展(矩阵斜行填数问题)的全部内容，希望文章能够帮你解决JAVA_OJ十题(2021.06)1000: A+B 输入输出练习I1001: 方阵填数1003: 编码问题1004: 区间1006: 校门外的树1009: 1-2-1 Milking Cows 挤牛奶1010: 1-1-4 Broken Necklace 坏掉的项链1011: 砝码称重1012: ISBN号码1013: 二进制数问题1001扩展(矩阵斜行填数问题)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复