/*———————————————————————————————————————————————————————————【结果填空题】T1题目：啤酒和饮料啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。注意：答案是一个整数。请通过浏览器提交答案。不要书写任何多余的内容（例如：写了饮料的数量，添加说明文字等）。————————————————————————————————————————————————————————————*///C++//思路：枚举#include
     
      using namespace std ;int main(){    for(int i = 1; i <= 50; ++i)    {        for (int j = 1; j <= 60; ++j)        {            if(2.3*i+1.9*j==82.3 && i
      
       using namespace std ;int main(){    return 0 ;}/*找规律条数：2  3  5  9  17   .... 1014+1折数：0  1  2  3  4    .... 10 *//*———————————————————————————————————————————————————————————【结果填空题】T3题目：李白打酒话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。————————————————————————————————————————————————————————————*///深搜#include
       
        using namespace std ;int ans ;void f(int dian,int hua,int jiu){    if(dian==0 && hua==0 && jiu==1) ans++ ;    if(dian>0) f(dian-1,hua,jiu*2) ;    if(hua>0) f(dian,hua-1,jiu-1) ;}int main(){    f(5,9,2) ;    cout << ans << endl ;    return 0 ;}/*———————————————————————————————————————————————————————————【代码填空题】T4题目：史丰收速算史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!速算的核心基础是：1位数乘以多位数的乘法。其中，乘以7是最复杂的，就以它为例。因为，1/7 是个循环小数：0.142857...，如果多位数超过 142857...，就要进1同理，2/7, 3/7, ... 6/7 也都是类似的循环小数，多位数超过 n/7，就要进n下面的程序模拟了史丰收速算法中乘以7的运算过程。乘以 7 的个位规律是：偶数乘以2，奇数乘以2再加5，都只取个位。乘以 7 的进位规律是：满 142857... 进1,满 285714... 进2,满 428571... 进3,满 571428... 进4,满 714285... 进5,满 857142... 进6请分析程序流程，填写划线部分缺少的代码。 ——————————————————————————————————————————————————————————*/#include
        
         using namespace std ;//计算个位 int ge_wei(int a){    if(a % 2 == 0) //偶数        return (a * 2) % 10; //乘以2保留个位    else //奇数        return (a * 2 + 5) % 10; //乘以2加上5保留个位}//计算进位 int jin_wei(char* p) //计算进位{    char* level[] = {        "142857",        "285714",        "428571",        "571428",        "714285",        "857142"    };//如果多位数超过n/7，就要进n        char buf[7];    buf[6] = '\0';    strncpy(buf,p,6); //将p这个字符串，拷贝到buff中        int i;    for(i=5; i>=0; i--){        int r = strcmp(level[i], buf); //从后往前，一次level中的串和buff比较        if(r<0) return i+1; //buf更大，得出进位数=i+1         while(r==0){ //buf和level[i]相同            p += 6; //往后偏移6位            strncpy(buf,p,6); //再拷贝6个字符到buf中            r = strcmp(level[i], buf); //再比较            if(r<0) return i+1;  //buf更大            /*此处为代码填空处            //buf更小            if(r>0)            {                return i ; //                 //测试：cout << i << " " << endl ;            }            */        }    }        return 0;}//多位数乘以7void f(char* s) //s代表多位数{    int head = jin_wei(s); //head是s的进位    if(head > 0) printf("%d", head); //输出进位        char* p = s; //拷贝字符串指针    while(*p){ //没有到末尾        int a = (*p-'0'); //依次取字符转数字        int ge = ge_wei(a) ; //算出个位        int x = (ge_wei(a) + jin_wei(p+1)) % 10;        printf("%d",x); //打印        p++; //指针后移    }        printf("\n");}int main(){    f("428571428571");    f("34553834937543");            return 0;}/*———————————————————————————————————————————————————————————【代码填空题】T5题目：打印图形小明在X星球的城堡中发现了如下图形和文字：rank=3   *   * *  *   *  * * * *rank=5               *                                                                    * *                                                                  *   *                                                                * * * *                                                              *       *                                                            * *     * *                                                          *   *   *   *                                                        * * * * * * * *                                                      *               *                                                    * *             * *                                                  *   *           *   *                                                * * * *         * * * *                                              *       *       *       *    * *     * *     * *     * *   *   *   *   *   *   *   *   * * * * * * * * * * * * * * * * *  ran=6                               *                                                                    * *                                                                  *   *                                                                * * * *                                                              *       *                                                            * *     * *                                                          *   *   *   *                                                        * * * * * * * *                                                      *               *                                                    * *             * *                                                  *   *           *   *                                                * * * *         * * * *                                              *       *       *       *                                            * *     * *     * *     * *                                          *   *   *   *   *   *   *   *                                        * * * * * * * * * * * * * * * *                                      *                               *                                    * *                             * *                                  *   *                           *   *                                * * * *                         * * * *                              *       *                       *       *                            * *     * *                     * *     * *                          *   *   *   *                   *   *   *   *                        * * * * * * * *                 * * * * * * * *                      *               *               *               *                    * *             * *             * *             * *                  *   *           *   *           *   *           *   *                * * * *         * * * *         * * * *         * * * *              *       *       *       *       *       *       *       *            * *     * *     * *     * *     * *     * *     * *     * *          *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *        * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *                                                                                 小明开动脑筋，编写了如下的程序，实现该图形的打印。————————————————————————————————————————————————————————————*///C++#include
         
          #define N 70void f(char a[][N], int rank, int row, int col) //设置限制和格式{    if(rank==1){        a[row][col] = '*';        return;    }        int w = 1;    int i;    for(i=0; i
          
           using namespace std ;int ans ;int gcd(int a,int b) //最大公约数{ if(b==0) return a ; return gcd(b,a%b) ; //辗转相除}int main(){ cput << gcd(12,16) << endl ; for (int a = 1; a < 10; ++a) { for (int b = 1; b < 10; ++b) { if(b==a) continue ; for (int c = 1; c < 10; ++c) { for (int d = 1; d < 10; ++d) { if(c == d) continue ; int g1 = gcd(a*c,b*d) ; int g2 = gcd(a*10+c,b*10+d) ; if(a*c/g1==(a*10+c)/g2 && b*d/g1==(b*10+d)/g2) { printf("%d %d %d %d\n",a,b,c,d) ; ans++ ; } } } } } cout << ans << endl ; return 0 ;}/*———————————————————————————————————————————————————————————【结果填空题】T7标题：六角填数如图【1.png】所示六角形中，填入1~12的数字。 (1) (8) () () () (*) () () () () () (3) 使得每条直线上的数字之和都相同。图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？————————————————————————————————————————————————————————————*///C++/*思路：*/#include
           
            #include
            
             using namespace std ;void check(vector
             
               v)int main(){ vector
              
                v ; v.push_back(2) ; for (int i = 4; i <= 7; ++i) { v.push_back(i) ; } for (int i = 9; i <= 12; ++i) { v.push_back(i) ; } do{ check(v) ; }while(next_permutation(v.begin(),v.end())) ; return 0 ;}void check(vector
               
                 y){ int r1 = 1 + v[0]+v[3]+v[5] ; int r2 = 1 + v[1]+v[4]+v[8] ; int r3 = 8 + v[0]+v[1]+v[2] ; int r4 = 11 + v[3]+v[6] ; int r5 = 3 + v[2] + v[4] + v[7] ; int r6 = v[5] + v[6] + v[7] + v[8] ; if(r1 == r2 && r2 == r3 && r3 ==r4 && r4 == r5 && r5 == r6) { for (int i = 0; i < 0; ++i) { cout << v[3] << " " << endl ; } }}/*———————————————————————————————————————————————————————————T-8标题：蚂蚁感冒 长100厘米的细长直杆子上有n只蚂蚁。 它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。 并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。【数据格式】 第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。 接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。 正值表示头朝右，负值表示头朝左，数据中不会出现0值， 也不会出现两只蚂蚁占用同一位置。 其中，第一个数据代表的蚂蚁感冒了。 要求输出1个整数，表示最后感冒蚂蚁的数目。例如，输入：35 -2 8程序应输出：1再例如，输入：5-10 8 -20 12 25程序应输出：3资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include 
                
                 ， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。————————————————————————————————————————————————————————————*//*同向蚂蚁：前面的追不上反向蚂蚁：相遇*///C++#include
                 
                  using namespace std ;int main(){ //输入 int n ; scanf("%d",&n) ; int arr[n] ; //数组存放数据 //搜索 for (int i = 0; i < n; ++i) { scanf("%d",&arr[i]) ; } //定义蚂蚁位置 int x = arr[0] ; if(x>0) //向右 { int ans = 1 ; //感冒的蚂蚁 //扫描所有蚂蚁 for (int i = 0; i < n; ++i) { if(arr[i]<0 && -arr[i]>x) //从右向左 ans++ ; } if(ans!=1) //有从右向左的 for (int i = 0; i < n; ++i) { //找跟在后面的 if(arr[i]>0 && arr[i]
                  
                   0 && arr[i]<-x) ans++ ; if(ans!=1) for (int i = 0; i < n; ++i) { if(arr[i]<0 && -arr[i]>-x) ans++ ; } printf("%d\n",ans) ; return 0 ; }}/*———————————————————————————————————————————————————————————【代码编程题】T9标题：地宫取宝X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。【数据格式】 输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12) 代表这个格子上的宝物的价值 要求输出一个整数，表示正好取k个宝贝的行动方案数。 该数字可能很大，输出它对 1000000007 取模的结果。例如，输入：2 2 21 22 1程序应该输出：2再例如，输入：2 3 21 2 32 1 5程序应该输出：14资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include 
                   
                    ， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。————————————————————————————————————————————————————————————*///地宫取宝//深搜 递归取模#include
                    
                     #include
                     
                      using namespace std ;const int MOD = 10000007 ;int n,m,k ; //int data[50][50] ;long long ans ;long long cache[50][50][14][13]void dfs(int x,int y,int max,int cnt){ if(x==n || y==m || cnt > k) //cnt > k 剪枝 return ; int cur = data[x][y] ; if(x==n-1 && y == m-1) //已经面临最后一个格子 { if(cnt==k || (cnt==k-1 && cur>max)) { ans++ ; if(ans>MOD) ans%=MOD ; } }//记忆型递归long long dfs2(int x,int y,int max,int cnt){ //查缓存 if(cache[x][y][max+1][cnt]!=-1) return cache[x][y][max+1][cnt] ; long long ans = 0 ; if(x==n || y==m || cnt > k) //cnt > k 剪枝 return ; int cur = data[x][y] ; if(x==n-1 && y == m-1) //已经面临最后一个格子 { if(cnt==k || (cnt==k-1 && cur>max)) { ans++ ; if(ans>MOD) ans%=MOD ; } }} if(cur > max)//可以取这个物品 { ans += dfs(x,y+1,cur,cnt+1) ; ans += dfs(x+1,y,cur,cnt+1) ; } //对于价值较小，或者价值大但不去这个物品的情况如下 ans += dfs(x,y+1,max,cnt) ; ans += dfs(x+1,y,max,cnt) ; ans += dfs2(x,y + 1,cur,cnt) ; ans += dfs2(x + 1,y,max,cnt) ; //写缓存 return ans % MOD ;}int main(){ scanf("%d %d %d",&n,&m,&k) ; // // for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d",&data[i][j]) ; } } dfs(0,0,-1,0) ; //第一个点的价值可能是0 dfs2(0,0,-1,0) ;// memset(cache,-1,sizeof) ; printf("%d\n",dfs2(0,0,-1,0)) ; return 0 ;}/*解决重复子问题的求解：动态规划：记忆性递归 *//*———————————————————————————————————————————————————————————【代码编程题】T10标题：小朋友排队n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。【数据格式】输入的第一行包含一个整数n，表示小朋友的个数。第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。例如，输入：33 2 1程序应该输出：9【样例说明】首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。【数据规模与约定】 对于10%的数据， 1<=n<=10； 对于30%的数据， 1<=n<=1000； 对于50%的数据， 1<=n<=10000； 对于100%的数据，1<=n<=100000，0<=Hi<=1000000。资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include 
                      
                       ， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。————————————————————————————————————————————————————————————*////*1. 前缀和数组(静态数组)2. 树状数组 C[k] (某个区间的和)[k-lowbi(k),x]lowbit(k)是k进制中最后一个1代表的整数B(6)->b(10)C6 sum(4,6)index 改动为 index + lowbit(index) *//** * 原始数组的i位置增加v后，更新C数组 * n 边界 * i 初始值 * v * c*///树状数组的模板#include
                       
                        #include
                        
                         int lowbit(int k){ return n-(n&(n-1)) ; }void updata(int,int i,int v,int[]c){ //int lb = Lowbit(i) ; for (int k = i; k <= n; k+=Lowbit(k)) { c[k] += v ; }}int getSum(int c[],int i){ int sum = 0 ; for (int k = i; k >= 1; k-=lowbit(k)) { sum+=c[k] ; } return sum ;}int main(int argc, char const *argv[]){ int arr[] = { 1,2,3,4,5,6,7,8} ; int c[9] ; for (int i = 0; i < 8; ++i) { updata(9,i+1,arr[i],c) ; } cout << getSum(c,5) << endl ; cout << getSum(c,6) << endl ; cout << getSum(c,7) - getSum(c,4) << endl ; return 0;}//解/*3 2 1 | 2 3 1 | 2 1 3 | 1 2 3 | for 对每一位右侧更小1. h ——> 树状数组的下标2. a ——> 计数 //按顺序为身高计数 如3加入 则a[3] = 1 由此统计sum3=1 证明<=3的个数为12加入 sum2 =1 总数=2说明此前加入且比2大的个数为11加入 sum1=1 总数=3说明此前加入且比1大的个数为1*/#include 
                         
                          #include 
                          
                           #include 
                           
                            using namespace std;int lowbit(int n) { return n - (n & (n - 1));}/** * 原始数组的i位置增加v后，更新c数组 * @param i * @param v * @param c */void updata(int n, int i, int v, int c[]) { for (int k = i; k <= n; k += lowbit(k)) { c[k] += v; }}int getSum(int c[], int i) { int sum = 0; for (int k = i; k >= 1; k -= lowbit(k)) { sum += c[k]; } return sum;}int h[100000];long long cnt[100000];//记录每个孩子的交换次数int c[1000000 + 1];int main(int argc, const char *argv[]) {// int arr[]={1,2,3,4,5,6,7,8};// int c[9];// memset(c,0, sizeof(c));// for (int i = 0; i < 8; ++i) {// updata(9,i+1,arr[i],c);// }// cout<
                            
                             <
                             
                               maxH)maxH = h[i]; } for (int i = 0; i < n; ++i) { updata(maxH + 1, h[i] + 1, 1, c);//在响应位置计数变为1，其实就是用树状数组维护数据出现的个数 // int sum = getSum(c, h[i] + 1);//小于等于h[i]+1的数据的个数 cnt[i] += (i + 1) - sum;//得到的就是当前数据左侧比数据大的数的个数 } memset(c, 0, sizeof(c)); for (int i = n - 1; i >= 0; --i) { updata(maxH + 1, h[i] + 1, 1, c); //在响应位置计数变为1，其实就是用树状数组维护数据出现的个数// int sum = getSum(c, h[i] + 1);//小于等于h[i]+1的数据的个数// int self = getSum(c,h[i]+1)-getSum(c,h[i]);// cnt[i] += sum-self;//上一步求出小于等于h的个数，扣掉自己的个数，得到的就是当前数据右侧比数据小的数的个数 cnt[i] += getSum(c, h[i]);//求出小于h[i]+1 的数据的个数 } long long ans = 0; for (int i = 0; i < n; ++i) { ans += (cnt[i] * (cnt[i] + 1) / 2); } printf("%lli\n", ans); return 0;}/************************************************************* * 【2014年省赛B组小结】 * 01【结果填空】啤酒与饮料：简单枚举 * * 02【结果填空】切面条：思维，归纳，找规律 * * 03【结果填空】李白打酒：递归所有的解 * * 04【代码填空】史丰收速算： * * 05【代码填空】打印图形：递归 整体思维 * * 06【代码填空】奇怪的分式：枚举+最大公约数 * * 07【结果填空】六角填数：全排列 * * 08【编程题】蚂蚁感冒：思维(穿过身体) * * 09【编程题】地宫取宝：搜索->记忆性递归 * * 10【编程题】小朋友排队：树状数组 * *****************************************************/