蓝桥杯题目汇编

文章目录

题目汇编

前言最长子段和

题目

题目描述输入格式输出格式输入输出样例说明/提示

样例 1 解释数据规模与约定题解

1.使用前缀和

什么是前缀和？c++代码-王宇哲二叉树的右视图

题目题解

1.广度（宽度）优先搜索

思路Java代码-谭方川c++代码 2.深度优先搜索

思路c++代码蓝桥杯算法提高递归

资源限制问题描述输入格式输出格式样例输入样例输出数据规模和约定题解

c++代码-耿莉芳第六届蓝桥杯真题-垒骰子

题目

输入格式输出格式数据范围输入样例：输出样例：题解第六届蓝桥杯真题-生命之树

题目

输入格式输出格式数据范围输入样例：输出样例：题解蓝桥杯算法训练-数字三角形

题目

资源限制问题描述输入格式输出格式样例输入样例输出题解

java代码-杨奕c++代码-王宇哲蓝桥杯历届试题-数字三角形

题目

问题描述输入格式输出格式样例输入样例输出题解

c++代码-王宇哲，谭琦java代码-杨奕蓝桥杯算法提高-组合数

题目

资源限制问题描述输入格式输出格式样例输入样例输出数据规模和约定题解

c++代码-谭琦蓝桥杯第十届真题年号字串

题目题解

c++代码-王宇哲蓝桥杯第十届真题迷宫

题目

题目描述输入地图题解

c++代码-王宇哲java代码-谭方川蓝桥杯第十届真题等差数列

题目

题目描述输入格式输出格式数据范围输入样例：输出样例：样例解释题解辗转相除法辗转相减法

基本方法：c++代码-王宇哲蓝桥杯第十届真题后缀表达式

题目

题目描述输入格式输出格式数据范围输入样例：输出样例：题解

分类讨论：

第一种：全是正数第二种：全是负数第三种：有负有正总结 java代码-谭方川c++代码-王宇哲蓝桥杯第十届真题灵能传输（压轴题）

题目

输入格式输出格式数据范围输入样例1：输出样例1：输入样例2：输出样例2：样例解释题解

第一种情况第二种情况第三种 c++代码-王宇哲蓝桥杯第十一届真题子串分值和

题目

输入格式输出格式数据范围输入样例：输出样例：样例解释题解

思路 c++代码-王宇哲蓝桥杯第九届真题测试次数

题目

输入格式输出格式数据范围输入样例1：输出样例1：样例1解释输入样例2：输出样例2：样例2解释题解

~~四层楼~~~~五层楼~~~~六层楼：~~~~七层楼~~~~八层楼~~ 解法1-数学问题

网上题解转化过程只有一个手机有两个手机有三部手机 c++代码解法2-递推

c++代码解法3-动态规划解释一下用Max函数和Min函数：

c++代码历届试题九宫幻方

题目

资源限制问题描述输入格式输出格式样例输入样例输出数据规模和约定题解

思路一

c++代码-杨作青c++代码-谭琦（改）思路二

c++代码-王宇哲总结参与贡献

题目汇编前言

以下题解均为我个人对代码作者思路的解读，可能有所偏差

如有错误或不明白的地方，可以私聊我更改

同时欢迎各位主动提供代码

最长子段和

来自20044王宇哲

题目题目描述

给出一个长度为 n n n 的序列 a a a ，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n n n 。

第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

说明/提示样例 1 解释

选取$ [3, 5]$ 子段 { 3 , − 1 , 2 } {3, -1, 2} {3,−1,2}，其和为 44。

数据规模与约定

对于 40 % 40% 40%的数据，保证 n ≤ 2 × 1 0 3 n leq 2 times 10^3 n≤2×103。对于 100%100% 的数据，保证$ 1 leq n leq 2 times 10^5$，$-104 leq a_i leq 10^4$。题解 1.使用前缀和什么是前缀和？

我们学过数列就一定知道， a n = S n − S n − 1 a_n=S_n-S_{n-1} an=Sn−Sn−1

同样的， a n + a n − 1 + . . . + a k = S n − S k − 1 a_n+a_{n-1}+...+a_k=S_n-S_{k-1} an+an−1+...+ak=Sn−Sk−1

这就是前缀和了，我们可以在输入的时候存储 S n S_n Sn的值，以便快速查找出来一段区间内的数列和，这样我们可以把时间复杂度由 O ( N ) O(N) O(N)减小到 O ( 1 ) O(1) O(1)

这就是前缀和了，使用前缀和可以快速的求出一段区间以内的数的和

c++代码-王宇哲

#include
using namespace std;
int  main(){
	int s[200005]={0};	//数列和
	int a[200005]={0};	//原数列
	int b[200005]={0}; 	//存储子段和
	int max1=-99999;	//存储字段和最大值
	int n;	//存储主段长度
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];//输入数列	
		s[i]=a[i]+s[i-1];	//数列和
	}
	b[1]=a[1];	//第一个1-1这个段中最小的子段当然是它本身
	int min1=min(0,s[1]);	//判断数列s0和s1哪个小，取小的
	for(int i=2;i<=n;i++){	//循环寻找0-i的串中的最大和子串
		b[i]=s[i]-min1;	
		min1=min(min1,s[i]);	//子串最大那么肯定第一个前缀和最小，寻找s[i+1]前面的最小的子串和
	}
	for(int i=1;i<=n;i++){
		max1=max(max1,b[i]);	//寻找最小子段和
	}
	cout< 
二叉树的右视图 
 
 来自18541谭方川 
 注：以下代码在洛谷有效，不能直接运行，需要自己编写主函数进行测试 
 
题目 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V1jaOBSS-1644222130862)(image/image-20210321200104486.png)] 
题解 
1.广度（宽度）优先搜索 
思路 
 
 从根节点开始向下遍历,首先将当前深度的所有结点数目存好（
     
      
       
        
         l
        
        
         e
        
        
         n
        
       
       
        len
       
      
     len），将同一深度的结点的左子节点和右子节点全部放入队列之中为下一次遍历做准备，找到队列中最后一个元素（第
     
      
       
        
         l
        
        
         e
        
        
         n
        
       
       
        len
       
      
     len个）并将其结果放入最后结果的列表之中，每一层的第
     
      
       
        
         l
        
        
         e
        
        
         n
        
       
       
        len
       
      
     len个结点（
     
      
       
        
         l
        
        
         e
        
        
         n
        
       
       
        len
       
      
     len不固定）就是所有的最右节点 
 
Java代码-谭方川 
static class TreeNode {	//自定义静态类
    int val;	
    TreeNode left;	//指向该树左边的树
    TreeNode right;	//指向该树右边的树
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;	//赋值给类成员变量val
    }
    TreeNode(int val, TreeNode left, TreeNode right) {	//传入当前结点的值和其左节点与右节点
        this.val = val;	//赋值给类成员变量val
        this.right = right;	//赋值给类成员变量right
    }
}
/上面是力扣给出的数据类型定义
public List rightSideView(TreeNode root) {	//传入的root为树的根节点
    List res = new linkedList<>();	//定义列表为一个新的链表
    if (root == null) {	//如果树的根节点为空
        return res;		//直接返回空列表
    }
    Queue queue = new linkedList<>();	//定义一个新队列
    queue.add(root);	//将根结点放入队列
    while (queue.size() > 0) { //队列不为空
       	//遍历方法为广度优先遍历，即层层搜索最右结点
        int len = queue.size();	//获取队列长度len
        for (int i = 0; i < len; i++) {	
            TreeNode node = queue.poll();	//将队列队首元素拿出
            if (node.left != null) {	//如果队首的那个结点存在左子节点，那就将左节点先放入队首
                queue.offer(node.left);	
            }
            if (node.right != null) {	//如果队首的那个结点存在右子节点，那就将右节点先放入队首
                queue.offer(node.right);	//在队尾插入该节点的右节点
            }
            if (i == len - 1) {	//如果遍历到最后一个，说明这是最右边的叶结点，就放入结果的列表中
                res.add(node.val);
            }
        }
    }
    return res;
}
 
c++代码 
class Solution {
public:
    vector rightSideView(TreeNode* root) {
        int max_depth = -1;
        vector b;
        if(root==NULL){
            return b;
        }
        queue queue;
        queue.push(root);
       
        while (!queue.empty()) {
            int len = queue.size();
            for(int i=0;ileft != NULL) {	
                    queue.push(node->left);	
                }
                if (node->right != NULL) {	
                    queue.push(node->right);	
                }
                if(len-1==i){
                    b.push_back(node->val);
                }
            }
        }
        return b;
    }
};
 
2.深度优先搜索 
思路 
 
 从根节点开始，深度优先搜索访问每一个结点（先右后左地访问），如果当前访问的结点的深度depth不等于队列的长度（也就是同一深度还没有结点被访问过），而他又是从右往左数当前深度的第一个结点，所以将它入队 
 代码来自洛谷题解（主要懒得自己再写了） 
 
c++代码 
class Solution {
public:
    vector rightSideView(TreeNode* root) {
        unordered_map rightmostValueAtDepth;
        int max_depth = -1;

        stack nodeStack;
        stack depthStack;
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode* node = nodeStack.top();nodeStack.pop();
            int depth = depthStack.top();depthStack.pop();

            if (node != NULL) {
            	// 维护二叉树的最大深度
                max_depth = max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {
                    rightmostValueAtDepth[depth] =  node -> val;
                }

                nodeStack.push(node -> left);
                nodeStack.push(node -> right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        vector rightView;
        for (int depth = 0; depth <= max_depth; ++depth) {
            rightView.push_back(rightmostValueAtDepth[depth]);
        }

        return rightView;
    }
};
 
蓝桥杯 算法提高 递归 
 
 来自19043 耿莉芳 
 
资源限制 
时间限制：
    
     
      
       
        1.0
       
       
        s
       
      
      
       1.0s
      
     
    1.0s 内存限制：
    
     
      
       
        256.0
       
       
        M
       
       
        B
       
      
      
       256.0MB
      
     
    256.0MB 
问题描述 
当x>1时，Hermite多项式的定义见第二版教材125页。用户输入x和n，试编写“递归”函数，输出对应的Hermite多项式的值。其中x为float型，n为int型。 
输入格式 
x n 
输出格式 
对应多项式的值 
样例输入 
一个满足题目要求的输入范例。
 例： 
1.8 7
 
样例输出 
与上面的样例输入对应的输出。
 例： 
-987.857
 
数据规模和约定 
 
 x>1
 　　n为自然数 
 
题解 
 
 网上百度出来的Hermite函数挺恐怖的。。。。 
 其实就是递归：
 
      
       
        
         
          
           H
          
          
           n
          
         
         
          (
         
         
          x
         
         
          )
         
         
          =
         
         
          2
         
         
          ∗
         
         
          x
         
         
          ∗
         
         
          
           H
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          2
         
         
          ∗
         
         
          (
         
         
          n
         
         
          −
         
         
          1
         
         
          )
         
         
          ∗
         
         
          
           H
          
          
           
            n
           
           
            −
           
           
            2
           
          
         
         
         
          
           H
          
          
           1
          
         
         
          (
         
         
          x
         
         
          )
         
         
          =
         
         
          1
         
         
          ;
         
         
         
          
           H
          
          
           2
          
         
         
          (
         
         
          x
         
         
          )
         
         
          =
         
         
          2
         
         
          ∗
         
         
          x
         
        
        
          H_n(x)=2*x*H_{n-1}-2*(n-1)*H_{n-2} \ H_1(x)=1; \ H_2(x)=2*x 
        
       
      Hn(x)=2∗x∗Hn−1−2∗(n−1)∗Hn−2H1(x)=1;H2(x)=2∗x 
 
c++代码-耿莉芳 
#include
using namespace std;
float Hermite(float x,int n){
    if(n==0){
        return 1;
    }
    if(n==1){
        return 2*x;
    }
    return 2*x*Hermite(x,n-1)-2*(n-1)*Hermite(x,n-2);
}
int main(){
	float x;
    int n;
    cin>>x>>n;
    cout< 
第六届蓝桥杯真题-垒骰子 
 
 来自20044王宇哲 
 
题目 
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。 
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！ 
我们先来规范一下骰子：
    
     
      
       
        1
       
      
      
       1
      
     
    1 的对面是 
    
     
      
       
        4
       
      
      
       4
      
     
    4，
    
     
      
       
        2
       
      
      
       2
      
     
    2 的对面是
    
     
      
       
        5
       
      
      
       5
      
     
    5，
    
     
      
       
        3
       
      
      
       3
      
     
    3 的对面是 
    
     
      
       
        6
       
      
      
       6
      
     
    6。 
假设有 
    
     
      
       
        m
       
      
      
       m
      
     
    m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 
atm想计算一下有多少种不同的可能的垒骰子方式。 
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 
由于方案数可能过多，请输出模 
    
     
      
       
        1
       
       
        
         0
        
        
         9
        
       
       
        +
       
       
        7
       
      
      
       10^9+7
      
     
    109+7 的结果。 
输入格式 
第一行包含两个整数 
    
     
      
       
        n
       
       
        ,
       
       
        m
       
      
      
       n,m
      
     
    n,m，分别表示骰子的数目和排斥的组数。 
接下来 
    
     
      
       
        m
       
      
      
       m
      
     
    m 行，每行两个整数 
    
     
      
       
        a
       
       
        ,
       
       
        b
       
      
      
       a,b
      
     
    a,b，表示 
    
     
      
       
        a
       
      
      
       a
      
     
    a 和 
    
     
      
       
        b
       
      
      
       b
      
     
    b 数字不能紧贴在一起。 
输出格式 
共一个数，表示答案模 
    
     
      
       
        1
       
       
        
         0
        
        
         9
        
       
       
        +
       
       
        7
       
      
      
       10^9+7
      
     
    109+7 的结果。 
数据范围 

    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       1≤n≤10^9
      
     
    1≤n≤109, 

    
     
      
       
        1
       
       
        ≤
       
       
        m
       
       
        ≤
       
       
        36
       
      
      
       1≤m≤36
      
     
    1≤m≤36, 

    
     
      
       
        1
       
       
        ≤
       
       
        a
       
       
        ,
       
       
        b
       
       
        ≤
       
       
        6
       
      
      
       1≤a,b≤6
      
     
    1≤a,b≤6 
输入样例： 
2 1
1 2
 
输出样例： 
544
 
题解 
 
 仔细阅读题目，我们不难分析出题目的意思： 
 n个骰子，在某几个面不能相碰的规则下，求出总共有多少种堆积方式？ 
 注：侧面朝向不同也算不同的堆放方式，这是很多人容易忽略的地方 
 大致读完题目以后，我们可以分析出，第
     
      
       
        
         i
        
       
       
        i
       
      
     i个骰子的堆放方式是由第
     
      
       
        
         i
        
        
         −
        
        
         1
        
       
       
        i-1
       
      
     i−1个骰子的排列方式决定的，那么我们应该就能想到一种解题方式：动态规划 
 设
     
      
       
        
         i
        
       
       
        i
       
      
     i为第
     
      
       
        
         i
        
       
       
        i
       
      
     i个骰子，
     
      
       
        
         j
        
       
       
        j
       
      
     j为
     
      
       
        
         j
        
       
       
        j
       
      
     j面朝上，那么
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
       
       
        dp[i][j]
       
      
     dp[i][j]代表的就是第
     
      
       
        
         i
        
       
       
        i
       
      
     i个骰子
     
      
       
        
         j
        
       
       
        j
       
      
     j面朝下的情况，动态转移方程就为
 
      
       
        
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          j
         
         
          ]
         
         
          =
         
         
          4
         
         
          ×
         
         
          
           ∑
          
          
           
            k
           
           
            =
           
           
            1
           
          
          
           6
          
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          −
         
         
          1
         
         
          ]
         
         
          [
         
         
          k
         
         
          ]
         
        
        
          dp[i][j]=4timessumlimits_{k=1}^{6}dp[i-1][k] 
        
       
      dp[i][j]=4×k=1∑6dp[i−1][k]
 解释一下，第
     
      
       
        
         i
        
       
       
        i
       
      
     i个骰子
     
      
       
        
         j
        
       
       
        j
       
      
     j面朝下的情况就是第
     
      
       
        
         i
        
        
         −
        
        
         1
        
       
       
        i-1
       
      
     i−1个骰子从1到6面朝下的情况的和乘以四（因为侧面有四种朝向）,当然前提条件为第
      
       
        
         
          i
         
        
        
         i
        
       
      i个骰子
      
       
        
         
          j
         
        
        
         j
        
       
      j面朝下的情况不与第
      
       
        
         
          i
         
         
          −
         
         
          1
         
        
        
         i-1
        
       
      i−1个骰子
      
       
        
         
          k
         
        
        
         k
        
       
      k面朝下的情况相冲突 
 因为我们输入时是输入的不能相互接触的两个面，其实也就是下面一个骰子的下面与**上面那个骰子的下面的对面（上面）**不能接触，那么我们只需要在输入时处理一下，就可以只考虑两个骰子下面不冲突的情况就行了 
 
好的，那么我们现在就可以直接敲代码了： 
#include
using namespace std;
const long long mod=1e9+7;
int map1[7][7];	//存储排斥关系 
int aside[7]={0,4,5,6,1,2,3};	//存储对面骰子 
int main(){
	int n,m;
	cin>>n>>m;
	long long dp[2][7];	//动态规划 
	memset(dp,0,sizeof(dp)); 
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		map1[x][y]=1;
		map1[y][x]=1;
	}
	for(int j=1;j<=6;j++){
		dp[0][j]=4;
	}
	for(int i=2;i<=n;i++){	//第i层 
		for(int j=1;j<=6;j++){	//尝试j在下的情况 
			for(int z=1;z<=6;z++){	//这时候看看前一层的每一种情况 
				if(map1[aside[z]][j]==0){	//如果前一层这种情况不排斥（z对面的数也就是上个骰子上面的数与当前骰子的下面的数j不排斥） 
					dp[(i-1)%2][j]+=4*(dp[i%2][z])%mod;	
				}
			}
		}
		for(int j=1;j<=6;j++){
			dp[i%2][j]=0;
		}
	}
	long long sum=0;
	for(int i=1;i<=6;i++){
		sum+=dp[(n-1)%2][i]%mod;
	}
	cout< 
 
 这里有个小细节，那就是
     
      
       
        
         d
        
        
         p
        
       
       
