入门篇-简单模拟--《算法笔记》同步笔记总结与补充

2020-03-02

专题要点：

对算法要求不高，主要是对代码能力，细节处理，题意理解，合理的数据结构（一维多维数组，结构体）的掌握与运用

几点注意：

1、要注意输入格式，尤其是字符串的输入（getchar()吃掉最后的‘\n’），输出格式（控制多余的空格与换行）
2、输出顺序（字典序，升降序）
3、过程中是否要保留小数，四舍五入，以便于最后输出正确结果
4、数据范围不明确时的处理方法如：取模循环，!=EOF；取模的目的是为了将数据控制在一定范围内或者取一个整数的后几位数字。
5、边界问题，做题前应先把边界想清楚，避免不断修改代码的情况出现
6、适当考虑提高代码效率，提前对数据做预处理，做取模运算（防止大数运算溢出）
7、关于多项式运算的两个数据结构，数组散列与结构体（double cof（系数）与int exp（指数））
8、输入数据过程中可进行比较大小与数据运算
9、如果题目较为复杂，可以根据题目测试点的介绍，局部考虑，先拿一部分（参见ccf201809-3题目链接）

PAT更优的解题思路

关于这一专题的上机训练中，我个人对A1065.A+B and C 和 B1010.一元多项式求导有优于书本的解题思路

A1065

题目不再赘述

个人思路

可通过对大数取模来避免溢出现象，而书中给出的正溢出，负溢出（参见计算机组成原理）略显深奥难懂
补充大数取模的性质
1.(a+b)%c = (a%c + b%c)%c
2.(ab)%c = (a%c)(b%c)%c

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int T;
int main(int argc, char *argv[]) {
	scanf("%d", &T);
	for(int i = 1; i <= T; i++)
	{
		ll A, B, C;
		scanf("%lld%lld%lld", &A, &B, &C);
		ll sum = (A % mod + B % mod) % mod;
		ll cc = C % mod;
		if(sum > cc)
		{
			printf("Case #%d: true\n", i);
		}
		else
		{
			printf("Case #%d: false\n", i);
		}
	}
	return 0;
}

B1010

采用两个数组num[]来存放系数，ex[]存放指数，输入一对数据，进行运算，存入数组，顺序输出num[],ex[]，若原式最后有常数项，输出时不再对其进行输出
而题解从低到高枚举，从高到低输出，略显麻烦

#include <bits/stdc++.h>
using namespace std;
int num[100005];
int ex[100005];
int main(int argc, char *argv[]) {
	int index = 0;
	int a, b;
	bool flag = false;//标记是否有常数项 
	while(scanf("%d %d", &a, &b) != EOF)
	{
		index++;
		num[index] = a * b;//求导后的系数 
		if(b != 0)
		{
			ex[index] = b - 1;//求导后指数-1 
		}
		else
		{
			ex[index] = 0;//常数项不做指数处理 
			flag = true;
			break;
		}
	}
	if(flag)//修改下标，不予输出常数项求导后的0 
	{
		index--;
	}
	if(index)
	{
		for(int i = 1; i <= index; i++)//输入到index为止，不再输出常数项
		{
			printf("%d %d", num[i], ex[i]);
			if(i < index)
			{
				printf(" ");
			}
		}
	}
	else//求导后index == 0，无非零项做特判处理 
	{
		printf("0 0");
	}
	return 0;
}