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

T1：多项式求和

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

解：

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

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

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<stdlib.h>using namespace std;
//计算多项式的值的题目：//“轩轩”前辈的代码非常值得学习，故而尝试 自己 默记着 尝试复写long long int n,m,a;
long long int mod = 1e9+7;
long long int *b;  //作为数组，之后可以开辟空间//处理输入的函数:
void init_input()
{//给上述变量赋值 和 处理b0 - bncin>>n>>m>>a;b = new  long long int[m+1];for(int i = 0 ;i<=m ;i++){cin>>b[i];}
}//处理 （a*b)%mod 的快速算法：
long long multiply(long long a,long long b , long long mod)
{long long ans = 0;//我觉得这里还可以优化：让b是那个小的数if(b > a){long long tmp = b;b = a;a = tmp;}while(b > 0){if(b&1 != 0){//b是一个奇数:ans = (ans + a)%mod;}a = (a<<1 ) % mod;b = b>>1;}return ans;
}//处理 a^n次方的 快速算法：
long long power(long long a, long long n , long long mod)
{long long ans = 1 ;//计算a的n次方:while(n > 0 ){if(n&1 != 0){//奇数:ans = multiply(ans,a,mod);}n = n>>1;ans = multiply(ans,ans,mod);}return ans;
}//计算 f(k) 的结果:
long long func(long long x)
{long long ans = 0;//而且，我觉得可以改进一点， 求x的i次方，可以用到x的i-1次方long long tmp = 1;for(long long  i = 0 ; i<=m ;i++){ans = (ans + multiply(tmp,b[i],mod))%mod;tmp = multiply(tmp,x,mod) % mod ; }return ans;
}//最后，计算S(n)的求和结果
long long Sum()
{long long ans = 0;//改进：保留 a的k-1次方的结果:long long tmp = 1;for(long long  i = 0 ; i<=n ;i++){ans = (ans + multiply(func(i),tmp,mod))%mod;tmp = (multiply(tmp,a,mod))%mod;}return ans;
}int main()
{//处理输入：// int n,m,a;// cin>>n>>m>>a;// vector<int> vec(m+1,0);// for(int i= 0; i<= m; i++)// {//     cin>>vec[i];// }//朴素一点的方法进行计算——先做一个垃圾出来：//第一步：需要一个计算f(k) % mod//第二步：再计算S（n）//可以改进的地方：//1.(a*b)%mod 可以利用 2的幂次 以及 左移，右移优化//2.计算a^k次方， 可以利用 2的幂次进行优化//其他的话，暂时就只能那样子了init_input();cout<<Sum()<<endl;//虽然，样例9 和 样例10 我肯定是做不出来的，//但是，只要过了一些样例，就有分，为啥不干脆 “针对样例编程”？//要有针对性！ -- 得分为王//第一：针对 a = 1的情况， —— 只要算f(k)求和即可//这里一定有更加高效的计算-可以合并 - 分治等//目前我的想法只有合并:if(a == 1){//但是如果要开辟一个10^9次方的数组的话，开辟不了//nice，合并之后，感觉因为m很小，复杂度可以降低到O（n）//甚至，只要知道1次求和，2次求和，3次求和，4次求和公式。。。。妙！//参考：https://www.bilibili.com/read/cv11243219///这个问题就是 “自然数”幂等和问题：//根据这个参考文章，基本就可以搞定所有a=1的case了//数学的美妙就在其中，而清华，必然是招收能够体会数学之美的学生//这里以m=2 , a =1 那个测试用例进行写代码：if(a == 1 && m==2){   //别忘了 0 的 0次方是 1long 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;cout<<sum<<endl;}}return 0 ;
}

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里面的数据：

测试用例：

输入：
5 4 2
1 1 3 10
3 1 2 5
3
输出：
4 1 
2 1