        dp
       
      
     dp数组我们只开了2*7的大小，因为防止超空间，我们就得重复使用这个数组 
 很不幸的是，这个方法超时了 
 
 
 现在，我们还得寻求另一种方法来解决超时的问题 
 我们知道，在动态转移方程中，
     
      
       
        
         j
        
       
       
        j
       
      
     j表示的是第
     
      
       
        
         j
        
       
       
        j
       
      
     j面在上，那么第
     
      
       
        
         i
        
       
       
        i
       
      
     i中排列的情况数用矩阵表示就是
 
      
       
        
         
          [
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          1
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          2
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          3
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          4
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          5
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          ]
         
         
          [
         
         
          6
         
         
          ]
         
         
          ]
         
        
        
          [dp[i][1],dp[i][2],dp[i][3],dp[i][4],dp[i][5],dp[i][6]] 
        
       
      [dp[i][1],dp[i][2],dp[i][3],dp[i][4],dp[i][5],dp[i][6]]
 （是的，你没听错，我们就是要使用矩阵来优化算法） 
 而上面这个矩阵是下面这个矩阵得到的
 
      
       
        
         
          
           [
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           1
          
          
           ]
          
          
           ,
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           2
          
          
           ]
          
          
           ,
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           3
          
          
           ]
          
          
           ,
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           4
          
          
           ]
          
          
           ,
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           5
          
          
           ]
          
          
           ,
          
          
           d
          
          
           p
          
          
           [
          
          
           i
          
          
           −
          
          
           1
          
          
           ]
          
          
           [
          
          
           6
          
          
           ]
          
          
           ]
          
         
         
          ×
         
         
          
           [
          
          
           
            
             
              
               
                a
               
               
                11
               
              
             
            
            
             
              
               
                a
               
               
                12
               
              
             
            
            
             
              
               
                a
               
               
                13
               
              
             
            
            
             
              
               
                a
               
               
                14
               
              
             
            
            
             
              
               
                a
               
               
                15
               
              
             
            
            
             
              
               
                a
               
               
                16
               
              
             
            
           
           
            
             
              
               
                a
               
               
                21
               
              
             
            
            
             
              
               
                a
               
               
                22
               
              
             
            
            
             
              
               
                a
               
               
                23
               
              
             
            
            
             
              
               
                a
               
               
                24
               
              
             
            
            
             
              
               
                a
               
               
                25
               
              
             
            
            
             
              
               
                a
               
               
                26
               
              
             
            
           
           
            
             
              
               
                a
               
               
                31
               
              
             
            
            
             
              
               
                a
               
               
                32
               
              
             
            
            
             
              
               
                a
               
               
                33
               
              
             
            
            
             
              
               
                a
               
               
                34
               
              
             
            
            
             
              
               
                a
               
               
                35
               
              
             
            
            
             
              
               
                a
               
               
                36
               
              
             
            
           
           
            
             
              
               
                a
               
               
                41
               
              
             
            
            
             
              
               
                a
               
               
                42
               
              
             
            
            
             
              
               
                a
               
               
                43
               
              
             
            
            
             
              
               
                a
               
               
                44
               
              
             
            
            
             
              
               
                a
               
               
                45
               
              
             
            
            
             
              
               
                a
               
               
                46
               
              
             
            
           
           
            
             
              
               
                a
               
               
                51
               
              
             
            
            
             
              
               
                a
               
               
                52
               
              
             
            
            
             
              
               
                a
               
               
                53
               
              
             
            
            
             
              
               
                a
               
               
                54
               
              
             
            
            
             
              
               
                a
               
               
                55
               
              
             
            
            
             
              
               
                a
               
               
                56
               
              
             
            
           
           
            
             
              
               
                a
               
               
                61
               
              
             
            
            
             
              
               
                a
               
               
                62
               
              
             
            
            
             
              
               
                a
               
               
                63
               
              
             
            
            
             
              
               
                a
               
               
                64
               
              
             
            
            
             
              
               
                a
               
               
                65
               
              
             
            
            
             
              
               
                a
               
               
                66
               
              
             
            
           
          
          
           ]
          
         
        
        
          left[dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5],dp[i-1][6]right]times left[ begin{matrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} &a_{16}\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} &a_{26}\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} &a_{36}\ a_{41} & a_{42} & a_{43} & a_{44} & a_{45} &a_{46}\ a_{51} & a_{52} & a_{53} & a_{54} & a_{55} &a_{56}\ a_{61} & a_{62} & a_{63} & a_{64} & a_{65} &a_{66}\ end{matrix} right] 
        
       
      [dp[i−1][1],dp[i−1][2],dp[i−1][3],dp[i−1][4],dp[i−1][5],dp[i−1][6]]×⎣⎢⎢⎢⎢⎢⎢⎡a11a21a31a41a51a61a12a22a32a42a52a62a13a23a33a43a53a63a14a24a34a44a54a64a15a25a35a45a55a65a16a26a36a46a56a66⎦⎥⎥⎥⎥⎥⎥⎤
 （很恐怖吧，别慌，听我细细道来） 
 左边的矩阵不必多说，就是第
     
      
       
        
         i
        
        
         −
        
        
         1
        
       
       
        i-1
       
      
     i−1层的堆放情况 
 而右边的矩阵的行表示的是第
      
       
        
         
          i
         
         
          −
         
         
          1
         
        
        
         i-1
        
       
      i−1个的朝上的面 
 而右边的矩阵的列表示的是第
      
       
        
         
          i
         
        
        
         i
        
       
      i个的朝上的面 
 每个元素的值就是当前行列所代表的情况能堆放的方式的个数 
 举个例子来说 
 图中的
     
      
       
        
         
          a
         
         
          24
         
        
       
       
        a_{24}
       
      
     a24表示的就是第
     
      
       
        
         i
        
        
         −
        
        
         1
        
       
       
        i-1
       
      
     i−1个骰子2面朝上，第
     
      
       
        
         i
        
       
       
        i
       
      
     i个骰子4面朝上的情况所能成立的方案数 
 
那么问题来了？为什么要用矩阵？这不是更麻烦吗？ 
 
 按常理来说，这样做确实麻烦（而且不会减少时间复杂度） 
 但是！ 
 当我们写成矩阵以后，就能用矩阵幂来计算动态规划方程的值了 
 这又能说明什么？幂？。。。。 
 快速幂？ 
 是的，就是用快速幂，但是这种方式叫做矩阵快速幂，方式跟快速幂差不多，也能将一个
     
      
       
        
         N
        
       
       
        N
       
      
     N的时间复杂度降低到
     
      
       
        
         l
        
        
         n
        
        
         N
        
       
       
        lnN
       
      
     lnN 
 （快速幂是什么？自己看去，我也懒得打字了。。。。） 
 
 
 想要练成矩阵快速幂大法，首先需要学会矩阵乘法： 
 void mul(long long a[7],long long b[7],long long c[7][7]){	
	long long tmp[7]={0}; 
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			tmp[i]=(tmp[i]+b[j]*c[i][j])%mod;
		}
	}
	memcpy(a,tmp,sizeof(tmp));
}
void mul(long long a[7][7],long long b[7][7],long long c[7][7]){
	long long tmp[7][7];
	memset(tmp,0,sizeof(tmp)); 
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			for(int z=1;z<=6;z++){
				tmp[i][j]=(tmp[i][j]+b[i][z]*c[z][j])%mod;
			}
		}
	}
	memcpy(a,tmp,sizeof(tmp));
}
 
 上面的矩阵乘法是1 * 6矩阵乘以6 * 6矩阵 
 下面的矩阵乘法是6 * 6矩阵乘以6 * 6矩阵 
 （运用了c++的特性——函数重载哦） 
 然后接着就是类似快速幂的矩阵快速幂了： 
 while(n){
if(n&1)mul(f1,f1,juzhen);
mul(juzhen,juzhen,juzhen);
n>>=1;
}
 
 
好了，那么完整代码就如下： 
#include
using namespace std;
const long long mod=1e9+7;
void mul(long long a[7],long long b[7],long long c[7][7]){
	long long tmp[7]={0}; 
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			tmp[i]=(tmp[i]+b[j]*c[i][j])%mod;
		}
	}
	memcpy(a,tmp,sizeof(tmp));
}
void mul(long long a[7][7],long long b[7][7],long long c[7][7]){
	long long tmp[7][7];
	memset(tmp,0,sizeof(tmp)); 
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			for(int z=1;z<=6;z++){
				tmp[i][j]=(tmp[i][j]+b[i][z]*c[z][j])%mod;
			}
		}
	}
	memcpy(a,tmp,sizeof(tmp));
}
int main(){
	int op[7]={0,4,5,6,1,2,3};
	long long juzhen[7][7];
	long long f1[7]={4,4,4,4,4,4,4};//1层骰子的情况
	int n,m;
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			juzhen[i][j]=4;	//矩阵初始化
		}
	}
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		juzhen[x][op[y]]=0;	//将不能接触的面标记（标记都为上面数字）
		juzhen[y][op[x]]=0;
	}
	n--;
	while(n){	//矩阵快速幂
		if(n&1)mul(f1,f1,juzhen);
		mul(juzhen,juzhen,juzhen);
		n>>=1;
	}

	long long res=0;
	for(int  i=1;i<=6;i++){
		res=(res+f1[i])%mod;	//最后就是得到总共的情况数了
	}
	cout< 
 
 这里有个小细节：在矩阵快速幂前先对
     
      
       
        
         n
        
       
       
        n
       
      
     n进行了自减操作，这是因为我们在一开始就已经存储了第一层的排列情况，所以我们只需要计算剩下的n-1个情况就行了 
 
第六届蓝桥杯真题-生命之树 
 
 来自20044王宇哲 
 
题目 
在X森林里，上帝创建了生命之树。 
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。 
上帝要在这棵树内选出一个非空节点集 
    
     
      
       
        S
       
      
      
       S
      
     
    S，使得对于 
    
     
      
       
        S
       
      
      
       S
      
     
    S 中的任意两个点 
    
     
      
       
        a
       
       
        ,
       
       
        b
       
      
      
       a,b
      
     
    a,b，都存在一个点列 ${a,v_1,v_2,…,v_k,b} $使得这个点列中的每个点都是 
    
     
      
       
        S
       
      
      
       S
      
     
    S 里面的元素，且序列中相邻两个点间有一条边相连。 
在这个前提下，上帝要使得 
    
     
      
       
        S
       
      
      
       S
      
     
    S 中的点所对应的整数的和尽量大。 
这个最大的和就是上帝给生命之树的评分。 
经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。 
但是由于 atm 不擅长计算，他不知道怎样有效的求评分。 
他需要你为他写一个程序来计算一棵树的分数。 
输入格式 
第一行一个整数 
    
     
      
       
        n
       
      
      
       n
      
     
    n 表示这棵树有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个节点。 
第二行 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个整数，依次表示每个节点的评分。 
接下来 
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n−1
      
     
    n−1 行，每行 22 个整数 
    
     
      
       
        u
       
       
        ,
       
       
        v
       
      
      
       u,v
      
     
    u,v，表示存在一条 
    
     
      
       
        u
       
      
      
       u
      
     
    u 到 
    
     
      
       
        v
       
      
      
       v
      
     
    v 的边。 
由于这是一棵树，所以是不存在环的。 
树的节点编号从 1 到 
    
     
      
       
        n
       
      
      
       n
      
     
    n。 
输出格式 
输出一行一个数，表示上帝给这棵树的分数。 
数据范围 

    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         5
        
       
      
      
       1≤n≤10^5
      
     
    1≤n≤105, 
每个节点的评分的绝对值均不超过 
    
     
      
       
        1
       
       
        
         0
        
        
         6
        
       
      
      
       10^6
      
     
    106。 
输入样例： 
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
 
输出样例： 
8
 
题解 
 
 老实说。。。。。我觉得这个题目把简单的问题复杂化了。。。。非要说的那么高大上 
 简单理解题意，就是说给定一个树，每个结点都有一个权值，要求这个树中的某个子树，使这个子树中的权值之和最大（单独的一个结点也算是一棵树） 
 
 
 开始解题 
 这里我们使用树形
     
      
       
        
         d
        
        
         p
        
       
       
        dp
       
      
     dp（树形动态规划算法），简单来说就是从一棵树的叶结点开始，将所有结点的子节点的最大权值求出，这样就能求出每个子树的权值（一个n个结点的数总共有n个子树，这些子树是以原来那棵树的每个节点作为各自父节点的树） 
 于是，我们只要取出所有子树中最大的那个权值就行了 
 这题要用到深度优先搜索（毕竟要先找到叶子才能开始） 
 还有个问题，当前的树是无根树，所以它是没有根节点的，所以我们只要任取一个结点作为根节点就可以解决了，这里我们取得是1结点为根节点 
 
#include
using namespace std;
const long long N=1e5+5; 	
int v[N];	//存储每个结点权值
vector way[N];	//动态数组，用来存储每个结点的子节点
long long f[N];	//存储子树的权值
long long res;	//最大权值（结果）
long long zero=0;	//0默认是整型。。。。所以定义一个变量存储长整型的0
void dfs(int u,int fa){	
    //u是当前要向下搜索的结点，fa是它的父节点
	for(int i=0;i>n;		//结点个数
	for(int i=1;i<=n;i++){	//循环输入结点权值
		cin>>v[i];
		f[i]=v[i];	//以每个节点自己作为一棵树的树的权值和为当前结点的值
	}
	int u,v;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		way[u].push_back(v);	//存储树支
		way[v].push_back(u);	//树是无向的，所以要存储两个
	}
	dfs(1,-1);	//以1结点开始向下搜索（-1的意思是它是祖先，没有父节点）
	res=f[1];	//令1为根节点的树的权值和为最大值
	for(int i=2;i<=n;i++){	//用打擂台找出最大权值和
		if(res 
蓝桥杯 算法训练-数字三角形 
 
 来自18541杨奕 
 
题目 
资源限制 
时间限制：
    
     
      
       
        1.0
       
       
        s
       
      
      
       1.0s
      
     
    1.0s 内存限制：
    
     
      
       
        256.0
       
      
      
       256.0
      
     
    256.0MB 
问题描述 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nDvFykkh-1644222130867)(image/RequireFile.do)].
 　　（图３.１－１) 
输入格式 
文件中首先读到的是三角形的行数。 
接下来描述整个三角形 
输出格式 
最大总和（整数） 
样例输入 
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
 
样例输出 
30
 
题解 
 
 咦？好像是和上面那道题有点像哎，都是使用了动态规划（差不多吧） 
 简单来说，就是从第n-1层开始，求出每一层每一个经过的节点的最大值，这样就能保证更新到最上面的时候求得从三角形顶端到底端所经过的最大值了 
 
java代码-杨奕 
import java.util.Iterator;
import java.util.Scanner;
public class Main {
	public static void main(String[] args )
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] arr = new int[n][n];
		for(int i = 0;i < n;i++) {
			for(int j = 0;j <= i; j++) {
				int num = sc.nextInt();
				arr[i][j] = num;
			}
		}
		
		for(int i = n-2;i >= 0; i--)
			for(int j = 0;j<=i;j++) 
				arr[i][j]+=Math.max(arr[i+1][j], arr[i+1][j+1]);
		System.out.println(arr[0][0]);
	}
}
 
c++代码-王宇哲 
#include
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[101][101]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	} 
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i;j++){
			a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
		}
	}
	cout< 
 
 这样看来c++确实比
     
      
       
        
         j
        
        
         a
        
        
         v
        
        
         a
        
       
       
        java
       
      
     java代码量少不少呢。。。。 
 
蓝桥杯 历届试题-数字三角形 
 
 20044王宇哲，18541杨奕，18541谭琦 
 （仔细看哦，跟上面题目不完全一样哦） 
 
题目 
资源限制 
时间限制：
    
     
      
       
        1.0
       
       
        s
       
      
      
       1.0s
      
     
    1.0s 内存限制：
    
     
      
       
        256.0
       
      
      
       256.0
      
     
    256.0MB 
