暑假算法练习Day5

咕咕了好几天哈哈哈哈,因为这几天在忙一些其他事(bushi ,好吧其实就是自己太懒啦,从今天开始继续每天的算法练习

1010 一元多项式求导 (25 分)

设计函数求一元多项式的导数。(注:\(x^n\)(\(n\)为整数)的一阶导数为\(nx^{n−1}\)。)

输入格式:

以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过 1000 的整数)。数字间以空格分隔。

输出格式:

以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0,但是表示为 0 0

输入样例:

3 4 -5 2 6 1 -2 0

输出样例:

12 3 -10 1 6 0

解题分析及代码:

这一题看起来很简单,但是其实还是存在着几个坑的,害得我整整调了快1个小时。我们需要注意四点:

  1. 对于“零多项式”,我们最终结果因输出为 0 0。其实不止零多项式,对于如1 0等输入,我们最终结果都需要输出0 0,因此在输出时应对输入多项式的第一项的系数进行判断,若为0,则直接输出0 0
  2. 对于输出格式的判断,这个我搞了很久,因为测试点3一直显示格式错误,最后发现对于3 4 0 0这样输入的例子,我最终输出时末尾会有多余空格,所以在输出时一定要注意格式的输出。
  3. 在输出时,若当前项的系数为0,不要输出。
  4. 在此题中对于输入结束的判断不应该仅局限于判断多项式的最后一项是否为0,如果这样写,测试点1就会显示超时。还是要用到Day4中提到的while判断的方法来判断输入是否结束。当然,在本地测试的话,mac系统是使用control+C来结束输入,win系统的话应为Ctrl+Z
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int p[1005]={0};
int main() {
    int n;
    int a,b;
    cin >> a >> b;
    n=b;
    if(b!=0)p[b-1]+=a*b;
    while(cin >> a >> b){
       if(b!=0) p[b-1]+=a*b;
    }
    if(n==0){
        cout <<"0 0"<<endl;
        return 0;
    }
    cout << p[n-1] <<" " <<n-1;
    if(n-2<0) return 0;
    for(int i=n-2;i>=0;i--){
        if(p[i]!=0) 
            cout <<" " <<p[i] <<" " <<i;
        if(i==0) cout << endl;
    }
    return 0;
}

还有一个更加简略的解答。

 int main() {
     int a, b, flag = 0;
     while (cin >> a >> b) {
         if (b != 0) {
             if (flag == 1) cout << " ";
             cout << a * b << " " << b - 1;
             flag = 1;
         }
     }
     if (flag == 0) cout << "0 0";
     return 0;
 }

1011 A+B 和 C (15 分)

给定区间 $[−2{31},2{31}] $​内的 3 个整数 \(A、B\)​和\(C\)​,请判断\(A+B\)​是否大于\(C\)​。

输入格式:

输入第 1 行给出正整数 \(T\) (≤10),是测试用例的个数。随后给出 T 组测试用例,每组占一行,顺序给出。\(A、B\)和\(C\)整数间以空格分隔。

输出格式:

对每组测试用例,在一行中输出 Case #X: true 如果 \(A+B>C\),否则输出 Case #X: false,其中 X 是测试用例的编号(从 1 开始)。

输入样例:

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例:

Case #1: false
Case #2: true
Case #3: true
Case #4: false

解题分析及代码:

本题唯一需要注意的就是A、B、C的范围,因此在定义时我们需定义为long long类型($[−2{31},2{31}-1] $​)并且还需注意的是,不能将A和B加起来再和C进行判断,相反需采用减法运算,将C减去A或B,再与B或A进行比较,否则会出现爆精度的问题,当然Python请随意哈哈哈哈哈哈哈。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
long long a,b,c;
int main() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int flag=0;
        cin >> a >> b >> c;
        c-=a;
        if(c<b) flag=1;
        if(flag==1) cout <<"Case #"<<i<<": true"<<endl;
        else cout <<"Case #"<<i<<": false"<<endl;
    }
    return 0;
}
上一篇:《软件工程之美》day5


下一篇:AcWing寒假每日一题——Day5回文平方