今日刷题列表课程来源AcWing
其中AcWing中的题目为翻译好的中文题目
- 1002 A+B for Polynomials
- 1009 Product of Polynomials
- 1023 Have Fun with Numbers
- 1024 Palindromic Number
- 1010 Radix
- 1015 Reversible Primes
- 1027 Colors in Mars
- 1100 Mars Numbers
AcWing链接
PAT链接
英语单词
- polynomials 多项式
- nonzero terms 非零项
- exponents and coefficients 指数和系数
解析
- 使用三个double数组来存放多项式的系数
- 数组的下标代表了多项式的次数
- 通过遍历将a与b多项式的和累加到c上
注意点
- con的判断过程中,要注意到类似a = [1 ... ],b =[ -1 ... ]的情况, 也就是说在a,与b中存在该次数的系数,但是累加之后被消去,不能统计到con中
- 如果最后的结果是0, 单单输出0即可
- 输出控制保留一位小数
#include1009 Product of Polynomials#include #include #include #include #include const int N = 1010; using namespace std; double a[N], b[N], c[N]; int main() { int k; cin >> k; int exponent; // 指数 for (int i = 0; i < k; ++i) { cin >> exponent; cin >> a[exponent]; } cin >> k; for (int i = 0; i < k; ++i) { cin >> exponent; cin >> b[exponent]; } int con = 0; for (int i = 0; i < N; ++i) { if (a[i] || b[i]) { c[i] += a[i] + b[i]; if(c[i]) con++; } } cout << con; for (int i = N - 1; i >= 0; i--) { if (c[i]) { printf(" %d %.1f", i, c[i]); } } return 0; }
AcWing链接
PAT链接
英语单词
- Product 乘积
解析 - 存储方面与上一题类似, 主要区别在于计算多项式的乘法
- 对于多项式的乘法可以采取两层循环,即让多项式a的每一项与多项式b来相乘, 相乘的过程为c[i + j] += a[i] * b[j]; 也就是系数相乘, 指数相加- 后面的操作与上一题一模一样
#include1023 Have Fun with Numbers#include const int N = 1010; using namespace std; double a[N], b[N], c[2 * N]; int main() { int k; cin >> k; int exponent; while (k--) { cin >> exponent; cin >> a[exponent]; } cin >> k; while (k--) { cin >> exponent; cin >> b[exponent]; } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (a[i] || b[j]) { c[i + j] += a[i] * b[j]; } } } int con = 0; for (int i = 0; i < 2 * N; ++i) { if (c[i]) { con++; } } printf("%d", con); for (int i = 2 * N - 1; i >= 0; i--) { if (c[i]) { printf(" %d %.1lf", i, c[i]); } } return 0; }
AcWing链接
PAT链接
英语单词
- consisting 组成
- permutation 排列
- this property 这个性质
解析
long long形的整数大概是18位左右,而题目中的要求是no more than 20 digits, 因此这里用数组或者vector来存取
知识点
- 可以直接用==来比较两个vector 数组是否相等
- sort排序的用法
- 首先要导入头文件algorithm
- sort(起始地址，结束地址)
- C++中sort排序用法跳转链接
#include1024 Palindromic Number#include #include #include using namespace std; vector double_number(vector &a) { vector b; int t = 0, i; for (i = a.size() - 1; i >= 0; i--) { b.push_back((a[i] * 2 + t) % 10); t = (a[i] * 2 + t) / 10; } if (t) b.push_back(t); return b; } int main() { // 1234567899 string n; cin >> n; vector number; for (int i = 0; i < n.size(); ++i) { number.push_back(n[i] - '0'); } vector result = double_number(number); vector tmp = result; sort(number.begin(), number.end()); sort(tmp.begin(), tmp.end()); if (tmp == number) { cout << "Yes" << endl; } else { cout << "No" << endl; } for (int i = result.size() - 1; i >= 0; i--) { cout << result[i]; } return 0; }
AcWing链接
PAT链接
英语单词
- Palindromic Number 回文数
- via 经过,通过
解析
- 编写函数判断是否为回文数
- 编写函数执行数字翻转相加
vector
a没循环完就继续加a
b没循环完就继续加b
进位t还在就继续加t
#include1010 Radix#include #include using namespace std; bool is_data(vector &x) { for (int i = 0, j = x.size() - 1; i < j; ++i, --j) { if (x[i] != x[j]) return false; } return true; } vector add_vec(vector &a) { vector b, c; int t = 0, i; for (i = a.size() - 1; i >= 0; i--) { b.push_back(a[i]); } for (i = 0; i < a.size(); ++i) { c.push_back((a[i] + b[i] + t) % 10); t = (a[i] + b[i] + t) / 10; } if (t) c.push_back(t); return c; } int main() { string N; int K; cin >> N >> K; vector number; int cur_k = 0; for (int i = 0; i < N.size(); ++i) { number.push_back(N[i] - '0'); } if (is_data(number)) { for (auto num:number) { cout << num; } cout << endl << cur_k; } else { while (!is_data(number)) { cur_k++; number = add_vec(number); if (cur_k == K) break; } for (int i = number.size() - 1; i >= 0; --i) { cout << number[i]; } cout << endl << cur_k; } return 0; }
AcWing链接
PAT链接
英语单词
- equation 等式,方程
- decimal number 十进制数, 小数
- radix 基数, 进制
解析 - 这道题花了很久的时间, 主要卡在了long long类型边界一些地方,这里的cal函数中的radix也要改为long long类型, 因为之后的进制可能会很大,超过int的范围
- LL cal(string N1, LL radix) 用来将给定进制的字符串转换为十进制的值
- 二分查找
int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; }
题解
#include1015 Reversible Primes#include #include #include #include typedef long long LL; using namespace std; int get(char c) { if (c <= '9') return c - '0'; else return c - 'a' + 10; } LL cal(string N1, LL radix) { LL res = 0; for (auto c:N1) { if ((double) res * radix + get(c) > 1e16) return 1e18; res = res * radix + get(c); } return res; } int main() { string N1, N2; int tag, radix; cin >> N1 >> N2 >> tag >> radix; if (tag == 2) { swap(N1, N2); }// 使得radix对应为N1的进制 // 将N1转换为radix进制数字 LL target = cal(N1, radix); // 二分查找 LL l = 0; for (auto c : N2) l = max(l, (LL) get(c) + 1); LL r = target + 1; while (l < r) { LL mid = l + r >> 1; if (cal(N2, mid) >= target) r = mid; else l = mid + 1; } if (cal(N2, r) != target) puts("Impossible"); else cout << r << endl; return 0; }
AcWing链接
PAT链接
英语单词
- Prime 质数
解析
- 注意反转数字的时候要先转成对应的进制反转,我一开始没想清楚直接用十进制反转了就G了
- 在翻转数字的过程中可以直接求得翻转后的十进制结果
- 比如6转为2进制本该为110,翻转后得到011
- 而使用辗转相除法得到的二进制结果正是011, 可以直接使用res = res * 2 + n % d的方式求和
#include1027 Colors in Mars#include #include #include typedef long long LL; using namespace std; bool is_prime(int x) { if (x == 1) return false; for (int i = 2; i * i <= x; ++i) { if (x % i == 0)return false; } return true; } // 7 2 // 7 / 2 = 3 ... 1 // 3 / 2 = 1 ... 1 // 1 / 2 = 0 ... 1 bool check(int n, int d) { if (!is_prime(n)) return false; // reverse int res = 0; while (n) { res = res * d + n % d; n = n / d; } return is_prime(res); } int main() { int n,d; while (true) { cin >> n; if (n < 0) break; cin >> d; if (check(n, d)) puts("Yes"); else puts("No"); } return 0; }
AcWing链接
PAT链接
解析
本题思路很简单, 输入的三个数字, 把每个数字都转成相应的13进制就可以了
这里要注意到进制之间的转换问题,以及不满两位的补0问题
我的代码
#include#include using namespace std; void change(int r) { // 将r转换为13进制的数并输出 // 因为数字小于169 // 15: 15 / 13 = 1 14 % 13 = 2 14 = 12 if (r < 10) printf("%02d", r); else if (r < 13) printf("0%c", r - 10 + 'A'); else { // r>=13 int high = r / 13; int low = r % 13; if (high >= 10 && low >= 10) printf("%c%c", high - 10 + 'A', low - 10 + 'A'); else if (high >= 10) printf("%c%d", high - 10 + 'A', low); else if (low >= 10) printf("%d%c", high, low - 10 + 'A'); else printf("%d%d", high, low); } } int main() { int r, g, b; scanf("%d %d %d", &r, &g, &b); printf("#"); change(r); change(g); change(b); return 0; }
优雅的代码
- cout << get(a[i] / 13) << get(a[i] % 13);
- 如果只有一位的情况下a[i] / 13其实是等于0的,只要这边输出0就好了,我没想到这一点
#include1100 Mars Numbersusing namespace std; char get(int x) { if (x <= 9) return '0' + x; return 'A' + x - 10; } int main() { int a[3]; for (int i = 0; i < 3; ++i)cin >> a[i]; cout << '#'; for (int i = 0; i < 3; ++i) { cout << get(a[i] / 13) << get(a[i] % 13); } return 0; }
AcWing链接
PAT链接
英语单词
- mutual translation 相互转换
- either or 要么 要么
- corresponding 相应的 相关的 对应的
解析
做这道题的时候碰到了很多小坑
- 用getline 获取一行，然后整行进行解析
- 如果带有数字， 那么将数字转换为火星数字
- 如果 是字符串 那么将字符串转换为整型数字
- 由于火星文只有两位所以数字转火星数字，只要将数字除以13和数字mod13进行操作
- 字符串需要对一位和两位的情况进行讨论
C++ stringstream之妙用
stringstream用法
本题中使用stringstream ssin(data);获取输入的string类型地球字/火星字
自动根据空格分割他们并输出到指定的类型num2(string)中
或转换为int形变量num
我的答案
#include#include #include #include #include using namespace std; string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; // 个位 string b[12] = {"tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; // 高位 int get_num(string num) { for (int i = 0; i < 13; ++i) { if (a[i] == num) return i; } for (int i = 0; i < 12; ++i) { if (b[i] == num) return (i + 1) * 13; } } int main() { // 29 = 2 3 elo nov = 8 11 = 8*13+11 = 115 int n; cin >> n; getchar(); for (int i = 0; i < n; ++i) { string data; getline(cin, data); stringstream ssin(data); if (data[0] <= '9') { // 输入的是地球的数字, 需要转换为13进制 29 => 2 3 => hel mar int num; ssin >> num; if (num < 13) { cout << a[num] << endl; } else { // 15 => 1 2 => 15/13 =1 15 %13 = 2 cout << b[num / 13 - 1]; if (num % 13 != 0) cout << " " << a[num % 13]; cout << endl; } } else { // 输入的是火星的数字,需要先转换为13进制再转为10进制 elo nov => 8 11 => 8*13 + 11 = 115 string num2; int res = 0; while (ssin >> num2) { res += get_num(num2); } cout << res << endl; } } return 0; }
AcWing课程的答案
#include#include #include #include #include using namespace std; char names[][5] = { "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou" }; int get(string word) { for (int i = 0; i < 25; ++i) { if (names[i] == word) { if (i < 13) return i; return ((i + 1) % 13) * 13; } } } int main() { int n; cin >> n; getchar(); while (n--) { string line; getline(cin, line); stringstream ssin(line); if (line[0] <= '9') { int v; ssin >> v; if (v < 13) cout << names[v] << endl; else { cout << names[12 + v / 13]; if (v % 13 == 0) cout << endl; else cout << " " << names[v % 13] << endl; } } else { int res = 0; string word; while (ssin >> word) res += get(word); cout << res << endl; } } return 0; }