问题描述 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ShmGPudd-1644222130870)(image/RequireFile.do)] 
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。 
输入格式 
输入的第一行包含一个整数N (
    
     
      
       
        1
       
       
        <
       
       
        N
       
       
        ≤
       
       
        100
       
      
      
       1 
输出格式 
输出一个整数，表示答案。 
样例输入 
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
 
样例输出 
27
 
题解 
 
 要想做出这道题，那首先就要用动态规划算法来算出所有到最后一行的最大路径权值之和 
 答案就在这n个最大权值和之中 
 接着，根据题意，我们要确保到达这个点的往左走的次数l与往右走的次数r的差的绝对值不大于1 
 这其实也很好理解 
 我们想想，在现实生活中，往东南方走x米，再往东北方走x米，那么实际上，我们到达的点其实就是在起点的正东方 
 所以，在数字三角形中，要求往左走的次数l与往右走的次数r的差的绝对值不大于1，其实就是我们最后走到的点是分布在三角形中线的左右不超过1个的范围之内的，所以我们进行分步讨论 
 
 
 1.当三角形行数为奇数时，那么左转次数和右转次数的和是n-1个也就是个偶数 
 那么列个方程：
 
      
       
        
         
          {
         
         
          
           
            
             
              
               l
              
              
               +
              
              
               r
              
              
               =
              
              
               2
              
              
               k
              
              
               (
              
              
               k
              
              
               ∈
              
              
               Z
              
              
               )
              
             
            
           
          
          
           
            
             
              
               ∣
              
              
               l
              
              
               −
              
              
               r
              
              
               ∣
              
              
               ≤
              
              
               1
              
             
            
           
          
         
        
        
          left{begin{matrix} l+r=2k(kin Z)\ |l-r|leq1end{matrix}right. 
        
       
      {l+r=2k(k∈Z)∣l−r∣≤1
 这个方程解出来就是
     
      
       
        
         l
        
        
         =
        
        
         r
        
        
         =
        
        
         k
        
       
       
        l=r=k
       
      
     l=r=k 
 所以说当三角形行数n为奇数时，最终最大值只能是以第n行第
     
      
       
        
         (
        
        
         n
        
        
         +
        
        
         1
        
        
         )
        
        
         /
        
        
         2
        
       
       
        (n+1)/2
       
      
     (n+1)/2列为最终点的最大值（如下图） 
 
 
 
 1.当三角形行数为偶数时，那么左转次数和右转次数的和是n-1也就是个偶奇数 
 那么列个方程：
 
      
       
        
         
          {
         
         
          
           
            
             
              
               l
              
              
               +
              
              
               r
              
              
               =
              
              
               2
              
              
               k
              
              
               +
              
              
               1
              
              
               (
              
              
               k
              
              
               ∈
              
              
               Z
              
              
               )
              
             
            
           
          
          
           
            
             
              
               ∣
              
              
               l
              
              
               −
              
              
               r
              
              
               ∣
              
              
               ≤
              
              
               1
              
             
            
           
          
         
        
        
          left{begin{matrix} l+r=2k+1(kin Z)\ |l-r|leq1end{matrix}right. 
        
       
      {l+r=2k+1(k∈Z)∣l−r∣≤1
 这个方程解出来就是：
 
      
       
        
         
          l
         
         
          =
         
         
          k
         
         
          +
         
         
          1
         
         
          ,
         
         
          r
         
         
          =
         
         
          k
         
        
        
          l=k+1,r=k 
        
       
      l=k+1,r=k 
 
  或者
  
 
      
       
        
         
          l
         
         
          =
         
         
          k
         
         
          ,
         
         
          r
         
         
          =
         
         
          k
         
         
          −
         
         
          1
         
        
        
          l=k,r=k-1 
        
       
      l=k,r=k−1 
 所以说当三角形行数n为偶数时，最终最大值只能是以第n行第
      
       
        
         
          (
         
         
          n
         
         
          +
         
         
          1
         
         
          )
         
         
          /
         
         
          2
         
        
        
         (n+1)/2
        
       
      (n+1)/2列为最终点的最大值或者以第n行第
      
       
        
         
          (
         
         
          n
         
         
          +
         
         
          1
         
         
          )
         
         
          /
         
         
          2
         
         
          +
         
         
          1
         
        
        
         (n+1)/2+1
        
       
      (n+1)/2+1列为最终点的最大值两者中的最大值（如下图） 
 
 
c++代码-王宇哲，谭琦 
#include
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[101][101]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	} 
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			a[i][j]+=max(a[i-1][j-1],a[i-1][j]);
		}
	}
	if(n%2==1)
		cout< 
java代码-杨奕 
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+1][n+1];
        int[][] a = new int[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = sc.nextInt();
                arr[i][j] =a[i][j] + Math.max(arr[i - 1][j - 1], arr[i - 1][j]);
            }
        }
        int result = n % 2 == 1 ? arr[n][n / 2 + 1] : Math.max(arr[n][n / 2], arr[n][n / 2 + 1]);
        System.out.println(result);
    }
}
 
 
 这个题解写的真费劲。。。希望你们能看懂吧 
 
蓝桥杯 算法提高-组合数 
 
 来自18541谭琦 
 
题目 
资源限制 
时间限制：
    
     
      
       
        1.0
       
       
        s
       
      
      
       1.0s
      
     
    1.0s 内存限制：
    
     
      
       
        256.0
       
      
      
       256.0
      
     
    256.0MB 
问题描述 
输入n, m, p, 输出C(n, m)%p。 
输入格式 
输入包含三个数n, m, p。 
输出格式 
输出答案。 
样例输入 
10 5 13
 
样例输出 
5
 
数据规模和约定 
1<=n, m<=60000, 1 
题解 
 
 逆元+快速幂 
 (挺难的，涉及到数论里面的东西，基础不好可以暂时不看) 
 这题的难点在于取余运算，有人就会觉得，取余不是很简单吗？直接在循环中的每个运算中对p取余不就行了吗？实则不然 
 在取余运算中，有以下运算律：
 
      
       
        
         
          (
         
         
          a
         
         
          +
         
         
          b
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          (
         
         
          a
         
         
          %
         
         
          p
         
         
          +
         
         
          b
         
         
          %
         
         
          p
         
         
          )
         
         
          %
         
         
          p
         
         
         
          (
         
         
          a
         
         
          −
         
         
          b
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          (
         
         
          a
         
         
          %
         
         
          p
         
         
          −
         
         
          b
         
         
          %
         
         
          p
         
         
          )
         
         
          %
         
         
          p
         
         
         
          (
         
         
          a
         
         
          ∗
         
         
          b
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          (
         
         
          a
         
         
          %
         
         
          p
         
         
          ∗
         
         
          b
         
         
          %
         
         
          p
         
         
          )
         
         
          %
         
         
          p
         
        
        
          (a+b)%p=(a%p+b%p)%p\ (a-b)%p=(a%p-b%p)%p\ (a*b)%p=(a%p*b%p)%p 
        
       
      (a+b)%p=(a%p+b%p)%p(a−b)%p=(a%p−b%p)%p(a∗b)%p=(a%p∗b%p)%p
 但是唯独这个：
     
      
       
        
         (
        
        
         a
        
        
         /
        
        
         b
        
        
         )
        
        
         %
        
        
         p
        
        
         =
        
        
         (
        
        
         a
        
        
         %
        
        
         p
        
        
         /
        
        
         b
        
        
         %
        
        
         p
        
        
         )
        
        
         %
        
        
         p
        
       
       
        (a/b)%p=(a%p/b%p)%p
       
      
     (a/b)%p=(a%p/b%p)%p是错误的
      
       
        
         
          ×
         
        
        
         times
        
       
      × 
 可是恰巧这个错误很多人都会自作主张的把当做正确的（包括我自己） 
 因为我们知道
 
      
       
        
         
          
           C
          
          
           n
          
          
           m
          
         
         
          =
         
         
          
           
            n
           
           
            !
           
           
            (
           
           
            n
           
           
            −
           
           
            m
           
           
            )
           
           
            !
           
          
          
           
            m
           
           
            !
           
          
         
        
        
          C_n^m=frac{n!(n-m)!}{m!} 
        
       
      Cnm=m!n!(n−m)!
 在组合数运算中一定是会有除法运算的，那恰好就在这个地方我们不知道该怎么解决~~（我怀疑题目是故意坑人的）~~，而想要直接把组合数求出来再进行取余操作是不大现实的（除非你用高精度算法？那考试的时候你确定有那么多时间思考吗？） 
 所以，搞明白这一题，我们必须搞明白除法取余的运算规则 
 
 
 想讲明白除法取余运算规则，我需要先说明什么是**“逆元”与“费马小定理”** 
 首先说逆元（此题目核心）： 
 对于一个数**
     
      
       
        
         a
        
       
       
        a
       
      
     a**， 
 
      
       
        
         
          a
         
         
          ∗
         
         
          x
         
         
          ≡
         
         
          1
         
         
          (
         
         
         
         
          
           m
          
          
           o
          
          
           d
          
           
         
          p
         
         
          )
         
        
        
         a*xequiv 1(mod p)
        
       
      a∗x≡1(modp) 
  其实也就是 
 
      
       
        
         
          (
         
         
          a
         
         
          ∗
         
         
          x
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          1
         
         
          %
         
         
          p
         
        
        
         (a*x)%p=1%p
        
       
      (a∗x)%p=1%p 
 则式子中的x称为a的乘法逆元 
 在这里，
     
      
       
        
         a
        
       
       
        a
       
      
     a存在乘法逆元的充要条件为
      
       
        
         
          a
         
        
        
         a
        
       
      a与
      
       
        
         
          p
         
        
        
         p
        
       
      p互质（这里很重要，这是能用上费马小定理的必须条件！！！） 
 逆元的应用**(也是本题中题解的原理)**：
 
      
       
        
         
          (
         
         
          a
         
         
          /
         
         
          b
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          a
         
         
          ∗
         
         
          (
         
         
          b
         
         
          的
         
         
          逆
         
         
          元
         
         
          )
         
         
          %
         
         
          p
         
        
        
          (a/b)%p=a*(b的逆元)%p 
        
       
      (a/b)%p=a∗(b的逆元)%p
 接下来的问题就是怎么求b的逆元了，这里开始介绍费马小定理： 
  
  费马小定理： 
  假设
      
       
        
         
          a
         
        
        
         a
        
       
      a是一个整数，
      
       
        
         
          p
         
        
        
         p
        
       
      p是一个质数，那么 
  1.如果a是p的倍数，那么
      
       
        
         
          
           a
          
          
           p
          
         
         
          ≡
         
         
          a
         
         
          (
         
         
         
         
          
           m
          
          
           o
          
          
           d
          
           
         
          p
         
         
          )
         
        
        
         a^pequiv a(mod p)
        
       
      ap≡a(modp) 
  2.如果a不是p的倍数，那么
       
        
         
          
           
            a
           
           
            
             p
            
            
             −
            
            
             1
            
           
          
          
           ≡
          
          
           1
          
          
           (
          
          
          
          
           
            m
           
           
            o
           
           
            d
           
            
          
           p
          
          
           )
          
         
         
          a^{p-1}equiv 1(mod p)
         
        
       ap−1≡1(modp) 
  
 这里我们主要用到费马小定理的第二个定理，因为逆元的前提条件是a与p互质，那么a就不可能是p的倍数 
 开始推公式：
 
      
       
        
         
          ∵
         
         
          
           b
          
          
           
            p
           
           
            −
           
           
            1
           
          
         
         
          ≡
         
         
          1
         
         
          (
         
         
         
         
          
           m
          
          
           o
          
          
           d
          
           
         
          p
         
         
          )
         
         
         
          ∴
         
         
          b
         
         
          ∗
         
         
          
           b
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          ≡
         
         
          1
         
         
          (
         
         
         
         
          
           m
          
          
           o
          
          
           d
          
           
         
          p
         
         
          )
         
         
         
          ∴
         
         
          
           b
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          是
         
         
          b
         
         
          的
         
         
          逆
         
         
          元
         
         
         
          ∴
         
         
          (
         
         
          a
         
         
          /
         
         
          b
         
         
          )
         
         
          %
         
         
          p
         
         
          =
         
         
          (
         
         
          a
         
         
          ∗
         
         
          
           b
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          )
         
         
          %
         
         
          p
         
         
         
          =
         
         
          (
         
         
          a
         
         
          %
         
         
          p
         
         
           
         
         
          ∗
         
         
           
         
         
          
           b
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          %
         
         
          p
         
         
          )
         
         
          %
         
         
          p
         
        
        
          because b^{p-1}equiv 1(mod p)\ therefore b*b^{p-2}equiv 1(mod p)\ therefore b^{p-2}是b的逆元\ therefore (a/b)%p=(a*b^{p-2})%p\=(a%p * b^{p-2}%p)%p 
        
       
      ∵bp−1≡1(modp)∴b∗bp−2≡1(modp)∴bp−2是b的逆元∴(a/b)%p=(a∗bp−2)%p=(a%p ∗ bp−2%p)%p
 由此：
 
      
       
        
         
          
           C
          
          
           n
          
          
           m
          
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
          =
         
         
          
           
            n
           
           
            !
           
          
          
           
            m
           
           
            !
           
           
            (
           
           
            n
           
           
            −
           
           
            m
           
           
            )
           
           
            !
           
          
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
         
          =
         
         
          (
         
         
          
           
            n
           
           
            !
           
          
          
           
            m
           
           
            !
           
          
         
         
          ÷
         
         
          (
         
         
          n
         
         
          −
         
         
          m
         
         
          )
         
         
          !
         
         
          )
         
         
           
         
         
          %
         
         
          p
         
         
           
         
         
         
          =
         
         
          (
         
         
          
           
            n
           
           
            !
           
          
          
           
            m
           
           
            !
           
          
         
         
          (
         
         
          n
         
         
          −
         
         
          m
         
         
          )
         
         
          
           !
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          )
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
         
          =
         
         
          
           
            n
           
           
            !
           
           
            {
           
           
            (
           
           
            n
           
           
            −
           
           
            m
           
           
            )
           
           
            !
           
           
            
             }
            
            
             
              p
             
             
              −
             
             
              2
             
            
           
          
          
           
            m
           
           
            !
           
          
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
         
          =
         
         
          (
         
         
          
           
            n
           
           
            !
           
          
          
           
            m
           
           
            !
           
          
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
          ∗
         
         
          (
         
         
          (
         
         
          n
         
         
          −
         
         
          m
         
         
          )
         
         
          
           !
          
          
           
            p
           
           
            −
           
           
            2
           
          
         
         
          )
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
          )
         
         
           
         
         
          %
         
         
           
         
         
          p
         
         
        
        
          C_n^m % p=frac{n!}{m!(n-m)!} % p\ =(frac{n!}{m!}div (n-m)!) %p \ =(frac{n!}{m!}(n-m)!^{p-2}) % p\ =frac{n!{(n-m)!}^{p-2}}{m!} % p\ =(frac{n!}{m!} % p*((n-m)!^{p-2}) % p) % p\ 
        
       
      Cnm % p=m!(n−m)!n! % p=(m!n!÷(n−m)!) %p =(m!n!(n−m)!p−2) % p=m!n!{(n−m)!}p−2 % p=(m!n! % p∗((n−m)!p−2) % p) % p
 在这里
     
      
       
        
         
          
           n
          
          
           !
          
         
         
          
           m
          
          
           !
          
         
        
       
       
        frac{n!}{m!}
       
      
     m!n!一定是个整数，可以提前算出来的，因为： 
 
     
      
       
        
         
          
           n
          
          
           !
          
         
         
          
           m
          
          
           !
          
         
        
        
         =
        
        
         (
        
        
         m
        
        
         +
        
        
         1
        
        
         )
        
        
         ∗
        
        
         (
        
        
         m
        
        
         +
        
        
         2
        
        
         )
        
        
         ∗
        
        
         …
        
        
         …
        
        
         ∗
        
        
         (
        
        
         n
        
        
         −
        
        
         1
        
        
         )
        
        
         ∗
        
        
         n
        
       
       
        frac{n!}{m!}=(m+1)*(m+2)*……*(n-1)*n
       
      
     m!n!=(m+1)∗(m+2)∗……∗(n−1)∗n 
 （这里绝对是我题解写的最累的地方。。。） 
 
c++代码-谭琦 
#include
using namespace std;
typedef unsigned long long ull;
int n , m , p;
ull calc(int a , int b)
{
	ull ans = 1;
	for(int i = a ;i <= b ; i ++)ans = (ans * i) % p;
	return ans;
}

ull inverse(ull num)
{
	int a = num , b = p - 2;
	ull ans = 1;
	while(b)
	{
		if(b & 1)ans = (ans * num) % p;
		b >>= 1;
		num = (num * num) % p;
	}
	return ans;
}

int main()
{
	cin >> n >> m >> p;
	return cout << ( calc(m + 1 , n) * inverse(calc(1 , n - m))) % p , 0;
}

 
 
 公式: 
 题解详细请参考 
 逆元求组合数 
 逆元与费马小定理可以参考b站视频： 
 数论.乘法逆元.费马小定理 
 
蓝桥杯 第十届真题 年号字串 
 
 来自20044王宇哲 
 
题目 
 
 小明用字母A 对应数字1，B 对应2，以此类推，用Z 对应26。对于27以上的数字
 小明用两位或更长位的字符串来对应，例如AA 对应27，AB 对应28，AZ 对应52，LQ 对应329。
 请问2019 对应的字符串是什么？ 
 
题解 
这道题目解法有很多，数据量也不大，所以应该可以说是一道送分题了吧 
 
 1.我们发现，这个字符串跟excel的列号很像，所以我们可以打开excel，找到第2019列（阿这，应该不算作弊吧哈哈哈。。。） 
 2.2019这个数据量本身也不大，可以直接拿笔计算。。。 
 
 
 3.代码（重点介绍）： 
 其实我本来不想讲的，但是网上大多数题解是错误的，尽管最后确实可以求出解，但是那都是瞎猫撞着死耗子，我希望大家不要被网上那些用26进制做的人误导 
 为什么说这题不能用进制做？虽说这道题看起来跟进制确实挺像的，但是他真的不是进制，因为不管什么进制，他的第一位数一定是0，但是这道题第一位是1 
 在这里，我会用递归做，为什么要用递归做？因为递归的本质就是栈，遵循后进先出的原则,按照我们的计算方法，如果使用顺序结构的话最后输出的结果是倒序的 
  
 首先，我们思考一下： 
 1代表‘A’,26代表‘Z’，所以当输入的数小于等于26的话，输出结果就是（char）26+‘A’-1 
 接着，27代表‘AA’,’28’代表‘AB’，这里的思考决定了我们思考问题的整个过程，我们先思考最后一位字母应该是怎么表示，27的最后一位是A，‘A’代表1，也就是说，27经过了一系列运算变成了1，那么这就很好解释了，1=27%26 
 我们来验证一下，53表示的应该是‘BA’，最后一位是A也就是1,53%26=1，成立 
 可是对吗？各位要不要试试把52代入？ 
 52%26=0，不对啊，这不应该是26吗？所以说，我们的公式不对 
 我们来分析一下，这里确实是26个数字，但是这里也确实不是26进制，因为它第一位是1，最后一位是26，而26进制第一位应该是0，最后一位应该是25 
 那么我们的公式应该是什么？我们应该是将这个数字-1以使他满足26进制的运算 
 那么也就是说，这时候，0代表‘A’，25代表‘Z’，所以我们最后一位运算应该是：
     
      
       
        
         (
        
        
         （
        
        
         n
        
        
         u
        
        
         m
        
        
         −
        
        
         1
        
        
         ）
        
        
         %
        
        
         26
        
        
         +
        
        
         1
        
        
         )
        
        
         
          +
         
         
          ′
         
        
        
         
          A
         
         
          ′
         
        
        
         −
        
        
         1
        
       
       
        (（num-1）%26+1)+'A'-1
       
      
     (（num−1）%26+1)+′A′−1 
  
 这时候我们就要思考怎么进行移位操作了，毕竟我们还需要求得第一位，第二位… 
 经过我们上面计算，我们发现最难处理的部分就是Z，也就是26 
 那我们不妨就52（‘AZ’）展开研究讨论 
 此时根据上面那个公式，我们已经得到了尾数‘Z’，现在我们就需要研究该怎么移位以保证接下来的运算顺利 
 我们知道，每+26我们就要进一位
 
      
       
        
         
          1
         
         
          +
         
         
          26
         
         
          =
         
         
          ‘
         
         
          A
         
         
          A
         
         
          ’
         
         
         
          27
         
         
          +
         
         
          26
         
         
          =
         
         
          ‘
         
         
          B
         
         
          A
         
         
          ’
         
         
         
          53
         
         
          +
         
         
          26
         
         
          =
         
         
          ’
         
         
          C
         
         
          A
         
         
          ’
         
         
         
          ∴
         
         
          1
         
         
          +
         
         
          26
         
         
          ∗
         
         
          k
         
         
          =
         
         
          ’
         
         
          k
         
         
           
         
         
          A
         
         
          ’
         
         
         
          ∴
         
         
          1
         
         
          +
         
         
          26
         
         
          ∗
         
         
          26
         
         
         
          =
         
         
          1
         
         
          +
         
         
          676
         
         
          
           =
          
          
           ′
          
         
         
          Z
         
         
          
           A
          
          
           ′
          
         
         
         
          ∴
         
         
          1
         
         
          +
         
         
          27
         
         
          ∗
         
         
          26
         
         
          =
         
         
          1
         
         
          +
         
         
          702
         
         
          
           =
          
          
           ′
          
         
         
          A
         
         
          A
         
         
          
           A
          
          
           ′
          
         
        
        
          1+26=‘AA’\27+26=‘BA’\53+26=’CA’\ therefore 1+26*k=’k A’ \therefore 1+26*26\=1+676='ZA' \therefore1+27*26=1+702='AAA' 
        
       
      1+26=‘AA’27+26=‘BA’53+26=’CA’∴1+26∗k=’k A’∴1+26∗26=1+676=′ZA′∴1+27∗26=1+702=′AAA′
 好，我们把几个比较特殊的例子拿出来给大家看看：
 
      
       
        
         
          1
         
         
          
           =
          
          
           ′
          
         
         
          
           A
          
          
           ′
          
         
         
         
          1
         
         
          +
         
         
          26
         
         
          
           =
          
          
           ′
          
         
         
          A
         
         
          
           A
          
          
           ′
          
         
         
         
          1
         
         
          +
         
         
          (
         
         
          1
         
         
          +
         
         
          26
         
         
          )
         
         
          ∗
         
         
          26
         
         
          
           =
          
          
           ′
          
         
         
          A
         
         
          A
         
         
          
           A
          
          
           ′
          
         
        
        
          1='A'\ 1+26='AA'\ 1+(1+26)*26='AAA' 
        
       
      1=′A′1+26=′AA′1+(1+26)∗26=′AAA′
 发动你的小脑袋瓜，猜猜
     
      
       
        
         ‘
        
        
         A
        
        
         A
        
        
         A
        
        
         A
        
        
         ’
        
       
       
        ‘AAAA’
       
      
     ‘AAAA’怎么表示吧，是的没错就是：
     
      
       
        
         1
        
        
         +
        
        
         (
        
        
         1
        
        
         +
        
        
         (
        
        
         1
        
        
         +
        
        
         26
        
        
         )
        
        
         ∗
        
        
         26
        
        
         )
        
        
         ∗
        
        
         26
        
       
       
        1+(1+(1+26)*26)*26
       
      
     1+(1+(1+26)∗26)∗26 
 所以找到规律了，知道怎么做了吗？ 
 
      
       
        
         
          a
         
         
          +
         
         
          (
         
         
          b
         
         
          +
         
         
          (
         
         
          c
         
         
          +
         
         
          d
         
         
          ∗
         
         
          26
         
         
          )
         
         
          ∗
         
         
          26
         
         
          )
         
         
          ∗
         
         
          26
         
         
          
           =
          
          
           ′
          
         
         
          d
         
         
           
         
         
          c
         
         
           
         
         
          b
         
         
           
         
         
          
           a
          
          
           ′
          
         
        
        
         a+(b+(c+d*26)*26)*26='d c b a'
        
       
      a+(b+(c+d∗26)∗26)∗26=′d c b a′ 
 所以我们的移位操作就是
     
      
       
        
         (
        
        
         n
        
        
         u
        
        
         m
        
        
         −
        
        
         1
        
        
         )
        
        
         /
        
        
         26
        
       
       
        (num-1)/26
       
      
     (num−1)/26 
 因此当
     
      
       
        
         n
        
        
         u
        
        
         m
        
       
       
        num
       
      
     num大于26的时候，就要将
     
      
       
        
         (
        
        
         n
        
        
         u
        
        
         m
        
        
         −
        
        
         1
        
        
         )
        
        
         /
        
        
         26
        
       
       
        (num-1)/26
       
      
     (num−1)/26传入下一个递归,这样最后的结果啦 
 （太费口舌了。。。） 
 
c++代码-王宇哲 
#include
using namespace std;
int cal(int num){
	if(num>26){
		cal((num-1)/26);
	}
	cout<<(char)((num-1)%26+1+'A'-1);
}
int main(){
	int n;
	cin>>n;
	cal(n); 
	return 0;
}
 
 
 小代码，大理论 
 
蓝桥杯 第十届真题 迷宫 
 
 来自18541 谭方川，20044王宇哲 
 （经过研究，迷宫题是蓝桥杯近几年的重点提醒） 
 
题目 
题目描述 
 
 下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可
 以通行的地方。
 010000
 000100
 001001
 110000
 迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
 个它的上、下、左、右四个方向之一。
 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
 一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
 对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，
 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
 请注意在字典序中D 
 
输入地图 
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
 
题解 
 
 就是一道简单的广度优先搜索题目，没什么好说的，主要需要注意的就是要保证输出字典序最小的那个答案，那也就是在执行搜索的时候就按照
     
      
       
        
         D
        
        
         <
        
        
         L
        
        
         <
        
        
         R
        
        
         <
        
        
         U
        
       
       
        D 
 
c++代码-王宇哲 
#include
using namespace std;
struct way{
	int x;
	int y;
	string step;
	int step2;
};
int n,m;
char dir1[4]={'D','L','R','U'};	//按照字典序来搜索
int dir[4][2]={
	{0,1},
	{-1,0},
	{1,0},
	{0,-1}
};
char map1[600][600];	//开为char型是因为输入数据中间没有空格，所以用char数组来保证他们数据能单独录入
queue q;
int main(){
	string min_str;
	struct way tmp;
	cin>>m>>n;	//输入地图高与宽
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>map1[j][i];
		}
	}
	tmp.x=1;
	tmp.y=1;
	tmp.step2=0;
	tmp.step="";
	map1[1][1]='1';
	q.push(tmp);
	int f=0;
	while(!q.empty()){
		if(q.front().x==n&&q.front().y==m){
			cout<=1&&tmp.y<=m&&tmp.y>=1&&map1[tmp.x][tmp.y]=='0'){
				q.push(tmp);
				map1[tmp.x][tmp.y]='1';
			}
		}
		q.pop();
	}
	return 0;
}
 
java代码-谭方川 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        char[][] maze = new char[n][m];
        for (int i = 0; i < n; i++) {
            maze[i] = scanner.nextLine().toCharArray();
        }
        // 最小字典序：只要按 D、L、R、U 方向搜索，第一个到达终点的肯定是方向的最小字典序
        int[] x = {1, 0, 0, -1};
        int[] y = {0, -1, 1, 0};
        char[] position = {'D', 'L', 'R', 'U'};
        int[][] visited = new int[n][m];

        Queue queue = new linkedList<>();
        queue.add(new Node(0, 0));
        visited[0][0] = 1;
        // 为每一个节点都保存一个路径
        Queue path = new linkedList<>();
        path.add(new StringBuilder(""));
        while (queue.size() > 0) {
            Node node = queue.poll();
            StringBuilder tempPath = path.poll();
            if (node.x == n - 1 && node.y == m - 1) {
                System.out.println(tempPath.toString());
                break;
            }
            for (int i = 0; i < 4; i++) {
                int newX = node.x + x[i];
                int newY = node.y + y[i];
                StringBuilder temp = new StringBuilder(tempPath.toString());
                if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                    if (visited[newX][newY] == 0 && maze[newX][newY] == '0') {
                        visited[newX][newY] = 1;
                        queue.add(new Node(newX, newY));
                        // 更新节点的路径
                        temp.append(position[i]);
                        path.add(temp);
                    }
                }
            }
        }
    }
    static class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
 
 
 2021年3月31日 
 在谭琦学长的建议下优化了代码，减少了代码的空间复杂度并让代码可观性变强，具体改动为将bfs中本该拥有的book数组取出，转而将地图数组map1同时也作为标记数组，让走过的点变为‘1’，使其无法再次通过，这样的思路可以让map1数组同时也担任book数组的作用 
 