#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<stdlib.h>using namespace std;struct cong
{int x;int y;int d;int f;//尝试写一个默认构造函数：cong(){this->x =0;this->y =0;   this->d =0;this->f =0;}
};int n,m,k;
int t;//算了，如果是二维数组的话，我还是老老实实的用int a[100][100]
//或者vector<vector<int> > vec(n,vector<int>(m,0))这种int main()
{//这个就是一个简单的 模拟题目 搞定即可://最关键一个点可能就是 数据如何存储的问题//处理输入 和 存储结构cin>>n>>m>>k;cong arr[1001];int flag[1001]; //用于记录这根是否存活，只有flag==0时，才需要更新//cong的下标是从1开始用的for(int i = 1;i <=k ;i++) //arr从1开始用！！！cong的下标{cin>>arr[i].x>>arr[i].y>>arr[i].d>>arr[i].f;}cin>>t;//直接模拟t个时间-for循环-立即更新board数据 和 arr数据for(int i=1;i <=t ;i++){//这里，设置一个board二维矩阵，nxm位置初始为0//之后，每次更新一个 活着的cong，在更新后的那里写上cong的下标//如果原来那个位置有非0的下标——>战斗->f小的那个flag设置为1，//坐标范围(0-n-1,0-m-1)//到达边界，下一个回合进行扭转，扭转也算做一步int board[101][101]; // 下标从0开始用，我估计是//调用for(int j = 1; j<=k;j++){if(flag[j] != 0){continue; //这根cong已经 不活了}//--否则进行更新：//上：if(arr[j].d == 0){//是否到达上边界:if(arr[j].y == m-1) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同{//修改arr[j].d即可arr[j].d = 1;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}}else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}else{//向上移动1格:arr[j].y +=1;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}} else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}}//下：else if(arr[j].d == 1){//是否到达下边界:if(arr[j].y == 0) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同{//修改arr[j].d即可arr[j].d = 0;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}}else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}else{//向下移动1格:arr[j].y -=1;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}} else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}}//左：else if(arr[j].d == 2){//是否到达上边界:if(arr[j].x == 0) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同{//修改arr[j].d即可arr[j].d = 3;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}}else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}else{//向左移动1格:arr[j].x -=1;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}} else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}}//右：else if(arr[j].d == 3){//是否到达上边界:if(arr[j].x == n-1) //我就按照正常的笛卡尔坐标来！之前那个贪吃蛇有点不同{//修改arr[j].d即可arr[j].d = 2;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}}else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}else{//向右移动1格:arr[j].x +=1;//--判断board同一个位置是否需要战斗if(board[arr[j].x][arr[j].y] != 0 ){//战斗:int index = board[arr[j].x][arr[j].y];if(arr[j].f > arr[index].f){// j留下board[arr[j].x][arr[j].y] = j;flag[index] = 1;}else{// index留下flag[j] = 1;//阵亡}} else{//在board上面占一个坑位，等其他人过来board[arr[j].x][arr[j].y] = j;}}}}}//输出k行，也就是最后的k根cong的位置for(int i =1 ;i<=k ;i++){cout<<arr[i].x<<" "<<arr[i].y<<endl;}return 0;
}

 T3:路径个数

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

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

解：

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

#include <iostream>
#include <bitset>int main() {// 定义一个包含8位的bitset，初始化所有位为0std::bitset<8> bitset1;// 通过下标赋值bitset1[0] = 1; // 设置第一位为1bitset1[3] = 1; // 设置第四位为1// 输出bitsetstd::cout << "Bitset1: " << bitset1 << std::endl; // 输出可能是 "00010010"// 通过整数初始化std::bitset<8> bitset2(7); // 二进制表示为 00000111std::cout << "Bitset2: " << bitset2 << std::endl; // 输出 "00000111"// 通过字符串初始化std::bitset<8> bitset3("10101010");std::cout << "Bitset3: " << bitset3 << std::endl; // 输出 "10101010"// 访问和修改std::cout << "Third bit of bitset3: " << bitset3.test(2) << std::endl; // 输出1，因为第三位是1bitset3.flip(2); // 翻转第三位std::cout << "After flipping third bit: " << bitset3 << std::endl; // 输出可能是 "10101000"// 操作std::bitset<8> bitset4("11110000");std::cout << "Bitset4 & bitset2: " << (bitset4 & bitset2) << std::endl; // 位与操作std::cout << "Bitset4 | bitset2: " << (bitset4 | bitset2) << std::endl; // 位或操作std::cout << "Bitset4 ^ bitset2: " << (bitset4 ^ bitset2) << std::endl; // 位异或操作return 0;
}

（2）更正参考解法：

//路径：
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<stdlib.h>using namespace std;//不要想那么多，置之死地而后生，对得起自己的money和精力即可，结果不要管他
//成为一个正在的编程算法强者，用思考力证明自己，这东西到哪都很有用！
//这一题很有意思，关键当然是 如何计算 “权值 与运算 后，二进制1的个数”
vector<int> power;
int n;void init()
{cin>>n;for(int i = 0;i<n ;i++){int tmp;cin>>tmp;power.push_back(tmp);}
}//写一个函数：输入2个整数， 输出 计算出1的个数:
//注意：调用bitset库 和 不调用库实现：
int count1(int a,int b)
{int ans = 0 ;int tmp = a&b;while(tmp>0){if(tmp&1 !=0)  // 或者 tmp%2 == 1{ans++;}tmp = tmp>>1;}return ans;}//第二个关键点：让我想起了 罗文寒 的那个 5=1+1+1+1+1的个数那个，递归思想//这一题我不太能接受，我给一个测试用例吧，如果对了还好，不对就自己再想一个：
//果然，就是有问题 —— 估计是题目给错了，不过，那我不如将错就错的写一写
int calc(int n )
{if(n == 1){return 2;}else{return 2+calc(n-1)*2;}
}//我的解法的测试用例：其中i与j之间都是2条路:
int calc2(int i , int j)
{if( i == j ){return 1;}else{int ans = 0;for(int k = i+1; k<=j ;k++){ans =(ans + 2*calc2(k,j))%991127;}return ans;}
}//下面这个是作为 该题答案
int mycalc(int i , int j)
{//i是小的那个起点 ， j是大的那个终点：//递归出口:if( i == j){return 1;}else{int ans = 0;for(int k = i+1; k<=j ;k++){ans =(ans + count1(power[i],power[k])*mycalc(power[k],power[j]))%991127;}return ans;}}int main()
{cout<<calc(3)<<endl;       //输出14 -不对cout<<calc2(0,3)<<endl;    //输出18 -这才对return 0;
}