• 备战 清华大学 上机编程考试-冲刺前50%,倒数第5天

    T1：多项式求和

    小K最近刚刚习得了一种非常酷炫的多项式求和技巧，可以对某几类特殊的多项式进行运算。非常不幸的是，小K发现老师在布置作业时抄错了数据，导致一道题并不能用刚学的方法来解，于是希望你能帮忙写一个程序跑一跑。给出一个 m 阶多项式\(f(x)=∑mi=0bixi\)对给定的正整数 a ，求\(S(n)=∑nk=0akf(k)\)由于这个数可能比较大，所以你只需计算 S(n) 对 109+7 取模后的值（即计算除以 109+7 后的余数）。

    解：

    涉及到：a*b整数相乘的优化， a^n的优化，

    多项式的计算-一个for循环，

    自然数的幂次求和公式-数学推导

    1. #include<iostream>
    2. #include<vector>
    3. #include<algorithm>
    4. #include<string>
    5. #include<stdio.h>
    6. #include<stdlib.h>
    7.  
    8. using namespace std;
    9. //计算多项式的值的题目：
    10.  
    11. //“轩轩”前辈的代码非常值得学习，故而尝试 自己 默记着 尝试复写
    12.  
    13. long long int n,m,a;
    14. long long int mod = 1e9+7;
    15. long long int *b;  //作为数组，之后可以开辟空间
    16.  
    17. //处理输入的函数:
    18. void init_input()
    19. {
    20.     //给上述变量赋值 和 处理b0 - bn
    21.     cin>>n>>m>>a;
    22.     b = new  long long int[m+1];
    23.     for(int i = 0 ;i<=m ;i++)
    24.     {
    25.         cin>>b[i];
    26.     }
    27. }
    28.  
    29. //处理 （a*b)%mod 的快速算法：
    30. long long multiply(long long a,long long b , long long mod)
    31. {
    32.     long long ans = 0;
    33.     //我觉得这里还可以优化：让b是那个小的数
    34.     if(b > a)
    35.     {
    36.         long long tmp = b;
    37.         b = a;
    38.         a = tmp;
    39.     }
    40.  
    41.     while(b > 0)
    42.     {
    43.         if(b&1 != 0)
    44.         {
    45.             //b是一个奇数:
    46.             ans = (ans + a)%mod;
    47.         }
    48.         a = (a<<1 ) % mod;
    49.         b = b>>1;
    50.     }
    51.     return ans;
    52. }
    53.  
    54.  
    55. //处理 a^n次方的 快速算法：
    56. long long power(long long a, long long n , long long mod)
    57. {
    58.     long long ans = 1 ;
    59.     //计算a的n次方:
    60.  
    61.     while(n > 0 )
    62.     {
    63.         if(n&1 != 0)
    64.         {
    65.             //奇数:
    66.             ans = multiply(ans,a,mod);
    67.         }
    68.         n = n>>1;
    69.         ans = multiply(ans,ans,mod);
    70.     }
    71.     return ans;
    72. }
    73.  
    74.  
    75. //计算 f(k) 的结果:
    76. long long func(long long x)
    77. {
    78.     long long ans = 0;
    79.     //而且，我觉得可以改进一点， 求x的i次方，可以用到x的i-1次方
    80.     long long tmp = 1;
    81.     for(long long  i = 0 ; i<=m ;i++)
    82.     {
    83.         ans = (ans + multiply(tmp,b[i],mod))%mod;
    84.         tmp = multiply(tmp,x,mod) % mod ; 
    85.     }
    86.     return ans;
    87. }
    88.  
    89.  
    90.  
    91. //最后，计算S(n)的求和结果
    92. long long Sum()
    93. {
    94.     long long ans = 0;
    95.     
    96.     //改进：保留 a的k-1次方的结果:
    97.     long long tmp = 1;
    98.     for(long long  i = 0 ; i<=n ;i++)
    99.     {
    100.         ans = (ans + multiply(func(i),tmp,mod))%mod;
    101.         tmp = (multiply(tmp,a,mod))%mod;
    102.  
    103.     }
    104.     return ans;
    105. }
    106.  
    107.  
    108. int main()
    109. {
    110.  
    111.     //处理输入：
    112.     // int n,m,a;
    113.     // cin>>n>>m>>a;
    115.     // vector<int> vec(m+1,0);
    116.     // for(int i= 0; i<= m; i++)
    117.     // {
    118.     //     cin>>vec[i];
    119.     // }
    120.     
    121.     //朴素一点的方法进行计算——先做一个垃圾出来：
    122.     //第一步：需要一个计算f(k) % mod
    123.     //第二步：再计算S（n）
    124.  
    125.     //可以改进的地方：
    126.     //1.(a*b)%mod 可以利用 2的幂次 以及 左移，右移优化
    127.     //2.计算a^k次方， 可以利用 2的幂次进行优化
    128.     //其他的话，暂时就只能那样子了
    129.  
    130.     init_input();
    131.     cout<<Sum()<<endl;
    132.  
    133.     //虽然，样例9 和 样例10 我肯定是做不出来的，
    134.     //但是，只要过了一些样例，就有分，为啥不干脆 “针对样例编程”？
    135.     //要有针对性！ -- 得分为王
    136.     
    137.     //第一：针对 a = 1的情况， —— 只要算f(k)求和即可
    138.     //这里一定有更加高效的计算-可以合并 - 分治等
    139.     //目前我的想法只有合并:
    140.     if(a == 1)
    141.     {
    142.         //但是如果要开辟一个10^9次方的数组的话，开辟不了
    143.         //nice，合并之后，感觉因为m很小，复杂度可以降低到O（n）
    144.         //甚至，只要知道1次求和，2次求和，3次求和，4次求和公式。。。。妙！
    145.         //参考：https://www.bilibili.com/read/cv11243219/
    146.         //这个问题就是 “自然数”幂等和问题：
    147.         //根据这个参考文章，基本就可以搞定所有a=1的case了
    148.         //数学的美妙就在其中，而清华，必然是招收能够体会数学之美的学生
    149.         //这里以m=2 , a =1 那个测试用例进行写代码：
    150.         if(a == 1 && m==2)
    151.         {   //别忘了 0 的 0次方是 1
    152.             long long sum = (b[0]*(n+1) %mod+b[1]*(n*(n+1)/2)%mod+ b[2]*(n*(n+1)*(2*n+1)/6)%mod)%mod;
    153.             cout<<sum<<endl;
    154.         }
    155.  
    156.     }
    157.  
    158.  
    159.  
    160.     return 0 ;
    161. }
    T2：葱的战争--模拟题

    一个n乘m的棋盘，上面有k根葱，每根葱面朝方向为d（0123分别表示上下左右），没跟葱一个战斗力f。每隔时间葱会向面朝方向走一格，如果遇到棋盘边界，那么他将把面朝方向转180度（此回合葱不会走动），如果某个时刻有两个或以上的葱在同一位置，那么他们将发生战争，只有战斗力最高的葱存活，其他的葱全部原地枯萎，不在走动，求经过t时间后所有葱的位置

    输入：第一行n m k，然后接下来k行每根葱的信息x y d f（坐标，方向，战斗力），最后一行输入时间t 输出：k行，分别表示每个葱的位置。 数据范围：n和m在100内，k在1000内，t在1000内，f在1000内，保证初始每颗葱位置不同，战斗力不同。

    解：

    结合之前的开发经验，这一题和 “贪吃蛇”的项目基本类似：

    直接使用 模拟的思想，——关键是记录 board[][]和 snake里面的数据：

    测试用例：

    1. 输入：
    2. 5 4 2
    3. 1 1 3 10
    4. 3 1 2 5
    5. 3
    6. 输出：
    7. 4 1 
    8. 2 1

    1. #include<iostream>
    2. #include<string>
    3. #include<vector>
    4. #include<stdio.h>
    5. #include<stdlib.h>
    6.  
    7. using namespace std;
    8.  
    9. struct cong
    10. {
    11.     int x;
    12.     int y;
    13.     int d;
    14.     int f;
    15.     //尝试写一个默认构造函数：
    16.     cong()
    17.     {
    18.         this->x =0;
    19.         this->y =0;   
    20.         this->d =0;
    21.         this->f =0;
    22.     }
    23. };
    24.  
    25. int n,m,k;
    26. int t;
    27.  
    28. //算了，如果是二维数组的话，我还是老老实实的用int a[100][100]
    29. //或者vector<vector<int> > vec(n,vector<int>(m,0))这种
    30.  
    31. int main()
    32. {
    33.     //这个就是一个简单的 模拟题目 搞定即可:
    34.     //最关键一个点可能就是 数据如何存储的问题
    35.     //处理输入 和 存储结构
    36.     cin>>n>>m>>k;
    37.     cong arr[1001];
    38.  
    39.     int flag[1001]; //用于记录这根是否存活，只有flag==0时，才需要更新
    40.                     //cong的下标是从1开始用的
    41.     for(int i = 1;i <=k ;i++) //arr从1开始用！！！cong的下标
    42.     {
    43.         cin>>arr[i].x>>arr[i].y>>arr[i].d>>arr[i].f;
    44.     }
    45.     cin>>t;
    47.     //直接模拟t个时间-for循环-立即更新board数据 和 arr数据
    48.     for(int i=1;i <=t ;i++)
    49.     {
    50.         //这里，设置一个board二维矩阵，nxm位置初始为0
    51.         //之后，每次更新一个 活着的cong，在更新后的那里写上cong的下标
    52.         //如果原来那个位置有非0的下标——>战斗->f小的那个flag设置为1，
    53.         //坐标范围(0-n-1,0-m-1)
    54.         //到达边界，下一个回合进行扭转，扭转也算做一步
    55.  
    56.         int board[101][101]; // 下标从0开始用，我估计是
    57.         //调用
    58.         for(int j = 1; j<=k;j++)
    59.         {
    60.             if(flag[j] != 0)
    61.             {
    62.                 continue; //这根cong已经 不活了
    63.             }
    64.             //--否则进行更新：
    65.  
    66.             //上：
    67.             if(arr[j].d == 0)
    68.             {
    69.                 //是否到达上边界:
    70.                 if(arr[j].y == m-1) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同
    71.                 {
    72.                     //修改arr[j].d即可
    73.                     arr[j].d = 1;
    74.                     //--判断board同一个位置是否需要战斗
    75.                     if(board[arr[j].x][arr[j].y] != 0 )
    76.                     {
    77.                         //战斗:
    78.                         int index = board[arr[j].x][arr[j].y];
    79.                         if(arr[j].f > arr[index].f)
    80.                         {
    81.                             // j留下
    82.                             board[arr[j].x][arr[j].y] = j;
    83.                             flag[index] = 1;
    84.                         }
    85.                         else{
    86.                             // index留下
    87.                             flag[j] = 1;//阵亡
    88.                         }
    89.                     }
    90.                     else{
    91.                         //在board上面占一个坑位，等其他人过来
    92.                         board[arr[j].x][arr[j].y] = j;
    93.                     }
    94.                 }
    95.                 else{
    96.                     //向上移动1格:
    97.                     arr[j].y +=1;
    98.                     //--判断board同一个位置是否需要战斗
    99.                     if(board[arr[j].x][arr[j].y] != 0 )
    100.                     {
    101.                         //战斗:
    102.                         int index = board[arr[j].x][arr[j].y];
    103.                         if(arr[j].f > arr[index].f)
    104.                         {
    105.                             // j留下
    106.                             board[arr[j].x][arr[j].y] = j;
    107.                             flag[index] = 1;
    108.                         }
    109.                         else{
    110.                             // index留下
    111.                             flag[j] = 1;//阵亡
    112.                         }
    113.                     } 
    114.                     else{
    115.                         //在board上面占一个坑位，等其他人过来
    116.                         board[arr[j].x][arr[j].y] = j;
    117.                     }
    118.  
    119.                 }
    120.             }
    121.  
    122.             //下：
    123.             else if(arr[j].d == 1)
    124.             {
    125.                 //是否到达下边界:
    126.                 if(arr[j].y == 0) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同
    127.                 {
    128.                     //修改arr[j].d即可
    129.                     arr[j].d = 0;
    130.                     //--判断board同一个位置是否需要战斗
    131.                     if(board[arr[j].x][arr[j].y] != 0 )
    132.                     {
    133.                         //战斗:
    134.                         int index = board[arr[j].x][arr[j].y];
    135.                         if(arr[j].f > arr[index].f)
    136.                         {
    137.                             // j留下
    138.                             board[arr[j].x][arr[j].y] = j;
    139.                             flag[index] = 1;
    140.                         }
    141.                         else{
    142.                             // index留下
    143.                             flag[j] = 1;//阵亡
    144.                         }
    145.                     }
    146.                     else{
    147.                         //在board上面占一个坑位，等其他人过来
    148.                         board[arr[j].x][arr[j].y] = j;
    149.                     }
    150.                 }
    151.                 else{
    152.                     //向下移动1格:
    153.                     arr[j].y -=1;
    154.                     //--判断board同一个位置是否需要战斗
    155.                     if(board[arr[j].x][arr[j].y] != 0 )
    156.                     {
    157.                         //战斗:
    158.                         int index = board[arr[j].x][arr[j].y];
    159.                         if(arr[j].f > arr[index].f)
    160.                         {
    161.                             // j留下
    162.                             board[arr[j].x][arr[j].y] = j;
    163.                             flag[index] = 1;
    164.                         }
    165.                         else{
    166.                             // index留下
    167.                             flag[j] = 1;//阵亡
    168.                         }
    169.                     } 
    170.                     else{
    171.                         //在board上面占一个坑位，等其他人过来
    172.                         board[arr[j].x][arr[j].y] = j;
    173.                     }
    174.  
    175.                 }
    176.             }
    177.  
    178.  
    179.             //左：
    180.             else if(arr[j].d == 2)
    181.             {
    182.                 //是否到达上边界:
    183.                 if(arr[j].x == 0) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同
    184.                 {
    185.                     //修改arr[j].d即可
    186.                     arr[j].d = 3;
    187.                     //--判断board同一个位置是否需要战斗
    188.                     if(board[arr[j].x][arr[j].y] != 0 )
    189.                     {
    190.                         //战斗:
    191.                         int index = board[arr[j].x][arr[j].y];
    192.                         if(arr[j].f > arr[index].f)
    193.                         {
    194.                             // j留下
    195.                             board[arr[j].x][arr[j].y] = j;
    196.                             flag[index] = 1;
    197.                         }
    198.                         else{
    199.                             // index留下
    200.                             flag[j] = 1;//阵亡
    201.                         }
    202.                     }
    203.                     else{
    204.                         //在board上面占一个坑位，等其他人过来
    205.                         board[arr[j].x][arr[j].y] = j;
    206.                     }
    207.                 }
    208.                 else{
    209.                     //向左移动1格:
    210.                     arr[j].x -=1;
    211.                     //--判断board同一个位置是否需要战斗
    212.                     if(board[arr[j].x][arr[j].y] != 0 )
    213.                     {
    214.                         //战斗:
    215.                         int index = board[arr[j].x][arr[j].y];
    216.                         if(arr[j].f > arr[index].f)
    217.                         {
    218.                             // j留下
    219.                             board[arr[j].x][arr[j].y] = j;
    220.                             flag[index] = 1;
    221.                         }
    222.                         else{
    223.                             // index留下
    224.                             flag[j] = 1;//阵亡
    225.                         }
    226.                     } 
    227.                     else{
    228.                         //在board上面占一个坑位，等其他人过来
    229.                         board[arr[j].x][arr[j].y] = j;
    230.                     }
    231.  
    232.                 }
    233.             }
    234.  
    235.  
    236.             //右：
    237.             else if(arr[j].d == 3)
    238.             {
    239.                 //是否到达上边界:
    240.                 if(arr[j].x == n-1) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同
    241.                 {
    242.                     //修改arr[j].d即可
    243.                     arr[j].d = 2;
    244.                     //--判断board同一个位置是否需要战斗
    245.                     if(board[arr[j].x][arr[j].y] != 0 )
    246.                     {
    247.                         //战斗:
    248.                         int index = board[arr[j].x][arr[j].y];
    249.                         if(arr[j].f > arr[index].f)
    250.                         {
    251.                             // j留下
    252.                             board[arr[j].x][arr[j].y] = j;
    253.                             flag[index] = 1;
    254.                         }
    255.                         else{
    256.                             // index留下
    257.                             flag[j] = 1;//阵亡
    258.                         }
    259.                     }
    260.                     else{
    261.                         //在board上面占一个坑位，等其他人过来
    262.                         board[arr[j].x][arr[j].y] = j;
    263.                     }
    264.                 }
    265.                 else{
    266.                     //向右移动1格:
    267.                     arr[j].x +=1;
    268.                     //--判断board同一个位置是否需要战斗
    269.                     if(board[arr[j].x][arr[j].y] != 0 )
    270.                     {
    271.                         //战斗:
    272.                         int index = board[arr[j].x][arr[j].y];
    273.                         if(arr[j].f > arr[index].f)
    274.                         {
    275.                             // j留下
    276.                             board[arr[j].x][arr[j].y] = j;
    277.                             flag[index] = 1;
    278.                         }
    279.                         else{
    280.                             // index留下
    281.                             flag[j] = 1;//阵亡
    282.                         }
    283.                     } 
    284.                     else{
    285.                         //在board上面占一个坑位，等其他人过来
    286.                         board[arr[j].x][arr[j].y] = j;
    287.                     }
    288.  
    289.                 }
    290.             }
    291.  
    292.         }
    293.     }
    294.     
    295.     //输出k行，也就是最后的k根cong的位置
    296.     for(int i =1 ;i<=k ;i++)
    297.     {
    298.         cout<<arr[i].x<<" "<<arr[i].y<<endl;
    299.     }
    300.  
    301.     return 0;
    302. }
     T3:路径个数

    有n个点，每个点有一个权值，每两点间的不同边的个数为他们权值相与得到的值的二进制数字中的1的个数（边为有向边，有第i指向第j，i小于j）求第1个点到第n个点的路径个数（当且仅当不止一条边不同才被称为两条不同的路径），由于数据很大，对991247取模。

    输入：第1行n，第二行分别试每个点权值 输出：路径个数 数据范围:n在2e5内，权值大小在1e9内

    解：

    （1）补充：库中的使用示例：

    1. #include <iostream>
    2. #include <bitset>
    3.  
    4. int main() {
    5.     // 定义一个包含8位的bitset，初始化所有位为0
    6.     std::bitset<8> bitset1;
    7.     
    8.     // 通过下标赋值
    9.     bitset1[0] = 1; // 设置第一位为1
    10.     bitset1[3] = 1; // 设置第四位为1
    11.     
    12.     // 输出bitset
    13.     std::cout << "Bitset1: " << bitset1 << std::endl; // 输出可能是 "00010010"
    14.     
    15.     // 通过整数初始化
    16.     std::bitset<8> bitset2(7); // 二进制表示为 00000111
    17.     
    18.     std::cout << "Bitset2: " << bitset2 << std::endl; // 输出 "00000111"
    19.     
    20.     // 通过字符串初始化
    21.     std::bitset<8> bitset3("10101010");
    22.     
    23.     std::cout << "Bitset3: " << bitset3 << std::endl; // 输出 "10101010"
    24.     
    25.     // 访问和修改
    26.     std::cout << "Third bit of bitset3: " << bitset3.test(2) << std::endl; // 输出1，因为第三位是1
    27.     bitset3.flip(2); // 翻转第三位
    28.     std::cout << "After flipping third bit: " << bitset3 << std::endl; // 输出可能是 "10101000"
    29.     
    30.     // 操作
    31.     std::bitset<8> bitset4("11110000");
    32.     std::cout << "Bitset4 & bitset2: " << (bitset4 & bitset2) << std::endl; // 位与操作
    33.     std::cout << "Bitset4 | bitset2: " << (bitset4 | bitset2) << std::endl; // 位或操作
    34.     std::cout << "Bitset4 ^ bitset2: " << (bitset4 ^ bitset2) << std::endl; // 位异或操作
    35.     
    36.     return 0;
    37. }

    （2）更正参考解法：

    1. //路径：
    2. #include<iostream>
    3. #include<algorithm>
    4. #include<vector>
    5. #include<string>
    6. #include<stdio.h>
    7. #include<stdlib.h>
    8.  
    9. using namespace std;
    10.  
    11. //不要想那么多，置之死地而后生，对得起自己的money和精力即可，结果不要管他
    12. //成为一个正在的编程算法强者，用思考力证明自己，这东西到哪都很有用！
    13. //这一题很有意思，关键当然是 如何计算 “权值 与运算 后，二进制1的个数”
    14. vector<int> power;
    15. int n;
    16.  
    17. void init()
    18. {
    19.     cin>>n;
    20.     for(int i = 0;i<n ;i++)
    21.     {
    22.         int tmp;
    23.         cin>>tmp;
    24.         power.push_back(tmp);
    25.     }
    26. }
    27.  
    28. //写一个函数：输入2个整数， 输出 计算出1的个数:
    29. //注意：调用bitset库 和 不调用库实现：
    30. int count1(int a,int b)
    31. {
    32.     int ans = 0 ;
    33.     int tmp = a&b;
    34.     while(tmp>0)
    35.     {
    36.         if(tmp&1 !=0)  // 或者 tmp%2 == 1
    37.         {
    38.             ans++;
    39.         }
    40.         tmp = tmp>>1;
    41.     }
    42.     return ans;
    43.  
    44. }
    45.  
    46. //第二个关键点：让我想起了 罗文寒 的那个 5=1+1+1+1+1的个数那个，递归思想
    47.  
    48. //这一题我不太能接受，我给一个测试用例吧，如果对了还好，不对就自己再想一个：
    49. //果然，就是有问题 —— 估计是题目给错了，不过，那我不如将错就错的写一写
    50. int calc(int n )
    51. {
    52.     if(n == 1)
    53.     {
    54.         return 2;
    55.     }
    56.     else{
    57.         return 2+calc(n-1)*2;
    58.     }
    59. }
    60.  
    61. //我的解法的测试用例：其中i与j之间都是2条路:
    62. int calc2(int i , int j)
    63. {
    64.     if( i == j )
    65.     {
    66.         return 1;
    67.     }
    68.     else{
    69.         int ans = 0;
    70.         for(int k = i+1; k<=j ;k++)
    71.         {
    72.             ans =(ans + 2*calc2(k,j))%991127;
    73.         }
    74.         return ans;
    75.  
    76.     }
    77. }
    78.  
    79. //下面这个是作为 该题答案
    80. int mycalc(int i , int j)
    81. {
    82.     //i是小的那个起点 ， j是大的那个终点：
    83.     //递归出口:
    84.     if( i == j)
    85.     {
    86.         return 1;
    87.     }
    88.     else
    89.     {
    90.         int ans = 0;
    91.         for(int k = i+1; k<=j ;k++)
    92.         {
    93.             ans =(ans + count1(power[i],power[k])*mycalc(power[k],power[j]))%991127;
    94.         }
    95.         return ans;
    96.     }
    97.  
    98. }
    99.  
    100.  
    101. int main()
    102. {
    103.     cout<<calc(3)<<endl;       //输出14 -不对
    104.     cout<<calc2(0,3)<<endl;    //输出18 -这才对
    105.  
    106.     return 0;
    107. }

  • 相关阅读:
    Andorid UNIX SOCKET c代码进程和java代码进程之间通讯
    Flutter高仿微信-视频演示
    屏幕录像推荐：Apeaksoft Screen Recorder 中文 for mac
    去中心化应用的终极是应用链？
    全局大喇叭--广播机制
    什么Vue单文件组件（SFC）?
    【Python】python常用用法细节（1）
    截取url地址后面参数方法
    RestCloud ETL WebService数据同步到本地
    Zookeeper环境搭建
  • 原文地址：https://blog.csdn.net/xiao_ZHEDA/article/details/139550137