蓝桥杯 第十届真题 等差数列 
题目 
 
 来自20044 王宇哲 
 
题目描述 
数学老师给小明出了一道等差数列求和的题目。 
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。 
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？ 
输入格式 
输入的第一行包含一个整数 N。 
第二行包含 N 个整数
    
     
      
       
        
         A
        
        
         1
        
       
       
        ,
       
       
        
         A
        
        
         2
        
       
       
        ,
       
       
        ⋅
       
       
        ⋅
       
       
        ⋅
       
       
        ,
       
       
        
         A
        
        
         N
        
       
      
      
       A_1,A_2,···,A_N
      
     
    A1,A2,⋅⋅⋅,AN。(注意
    
     
      
       
        
         A
        
        
         1
        
       
       
        ∼
       
       
        
         A
        
        
         N
        
       
      
      
       A_1∼A_N
      
     
    A1∼AN 并不一定是按等差数
 列中的顺序给出) 
输出格式 
输出一个整数表示答案。 
数据范围 

    
     
      
       
        2
       
       
        ≤
       
       
        N
       
       
        ≤
       
       
        100000
       
      
      
       2≤N≤100000
      
     
    2≤N≤100000, 

    
     
      
       
        0
       
       
        ≤
       
       
        
         A
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       0≤A_i≤10^9
      
     
    0≤Ai≤109 
输入样例： 
5
2 6 4 10 20
 
输出样例： 
10
 
样例解释 
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。 
题解 
 
 为了找到最短的等差数列，我们肯定是要找到最大的公差数，而现在的问题就是如何找到最大公差数 
 经过分析以后，我们会得到，最大的公差数一定是等差数列中每两项间的差数全部的最大公倍数 
 最后那个最大公倍数就是整个数列的公差了 
 我们接下来可以通过最大公差得到最小的项数：
 
      
       
        
         
          
           a
          
          
           n
          
         
         
          =
         
         
          
           a
          
          
           1
          
         
         
          +
         
         
          (
         
         
          n
         
         
          −
         
         
          1
         
         
          )
         
         
          d
         
         
         
          ∴
         
         
          n
         
         
          =
         
         
          (
         
         
          
           a
          
          
           n
          
         
         
          −
         
         
          
           a
          
          
           1
          
         
         
          )
         
         
          /
         
         
          d
         
         
          +
         
         
          1
         
        
        
          a_n=a_1+(n-1)d \therefore n=(a_n-a_1)/d+1 
        
       
      an=a1+(n−1)d∴n=(an−a1)/d+1
 最小的项的数量就可以得到了 
 辗转相除法 
 我们已知：
 
      
       
        
         
          被
         
         
          除
         
         
          数
         
         
          /
         
         
          除
         
         
          数
         
         
          =
         
         
          商
         
         
          …
         
         
          余
         
         
          数
         
        
        
          被除数/除数=商…余数 
        
       
      被除数/除数=商…余数
 辗转相除法就是将每次除得的余数取来作第二次的除数，除数作第二次的被除数 
 也就是： 
 
      
       
        
         
          a
         
         
          /
         
         
          b
         
         
          =
         
         
          a
         
         
          /
         
         
          b
         
         
          …
         
         
          a
         
         
          %
         
         
          b
         
         
         
          b
         
         
          /
         
         
          (
         
         
          a
         
         
          %
         
         
          b
         
         
          ）
         
         
          =
         
         
          c
         
         
          …
         
         
          b
         
         
          %
         
         
          (
         
         
          a
         
         
          %
         
         
          b
         
         
          )
         
        
        
          a/b=a/b…a%b \ b/(a%b）=c…b%(a%b) 
        
       
      a/b=a/b…a%bb/(a%b）=c…b%(a%b) 
 这样一直到余数为0，那么本次的除数（也就是上一次的余数）就是a与b的最大公约数了 
 int min_ab = 0,a,b;
cin>>a>>b;
while(1){
min_ab = a%b;
a = b;
b = min_ab;
if(a%b==0) break;
} 
cout< 
 辗转相减法 
 基本方法： 
 1.将a-b得到结果c 
 2.在a,b,c中选取最小的两个数相减，直到取得相同的两个数（最小的两个数相等）那么这两个数（相等）就是最大公约数 
 代码： 
 int n,m;
cin>>n>>m;
while (m != n){
while (m>n) { m = m - n; }
while (n>m) { n = n - m; }
}
cout< 
 
c++代码-王宇哲 
#include
using namespace std;
int gys(int n,int m){	//辗转相减法得到最大公倍数
	while (m != n){
	    while (m>n) { m = m - n; }
	    while (n>m) { n = n - m; }
	}
	return n;
}
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i>a[i];
	sort(a,a+n);	//主要自己看着顺眼
	int min1=a[1]-a[0];
	for(int i=2;i 
 
 题解瑕疵还是有点多的，其实比较最小值的过程不太需要 
 
蓝桥杯 第十届真题 后缀表达式 
 
 来自20044 王宇哲 ，18541谭方川 
 
题目 
题目描述 
给定 N 个加号、M 个减号以及 N+M+1 个整数 
    
     
      
       
        
         A
        
        
         1
        
       
       
        ,
       
       
        
         A
        
        
         2
        
       
       
        ,
       
       
        ⋅
       
       
        ⋅
       
       
        ⋅
       
       
        ,
       
       
        
         A
        
        
         
          N
         
         
          +
         
         
          M
         
         
          +
         
         
          1
         
        
       
      
      
       A_1,A_2,···,A_{N+M+1}
      
     
    A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？ 
请你输出这个最大的结果。 
例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。 
输入格式 
第一行包含两个整数 N 和 M。 
第二行包含 N+M+1 个整数$ A_1,A_2,⋅⋅⋅,A_{N+M+1}$。 
输出格式 
输出一个整数，代表答案。 
数据范围 

    
     
      
       
        0
       
       
        ≤
       
       
        N
       
       
        ,
       
       
        M
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         5
        
       
      
      
       0≤N,M≤10^5
      
     
    0≤N,M≤105, 

    
     
      
       
        −
       
       
        1
       
       
        
         0
        
        
         9
        
       
       
        ≤
       
       
        
         A
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       −10^9≤A_i≤10^9
      
     
    −109≤Ai≤109 
输入样例： 
1 1
1 2 3
 
输出样例： 
4
 
题解 
 
 这道题总共分为两种情况，第一种是只有加号，那么最后结果就是全部的数加起来的结果（毋庸置疑） 
 这里重点讲解第二种的情况： 
 分类讨论： 
 第一种：全是正数 
 1、假设只有一个减号，n-2个加号，而且输入的数全部是正数，我们先将全部的n个数从大到小进行排序，那么最终的最大值一定是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
        
        
          A_n+A_{n-1}+...+A_3+A_2-A_1 
        
       
      An+An−1+...+A3+A2−A1
 2、假设有2个减号，n-3个加号，且输入的全是整数，我们想将n个数从小到大进行排序，那么最终的最大值便是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           1
          
         
         
          −
         
         
          
           A
          
          
           2
          
         
         
          )
         
         
         
          =
         
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
        
        
          A_n+A_{n-1}+....+A_3-(A_1-A_2)\ =A_n+A_{n-1}+...+A_3+A_2-A_1 
        
       
      An+An−1+....+A3−(A1−A2)=An+An−1+...+A3+A2−A1
 3、假设有3个减号，n-4个加号，且输入的全是整数，我们想将n个数从小到大进行排序，那么最终的最大值便是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           4
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           1
          
         
         
          −
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           3
          
         
         
          )
         
         
         
          =
         
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
        
        
          A_n+A_{n-1}+....+A_4-(A_1-A_2-A_3)\ =A_n+A_{n-1}+...+A_3+A_2-A_1 
        
       
      An+An−1+....+A4−(A1−A2−A3)=An+An−1+...+A3+A2−A1
 4、假设有n-1个减号，0个加号，且输入的全是整数，我们想将n个数从小到大进行排序，那么最终的最大值便是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           1
          
         
         
          −
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          −
         
         
          
           A
          
          
           4
          
         
         
          −
         
         
          
           A
          
          
           3
          
         
         
          −
         
         
          
           A
          
          
           2
          
         
         
          )
         
         
         
          =
         
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
        
        
          A_n-(A_1-A_{n-1}-....-A_4-A_3-A_2)\ =A_n+A_{n-1}+...+A_3+A_2-A_1 
        
       
      An−(A1−An−1−....−A4−A3−A2)=An+An−1+...+A3+A2−A1
 通过观察，我们发现，无论多少个减号都是可以化成n-2个加号和一个减号的形式，那么这个时候我们的最优解就是减去一个最小的数，其他数相加 
 第二种：全是负数 
 1、假设只有一个减号，n-2个加号 
 此时选取最大的一个数在括号外面，然后其余的数在括号里：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           4
          
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          +
         
         
          
           A
          
          
           1
          
         
         
          )
         
        
        
          A_n-(A_{n-1}+....+A_4+A_3+A_2+A_1) 
        
       
      An−(An−1+....+A4+A3+A2+A1)
 这样就能保证是最大值了 
 2、假设有2个减号，n-3个加号 
 此时最大值就是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            2
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          )
         
         
         
          =
         
         
          
           A
          
          
           n
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           4
          
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          +
         
         
          
           A
          
          
           1
          
         
         
          )
         
        
        
          A_n-A_1-(A_{n-1}+A_{n-2}+...A_3+A_2)\ =A_n-(A_{n-1}+....+A_4+A_3+A_2+A_1) 
        
       
      An−A1−(An−1+An−2+...A3+A2)=An−(An−1+....+A4+A3+A2+A1)
 3、假设有n-1个减号，0个加号,则最大值是：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          −
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            2
           
          
         
         
          −
         
         
          .
         
         
          .
         
         
          .
         
         
          −
         
         
          
           A
          
          
           3
          
         
         
          −
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
         
         
          =
         
         
          
           A
          
          
           n
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           4
          
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          +
         
         
          
           A
          
          
           1
          
         
         
          )
         
        
        
          A_n-A_{n-1}-A_{n-2}-...-A_3-A_2-A_1\ =A_n-(A_{n-1}+....+A_4+A_3+A_2+A_1) 
        
       
      An−An−1−An−2−...−A3−A2−A1=An−(An−1+....+A4+A3+A2+A1) 
 第三种：有负有正 
 1、假设只有一个减号 
 那么最大值就是：
 
      
       
        
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          （
         
         
          全
         
         
          部
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          ）
         
        
        
          全部正整数之和-（全部负整数之和） 
        
       
      全部正整数之和−（全部负整数之和）
 2、假设有2个减号，n-3个减号 
 那么最大值就是：
 
      
       
        
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          最
         
         
          小
         
         
          的
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          （
         
         
          剩
         
         
          下
         
         
          的
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          ）
         
         
         
          =
         
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          （
         
         
          全
         
         
          部
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          ）
         
        
        
          全部正整数之和-最小的负整数-（剩下的负整数之和）\ =全部正整数之和-（全部负整数之和） 
        
       
      全部正整数之和−最小的负整数−（剩下的负整数之和）=全部正整数之和−（全部负整数之和）
 3、假设只有一个加号，其余全是减号 
 若要最大值，则取出一个负数：
 
      
       
        
         
          一
         
         
          个
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          （
         
         
          一
         
         
          个
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          .
         
         
          .
         
         
          .
         
         
          ）
         
         
          +
         
         
          一
         
         
          个
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          负
         
         
          整
         
         
          数
         
         
          .
         
         
          .
         
         
          .
         
         
         
          =
         
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          全
         
         
          部
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
        
        
          一个正整数-（一个负整数-正整数-正整数-...）+一个正整数-负整数-负整数-负整数...\ =全部正整数之和-全部负整数之和 
        
       
      一个正整数−（一个负整数−正整数−正整数−...）+一个正整数−负整数−负整数−负整数...=全部正整数之和−全部负整数之和
 4、假设全是减号，最大值为：
 
      
       
        
         
          一
         
         
          个
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          （
         
         
          一
         
         
          个
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          其
         
         
          余
         
         
          正
         
         
          整
         
         
          数
         
         
          ）
         
         
          −
         
         
          负
         
         
          整
         
         
          数
         
         
          −
         
         
          负
         
         
          整
         
         
          数
         
         
          .
         
         
          .
         
         
          .
         
         
         
          =
         
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          全
         
         
          部
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
        
        
          一个正整数-（一个负整数-其余正整数）-负整数-负整数...\ =全部正整数之和-全部负整数之和 
        
       
      一个正整数−（一个负整数−其余正整数）−负整数−负整数...=全部正整数之和−全部负整数之和 
 总结 
 我们现在将所有的三种大的情况列在下面： 
 全是正数：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          +
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          −
         
         
          
           A
          
          
           1
          
         
        
        
          A_n+A_{n-1}+...+A_3+A_2-A_1 
        
       
      An+An−1+...+A3+A2−A1
 全是负数：
 
      
       
        
         
          
           A
          
          
           n
          
         
         
          −
         
         
          (
         
         
          
           A
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           A
          
          
           4
          
         
         
          +
         
         
          
           A
          
          
           3
          
         
         
          +
         
         
          
           A
          
          
           2
          
         
         
          +
         
         
          
           A
          
          
           1
          
         
         
          )
         
        
        
          A_n-(A_{n-1}+....+A_4+A_3+A_2+A_1) 
        
       
      An−(An−1+....+A4+A3+A2+A1)
 有负有正：
 
      
       
        
         
          全
         
         
          部
         
         
          正
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          −
         
         
          （
         
         
          全
         
         
          部
         
         
          负
         
         
          整
         
         
          数
         
         
          之
         
         
          和
         
         
          ）
         
        
        
          全部正整数之和-（全部负整数之和） 
        
       
      全部正整数之和−（全部负整数之和）
 现在我们寻求一下全部的规律 
 最小数就是：
 
      
       
        
         
          最
         
         
          大
         
         
          值
         
         
          −
         
         
          最
         
         
          小
         
         
          值
         
         
          +
         
         
          所
         
         
          有
         
         
          正
         
         
          整
         
         
          数
         
         
          −
         
         
          所
         
         
          有
         
         
          负
         
         
          整
         
         
          数
         
        
        
          最大值-最小值+所有正整数-所有负整数 
        
       
      最大值−最小值+所有正整数−所有负整数 
 
