腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

glm的全栈学习之路

专栏作者

427

文章

238804

阅读量

33

订阅数

一元多项式的乘法与加法运算

数据结构编程算法

一道看似很水其实大有文章对初学数据结构的同学大有裨益的好题题源：pta数据结构自测第二题题目描述 7-2 一元多项式的乘法与加法运算（20 分）设计函数分别求两个一元多项式的乘积与和。输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式: 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。给出两种做法 (题目不难，坑点很多)正常做一开始只能过25%的数据法一：常规思路用数组乘法： a1 x^m * a2 x^n = (a1*a2) x^(m+n) (m>=0,n>=0) 加法： a1 x^n + a2 x^n = (a1+a2) x^n (n>=0) a[i][0]表示存放第i项的系数，a[i][1]表示存放第i项的指数不解释看代码自然懂

2022-06-15

6610

2021-10-10-Acwin1087. 修剪草坪(单调队列优化dp）

https://www.acwing.com/problem/content/1089/

2022-05-11

1470

冲刺预推免刷题复习小记

四道pat甲级链表题 1516. 共享标记一下地址就可以 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,fir,sec,ne[N]; char e[N]; vector<int>a,b; int st[N]; int main(){ cin>>fir>>sec>>n; for(int i=1;i<=n;i++){ int add,next; char val;

2022-05-11

1550

软件工程七大设计原则

一个类对另一个类的依赖应该建立在最小的接口上，应该要最小化接口，使得所有实现接口的类完全实现接口中的函数

2022-01-20

6580

AcWing 1088. 旅行问题（前缀和单调队列优化dp 破环成链）

顺时针，我们可以倒着遍历，为什么呢，是因为我们可以在倒着遍历的时候处理到后n个的窗口最小值，然后遍历到前n个的时候我们就可以将第i个和窗口最值比较，只要比这个最值小就可以保证环绕一圈

2021-10-15

2500

2021-10-10-Acwing1087(单调队列优化dp）

https://www.acwing.com/problem/content/1089/

2021-10-13

2280

AcWing 300. 任务安排1（前缀和 dp优化）

📷 思路： 📷 代码： #include<iostream> #include<limits.h> #include<cstring> #define int long long using namespace std; const int N=5010; int n,f[N],sumt[N],sumc[N],s; //f[i][j]=f[k][j-1]+(t[1]+...+t[i]+j*s)*(c[k+1]+...+c[i]) signed main(){ cin>>n>>s; for(i

2021-10-09

2650

关于DMA（Direct memory access）比较通俗浅白的理解

如果通过CPU来传送，分为轮询（CPU不断查询外设接口数据准备情况或接收情况）、中断（外设发出请求CPU暂停保存现场后执行中断程序传送数据）占用CPU计算周期

2021-08-10

1.6K0

冲刺预推免第一天刷题复习小记

四道pat甲级链表题 1516. 共享标记一下地址就可以 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,fir,sec,ne[N]; char e[N]; vector<int>a,b; int st[N]; int main(){ cin>>fir>>sec>>n; for(int i=1;i<=n;i++){ int add,next; char val;

2021-08-10

1710

AcWing 3194. 最大的矩形（单调栈变形）

我们都知道单调栈可以求出左边第一个比自己小的数，那么其实这道题目我们只要线性复杂度求出最左边第一个比自己小的数和最右边比自己小的数就可以，比较麻烦的是最右边的，我们可以反转一遍数组，然后简单推导一下就可以求出等价最右边比自己小的数

2021-07-08

2180

编译原理复习预测分析法中出错处理

2.栈顶是非终结符A，输入符号是a，而M[A , a]是空白– No allowable actions

2021-06-22

4900

AcWing 3549. 最长非递减子序列（lis或者状态机）

这道题目最优解是1*2*1*2*类型，这样就有两种处理方式：一种是求1*2*的长度再加上1*2*的长度，枚举求最大值还有一种方式是四部分分成四个状态去求，也很好转移，下面代码给出的是第一种求法： #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,a[N],pre[N],ne[N],f[2],ans; int main(){ cin>>n; for(int i=1;i<=n;i++){

2021-06-08

4460

AcWing 80. 骰子的点数 (背包、滚动数组优化）

考虑用动归，数组dp[i][j]表示用i个骰子扔出和为j的可能数，因为第i个骰子可能扔出1-6的点数，则dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6]，由于我们只需要用到最后一次的结果，因此为了节省空间可以使用滚动数组，将二维dp数组变为一维。

2021-06-08

3470

集成学习boosting

Boosting 和 bagging 最本质的差别在于他对基础模型不是一致对待的，而是经过不停的考验和筛选来挑选出「精英」，然后给精英更多的投票权，表现不好的基础模型则给较少的投票权，然后综合所有人的投票得到最终结果。

2021-05-27

2920

集成学习bagging

bagging（bootstrap aggregating的缩写，也称作“套袋法”）就是其中的一种

2021-05-27

3010

AcWing 631. Googol字符串 (递归、思维题）

继承字符串

对于每个字符串，分为三个部分、前中后，中间由最独立的0组成，前面一直继承下来不变，后面记录一个反转对应的位置以及将本位上的值翻转的次数（0变1,1变0）

2021-05-27

2210

Acwing 152. 城市游戏(暴力枚举平面单调栈）

这道题目就是模板题AcWing 131. 直方图中最大的矩形的一个升级版，就是要枚举每一个平面的最大值，然后套模板题的板子就可以了

2021-05-14

2440

AcWing 12. 背包问题求具体方案(背包求方案数经典模板，一定要会）

#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m,f[N][N],v[N],w[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } for(int i=n;i>=1;i--){ for(int j=0;j<=m;j++){ f[i][j]=f[i

2021-05-13

3600

AcWing 11. 背包问题求方案数(背包问题求方案数）

#include<bits/stdc++.h> using namespace std; const int N=1010,mod=1e9+7; int f[N],cnt[N],n,m; signed main(){ cin>>n>>m; for(int i=0;i<=m;i++)cnt[i]=1; int u,v; for(int i=1;i<=n;i++){ cin>>u>>v; for(int j=m;j>=u;j--){

2021-05-13

6660

Leetcode 1723. 完成所有工作的最短时间 (dfs,剪枝）

class Solution { public: int ans=INT_MAX,sum[13]={0}; int minimumTimeRequired(vector<int>& jobs, int k) { dfs(0,k,sum,jobs,0,0); return ans; } void dfs(int u,int k,int sum[],vector<int>jobs,int tepans,int use){ if(te

2021-05-10

4030

点击加载更多

社区活动

腾讯技术创作狂欢月

“码”上创作 21 天，分 10000 元奖品池！

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态