2. it
  3. PTA A1009&A1010

PTA A1009&A1010

mac2022-06-30  64

第五天

A1009 Product of Polynomials (25 分)

题目内容

This time, you are supposed to find A×B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2... NKaNK where K is the number of nonzero terms in the polynomial, Niand aNi(i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2 2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

单词

product

英 /'prɒdʌkt/ 美 /'prɑdʌkt/

n. 产品；结果；[数] 乘积；作品

题目分析

多项式相乘，类似于A1002的多项式相加，之前也写过用的开结构体数组的方法，很笨，所以用之前在A1002学到的开一个数组，用下标代表指数，对应元素代表系数的方式来存，不过因为是乘法所以要多开两个数组把数据临时保存一下。代码如下。

具体代码

#include<stdio.h> #include<stdlib.h> double p1[1001]; double p2[1001]; double res[2002]; int N, M; int main(void) { scanf("%d", &N); for (int i = 0; i < N; i++) { int e; double c; scanf("%d %lf", &e, &c); p1[e] = c; } scanf("%d", &M); for (int i = 0; i < M; i++) { int e; double c; scanf("%d %lf", &e, &c); p2[e] = c; } for (int i = 0; i < 1001; i++) { if (p1[i] != 0) for (int j = 0; j < 1001; j++) if (p2[j] != 0) res[i + j] += p1[i] * p2[j]; } int num = 0; for (int i = 0; i < 2002; i++) { if (res[i] != 0) num++; } printf("%d", num); for (int i = 2001; i >= 0; i--) { if (res[i] != 0) printf(" %d %0.1f", i, res[i]); } system("pause"); }

A1010 Radix (25 分)

题目内容

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number. Now for any pair of positive integers N1 and N​2, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input:

6 110 1 10

Sample Output:

2

单词

radix

英 /'rædɪks; 'reɪ-/ 美 /'redɪks/

n. 根；[数] 基数

n. (Radix)人名；(法、德、西)拉迪克斯；(英)雷迪克斯

decimal

英 /'desɪm(ə)l/ 美 /'dɛsɪml/

n. 小数 adj. 小数的；十进位的

题目分析

从9点做到11点多，巨坑，第一次是默认最大基数为36，部分通过，找不到bug很懵，上网查了一会儿看了一些博客才知道，最大的基数不一定是36，可以非常的大，最大值应该是已经算出的值+1，由于数据可以非常的大，所以int的数据大小肯定是不够了，而且用暴力方法遍历查找，必然会超时，这时候就要用二分查找，于是把之前写的全删掉重新写了个二分查找的代码，调试完依然有几个无法通过，于是把自己的代码和别人已经AC的代码对比，发现大佬的代码中在二叉搜索时多了一个判断条件，即算出的值需要判断是否小于0，这是因为如果数字实在太大甚至超过了long long的范围，那么这时我们去另一半继续找基数，我对这里有一点疑惑，如果数据真的特别大，或者基数卡在溢出和mid中间，那么这个方法可能找不到，可是数据又是无限的，所以这个问题深究起来可能是无解的（这么看来这好像是个数学问题，不知道有没有大佬能证明出来这道题到底有没有通解）。最后的最后，大家在开字符数组的时候一定记得要加一。。。。。 对了，关于把字符串转换成数字的问题，我之前一直用的是算出数组长度，减一后用math.h里的pow算出每个进位的值后一个一个加，今天看了大佬的代码，发现了一种更简洁的方法：

int sum=0; while(*p != '\0') { int n = convert(*p); sum = sum * radix + n; p++; }

具体代码

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXSIZE 11 char s1[MAXSIZE]; char s2[MAXSIZE]; int tag; long long radix; long long result; long long int finalradix; int convert(char a) { if (a >= '0'&&a <= '9') return a - '0'; else return a - 'a' + 10; } long long count_num(char *s, long long radix) { char *p = s; long long sum = 0; while(*p != '\0') { int n = convert(*p); sum = sum * radix + n; p++; } return sum; } long long min_radix(char *s) { long long max = 0; char *p = s; while(*p!='\0') { int f = convert(*p); if (f > max) max = f; p++; } return max + 1; } long long binary_search(long long result,char *s,long long rmin,long long rmax) { while (rmin <= rmax) { long long mid = rmin+(rmax-rmin)/2; long long n = count_num(s, mid); if (n > result || n < 0 ) rmax = mid - 1; else if (n < result) rmin = mid + 1; else return mid; } return -1; } int main(void) { char c1[MAXSIZE]; char c2[MAXSIZE]; scanf("%s %s %d %lld", c1, c2, &tag, &radix); if (tag == 1) { strcpy(s1, c1); strcpy(s2, c2); } else { strcpy(s2, c1); strcpy(s1, c2); } result = count_num(s1, radix); long long rmax; if(result != 0) rmax = result + 1; else rmax = 2; long long rmin = min_radix(s2); long long r = binary_search(result, s2, rmin, rmax); if (r == -1) printf("Impossible"); else printf("%lld", r); system("pause"); }

参考博客

【笨方法学PAT】1010 Radix（25 分）1010 Radix (25 分)*甲级PAT 1010 Radix（二分搜索+坑）1010 Radix （25 分）C++实现-终于AC了

转载于:https://www.cnblogs.com/z-y-k/p/11538045.html

相关资源：JAVA上百实例源码以及开源项目
最新回复(0)