java代码-谭方川 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int len = n + m + 1;
        double[] nums = new double[len];
        for (int i = 0; i < len; i++) {
            nums[i] = scanner.nextDouble();
        }
        Arrays.sort(nums);
        double res = 0;
        if (m == 0) {
            for (int i = 0; i < len; i++) {
                res += nums[i];
            }
        } else {
            res += nums[len - 1] - nums[0];
            for (int i = 1; i < len - 1; i++) {
                res += Math.abs(nums[i]);
            }
        }
        System.out.printf("%.0f", res);
    }
}
 
c++代码-王宇哲 
#include
using namespace std;
int main(){
	int n,m,z=0,f=0;
	cin>>n>>m;
	long long a[n+m+1];
	for(int i=0;i>a[i];
	}
	sort(a,a+n+m+1);
	long long sum=0;
	if(m){
		for(int i=1;i 
蓝桥杯 第十届真题 灵能传输（压轴题） 
 
 来自20044王宇哲 
 
题目 
在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。 
经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。 
你控制着 n 名高阶圣堂武士，方便起见标为 
    
     
      
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        ⋅
       
       
        ⋅
       
       
        ⋅
       
       
        ,
       
       
        n
       
      
      
       1,2,···,n
      
     
    1,2,⋅⋅⋅,n。 
每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai 表示其拥有的灵能的多少（
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai 点灵能，
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai 为负则表示这名高阶圣堂武士还需要 
    
     
      
       
        −
       
       
        
         a
        
        
         i
        
       
      
      
       −a_i
      
     
    −ai 点灵能才能到达最佳战斗状态）。 
现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个
    
     
      
       
        i
       
       
        ∈
       
       
        [
       
       
        2
       
       
        ,
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       i∈[2,n−1]
      
     
    i∈[2,n−1]，若 
    
     
      
       
        
         a
        
        
         i
        
       
       
        ≥
       
       
        0
       
      
      
       a_i≥0
      
     
    ai≥0 则其两旁的高阶圣堂武士，也就是
    
     
      
       
        i
       
       
        −
       
       
        1
       
       
        、
       
       
        i
       
       
        +
       
       
        1
       
      
      
       i−1、i+1
      
     
    i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai 点灵能；若 
    
     
      
       
        
         a
        
        
         i
        
       
       
        <
       
       
        0
       
      
      
       a_i<0
      
     
    ai<0 则其两旁的高阶圣堂武士，也就是 
    
     
      
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        i
       
       
        +
       
       
        1
       
      
      
       i−1,i+1
      
     
    i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 
    
     
      
       
        −
       
       
        
         a
        
        
         i
        
       
      
      
       −a_i
      
     
    −ai 点灵能。 
形式化来讲就是 
    
     
      
       
        
         a
        
        
         
          i
         
         
          −
         
         
          1
         
        
       
       
        +
       
       
        =
       
       
        
         a
        
        
         i
        
       
       
        ,
       
       
        
         a
        
        
         
          i
         
         
          +
         
         
          1
         
        
       
       
        +
       
       
        =
       
       
        
         a
        
        
         i
        
       
       
        ,
       
       
        
         a
        
        
         i
        
       
       
        −
       
       
        =
       
       
        2
       
       
        
         a
        
        
         i
        
       
      
      
       a_{i−1}+=a_i,a_{i+1}+=a_i,a_i−=2a_i
      
     
    ai−1+=ai,ai+1+=ai,ai−=2ai。 
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 
    
     
      
       
        m
       
       
        a
       
       
        
         x
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
       
        ∣
       
       
        
         a
        
        
         i
        
       
       
        ∣
       
      
      
       max_{i=1}^n|a_i|
      
     
    maxi=1n∣ai∣，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。 
输入格式 
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。 
接下来依次输入每一组询问。 
每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。 
接下来一行包含 n 个数 
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        ⋅
       
       
        ⋅
       
       
        ⋅
       
       
        ,
       
       
        
         a
        
        
         n
        
       
      
      
       a_1,a_2,···,a_n
      
     
    a1,a2,⋅⋅⋅,an。 
输出格式 
输出 T 行。 
每行一个整数依次表示每组询问的答案。 
数据范围 

    
     
      
       
        1
       
       
        ≤
       
       
        T
       
       
        ≤
       
       
        3
       
       
        ,
       
       
        3
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        300000
       
       
        ,
       
       
        ∣
       
       
        
         a
        
        
         i
        
       
       
        ∣
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       1≤T≤3,3≤n≤300000,|a_i|≤10^9
      
     
    1≤T≤3,3≤n≤300000,∣ai∣≤109,
 每个评测用例的限制如下： 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a7UBJSZm-1644222130872)(image/19_ba773c9e17-QQ截图20191205220735.png)] 
输入样例1： 
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
 
输出样例1： 
3
0
3
 
输入样例2： 
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
 
输出样例2： 
5
7
4
 
样例解释 
样例一
 对于第一组询问：
 对 2 号高阶圣堂武士进行传输操作后
    
     
      
       
        
         a
        
        
         1
        
       
       
        =
       
       
        3
       
       
        ，
       
       
        
         a
        
        
         2
        
       
       
        =
       
       
        2
       
       
        ，
       
       
        
         a
        
        
         3
        
       
       
        =
       
       
        1
       
      
      
       a_1=3，a_2=2，a_3=1
      
     
    a1=3，a2=2，a3=1。答案为 3。
 对于第二组询问：
 这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。 
题解 
 
 这题我们用前缀和来解答，令s为前缀和 
 则
      
       
        
         
          
           s
          
          
           0
          
         
         
          =
         
         
          0
         
         
          ,
         
         
          
           s
          
          
           n
          
         
         
          =
         
         
          
           s
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          
           a
          
          
           n
          
         
        
        
         s_0=0,s_n=s_{n-1}+a_n
        
       
      s0=0,sn=sn−1+an 
 （前缀和其实就是数列和） 
 1.假设
     
      
       
        
         
          a
         
         
          i
         
        
        
         >
        
        
         0
        
       
       
        a_i>0
       
      
     ai>0，现在以
     
      
       
        
         
          a
         
         
          i
         
        
       
       
        a_i
       
      
     ai作为中间值进行灵能传输，则：
 
      
       
        
         
          
           a
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
          =
         
         
          
           a
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          
           a
          
          
           i
          
         
         
         
          
           a
          
          
           i
          
         
         
          =
         
         
          
           a
          
          
           i
          
         
         
          −
         
         
          2
         
         
          a
         
         
          [
         
         
          i
         
         
          ]
         
         
         
          
           a
          
          
           
            i
           
           
            +
           
           
            1
           
          
         
         
          =
         
         
          
           a
          
          
           
            i
           
           
            +
           
           
            1
           
          
         
         
          +
         
         
          
           a
          
          
           i
          
         
         
        
        
          a_{i-1}=a_{i-1}+a_i\ a_i=a_i-2a[i]\ a_{i+1}=a_{i+1}+a_i\ 
        
       
      ai−1=ai−1+aiai=ai−2a[i]ai+1=ai+1+ai
 那么：
 
      
       
        
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
          =
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          
           a
          
          
           i
          
         
         
          =
         
         
          (
         
         
          原
         
         
          )
         
         
          
           s
          
          
           i
          
         
         
         
          
           s
          
          
           i
          
         
         
          =
         
         
          
           s
          
          
           i
          
         
         
          −
         
         
          
           a
          
          
           i
          
         
         
          =
         
         
          (
         
         
          原
         
         
          )
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
         
          
           s
          
          
           
            i
           
           
            +
           
           
            1
           
          
         
         
          =
         
         
          (
         
         
          原
         
         
          )
         
         
          
           s
          
          
           
            i
           
           
            +
           
           
            1
           
          
         
        
        
          s_{i-1}=s_{i-1}+a_i=(原)s_i\ s_i=s_i-a_i=(原)s_{i-1}\ s_{i+1}=(原)s_{i+1} 
        
       
      si−1=si−1+ai=(原)sisi=si−ai=(原)si−1si+1=(原)si+1
 这里我们发现，所谓的灵能传输其实就是将
     
      
       
        
         
          s
         
         
          i
         
        
        
         与
        
        
         
          s
         
         
          
           i
          
          
           −
          
          
           1
          
         
        
       
       
        s_i与s_{i-1}
       
      
     si与si−1进行交换罢了 
 我们要求最大的灵能
     
      
       
        
         
          a
         
         
          
           m
          
          
           a
          
          
           x
          
         
        
       
       
        a_{max}
       
      
     amax，其实就是
     
      
       
        
         
          s
         
         
          
           m
          
          
           a
          
          
           x
          
         
        
        
         −
        
        
         
          s
         
         
          
           m
          
          
           a
          
          
           x
          
          
           −
          
          
           1
          
         
        
       
       
        s_{max}-s_{max-1}
       
      
     smax−smax−1罢了，要使最大的灵能最小，其实就是让s按序排列罢了（这里要注意，
     
      
       
        
         
          s
         
         
          0
         
        
        
         与
        
        
         
          s
         
         
          n
         
        
       
       
        s_0与s_n
       
      
     s0与sn不能参与排序） 
 如果说，
     
      
       
        
         
          s
         
         
          0
         
        
        
         与
        
        
         
          s
         
         
          n
         
        
       
       
        s_0与s_n
       
      
     s0与sn也能参与正常排序交换的话，那么本题就已经结束了，答案就是
     
      
       
        
         m
        
        
         a
        
        
         x
        
        
         (
        
        
         
          s
         
         
          i
         
        
        
         −
        
        
         
          s
         
         
          
           i
          
          
           −
          
          
           1
          
         
        
        
         )
        
       
       
        max(s_i-s_{i-1})
       
      
     max(si−si−1)，但是事实上，最让人头疼的就是这个
     
      
       
        
         
          s
         
         
          0
         
        
        
         与
        
        
         
          s
         
         
          n
         
        
       
       
        s_0与s_n
       
      
     s0与sn 
  
  
  不能排序的原因： 
  在题目中，从
      
       
        
         
          
           a
          
          
           1
          
         
         
          −
         
         
          
           a
          
          
           n
          
         
        
        
         a_1-a_n
        
       
      a1−an之间，
      
       
        
         
          
           a
          
          
           1
          
         
         
          和
         
         
          
           a
          
          
           n
          
         
        
        
         a_1和a_n
        
       
      a1和an是不能参与灵能传输的，对应的前缀和（
      
       
        
         
          
           s
          
          
           0
          
         
         
          与
         
         
          
           s
          
          
           1
          
         
        
        
         s_0与s_1
        
       
      s0与s1）和（
      
       
        
         
          
           s
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          与
         
         
          
           s
          
          
           n
          
         
        
        
         s_{n-1}与s_n
        
       
      sn−1与sn）是不能进行交换的，换言之就是
      
       
        
         
          
           s
          
          
           0
          
         
         
          ,
         
         
          
           s
          
          
           n
          
         
        
        
         s_0,s_n
        
       
      s0,sn只能固定在首位不能交换 
  
 因此我们要思考一个方法解决这个序列非单调的问题 
 在此，我会举全部特例来解决这道题 
  
 第一种情况 
  
  假设我们目前已经将
      
       
        
         
          
           s
          
          
           1
          
         
         
          −
         
         
          
           s
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
        
        
         s_1-s_{n-1}
        
       
      s1−sn−1全部从那个小到大排好序了，而
      
       
        
         
          
           s
          
          
           0
          
         
         
          <
         
         
          
           s
          
          
           1
          
         
        
        
         s_0 
   
  
或者说是这样子的图像（因为这些是数，不是一段连续的函数）： 
   
  那么这个时候，很明显
      
       
        
         
          ∣
         
         
          
           a
          
          
           
            m
           
           
            a
           
           
            x
           
          
         
         
          ∣
         
        
        
         |a_{max}|
        
       
      ∣amax∣就是
      
       
        
         
          m
         
         
          a
         
         
          x
         
         
          (
         
         
          
           s
          
          
           i
          
         
         
          −
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
         
          )
         
         
          (
         
         
          i
         
         
          ∈
         
         
          [
         
         
          1
         
         
          ,
         
         
          n
         
         
          ]
         
         
          )
         
        
        
         max(s_i-s_{i-1})(iin[1,n])
        
       
      max(si−si−1)(i∈[1,n]) 
   
  
 第二种情况 
  
  还是先假设我们已经排好序了，但是
      
       
        
         
          
           s
          
          
           0
          
         
         
          >
         
         
          
           s
          
          
           1
          
         
         
          ,
         
         
          
           s
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          >
         
         
          
           s
          
          
           n
          
         
        
        
         s_0>s_1,s_{n-1}>s_n
        
       
      s0>s1,sn−1>sn 
  也就是说是如下图像： 
   
  或者也可以说是这样子： 
   
  这时候很明显的，这样排列肯定不是让
      
       
        
         
          
           s
          
          
           i
          
         
         
          −
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
        
        
         s_i-s_{i-1}
        
       
      si−si−1的最大值最小的排列情况 
  现在我们需要在这种排列情况下把这个数列构造成看起来连续性更强的样子，因为连续了才能保证
      
       
        
         
          
           s
          
          
           i
          
         
         
          −
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
        
        
         s_i-s_{i-1}
        
       
      si−si−1的值不会显得太大 
  也就是化成类似于这个形状： 
   
  (当然这不是一个真正连续的函数，我只是为了让图像直观性更强一些才化成了这样) 
  那如何变成这样子呢？ 
   
  我们过
      
       
        
         
          
           s
          
          
           0
          
         
        
        
         s_0
        
       
      s0和
      
       
        
         
          
           s
          
          
           n
          
         
        
        
         s_n
        
       
      sn分别作两条平行于x轴的直线
      
       
        
         
          
           l
          
          
           1
          
         
         
          ,
         
         
          
           l
          
          
           2
          
         
        
        
         l_1,l_2
        
       
      l1,l2（
      
       
        
         
          
           s
          
          
           0
          
         
         
          <
         
         
          
           s
          
          
           n
          
         
        
        
         s_0 
   
  
我们说了，这个图形其实就是一堆点（
      
       
        
         
          
           s
          
          
           0
          
         
         
          到
         
         
          
           s
          
          
           n
          
         
        
        
         s_0到s_n
        
       
      s0到sn），所以其实上面的变换就是这样的： 
  把下面这张图： 
   
  变化为下面这张： 
   
  你们看，这样子是不是看起来更连续了？这样子排列s中的各项以后，就基本能满足
      
       
        
         
          
           s
          
          
           i
          
         
         
          −
         
         
          
           s
          
          
           
            i
           
           
            −
           
           
            1
           
          
         
        
        
         s_i-s_{i-1}
        
       
      si−si−1的最大值最小 
  第三种 
  要是
      
       
        
         
          
           s
          
          
           0
          
         
         
          >
         
         
          
           s
          
          
           n
          
         
        
        
         s_0>s_n
        
       
      s0>sn怎么办?是不是就不满足上面的方法了？ 
  确实如此，那我们就将
      
       
        
         
          
           s
          
          
           0
          
         
         
          和
         
         
          
           s
          
          
           n
          
         
        
        
         s_0和s_n
        
       
      s0和sn换位置，其实也就相当于将整个数列按照从小到大的顺序改变成从大到小的顺序排列，这样还是满足上面的要求的 
  
 至此，这就是所有情况的解释了（语言表达能力太差了，说不明白请见谅） 
 
c++代码-王宇哲 
#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
int main(){
	int times;
	ll max1;
	ll a[N];	//存储灵能值
	ll s[N];	//存储前缀和
	ll b[N];	//存储排序完成后的前缀和
	bool c[N];	//当前下标前缀和是否排入b数组
	int n;
	cin>>times;
	while(times--){
		memset(c,false,sizeof(c));
		memset(s,0,sizeof(s));
		cin>>n;
		s[0]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			s[i]=s[i-1]+a[i];	//存储前缀和
		}
		//将首尾存储并定位
		ll s0=s[0];
		ll sn=s[n];
		if(s0>sn) swap(s0,sn);
		sort(s,s+n+1);	
        //寻找首元素排序后的位置（相当于画平行于x的直线，用于寻找比s[0]小的数集合）
		for(int i=0;i<=n;i++){
			if(s[i]==s0) {
				s0=i;
				break;	
			}
		}
        //寻找末元素排序后的位置（相当于画平行于x的直线，用于寻找比s[n]大的数集合）
		for(int i=0;i<=n;i++){
			if(s[i]==sn) {
				sn=i;
				break;	
			}
		}
        
		int l=0,r=n;
        //开始隔项取出，逆序排列，以增强整个数列连续性
		for(int i=s0;i>=0;i-=2){
			b[l++]=s[i],c[i]=true;
		}
		for(int i=sn;i<=n;i+=2){
			b[r--]=s[i],c[i]=true;
		}
        //将剩下的全部存入排列后的前缀和数组
		for(int i=0;i<=n;i++){
			if(!c[i]) b[l++]=s[i]; 
		} 
		max1=0;
        //寻找最大的a[i]
		for(int i=1;i<=n;i++) max1=max(max1,abs(b[i]-b[i-1]));
		cout< 
 
 如果还是看不懂可以去下面链接学习，我的理解方式跟网上主流理解方式并不一样，因为我认为网上的理解方式有理有据却难以咀嚼 
 下面是两个我认为讲的还不算太难理解的题解 
 https://www.acwing.com/solution/content/8433/ 
 https://www.acwing.com/solution/content/10886/ 
 
蓝桥杯 第十一届真题 子串分值和 
 
 20044王宇哲 
 
题目 
对于一个字符串 S，我们定义 S 的分值 
    
     
      
       
        f
       
       
        (
       
       
        S
       
       
        )
       
      
      
       f(S)
      
     
    f(S) 为 S 中出现的不同的字符个数。 
例如 
    
     
      
       
        f
       
       
        (
       
       
        “
       
       
        a
       
       
        b
       
       
        a
       
       
        ”
       
       
        )
       
       
        =
       
       
        2
       
       
        ，
       
       
        f
       
       
        (
       
       
        “
       
       
        a
       
       
        b
       
       
        c
       
       
        ”
       
       
        )
       
       
        =
       
       
        3
       
       
        ,
       
       
        f
       
       
        (
       
       
        “
       
       
        a
       
       
        a
       
       
        a
       
       
        ”
       
       
        )
       
       
        =
       
       
        1
       
      
      
       f(“aba”)=2，f(“abc”)=3,f(“aaa”)=1
      
     
    f(“aba”)=2，f(“abc”)=3,f(“aaa”)=1。 
现在给定一个字符串
    
     
      
       
        S
       
       
        [
       
       
        0..
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       S[0..n−1]
      
     
    S[0..n−1]（长度为 n），请你计算对于所有 SS 的非空子串 
    
     
      
       
        S
       
       
        [
       
       
        i
       
       
        .
       
       
        .
       
       
        j
       
       
        ]
       
       
        (
       
       
        0
       
       
        ≤
       
       
        i
       
       
        ≤
       
       
        j
       
       
        <
       
       
        n
       
       
        )
       
      
      
       S[i..j](0≤i≤j 
输入格式 
输入一行包含一个由小写字母组成的字符串 S。 
输出格式 
输出一个整数表示答案。 
数据范围 
对于 20% 的评测用例，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        10
       
      
      
       1≤n≤10
      
     
    1≤n≤10； 
对于 40% 的评测用例，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        100
       
      
      
       1≤n≤100
      
     
    1≤n≤100； 
对于 50% 的评测用例，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        1000
       
      
      
       1≤n≤1000
      
     
    1≤n≤1000； 
对于 60% 的评测用例，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        10000
       
      
      
       1≤n≤10000
      
     
    1≤n≤10000； 
对于所有评测用例，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        100000
       
      
      
       1≤n≤100000
      
     
    1≤n≤100000。 
输入样例： 
ababc
 
输出样例： 
28
 
样例解释 
子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3
 b    1
 ba   2
 bab  2
 babc 3
  a   1
  ab  2
  abc 3
   b  1
   bc 2
    c 1
 
题解 
 
 这题思维性比较强，但是如果考试的时候是在不会的话可以使用三重循环（即暴力枚举）来完成，这样子的话可以得到一定的分数（毕竟比赛就是以分数决定名次的嘛） 
 但是在这里，我们会介绍在网上出现的主流解法 
  
 思路 
 1.首先，我们下一个定义，如果说一个字符串中没有任何重复的字符，那么我们就称这个字符串为无重复字符串 
  
 2.我们认为对于每一个字符串，只有第一次在这个字符串中出现的字符才能为这个字符串中的无重复字符子串提供分值，即对其有贡献，举个例子，对于字符串“
     
      
       
        
         a
        
        
         b
        
        
         a
        
       
       
        aba
       
      
     aba”，它所能形成的无重复字符子串为“ab”，也就是第一次出现的“a”和第一次出现的“b”才能对这个无重复字符子串的分值有所贡献 
 可能这个例子还不足以我们来理解他那么我们举个长一点的例子： 
 对于字符串“
     
      
       
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
       
       
        ababa
       
      
     ababa”， 
 第一个字符
     
      
       
        
         “
        
        
         a
        
        
         ”
        
       
       
        “a”
       
      
     “a”能为子串
     
      
       
        
         “
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “a”，“ab”，“aba”，“abab”，“ababa”
       
      
     “a”，“ab”，“aba”，“abab”，“ababa”提供分值 
 第二个字符
     
      
       
        
         “
        
        
         b
        
        
         ”
        
       
       
        “b”
       
      
     “b”能为子串
     
      
       
        
         “
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “b”，“ab”，“ba”，“aba”，“bab”，“abab”，“baba”，“ababa”
       
      
     “b”，“ab”，“ba”，“aba”，“bab”，“abab”，“baba”，“ababa”提供分值 
 第三个字符
     
      
       
        
         “
        
        
         a
        
        
         ”
        
       
       
        “a”
       
      
     “a”能为子串
     
      
       
        
         “
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ,
        
        
         ”
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “a”，“ba”，“ab”，“bab”，“aba”,”baba”
       
      
     “a”，“ba”，“ab”，“bab”，“aba”,”baba”提供分值 
 第四个字符
     
      
       
        
         “
        
        
         b
        
        
         ”
        
       
       
        “b”
       
      
     “b”能为子串
     
      
       
        
         “
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “b”，“ab”，“ba”，“aba”
       
      
     “b”，“ab”，“ba”，“aba”提供分值 
 第五个字符
     
      
       
        
         “
        
        
         a
        
        
         ”
        
       
       
        “a”
       
      
     “a”能为子串
     
      
       
        
         “
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “a”，“ba”
       
      
     “a”，“ba”提供分值 
 最后将这些子串数量加起来，答案就是25 
  
 3.现在问题，就是如何找到每个字符能有贡献的子串数量 
 还是拿上面那个字符串举例子吧，以
     
      
       
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “ababa”
       
      
     “ababa”中的第一个
     
      
       
        
         b
        
       
       
        b
       
      
     b（也就是第二个字符）来举例子吧： 
 首先，毋庸置疑，对于以“b”（第二个字符）出发往后面的所有字符串，这个“b”都是对他们的分值有所贡献的，即这个“b”对其往后的每个字符串
     
      
       
        
         “
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “b”，“ba”，“bab”，“baba”
       
      
     “b”，“ba”，“bab”，“baba”，都是有贡献的 
 然后往前找，只要不是
     
      
       
        
         “
        
        
         b
        
        
         ”
        
       
       
        “b”
       
      
     “b”，那么他都可以与后面的字符串合成一个新的字符串，使得这个字符串是以第一个“b”（第二个字符）作为一个贡献的字符串，也就是说，在这题中，往前找到字符“a”，那么这个字符“a”又能和字符串
     
      
       
        
         “
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “b”，“ba”，“bab”，“baba”
       
      
     “b”，“ba”，“bab”，“baba”合成四个新的字符串
     
      
       
        
         “
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “ab”，“aba”，“abab”，“ababa”
       
      
     “ab”，“aba”，“abab”，“ababa” 
 那如果在字符串
     
      
       
        
         “
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “ababa”
       
      
     “ababa”前面又添加了一个字符
     
      
       
        
         “
        
        
         a
        
        
         ”
        
       
       
        “a”
       
      
     “a”,变成了
     
      
       
        
         “
        
        
         a
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “aababa”
       
      
     “aababa”，那么第一个
     
      
       
        
         “
        
        
         b
        
        
         ”
        
       
       
        “b”
       
      
     “b”(在这里变成了第三个字符串)，又可以与第一个字符串组出四个新的以这个“b”参与贡献分值的字符串
     
      
       
        
         “
        
        
         a
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         ”
        
        
         ，
        
        
         “
        
        
         a
        
        
         a
        
        
         b
        
        
         a
        
        
         b
        
        
         a
        
        
         ”
        
       
       
        “aab”，“aaba”，“aabab”，“aababa”
       
      
     “aab”，“aaba”，“aabab”，“aababa” 
 那么经过上面的分析，我们在计算某个字符的贡献值，先假设这个字符上一次出现的位置为
     
      
       
        
         l
        
       
       
        l
       
      
     l,这一次出现的位置为
     
      
       
        
         c
        
       
       
        c
       
      
     c,字符串总长度为
     
      
       
        
         s
        
       
       
        s
       
      
     s，那么当前字符的贡献值就是
     
      
       
        
         (
        
        
         c
        
        
         −
        
        
         i
        
        
         )
        
        
         ∗
        
        
         (
        
        
         s
        
        
         −
        
        
         c
        
        
         +
        
        
         1
        
        
         )
        
       
       
        (c-i)*(s-c+1)
       
      
     (c−i)∗(s−c+1) 
  
 至此分析完成（如果看不懂我真的就无能为力了。。。。我敲了好久的。。。） 
 
c++代码-王宇哲 
#include
using namespace std;
int main(){
	string s;
	cin>>s;
	int mark;	//每一次用来取当前字符上一次的标记位置
	long long sum=0;
	int book[27];
	memset(book,-1,sizeof(book));	//初始化为-1，意思是当前数都还未出现（因为字符串初始下标是0，如果字符串初始下标是1的话就初始化为0）
	for(int i=0;i 
 
 说实在代码还挺简单的，但是分析真的花了我好长时间，感觉自己就是个菜鸡 
 
蓝桥杯 第九届真题 测试次数 
题目 
x 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。 
各大厂商也就纷纷推出各种耐摔型手机。 
x 星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。 
x 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。 
塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 2 楼。 
如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指数 =7。 
特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 =0。 
如果到了塔的最高层第n 层扔没摔坏，则耐摔指数 =n。 
为了减少测试次数，从每个厂家抽样 3 部手机参加测试。 
如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？ 
输入格式 
一个整数 n，表示测试塔的高度。 
输出格式 
一个整数，表示最多测试多少次。 
数据范围 

    
     
      
       
        3
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        10000
       
      
      
       3≤n≤10000
      
     
    3≤n≤10000 
输入样例1： 
3
 
输出样例1： 
2
 
样例1解释 
手机 a 从2 楼扔下去，坏了，就把 b 手机从 1 楼扔；否则 a 手机继续 3 层扔下。 
输入样例2： 
7
 
输出样例2： 
3
 
样例2解释 
a 手机从 4 层扔，坏了，则下面有 3 层，b,c 两部手机 2 次足可以测出指数；若是没坏，手机充足，上面 5,6,7 三层 2 次也容易测出。 
题解 
 
 本来想着这道题应该是个二分查找的题目，直接计算
      
       
        
         
          l
         
         
          o
         
         
          
           g
          
          
           2
          
         
         
          N
         
        
        
         log_2N
        
       
      log2N,结果没有过。。。。分析了一下，他说有三个手机的意思是，摔碎了的就不能测试了，没摔碎的就还能测试 
 阿这…好难啊（绞尽脑汁） 
 没办法了，我们还是先推理一下吧 
  
 1层楼只要测试一次，2层楼要测试两次 
 接下来就没那么简单了： 
 3层楼我们先测试第二层，如果坏了就测试第一层，如果没坏就测试第三层，所以总共要测试2次 
 四层楼 
 4层楼我们先测试2层，如果没坏就测试第三层，如果坏了就测试第一层，如果第三层测试坏了就测试结束，如果没坏就要测第四层，所以总共加起来要测试3次，最多消耗两部手机，这里我们可以画个图： 
  
 其中靠左意思是摔碎了的情况，靠右是完好的情况，所以最少测试次数就是这个树的深度，最少需要手机数量是整个树中任意回路中左支数的最大值，同样的我们也能将图画成这样，意思是从第三层开始测试： 
  
  
 那么接下来我开始都用树状图表示测试次数咯 
  
 五层楼 
  
 或者： 
  
 很明显，虽然两种测试次数都是3次（深度为3），但是第一种是最优解，因为第一种只需要最多消耗一部手机就可以完成测试了 
 六层楼： 
  
 两种方案都可 
 七层楼 
  
 八层楼 
  
 我们先停一停，分析到这，找到什么规律没？（其实我还没找到规律） 
 那我们不妨先列举一下这些树的特点： 
 1、对于任何结点
      
       
        
         
          左
         
         
          支
         
         
          <
         
         
          父
         
         
          亲
         
         
          <
         
         
          右
         
         
          支
         
        
        
         左支<父亲<右支
        
       
      左支<父亲<右支 
 2、任意祖先到叶子的路径上，
      
       
        
         
          左
         
         
          支
         
         
          数
         
         
          量
         
         
          ≤
         
         
          3
         
        
        
         左支数量leq3
        
       
      左支数量≤3 
 3、1所在的结点一定在树的最左边（因为） 
  
 上面解法想到一半实在是想不下去了，有能力的可以自己试试 
 
解法1-数学问题 
 
 网上题解 
 仔细研究了网上的题解以后，发现他将这个问题转化成了一个数学的基本不等式问题，最后写出来的人脑复杂度，空间复杂度和时间复杂度都是无可挑剔的 
 首先，先把人家的公式放出来：
 
      
       
        
         
          (
         
         
          
           k
          
          
           3
          
         
         
          +
         
         
          5
         
         
          k
         
         
          )
         
         
          /
         
         
          6
         
         
          ≥
         
         
          n
         
        
        
          (k^3+5k)/6geq n 
        
       
      (k3+5k)/6≥n
 其中n是楼的层数 
 求出最小的满足上面式子的整数k就是题目的答案 
  
 接下来介绍这位博主是如何把一个计算机问题转化成一个数学问题的： 
 转化过程 
 首先说明一下，这位博主也是采用推理的方式求解的这道题，但是不同的是他是对手机数量进行推理的 
 只有一个手机 
 这很明显，在最坏的运气下，我们只能从1楼开始往上找，直到某一层摔碎了，那么运气最差肯定是要测试n次的（n是楼的层数） 
 所以：
 
      
       
        
         
          n
         
         
          ≤
         
         
          k
         
        
        
          nleq k 
        
       
      n≤k 
 有两个手机 
 好的，真正的头脑风暴才刚刚开始。。。。 
 现在我们手里有两部手机，相当于多了一次摔碎手机的机会，这样我们可以凭借运气减少一些扔手机的次数，这时候我们假设一下吧，最坏测试的次数是k，那么也就是说，无论我们耐摔指数是多少，我们都可以在k次测试找到耐摔指数 
  
 假设我们在第一次的时候，选择了
     
      
       
        
         
          i
         
         
          1
         
        
       
       
        i_1
       
      
     i1层扔手机，那么很不巧，碎了（运气还挺背），那么我们现在手里只有一个手机了吧，那么我们就只能从第一层开始网上逐个测试了吧 
 那么如果真的真的很不巧，我们手机的耐摔指数恰好就是
     
      
       
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
       
       
        i_1-1
       
      
     i1−1（老倒霉蛋了），那么我们总共要再进行
     
      
       
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
       
       
        i_1-1
       
      
     i1−1次测试才能求出手机的耐摔指数，那么我们求出来手机的耐摔指数总共扔了
     
      
       
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
        
         +
        
        
         1
        
        
         =
        
        
         
          i
         
         
          1
         
        
       
       
        i_1-1+1=i_1
       
      
     i1−1+1=i1次手机，虽说这个情况确实很倒霉，那也不一定是最糟糕的，因为我们刚刚已经假设最糟糕的测试次数是
     
      
       
        
         k
        
       
       
        k
       
      
     k，所以说，满足第一个式子
     
      
       
        
         
          i
         
         
          1
         
        
        
         ≤
        
        
         k
        
       
       
        i_1leq k
       
      
     i1≤k 
  
 那要是说，我们选择了第
     
      
       
        
         
          i
         
         
          1
         
        
       
       
        i_1
       
      
     i1层摔手机，但是运气略微好那么一丢丢，也就是说，我们第
     
      
       
        
         
          i
         
         
          1
         
        
       
       
        i_1
       
      
     i1层的时候，手机还没有碎，那么我们就还有两部手机进行挥霍了 
 那么这个时候，我们在第
      
       
        
         
          
           i
          
          
           2
          
         
        
        
         i_2
        
       
      i2层（
     
      
       
        
         
          i
         
         
          2
         
        
        
         >
        
        
         
          i
         
         
          1
         
        
       
       
        i_2>i_1
       
      
     i2>i1）再扔一次手机，结果这次碎了（没想到啊），那么我们又只好从
     
      
       
        
         
          i
         
         
          1
         
        
        
         +
        
        
         1
        
       
       
        i_1+1
       
      
     i1+1层开始往上一层层摔手机了，那么此时呢，又是很倒霉，恰好手机的耐摔指数是
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         1
        
       
       
        i_2-1
       
      
     i2−1，那么这个时候，我们就还要从
     
      
       
        
         
          i
         
         
          1
         
        
        
         +
        
        
         1
        
       
       
        i_1+1
       
      
     i1+1层测试到
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         1
        
       
       
        i_2-1
       
      
     i2−1层，那么就要测试
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         1
        
        
         −
        
        
         
          i
         
         
          1
         
        
       
       
        i_2-1-i_1
       
      
     i2−1−i1次，加上前面的两次测试，那么总共是测试了
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         
          i
         
         
          1
         
        
        
         +
        
        
         1
        
       
       
        i_2-i_1+1
       
      
     i2−i1+1次，当然的，当前情况也不是最惨的，所以可以得到公式
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
        
         ≤
        
        
         k
        
       
       
        i_2-i_1-1leq k
       
      
     i2−i1−1≤k 
  
 如果在第
     
      
       
        
         
          i
         
         
          2
         
        
       
       
        i_2
       
      
     i2层还是没有碎，那么我们就可以再选一层
     
      
       
        
         
          i
         
         
          3
         
        
       
       
        i_3
       
      
     i3进行测试，如果在这一层碎了，那么我们就要再测试
     
      
       
        
         
          i
         
         
          3
         
        
        
         −
        
        
         1
        
        
         −
        
        
         
          i
         
         
          2
         
        
       
       
        i_3-1-i_2
       
      
     i3−1−i2次了，那么加上前面测试的3次，总共测试了
     
      
       
        
         
          i
         
         
          3
         
        
        
         −
        
        
         
          i
         
         
          2
         
        
        
         +
        
        
         2
        
       
       
        i_3-i_2+2
       
      
     i3−i2+2次，同样的
     
      
       
        
         
          i
         
         
          3
         
        
        
         −
        
        
         
          i
         
         
          2
         
        
        
         +
        
        
         2
        
        
         ≤
        
        
         k
        
       
       
        i_3-i_2+2leq k
       
      
     i3−i2+2≤k 
  
 下面就不用列举了吧，我们直接推测就行了，所以说一直到选到了
     
      
       
        
         
          i
         
         
          k
         
        
       
       
        i_k
       
      
     ik层，第
     
      
       
        
         
          i
         
         
          k
         
        
       
       
        i_k
       
      
     ik层的式子就是
     
      
       
        
         
          i
         
         
          k
         
        
        
         −
        
        
         
          i
         
         
          
           k
          
          
           −
          
          
           1
          
         
        
        
         +
        
        
         k
        
        
         −
        
        
         1
        
        
         ≤
        
        
         k
        
       
       
        i_k-i_{k-1}+k-1leq k
       
      
     ik−ik−1+k−1≤k 
 我们把全部的式子列下来：
 
      
       
        
         
          
           i
          
          
           1
          
         
         
          ≤
         
         
          k
         
         
         
          
           i
          
          
           2
          
         
         
          −
         
         
          
           i
          
          
           1
          
         
         
          +
         
         
          1
         
         
          ≤
         
         
          k
         
         
         
          
           i
          
          
           3
          
         
         
          −
         
         
          
           i
          
          
           2
          
         
         
          +
         
         
          2
         
         
          ≤
         
         
          k
         
         
         
          
           i
          
          
           4
          
         
         
          −
         
         
          
           i
          
          
           3
          
         
         
          +
         
         
          3
         
         
          ≤
         
         
          k
         
         
         
          .
         
         
          .
         
         
          .
         
         
         
          
           i
          
          
           k
          
         
         
          −
         
         
          
           i
          
          
           
            k
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          (
         
         
          k
         
         
          −
         
         
          1
         
         
          )
         
         
          ≤
         
         
          k
         
         
        
        
          i_1leq k\ i_2-i_1+1leq k\ i_3-i_2+2leq k\ i_4-i_3+3leq k\ ...\ i_k-i_{k-1}+(k-1)leq k\ 
        
       
      i1≤ki2−i1+1≤ki3−i2+2≤ki4−i3+3≤k...ik−ik−1+(k−1)≤k
 好的现在我们式子就全部出来了，我们将所有方程加起来以消去多余的未知量:
 
      
       
        
         
          
           i
          
          
           1
          
         
         
          +
         
         
          
           i
          
          
           2
          
         
         
          −
         
         
          
           i
          
          
           1
          
         
         
          +
         
         
          
           i
          
          
           3
          
         
         
          −
         
         
          
           i
          
          
           2
          
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          
           i
          
          
           k
          
         
         
          −
         
         
          
           i
          
          
           
            k
           
           
            −
           
           
            1
           
          
         
         
          +
         
         
          1
         
         
          +
         
         
          2
         
         
          +
         
         
          .
         
         
          .
         
         
          .
         
         
          +
         
         
          (
         
         
          k
         
         
          −
         
         
          2
         
         
          )
         
         
          +
         
         
          (
         
         
          k
         
         
          −
         
         
          1
         
         
          )
         
         
          ≤
         
         
          k
         
         
          ∗
         
         
          k
         
        
        
          i_1+i_2-i_1+i_3-i_2+...+i_k-i_{k-1}+1+2+...+(k-2)+(k-1)leq k*k 
        
       
      i1+i2−i1+i3−i2+...+ik−ik−1+1+2+...+(k−2)+(k−1)≤k∗k
 化简得到：
 
      
       
        
         
          
           i
          
          
           k
          
         
         
          +
         
         
          
           
            k
           
           
            ∗
           
           
            (
           
           
            k
           
           
            −
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
          ≤
         
         
          
           k
          
          
           2
          
         
        
        
          i_k+frac{k*(k-1)}{2}leq k^2 
        
       
      ik+2k∗(k−1)≤k2
 由于最后一次是第k次扔手机，那么在最坏的情况下，我们会将所有层数都尝试过一遍，也就是说，
     
      
       
        
         
          i
         
         
          k
         
        
       
       
        i_k
       
      
     ik要取
     
      
       
        
         n
        
       
       
        n
       
      
     n最好,那么公式最后就变成了:
 
      
       
        
         
          n
         
         
          ≤
         
         
          
           
            k
           
           
            (
           
           
            k
           
           
            +
           
           
            1
           
           
            )
           
          
          
           2
          
         
        
        
          nleq frac{k(k+1)}{2} 
        
       
      n≤2k(k+1) 
 有三部手机 
 我们还是假设最坏的测试次数是
     
      
       
        
         T
        
       
       
        T
       
      
     T，而每一次选择层数时的最坏情况时要测试的次数为k 
  
 我们先假定已经选定了
     
      
       
        
         
          i
         
         
          1
         
        
       
       
        i_1
       
      
     i1层来摔手机，不巧，摔坏了，那么我们还有两部手机来测试第1层到第
     
      
       
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
       
       
        i_1-1
       
      
     i1−1层的耐摔指数，那么最坏的测试情况就是
     
      
       
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
        
         ≤
        
        
         
          
           k
          
          
           (
          
          
           k
          
          
           +
          
          
           1
          
          
           )
          
         
         
          2
         
        
       
       
        i_1-1leqfrac{k(k+1)}{2}
       
      
     i1−1≤2k(k+1)(用剩下的手机要测试
      
       
        
         
          
           i
          
          
           1
          
         
         
          −
         
         
          1
         
        
        
         i_1-1
        
       
      i1−1层),其中（
     
      
       
        
         k
        
        
         +
        
        
         1
        
        
         ≤
        
        
         T
        
       
       
        k+1leq T
       
      
     k+1≤T） 
  
 好，假定没有摔坏的话，那我们再往上选定
     
      
       
        
         
          i
         
         
          2
         
        
       
       
        i_2
       
      
     i2层（
     
      
       
        
         
          i
         
         
          2
         
        
        
         >
        
        
         
          i
         
         
          1
         
        
       
       
        i_2>i_1
       
      
     i2>i1）来测试，如果在
     
      
       
        
         
          i
         
         
          2
         
        
       
       
        i_2
       
      
     i2层摔坏了，但是我们依然有两部手机，所以此时最坏的测试情况数就是
     
      
       
        
         
          i
         
         
          2
         
        
        
         −
        
        
         
          i
         
         
          1
         
        
        
         −
        
        
         1
        
        
         ≤
        
        
         
          
           k
          
          
           (
          
          
           k
          
          
           +
          
          
           1
          
          
           )
          
         
         
          2
         
        
       
       
        i_2-i_1-1leqfrac{k(k+1)}{2}
       
      
     i2−i1−1≤2k(k+1),（
     
      
       
        
         k
        
        
         +
        
        
         1
        
        
         +
        
        
         1
        
        
         ≤
        
        
         T
        
       
       
        k+1+1leq T
       
      
     k+1+1≤T） 
  
 假定没有摔坏的话，那我们再往上选定
     
      
       
        
         
          i
         
         
          3
         
        
       
       
        i_3
       
      
     i3层（
     
      
       
        
         
          i
         
         
          3
         
        
        
         >
        
        
         
          i
         
         
          2
         
        
       
       
        i_3>i_2
       
      
     i3>i2）来测试，如果在
     
      
       
        
         
          i
         
         
          3
         
        
       
       
        i_3
       
      
     i3层摔坏了，但是我们依然有两部手机，所以此时最坏的测试情况数就是
     
      
       
        
         
          i
         
         
          3
         
        
        
         −
        
        
         
          i
         
         
          2
         
        
        
         −
        
        
         1
        
        
         ≤
        
        
         
          
           k
          
          
           (
          
          
           k
          
          
           +
          
          
           1
          
          
           )
          
         
         
          2
         
        
       
       
        i_3-i_2-1leqfrac{k(k+1)}{2}
       
      
     i3−i2−1≤2k(k+1),（
     
      
       
        
         k
        
        
         +
        
        
         1
        
        
         +
        
        
         1
        
        
         +
        
        
         1
        
        
         ≤
        
        
         T
        
       
       
        k+1+1+1leq T
       
      
     k+1+1+1≤T） 
 最后我们推出来的式子就是：
 
      
       
        
         
          
           i
          
          
           T
          
         
         
          −
         
         
          
           i
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            k
           
           
            (
           
           
            k
           
           
            +
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
          ,
         
         
          (
         
         
          k
         
         
          +
         
         
          T
         
         
          ≤
         
         
          T
         
         
          )
         
        
        
          i_T-i_{T-1}-1leqfrac{k(k+1)}{2},(k+Tleq T) 
        
       
      iT−iT−1−1≤2k(k+1),(k+T≤T) 
 式子全都列出来：
 
      
       
        
         
          
           i
          
          
           1
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            k
           
           
            (
           
           
            k
           
           
            +
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
          ,
         
         
          (
         
         
          k
         
         
          +
         
         
          1
         
         
          ≤
         
         
          T
         
         
          )
         
         
         
          
           i
          
          
           2
          
         
         
          −
         
         
          
           i
          
          
           1
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            k
           
           
            (
           
           
            k
           
           
            +
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
          ,
         
         
          (
         
         
          k
         
         
          +
         
         
          2
         
         
          ≤
         
         
          T
         
         
          )
         
         
         
          .
         
         
          .
         
         
          .
         
         
         
          
           i
          
          
           T
          
         
         
          −
         
         
          
           i
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            k
           
           
            (
           
           
            k
           
           
            +
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
          ,
         
         
          (
         
         
          k
         
         
          +
         
         
          T
         
         
          ≤
         
         
          T
         
         
          )
         
        
        
          i_1-1leqfrac{k(k+1)}{2},(k+1leq T)\ i_2-i_1-1leqfrac{k(k+1)}{2},(k+2leq T)\ ...\ i_T-i_{T-1}-1leqfrac{k(k+1)}{2},(k+Tleq T) 
        
       
      i1−1≤2k(k+1),(k+1≤T)i2−i1−1≤2k(k+1),(k+2≤T)...iT−iT−1−1≤2k(k+1),(k+T≤T)
 全部用K替换
 
      
       
        
         
          
           i
          
          
           1
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            T
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
         
          
           i
          
          
           2
          
         
         
          −
         
         
          
           i
          
          
           1
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            )
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
          
          
           2
          
         
         
         
          .
         
         
          .
         
         
          .
         
         
         
          
           i
          
          
           T
          
         
         
          −
         
         
          
           i
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          −
         
         
          1
         
         
          ≤
         
         
          
           
            (
           
           
            T
           
           
            −
           
           
            T
           
           
            )
           
           
            (
           
           
            T
           
           
            −
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            )
           
          
          
           2
          
         
        
        
          i_1-1leqfrac{T(T-1)}{2}\ i_2-i_1-1leqfrac{(T-2)(T-1)}{2}\ ...\ i_T-i_{T-1}-1leqfrac{(T-T)(T-(T-1))}{2} 
        
       
      i1−1≤2T(T−1)i2−i1−1≤2(T−2)(T−1)...iT−iT−1−1≤2(T−T)(T−(T−1))
 全部加起来：
 
      
       
        
         
          
           i
          
          
           T
          
         
         
          −
         
         
          T
         
         
          ≤
         
         
          
           
            [
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            ∗
           
           
            T
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            )
           
           
            ∗
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            3
           
           
            )
           
           
            ∗
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            )
           
           
            +
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            T
           
           
            )
           
           
            ∗
           
           
            (
           
           
            T
           
           
            −
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            )
           
           
            ]
           
          
          
           2
          
         
         
         
          =
         
         
          
           
            ∗
           
           
            [
           
           
            
             T
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            3
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            
             )
            
            
             2
            
           
           
            ]
           
           
            −
           
           
            [
           
           
            T
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            3
           
           
            )
           
           
            +
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            )
           
           
            ]
           
          
          
           2
          
         
         
         
          =
         
         
          
           
            [
           
           
            
             T
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            3
           
           
            
             )
            
            
             2
            
           
           
            +
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            +
           
           
            
             1
            
            
             2
            
           
           
            ]
           
           
            −
           
           
            [
           
           
            T
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            2
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            3
           
           
            )
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            .
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            (
           
           
            T
           
           
            −
           
           
            1
           
           
            )
           
           
            )
           
           
            +
           
           
            (
           
           
            T
           
           
            −
           
           
            T
           
           
            )
           
           
            ]
           
          
          
           2
          
         
         
         
          =
         
         
          
           
            
             
              T
             
             
              (
             
             
              T
             
             
              +
             
             
              1
             
             
              )
             
             
              (
             
             
              2
             
             
              T
             
             
              +
             
             
              1
             
             
              )
             
            
            
             6
            
           
           
            −
           
           
            [
           
           
            (
           
           
            T
           
           
            +
           
           
            1
           
           
            )
           
           
            T
           
           
            −
           
           
            
             
              T
             
             
              (
             
             
              T
             
             
              +
             
             
              1
             
             
              )
             
            
            
             2
            
           
           
            ]
           
          
          
           2
          
         
         
        
        
          i_T-Tleq frac{ [(T-1)*T+ (T-2)*(T-1)+(T-3)*(T-2)+......+(T-T)*(T-(T-1))]}{2}\=frac{* [T^2+(T-1)^2+ (T-2)^2+(T-3)^2+......+(T-(T-1))^2]-[T+(T-1)+(T-2)+(T-3)+......+(T-(T-1))]}{2}\=frac{ [T^2+(T-1)^2+ (T-2)^2+(T-3)^2+......+1^2]-[T+(T-1)+(T-2)+(T-3)......+(T-(T-1))+(T-T)]}{2}\= frac{frac{T(T+1)(2T+1)}{6}-[(T+1)T-frac{T(T+1)}{2}]}{2}\ 
        
       
      iT−T≤2[(T−1)∗T+(T−2)∗(T−1)+(T−3)∗(T−2)+......+(T−T)∗(T−(T−1))]=2∗[T2+(T−1)2+(T−2)2+(T−3)2+......+(T−(T−1))2]−[T+(T−1)+(T−2)+(T−3)+......+(T−(T−1))]=2[T2+(T−1)2+(T−2)2+(T−3)2+......+12]−[T+(T−1)+(T−2)+(T−3)......+(T−(T−1))+(T−T)]=26T(T+1)(2T+1)−[(T+1)T−2T(T+1)]
 由此可以推得：
 
      
       
        
         
          
           i
          
          
           T
          
         
         
          ≤
         
         
          
           
            
             T
            
            
             3
            
           
           
            +
           
           
            5
           
           
            K
           
          
          
           6
          
         
        
        
          i_Tleq frac{T^3+5K}{6} 
        
       
      iT≤6T3+5K
 最后把n代入：
 
      
       
        
         
          n
         
         
          ≤
         
         
          
           
            
             T
            
            
             3
            
           
           
            +
           
           
            5
           
           
            K
           
          
          
           6
          
         
        
        
          nleqfrac{T^3+5K}{6} 
        
       
      n≤6T3+5K 
 
 
 参考博客：测试次数（详解） 
 
c++代码 
#include
using namespace std;
int main(){
	int n;
	cin>>n;
	int num=1;
	int sum=1;
	while(1){
		sum=(num*num*num+5*num)/6;
		if(sum>=n)break;
		num++;
	}
	cout< 
剩下套公式就ok了 
解法2-递推 
 
 设
     
      
       
        
         f
        
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         )
        
       
       
        f(i,j)
       
      
     f(i,j)表示总共摔
     
      
       
        
         i
        
       
       
        i
       
      
     i次，在拥有
     
      
       
        
         j
        
       
       
        j
       
      
     j个手机的情况下，能到达的最大高度 
 开始时，
     
      
       
        
         f
        
        
         (
        
        
         1
        
        
         ,
        
        
         0
        
        
         )
        
        
         =
        
        
         0
        
       
       
        f(1,0)=0
       
      
     f(1,0)=0（没有手机当然测试不了），
     
      
       
        
         f
        
        
         (
        
        
         1
        
        
         ,
        
        
         j
        
        
         )
        
        
         =
        
        
         1
        
       
       
        f(1,j)=1
       
      
     f(1,j)=1(无论有多少部手机，只摔一次肯定只能测试到1的高度) 
 动态转移方程：
     
      
       
        
         f
        
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         )
        
        
         =
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         −
        
        
         1
        
        
         )
        
        
         +
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         )
        
        
         +
        
        
         1
        
       
       
        f(i,j)=f(i-1,j-1)+f(i-1,j)+1
       
      
     f(i,j)=f(i−1,j−1)+f(i−1,j)+1 
 表示的是当摔
     
      
       
        
         i
        
        
         −
        
        
         1
        
       
       
        i-1
       
      
     i−1次时，手机摔碎时能测到的最大的高度和手机没摔碎时能测得的最大高度之和，由于现在有两个情况，因为现在有一种情况手机还没摔碎（也就是
     
      
       
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         −
        
        
         1
        
        
         )
        
       
       
        f(i-1,j-1)
       
      
     f(i−1,j−1)）,所以至少还可以往上再去摔一层，所以要加一，因此我觉得动态转移方程应该写成这样： 
 
     
      
       
        
         f
        
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         )
        
        
         =
        
        
         [
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         −
        
        
         1
        
        
         )
        
        
         +
        
        
         1
        
        
         ]
        
        
         +
        
        
         f
        
        
         (
        
        
         i
        
        
         −
        
        
         1
        
        
         ,
        
        
         j
        
        
         )
        
       
       
        f(i,j)=[f(i-1,j-1)+1]+f(i-1,j)
       
      
     f(i,j)=[f(i−1,j−1)+1]+f(i−1,j) 
 
 
 参考博客：耐摔指数 
 
