2015蓝桥杯真题
15省7-牌型种数 小明被劫持到X赌城，被迫与其他3人玩牌。 一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 这时，小明脑子里突然冒出一个问题： 如果不考虑花色，只考虑点数，也不考虑自己得排后的先后顺序，自己手里能拿到的初始牌型组合一共多少种？
思路：这根本就是一道高中排列组合的题，可能感觉很烦，但是多想一想也就有了思路。一个人13张牌，不考虑花色，那就有13种牌型：A、1、2、3、4、5、6、7、8、9、10、J、Q、K。因为一个人13张牌，可以思考对于这13张牌，其中A,1,2,3,....J,Q,K各占多少张。一种牌型，例如A可以有0张，或者4张，其它的牌型同理，最终一个人的总的牌数量等于13张。所以可以用暴力求解的办法来做，每种牌型一个for循环，依次嵌套，它们可以有0张到4张。
1 public static void main(String args[]) { 2 int num = 0; 3 int[] a=new int[13]; 4 for(a[0]=0;a[0]<=4;a[0]++){ 5 for(a[1]=0;a[1]<=4;a[1]++){ 6 for(a[2]=0;a[2]<=4;a[2]++){ 7 for(a[3]=0;a[3]<=4;a[3]++){ 8 for(a[4]=0;a[4]<=4;a[4]++){ 9 for(a[5]=0;a[5]<=4;a[5]++){ 10 for(a[6]=0;a[6]<=4;a[6]++){ 11 for(a[7]=0;a[7]<=4;a[7]++){ 12 for(a[8]=0;a[8]<=4;a[8]++){ 13 for(a[9]=0;a[9]<=4;a[9]++){ 14 for(a[10]=0;a[10]<=4;a[10]++){ 15 for(a[11]=0;a[11]<=4;a[11]++){ 16 for(a[12]=0;a[12]<=4;a[12]++){ 17 if(a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]==13){ 18 num++; 19 } 20 } 21 } 22 } 23 } 24 } 25 } 26 } 27 } 28 } 29 } 30 } 31 } 32 } 33 System.out.println(num); 34 }
输出一行，包含一个实数，四舍五入保留小数点后7位，表示圆的面积。
说明：在本题中，输入是一个整数，但是输出是一个实数。
对于实数输出的问题，请一定看清楚实数输出的要求，比如本题中要求保留小数点后7位，则你的程序必须严格的输出7位小数，输出过多或者过少的小数位数都是不行的，都会被认为错误。
实数输出的问题如果没有特别说明，舍入都是按四舍五入进行。
这个题和以前C语言的题不一样，C语言需要的是return，蓝桥杯只需要打印出来就行。
而printf函数的(%.f)机制就可以进行按照多少位自动四舍五入，或者用String.format方法也能够四舍五入。
String.format可以改变原来的数，返回处理后的结果
public class Main {
public static void main(String args[]){
NumberFormat formatter = NumberFormat.getNumberInstance();
formatter.setMaximumFractionDigits(18);
Scanner scan=new Scanner(System.in);
int r = scan.nextInt();
double s=r*r*(Math.PI);
String result=String.format("%.7f", s);
// System.out.printf("%.7f",s);//方法一
System.out.printf(result);//方法二
}
}
试题 基础练习 分解质因数
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
//java中静态方法不能调用非静态方法。
public class Main {
public static void main(String [] args){
for (int i = 3; i < 10; i++) {
decompose(i);
System.out.println();
}
}
//因数分解函数
private static void decompose(int n)
{
System.out.print(n+"=");
for(int i=2;i<=n;i++)
{
while (n%i==0&&n!=i)
{
n/=i;//能够除尽，并且不是本身，继续除
System.out.print(i+"*");//并且输出当前的i
}
if(n==i){
System.out.print(i);//输出最后一位
break;
}
}
}
}
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
第二行是一个字符串，长度为N.只包含小写字母
否则输出Impossible
public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); String s=scan.next(); int end=n-1; char[] arr=s.toCharArray(); int cnt=0;//交换次数 int oddNum=0;//判断是否有一个单独的奇个数字符 for (int i = 0; i < end; i++) {//从第一个字符到倒数第二个字符的遍历 for (int j = end; j >=i ; j--) {//从最后一个字符到第i个字符，寻找与s[i]相同的字符 if(i==j){//如果没找到 if(n%2==0||oddNum==1){//输出impossible的情况 odd已经有一个为奇数次数了，当n为偶数时只要出现一个奇数词 System.out.println("Impossible"); return; } oddNum++; cnt+=n/2-i;//将该单字符交换到中间位置的次数 }else if(arr[i]==arr[j]){//找到了的情况 for (int j2 = j; j2 < end; j2++) { char temp=arr[j2]; arr[j2]=arr[j2+1]; arr[j2+1]=temp; cnt++; } end--; break; } } } System.out.println(cnt); } }
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出一个整数，表示大臣J最多花费的路费是多少。
1 2 2
1 3 1
2 4 5
2 5 4
public class Main {
static int n;
static int max=0;
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
n=sca.nextInt();
int[][] field=new int[n][n];
for (int i = 0; i < n-1; i++) {
int temp1=sca.nextInt();
int temp2=sca.nextInt();
int temp3=sca.nextInt();
field[temp1-1][temp2-1]=temp3;
field[temp2-1][temp1-1]=temp3;
}
int MAX=0;
for (int i = 0; i < n; i++) {
int max1=0;
int max2=0;
boolean[][] flag= new boolean[n][n];
for (int j = i; j < n; j++) {
if (i!=j&&field[i][j]!=0&&field[j][i]!=0) {
max = 0;
flag[i][j] = true;
flag[j][i] = true;
dfs(field, i, j, flag, 0);
max1 = max;
max = 0;
flag[j][i] = true;
flag[i][j] = true;
dfs(field, j, i, flag, 0);
max2 = max;
int temp = 0;
if (max1 > max2) {
temp = max1;
} else {
temp = max2;
}
if (temp > MAX) {
MAX = temp;
}
}
}
}
int d=11;
int i = 0;
int sumAll=0;
for (int j = 0; j < MAX; j++) {
sumAll+=d;
d++;
}
System.out.println(sumAll);
}
static void dfs(int[][] field,int x,int y,boolean[][] flag,int sum)
{
sum+=field[x][y]; //访问到当前节点将到sum计算路程长度
if(sum>max){//如果当前路径大于最大路径则更改当前路径
max=sum;
}
for (int i = 0; i < n; i++) {
if(field[y][i]!=0&&flag[y][i]==false){ //进行遍历，因为是深度搜索那么如果传入的x是1，y是2那么下一次只能遍历，以2这个节点开始的其他节点。进行遍历。判断的if语句为需要走的路径存在也就是field[y][i]不为空。这里就没有考虑对角线的元素，因为对角线自己到自己肯定为0。并且判断flag数组当前该节点是否被访问过，如果没访问过，则为真。满足以上两个条件则可以进行遍历下一个城市。
flag[y][i]=true;//把下一个这个城市flag置为真代表访问过。
flag[i][y]=true;//采用的二维数组，对称矩阵 无向图 所以需要把两个地方的状态都改变。
dfs(field,y,i,flag,sum);//将下一个这个城市进行递归 遍历它的周围
flag[i][y]=false;//回溯将当前这个点 置为false;
flag[y][i]=false;
}
}//访问不动了直接return .
return;
}
}
该题没做到100分，最后一个数据10000条，超时，但是答案跑了20分钟是对的。可以继续优化一些判断条件，减少递归次数。
快速幂取模算法
蓝桥杯中，有很多的时候都会用到取余运算，如斐波拉契数列的余数等题。思路很容易就能想到，但是会出现一个问题就是出现结果超精度范围的问题，所以需要缩小每次的结果，对每次的结果进行求余再进行求和运算等操作。
最近发现了如公式(a+b)%c=(a%c+b%c)%c=(a%c+b)%c等。并且发现乘法也能成立，(a * b) % c = [ (a % c) * ( b % c) ] % c，所以在遇到这些情况，需要及时考虑是否能用这些方法缩小运算结果。
这个题就会用到乘法(a * b) % c = [ (a % c) * ( b % c) ] % c公式的深化，快速幂取模算法。
原博客：快速幂取模算法
所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。我们先从简单的例子入手：求abmodc
int ans = 1;
for(int i = 1;i<=b;i++)
{
ans = ans * a;
}
ans = ans % c;
缺点：这个算法存在着明显的问题，如果a和b过大，很容易就会溢出。
我们先来看看第一个改进方案：在讲这个方案之前，要先看这样一个公式：ab mod c = (a mod c)c mod c
于是不用思考的进行了改进：
既然某个因子取余之后相乘再取余保持余数不变，那么新算得的ans也可以进行取余
int ans = 1;
a = a % c; //加上这一句
for(int i = 1;i<=b;i++)
{
ans = ans * a;
}
ans = ans % c;
快速幂算法：
快速幂算法依赖于以下明显的公式：
int PowerMod(int a, int b, int c)
{
int ans = 1;
a = a % c;
while(b>0) {
if(b % 2 = = 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
return ans;
}
可以看到指数b是按照根号2倍缩小，所以运算较少了很多次，时间复杂度很好。
试题 历届试题 小数第n位
该题会遇到数论的知识：x/d%m = x%(d*m)/d。
第 n 位的后三位，也就是第 n ------ n + 2 位，把第 n + 2 位(含)之前的部分变成整数，再%1000就是我们要的三位数答案，最小的位是第 n + 2 位，想把它变成整数的个位，需要 乘 10n+2 ，也就是 a / b * 10n+2 % 1000 即为答案，因为 n 的范围可能很大，所以就需要用快速幂取模算法 。
可见就是简单的求逆元！但是由于模的是1000，不是素数，不能使用费马小定理和扩展欧几里得来求逆元。需要用下面的公式：
x/d%m = x%(d*m)/d
对应前式，x = a * 10n+2 ，d = b，m = 1000
这样这道题就变成了
[ a * 10 n+2 % (b * 1000) ] / b (式1)
又有公式：
(a * b) % c = [ (a % c) * ( b % c) ] % c
所以式1中的 [ a * 10 n+2 % (b * 1000) ] 部分可以转换为
[ a % (b * 1000) ] * [ 10n+2 % (b * 1000) ] % (b * 1000)
而 [ 10n+2 % (b * 1000) ] 可以通过快速幂取模运算直接求出，代码中用 res 表示
import java.util.Map;
//java中静态方法不能调用非静态方法。
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int n = sc.nextInt();
sc.close();
long mod = b * 1000;
long res = qPow(10, n + 2, mod);
long tem = (a % mod * res) % mod;
System.out.println(String.format("%03d", tem / b));//3位整数形式，不足3位补0
}
public static long qPow(long a, long b, long c) {
long res = 1;
long prod = a;
while(b > 0) {//用的位运算。
if((b & 1) == 1) res = (res * prod) % c;//快速幂 公式。
prod = (prod * prod) % c;
b >>= 1;
}
return res;
}
}
RSA解密
需要用到正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
分析：从1到N先找出最小的质因数，如果等于本身，那么说明只有一个质因数，如果不是，那么将该质因数打印出来，并将N/该质因数作为新的N值进行运算
public class Main {
public static void main(String[] args) {
long res=1001733993063167141L;
for(int i = 2;i<=res;i++){//符合第三步
if(res%i==0&&res!=i){//n能够被k整除，并且n不等于k 符合第二步
System.out.println(i);
res=res/i;
}
if(res==i){//符合第一步打印
System.out.println(i);
break;
}
}
}
public class Main {
public static void main(String[] args) {
String a=String.format("%.5f", 0.123125);//保留五位小数
String b=String.format("%.4f", 0.12346);//保留四位小数
String c=String.format("%.3f", 0.1234);//保留三位小数
String d=String.format("%.2f", 0.129);
String e=String.format("%.1f", 0.18);
System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(d);
System.out.println(e);
}
}
结果输出：
0.12313
0.1235
0.123
0.13
0.2