倒计时4
一、 加法变乘法
我们都知道:1+2+3+ … + 49 = 1225。现在要求你把其中两个不相邻的加号变成乘号,使得结果为2015
比如:
1+2+3+…+1011+12+…+2728+29+…+49 = 2015 就是符合要求的答案。
请你寻找另外一个可能的答案,并把位置靠前的那个乘号左边的数字提交(对于示例,就是提交10)。
思路:(其实是在很久之前看的另一个博主的思路)如果按照每个数来,会很麻烦。就换个视角,直接去看符号。遍历符号的位置,进行计算就可以
package lijie_15;
/**
* */
public class G {
public static void main(String[] args) {
for(int i=0;i<46;i++){
for(int j=i+2;j<48;j++){
int sum=1225;
sum-=((i+1)+(i+2));
sum-=((j+1)+(j+2));
sum+=((i+1)*(i+2));
sum+=((j+1)*(j+2));
if(sum==2015){
// System.out.println((i+1)+","+(j+1)+","+sum);
if((i+1)!=10){
System.out.println((i+1));
}
}
}
}
}
}
二、牌型种数
小明被劫持到X赌城,*与其他3人玩牌。
一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。
这时,小明脑子里突然冒出一个问题:
如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?
请填写该整数,不要填写任何多余的内容或说明文字。
思路:我本来想的是 52张牌全排列,我只取前12张,看看有多少种前十二张。反正是个结果填空,时间也没要求…结果,三分钟还没运行完…那我换个暴力法吧…其实也就是换个视觉,换个出发点。一共十三种牌,一种牌可取0,1,2,3,4,。那就13个for,看最终凑出来的,够不够13张
1.我的巨费时答案
package lijie_15;
import java.util.ArrayList;
import java.util.TreeMap;
public class H {
static TreeMap<Integer, ArrayList> tm=new TreeMap<Integer, ArrayList>();
static int len=0;
public static void main(String[] args) {
int []num=new int[52];
for(int i=0;i<52;i++){
num[i]=(i/4)+1;
}
demo(num,0,51);
System.out.println(tm.size());
}
public static int demo(int []num,int start,int end){
if(start==end){
ArrayList<Integer> al=new ArrayList<Integer>();
for(int i=0;i<13;i++){
al.add(num[i]);
}
// System.out.println(al);
tm.put(len, al);
return num[12];
}
for(int i=start;i<end;i++){
swap(num, i, start);
// System.out.println(start+1+"**");
int t=demo(num,start+1,end);
swap(num, i, start);
if(t==num[12]){
// return t;
}else{
return t;
}
}
return 0;
}
public static void swap(int []num,int i,int j){
int t=num[i];
num[i]=num[j];
num[j]=t;
}
}
2.正确答案
package lijie_15;
public class H_right {
public static void main(String[] args) {
int sum=0;
for(int a=0; a<=4; a++)
for(int b=0; b<=4; b++)
for(int c=0; c<=4; c++)
for(int d=0; d<=4; d++)
for(int e=0; e<=4; e++)
for(int f=0; f<=4; f++)
for(int g=0; g<=4; g++)
for(int h=0; h<=4; h++)
for(int i=0; i<=4; i++)
for(int j=0; j<=4; j++)
for(int k=0; k<=4; k++)
for(int l=0; l<=4; l++)
for(int m=0; m<=4; m++)
{
if(a+b+c+d+e+f+g+h+i+j+k+l+m==13)
sum++;
}
System.out.println(sum);
}
}
三、垒骰子
赌圣atm晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。
经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥!
我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。
假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多,请输出模 10^9 + 7 的结果。
不要小看了 atm 的骰子数量哦~
「输入格式」
第一行两个整数 n m
n表示骰子数目
接下来 m 行,每行两个整数 a b ,表示 a 和 b 不能紧贴在一起。
「输出格式」
一行一个数,表示答案模 10^9 + 7 的结果。
「样例输入」
2 1
1 2
「样例输出」
544
「数据范围」
对于 30% 的数据:n <= 5
对于 60% 的数据:n <= 100
对于 100% 的数据:0 < n <= 10^9, m <= 36
思路:我的第一反应是以1-6分别作底,就可以得到最上的面。对于第二个骰子,再分别以1-6作底,检查与上一个符不符合。如果符合就继续。但是数据量太大了…
附两个博主的文,第一个看代码(因为有矩阵快速幂的模板),第二个看思路
复制思路如下:
1.矩阵快速幂
先了解以下快速幂,假如我们要求x^21 的值,普通方法直接xxxxxx…x,这样做了20次乘法。如果使用快速幂方法,21=16+4+1 , x^21 =x^16 * x^4 * x。 我们可以先算x^2 ,再算 x^4 ,再算 x^8 ,再算x^16 ,这样一共做了3次乘法 ,再将x^21 算出来需要再做3次乘法,总共6次乘法,相比于直接运算节省了不少时间。
快速幂代码:
private static int pow(int x,int n) //求x的n次幂
{
int ans = 1;
int pos = x;
while(n!=0)
{
if((1&n)==1)
{
ans = ans * pos;
}
pos = pos*pos;
n >>=1;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
对于矩阵快速幂,只需要把初始的ans=1换成单位矩阵即可,代码如下:
private static Matrix pow(Matrix T,int n) //求矩阵T(方阵)的n次幂
{
Matrix ans = new Matrix(T.m,T.m);
for(int i=0;i<T.m;i++)
for(int j=0;j<T.m;j++)
{
if(i==j)
ans.ma[i][j]=1;
else ans.ma[i][j]=0;
} //建立一个单位阵
while(n!=0)
{
if((1&n)==1)
{
ans = mul(ans,T);
}
T = mul(T,T);
n >>=1;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
矩阵快速幂一般可以用于求矩阵的等比递推式,对于这个题,我们首先需要从题目分析出递推关系。
显然,在垒骰子的过程中,前n个的骰子的垒法是和前n-1个骰子的垒法密切相关的,且和第n-1的骰子朝上面的数字也相关的,这样我们可以得到一个二维的状态转移方程,设d[i][j]表示第i个骰子j面朝上的垒法,则d[i][j]=d[i-1][1]+d[i-1][2]+…+d[i-1][6].
且d[1][j]=1+1+1+1+1+1.可以用一个列向量矩阵Ai来表示d.
现在考虑面的互斥问题,某些面之间是不能贴在一起放的,同样可以用一个66的矩阵T来表示这个互斥关系,Tij表示第i面和第j面互斥。于是可以得到矩阵递推关系,A2=TA1 , A3=TA2 , … ,An=TAn-1
所以An = T^n-1 * A1 ,利用矩阵快速幂求出T^n-1 即可。
复制代码如下:
package lijie_15;
import java.util.Scanner;
public class J {
static final double MOD = 10e9-7;
static int[][] arr = new int[6][6];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
/**
* 初始化arr数组
* */
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
arr[i][j] = 1;
}
}
for (int i = 0; i < m; i++) {
int a = input.nextInt();
int b = input.nextInt();
arr[a-1][b-1] = 0;
arr[b-1][a-1] = 0;
}
int[][] ans = pow(arr, n-1);
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
System.out.print(ans[i][j]+" ");
}
System.out.println();
}
int sum = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
sum += ans[i][j]%MOD;
}
}
/**
* 旋转情况 4^n
* */
sum *= Math.pow(4, n)%MOD;
System.out.println((int)(sum%MOD));
}
private static int[][] pow(int[][] arr, int k) {
/**
* 初始化单位矩阵
* */
int[][] ans = new int[6][6];
for (int i = 0; i < 6; i++) {
ans[i][i] = 1;
}
/**
* 矩阵快速幂核心算法
* */
while (k != 0) {
if (k % 2 != 0) {
ans = Multiply(arr, ans);
} else {
arr = Multiply(arr, arr);
}
k >>= 1;
}
return ans;
}
private static int[][] Multiply(int[][] m, int[][] n) {
// 标准计算矩阵乘法算法
int rows = m.length;
int cols = n[0].length;
int[][] r = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int k = 0; k < m[i].length; k++) {
r[i][j] += (m[i][k] * n[k][j])%MOD;
}
}
}
return r;
}
}
四、标题:五星填数
如【图1.png】的五星图案节点填上数字:1~12,除去7和11。
要求每条直线上数字和相等。如图就是恰当的填法。请你利用计算机搜索所有可能的填法有多少种。注意:旋转或镜像后相同的算同一种填法。请提交表示方案数目的整数,不要填写任何其它内容。
思路:我是打算走一步看一步的。首先全排列,判断各个直线的和是否相等。然后发现每个位置的最后一个都是12。那就不存在旋转或镜像了…
package lijie_16_1;
public class B_2 {
static int res=0;
public static void main(String[] args) {
int []num={1,2,3,4,5,6,8,9,10,12};
demo(num, 0, 9);
System.out.println(res);
}
public static void demo(int []num,int start,int end){
if(start==end){
if(check(num)){
int nn=num[0]+num[3]+num[8]+num[9];
// for(int i=0;i<num.length;i++){
//
// System.out.print(num[i]+" ");
// }
// System.out.println(nn);
res++;
}
}
for(int i=start;i<end;i++){
swap(num, i, start);
demo(num,start+1,end);
swap(num, i, start);
}
}
public static void swap(int []num,int i,int j){
int t=num[i];
num[i]=num[j];
num[j]=t;
}
public static boolean check(int []num){
int a=num[0]+num[3]+num[8]+num[9];
int b=num[0]+num[4]+num[5]+num[6];
int c=num[1]+num[2]+num[3]+num[4];
int d=num[1]+num[5]+num[7]+num[9];
int e=num[2]+num[6]+num[7]+num[8];
if(a==b&&b==c&&c==d&&d==e){
return true;
}
return false;
}
}
五、穿越雷区
X星的坦克战车很奇怪,它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转,否则将报废。
某坦克需要从A区到B区去(A,B区本身是安全区,没有正能量或负能量特征),怎样走才能路径最短?
已知的地图是一个方阵,上面用字母标出了A,B区,其它区都标了正号或负号分别表示正负能量辐射区。
例如:
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求:
输入第一行是一个整数n,表示方阵的大小, 4<=n<100
接下来是n行,每行有n个数据,可能是A,B,+,-中的某一个,中间用空格分开。
A,B都只出现一次。
要求输出一个整数,表示坦克从A区到B区的最少移动步数。
如果没有方案,则输出-1
例如:
用户输入:
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
则程序应该输出:
10
资源约定:
峰值内存消耗(含虚拟机) < 512M
思路:从(i,j)开始,每一步都有四个选择,左右上下。选择完毕,进行下一位置
import java.util.Scanner;
public class Main {
// 代表四个方向
private static final int[][] dir = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
private static int minVal = Integer.MAX_VALUE;
private static int count = 0;
private static char[][] modelArr = null;// 作为模板,回溯还原格局用
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int line = Integer.parseInt(scanner.nextLine());
int x = 0, y = 0;
modelArr = new char[line][line];
char[][] newArr = new char[line][line];
for (int i = 0; i < line; i++) {
char[] chArr = scanner.nextLine().toCharArray();
for (int j = 0; j < chArr.length; j += 2) {
int idx = j / 2;
char ch = chArr[j];
modelArr[i][idx] = newArr[i][idx] = ch;
if (ch == 'A') {
x = i;
y = idx;
}
}
}
// System.out.println(x+","+y);
// print(newArr);
long t = System.currentTimeMillis();
dfs(newArr, x, y);
System.out.println(minVal);
System.out.println("耗时:" + (System.currentTimeMillis() - t));
}
/**
* 深搜+回溯
*
* @param localArr
* @param x
* @param y
*/
private static void dfs(char[][] localArr, int x, int y) {
for (int i = 0; i < dir.length; i++) {
int offsetX = x + dir[i][0];
int offsetY = y + dir[i][1];
// 判断越界,如果越界,走另一个方向
if (offsetX >= 0 && offsetX < localArr[0].length && offsetY >= 0 && offsetY < localArr.length) {
if (localArr[x][y] == 'B') {
if (count < minVal)
minVal = count;
// print(localArr);
count--;
return;
}
if (canWalk(localArr, x, y, offsetX, offsetY)) {
localArr[x][y] = '0';// 访问过的就标记为0
count++;
dfs(localArr, offsetX, offsetY);
localArr[x][y] = modelArr[x][y];// 回溯还原,写在这里就显得很重要,每返回就还原
}
}
}
count--;
}
/**
* 打印数组,测试用
*
* @param localArr
*/
private static void print(char[][] localArr) {
for (int i = 0; i < localArr.length; i++) {
for (int j = 0; j < localArr[i].length; j++) {
System.out.print(localArr[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
/**
* 判断是否下一个方向可走
*
* @param newArr
* @param x1
* 现在的位置
* @param y1
* @param x2
* 下个方向
* @param y2
* @return
*/
private static boolean canWalk(char[][] newArr, int x1, int y1, int x2, int y2) {
return (newArr[x1][y1] != newArr[x2][y2]) && (newArr[x2][y2] != '0');
}
}