c++代码 
#include 
using namespace std;
const int N = 10010;
int n;
int f[4];
int main() {
    cin>>n;
    f[0] = 0;
    for (int i = 1; i <= 3; i++)
        f[i] = 1;

    int ans = 1;
    while (f[3] < n) {
        for (int i = 3; i >= 1; i--)
            f[i] = f[i] + f[i - 1] + 1;
        ans++;
    }
	cout< 
 
 这个好像简单多了对吗，但是我认为我考试想不到这个。。。因为比较难理解 
 
解法3-动态规划 
 
 我们先将题目抽象成一个数轴，，数轴的区间在
     
      
       
        
         [
        
        
         0
        
        
         ,
        
        
         1000
        
        
         ]
        
       
       
        [0,1000]
       
      
     [0,1000] 
 我们设
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
       
       
        dp[ind][cnt]
       
      
     dp[ind][cnt]为在长度为ind的区间上区间上，有
     
      
       
        
         c
        
        
         n
        
        
         t
        
       
       
        cnt
       
      
     cnt部手机，此时确定耐摔指数局部（
     
      
       
        
         [
        
        
         0
        
        
         ，
        
        
         i
        
        
         n
        
        
         d
        
        
         ]
        
       
       
        [0，ind]
       
      
     [0，ind]）最少次数 
 假设只有一部手机，那么只能从小到大一个个测试，也就是说
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         ]
        
        
         [
        
        
         1
        
        
         ]
        
        
         =
        
        
         i
        
        
         n
        
        
         d
        
       
       
        dp[ind][1]=ind
       
      
     dp[ind][1]=ind 
 那假如我们有两部手机？ 
 那么我们选择一层K,如果在K层碎了，那么问题就等价成拿一个手机搜索区间[0,k-1]的次数+1(这个1是在K层测试的那一次)，也就是
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         k
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         1
        
        
         ]
        
        
         +
        
        
         1
        
       
       
        dp[k-1][1]+1
       
      
     dp[k−1][1]+1 
 如果在K层没有碎，那么就等价于拿两个手机搜索区间[k+1,n]的次数+1,也就是
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         n
        
        
         −
        
        
         k
        
        
         −
        
        
         1
        
        
         +
        
        
         1
        
        
         ]
        
        
         [
        
        
         2
        
        
         ]
        
        
         +
        
        
         1
        
        
         =
        
        
         d
        
        
         p
        
        
         [
        
        
         n
        
        
         −
        
        
         k
        
        
         ]
        
        
         [
        
        
         2
        
        
         ]
        
        
         +
        
        
         1
        
       
       
        dp[n-k-1+1][2]+1=dp[n-k][2]+1
       
      
     dp[n−k−1+1][2]+1=dp[n−k][2]+1，当然，我们在次测试还是需要再选定一个在此区间中的楼层来进行搜索的，但是由于我们使用了动态规划，就没必要思考这么多东西了 
 那么实际上我们在选定K为测试楼层时，所需要搜索的次数就是两种情况的最大值（保险起见要选最大值） 
 但是假设我们楼层最高高度为
     
      
       
        
         i
        
        
         n
        
        
         d
        
       
       
        ind
       
      
     ind，而楼层最高为
     
      
       
        
         i
        
        
         n
        
        
         d
        
        
         −
        
        
         1
        
       
       
        ind-1
       
      
     ind−1时 
 用cnt部手机已经测出来需要的最少次数，那么此时只要再往上测试一次，即：
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
        
         +
        
        
         1
        
       
       
        dp[ind-1][cnt]+1
       
      
     dp[ind−1][cnt]+1,那么也就是说，要从这两种情况所需测试次数之中取最小值即可，即 
 
      
       
        
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          n
         
         
          d
         
         
          ]
         
         
          [
         
         
          c
         
         
          n
         
         
          t
         
         
          ]
         
         
          =
         
         
          M
         
         
          i
         
         
          n
         
         
          (
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          n
         
         
          d
         
         
          −
         
         
          1
         
         
          ]
         
         
          [
         
         
          c
         
         
          n
         
         
          t
         
         
          ]
         
         
          +
         
         
          1
         
         
          ,
         
         
          M
         
         
          a
         
         
          x
         
         
          (
         
         
          d
         
         
          p
         
         
          [
         
         
          k
         
         
          −
         
         
          1
         
         
          ]
         
         
          [
         
         
          c
         
         
          n
         
         
          t
         
         
          −
         
         
          1
         
         
          ]
         
         
          ,
         
         
          d
         
         
          p
         
         
          [
         
         
          i
         
         
          n
         
         
          d
         
         
          −
         
         
          k
         
         
          ]
         
         
          [
         
         
          c
         
         
          n
         
         
          t
         
         
          ]
         
         
          )
         
         
          )
         
        
        
         dp[ind][cnt]=Min(dp[ind-1][cnt]+1,Max(dp[k-1][cnt-1],dp[ind-k][cnt]))
        
       
      dp[ind][cnt]=Min(dp[ind−1][cnt]+1,Max(dp[k−1][cnt−1],dp[ind−k][cnt])) 
 如果没看懂的话，下面是原作者的解释： 
  
 解释一下 用Max函数和Min函数： 
 我们本意是写一个算法，实现对n是任何可能值的求解。 
 假设层数是6，2部手机，看图解： 
  
 结论：题目实际是求全局最优解——常用方法DP！ 
 DP：全局最优——>局部最优——>求动态转移方程 
 就是用动态规划的思想，去走遍所有所可能的情况，通过条件限制，求最小次数啦。 
 Max：最坏情况的判断，n=2是最好情况，可是如果这些手机耐摔指数 
 n=0，1，2，3，4，5，6呢！ 
 Min：最少次数的选择，情况虽然不妙！但是我们可以尽量少花力气去摔手机哇！ 
 选出确定
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
       
       
        dp[ ind ][ cnt ]
       
      
     dp[ind][cnt]需要的最小次数。 
 状态方程就这么总结出来啦！！！ 
 
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
        
         =
        
        
         M
        
        
         i
        
        
         n
        
        
         (
        
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
        
         +
        
        
         1
        
        
         ,
        
        
         1
        
        
         +
        
        
         M
        
        
         a
        
        
         x
        
        
         (
        
        
         d
        
        
         p
        
        
         [
        
        
         k
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         −
        
        
         1
        
        
         ]
        
        
         ,
        
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         n
        
        
         d
        
        
         −
        
        
         k
        
        
         ]
        
        
         [
        
        
         c
        
        
         n
        
        
         t
        
        
         ]
        
        
         )
        
        
         )
        
       
       
        dp[ind][cnt] = Min( dp[ind-1][cnt]+1 , 1+Max( dp[k - 1][cnt - 1] , dp[ ind-k ][ cnt ] ) )
       
      
     dp[ind][cnt]=Min(dp[ind−1][cnt]+1,1+Max(dp[k−1][cnt−1],dp[ind−k][cnt])) 
 作者：code木木 
 链接：https://www.jianshu.com/p/3f56a77ab96e 
  
 那么分析出来以后代码也就很简单了 
 
