平方拆分
【问题描述】 将 2019 拆分为若干个两两不同的完全平方数之和,一共有多少种不同的方 法?
注意交换顺序视为同一种方法,例如 132 + 252 + 352 = 2019 与 132 + 352 + 252 = 2019 视为同一种方法。
答案:26287
(如果可以拆成0*0 那么答案:52574)
package The_tenth;
public class Three {
static int sum;
public static void main(String[] args) {
//平方拆分
dfs(2019,1,45);
System.out.println(sum);
}
//深搜平方和为2019的所有子集
private static void dfs(int num, int min, int max) {
if (num < 0) {
return;
}
if (num == 0) {
sum ++;
return;
}
//按顺序 2019- 1^2 - 2^2 ...-n^2
//传入的第一个值为2019 第二个值为 组合2019的完全平方数 的其中一个
//第二个值每轮+1 第一个值每轮都减去 第二个值的平方
// 当num<0或者等于0时 (num:第一个值(2019))
// 如果小于0那么return,然后回溯 继续 n的值+1 如果还是小于继续+1
// 期间如果num=0了说明拼成了一次(即前面所有数的平方的和=2019)
//n的值+到44后到达上限无法再加 然后再回溯改变n上一个数的值 ....
//因为n是有序递增的 所以不会出现重复的顺序不同组成的值相同的情况
for (int i = min; i < max; i++) {
//去重,保证下一位数字一定大于当前数字
dfs(num - i * i, i + 1, max);
}
}
}
数正方形
【问题描述】 在一个 N × N 的点阵上,取其中 4 个点恰好组成一个正方形的 4 个顶点, 一共有多少种不同的取法?
由于结果可能非常大,你只需要输出模 109 + 7 的余数。
如上图所示的正方形都是合法的。
【输入格式】
输入包含一个整数 N。
【输出格式】
输出一个整数代表答案。
【样例输入】
4
【样例输出】
20
package The_tenth;
import java.util.Scanner;
public class G {
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);
int n = sn.nextInt()-1; //题目中的例子似乎是错的? 事实上3*3的点阵的正方形的数量才是20 如果要达到例子的效果 在接受输入值的时候-1即可(没明白什么意思)
long count = 0;//正方形的数量
long num = 1000000007;
//平放
// a 表示正方形边长
//表面的正方形 边长从1 - 最大长度
//count(正方形的总数量) += ( n(最大边长) - a(当前边长) + 1 ) * ( n(最大边长) - a(当前边长) + 1 )
//比如 当a = 1,n = 4的时候 count += (4-1+1) * (4-1+1) = 4 * 4 = 16 也就是边长为1的正方形 在4*4的表格中 有16个
//再比如 当a = 2, n = 4的时候 count += (4-2+1)*(4-2+1) = 3*3 = 9 也就是边长为2的正方形 在4*4的表格中 有9个
//原理就是 求出长度为4的表格 可以划出多少个 不同的长度为 2的表格
for (int a = 1; a <= n; a++) {
//a表示 当前正方形的边长 然后count += 当前边长正方行的数量
count += (n - a+1) * (n - a+1);
// System.out.println((n - a+1) * (n - a+1));
count %= num;
}
// System.out.println(count);
// 斜放
//根据观察 1*1的矩阵 不存在正方形(指这个大小的矩阵特有的正方形)
//2 * 2的矩阵 有一个斜边正方形 ;3 * 3的矩阵有 2个斜边正方形
//观察发现 2*2的矩阵每个边有3个顶点 最左和最右的顶点无法构成斜边正方形
//所以可以构成斜边正方形的顶点 就是 顶点数量 - 2(最左和最有的顶点)
//每个顶点可以构成一个斜边正方行 所以 当前大小矩阵的特有斜边正方形数量 = 当前一个边顶点数-2
for (int i = 1; i <= n; i++) {
//i为当前矩阵长度
// i+1 : 当前顶点数量
// -2 : 因为最左和最右的顶点无法构成斜边正方形所以减去他们 就得到了当前顶点你数量 = 当前斜边正方形数量
// (n-i+1) * (n-i+1) :表示当前最大矩阵 有多少个边长为i的正方形
// count += 边长为i的矩形有的斜边正方形的数量 * 边长为N的矩形(最大边长)有多少个边长为i的矩形
count += (i+1-2) * (n-i+1) * (n-i+1);
count %= num;
}
System.out.println(count);
}
}
矩阵计数
【问题描述】
一个 N × M 的方格矩阵,每一个方格中包含一个字符 O 或者字符 X。
要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。
问这样的矩阵一共有多少种?
【输入格式】
输入一行包含两个整数 N 和 M。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 3
【样例输出】
49
【数据规模与约定】
对于所有评测用例,1 ≤ N, M ≤ 5。
package The_tenth;
import java.util.ArrayList;
import java.util.Scanner;
public class H {
static int count = 0;
static ArrayList> z = new ArrayList>();
public static void main(String[] args) {
//矩阵计数
//每个格子有0(x),1(o)两种状态
//假如矩阵有 a 列 那么每行都有2^m种情况(例如每行有3列 那么每行就有 2*2*2种情况)
//加入有2列 每行有8种情况(8种是所有情况 实际应该筛掉行中不符合条件的情况 比如如果有3列 那么行一共有8种情况 但符合条件的有7种情况 所以我们使用的应该是7)
// 那么一共就有8 *8种矩形 然后分别判断每个矩形是否符合条件就行了
Scanner sr = new Scanner(System.in);
int x = sr.nextInt();//行数
int y = sr.nextInt();//列数
int [][]jz = new int[x][y];
int []xx = new int[y];
ArrayList arr = new ArrayList();
get(y,arr);//获取 每行的所有符合条件的可能性
examine(0,jz);//将每行的情况组合起来并判断组合完后的矩形是否符合条件
System.out.println(count);
// for (ArrayList i: z){
// System.out.println(i);
// }
}
//获取所有符合条件的矩阵 i=当前行数
public static void examine(int i,int [][]jz){
//当所有行都装完了(矩阵填充完毕)
if (i>=jz.length){
//判断当前填充结果是否符合条件
if (getif(jz)){
count++;
}
return;
}
//遍历行的所有符合条件可能
for (int j = 0; j < z.size(); j++) {
//设置当前行为当前可能性
ArrayList zc = new ArrayList();
zc = z.get(j);
for (int k = 0; k < jz[i].length; k++) {
jz[i][k] = zc.get(k);
}
//当前行装完可能性后 装下一行
examine(i+1,jz);
// //清除当前行为空
// for (int k = 0; k < jz[i].length; k++) {
// jz[i][k] = 0;
// }
}
}
//判断当前填充结果是否符合条件
public static boolean getif(int [][]jz){
//遍历
for (int i = 0; i < jz.length; i++) {
for (int j = 0; j < jz[i].length; j++) {
//判断当前格子向右
if (j+2 arr){
if (arr.size()>=y){
ArrayList temp = new ArrayList();
temp.addAll(arr);
//检查是否符合条件
int sign = 0;
for (int j = 0;j