c++代码 
#include
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a 
历届试题 九宫幻方 
题目 
 
 18541谭琦，杨作青 
 
资源限制 
时间限制：1.0s 内存限制：256.0MB 
问题描述 
小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。 
三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。 
4 9 2
3 5 7
8 1 6
 
有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。 
而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~ 
输入格式 
输入仅包含单组测试数据。 
每组测试数据为一个3*3的矩阵，其中为0的部分表示被小明抹去的部分。
 　　对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。 
输出格式 
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。 
样例输入 
0 7 2
0 5 0
0 3 0
 
样例输出 
6 7 2
1 5 9
8 3 4
 
数据规模和约定 
峰值内存消耗（含虚拟机） < 256M 
CPU消耗 < 1000ms 
 
 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。 
 注意：
 　　main函数需要返回0;
 　　只使用ANSI C/ANSI C++ 标准;
 　　不要调用依赖于编译环境或操作系统的特殊函数。
 　　所有依赖的函数必须明确地在源文件中 #include 
 　　不能通过工程设置而省略常用头文件。 
 提交程序时，注意选择所期望的语言类型和编译器类型。 
  
 笨笨有话说：
 　　我最喜欢这类题目了。既然九宫幻方一共也没有多少，我就不辞辛劳地一个一个写出来好了。
 　　也不能太过分，好歹用个数组。 
 
题解 
思路一 
 
 简单来说，这就是一道深度优先搜索题 
 首先，题目中的九方格有这样一个性质：那就是横竖斜的每三个对角线之和一定是15 
 （所以如果你懒得思考就可以将九方格成立的八个条件手写出来） 
 然后就是枚举每一次填写数字的情况了 
 
c++代码-杨作青 
#include 
using namespace std;
int g[5][5], up[5][5];	//g是深搜过程中的九宫格，up是最后的结果的九宫格
int d[10], used[20];	//d存储空白格的坐标，used标记数是否已在九宫格之中了
int cnt, n;//cnt是找到的九宫格数量，n为未填入的格子的数量
bool check ()
{
    for (int i = 0;i < 3;i ++)	//判断每个行列是否成立
    {
        int sum1 = 0;
        int sum2 = 0;
        for (int j = 0;j < 3;j ++)
        {
            sum1 += g[i][j];
            sum2 += g[j][i];
        }
        if (sum1 % 15 != 0 || sum2 % 15 != 0) return false;	//不成立返回false
    }
    int sum1 = g[0][0] + g[1][1] + g[2][2];
    int sum2 = g[0][2] + g[1][1] + g[2][0];	//判断两个斜对角线之和是否为15
    if (sum1 % 15 != 0 || sum2 % 15 != 0) return false;
    return true;
}
void dfs (int u)
{
    if (u > n)	//如果全部的空都已经填满
    {
        if (check())	//如果满足九方格的性质
        {
            memcpy (up, g, sizeof g);	//将这次深搜的结果放入up（后续的输出数组）中
            cnt ++;	//找到的九宫格数加一
        }       
        return;
    }
    for (int i = 1;i <= 9;i ++)
    {
        int x = d[u] / 3, y = d[u] % 3;	//将一维的坐标转化回x,y坐标
        if (g[x][y] == 0 && !used[i])	//如果当前格子还未使用
        {
            g[x][y] = i;	//将数字填入
            used[i] = 1;	//将该数标记
            dfs (u + 1);	//往后深搜
            g[x][y] = 0;	//回溯
            used[i] = 0;
        }
    }
}
int main()
{
    int k = 0;
    for (int i = 0;i < 3;i ++)
        for (int j = 0;j < 3;j ++)
        {
            cin >> g[i][j];
            if (g[i][j] != 0)	//输入的值不为零就标记当前的数已经在九宫格之中了
            {
                used[g[i][j]] = 1;	
            }
            else
            {
                d[++k] = i * 3 + j;		//降维存储，用一维方式存储二维九方格的坐标
                n ++;	//未使用的数加一
            }
        }
    dfs (1);	//如果深搜结束后且只有唯一解，那么就输出九方格，否则输出Too Many
    if (cnt == 1)
    {
        for (int i = 0;i < 3;i ++)
        {
            for (int j = 0;j < 3;j ++)
            {
                cout << up[i][j] << " ";
            }
            puts ("");
        }
    }
    else cout << "Too Many";
    
    return 0;
}
 
c++代码-谭琦（改） 
 
 Tips: 
 next_premutation(&a,&b) 函数：求出一段内存空间上的数的全排列，操作为将数组变为下一种排列组合的方式,这也是为什么先要从小到大排序后才能产生全排列，返回值为往后的排列情况的数量，实现原理为深搜，但是其算法时间复杂度过高，不建议在数据范围太大的题目上使用 
 
#include
using namespace std;

int a[20][20],b[20][20],c[20][20],vis[20];
int t[10],len,cnt;
int judge()	//判断当前九方格是否满足要求
{
    int sum = a[1][1]+a[1][2]+a[1][3];
    if(a[2][1]+a[2][2]+a[2][3]!=sum||a[3][1]+a[3][2]+a[3][3]!=sum||a[1][1]+a[2][2]+a[3][3]!=sum||a[1][3]+a[2][2]+a[3][1]!=sum||a[1][1]+a[2][1]+a[3][1]!=sum||a[1][2]+a[2][2]+a[3][2]!=sum||a[1][3]+a[2][3]+a[3][3]!=sum)return  0;
    return 1;
}
void copy()	//复制九宫格 
{
	for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            c[i][j]=a[i][j];
    }
}
void pr()	//输出九宫格
{
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            cout<>a[i][j];b[i][j]=a[i][j];
            if(a[i][j])vis[a[i][j]]=1;	//如果当前数不为0就标记当前数已经存在九方格之中
        }
    }
    for(int i=1;i<=9;i++)if(!vis[i])t[len++]=i;	//如果当前数还未使用就存储到t数组之中以备后续使用
    sort(t,t+len);	//将数进行排序（可以不需要，因为上面已经按序排列了）
    while(next_permutation(t,t+len)){
        if(cnt>=2)return cout<<"Too Many"< 
思路二 
 
 看了这么久，大家真的了解九方格了吗？ 
 这里我将介绍一下九宫格的来源： 
 首先看这样一个方阵： 
 1 2 3 
 4 5 6 
 7 8 9 
 1 2 3
4 5 6
7 8 9
 我们将整个方阵顺时针旋转45度，就得到： 
 4 1 2
7 5 3
8 9 6
 再把各对角交换一下，得到： 
 6 1 8
7 5 3
2 9 4
 现在我们就得到一个基本九方阵了，这还有个口诀： 
  
  九宫之义， 
  法以灵龟， 
  二四为肩， 
  六八为足， 
  左七右三， 
  戴九履一， 
  五居中央。 
  
 (这是我玩一个探案游戏中学到的，我还有好多算法也是在那上面学到的，嘻嘻~) 
  
 所有的九方阵都是根据上面那个九方阵旋转或者对称变换得到的，那么这就简单了，我们只要把所有方阵列出来再比较就行了，那么总共就只有8种填写方法，时间复杂度一下子降低到了常数级 
 
c++代码-王宇哲 
#include
using namespace std;
int ans;
int b[3][3];
int c[3][3];
int a[8][3][3]={
	{
		{4,9,2},
		{3,5,7},
		{8,1,6}
	},{
		{8,1,6},
		{3,5,7},
		{4,9,2}
	},{
		{6,1,8},
		{7,5,3},
		{2,9,4}
	},{
		{2,9,4},
		{7,5,3},
		{6,1,8}
	},{
		{6,7,2},
		{1,5,9},
		{8,3,4}
	},{
		{8,3,4},
		{1,5,9},
		{6,7,2}
	},{
		{2,7,6},
		{9,5,1},
		{4,3,8}
	},{
		{4,3,8},
		{9,5,1},
		{2,7,6}
	}
};
void copy(int z){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			c[i][j]=a[z][i][j];	
		}	
	}
}
int main(){
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cin>>b[i][j];
	for(int z=0;z<8;z++){
		int is=1;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(b[i][j]!=0){
					if(b[i][j]!=a[z][i][j]) is=0;
				}	
			}	
		}
		if(is==1){
			copy(z);	
			ans++;
		} 
	}
	if(ans==1){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				cout< 
 
 打表很费劲，所以不太推荐最后一个，但是依然是可以使用原矩阵旋转来生成其余的方阵的，因此这题解法有很多 
 
总结 
 
 1.在蓝桥杯比赛之中，不是只有全对才能拿分，即使只通过部分样例依然可以拿分，所以不要纠结于一道题目，可以先用暴力算法提交，有时间再回来看 
 2.蓝桥杯一般只有最后两道题会涉及到数据结构，其他的基本是简单算法知识 
 3.近几年蓝桥杯的算法中，前缀和，日期计算，字符串处理，递推，递归考察比较频繁规范，可以优先从这些方面下手 
 
参与贡献 
 
 参与代码贡献的同学： 
 18541 谭方川 
 18541 谭琦 
 18541 杨作青 
 18541 杨奕 
 19043 耿莉芳

蓝桥杯题目汇编

Java相关栏目本月热门文章