昨天写了一天transformer代码,就写了一题简单模拟题,今天打了球,也没补上,花费1.5h左右;
题目详情 - 1042 Shuffling Machine (pintia.cn)
思路:用两个数组储存,start装着一开始的0-53编号,然后把start中的值赋给end的转换位置后的地方,最后用end覆盖start,继续循环。
值得注意的是输出时数字和字符的下标需要清楚。
#include<iostream>
using namespace std;
int main() {
string ss = "SHCDJ";// /13, 0-12:S
int k;
cin >> k;
const int n = 54;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];//记得-1取得下标
}
int start[n], end[n];
for (int i = 0; i < n; i++) {//0-53,记得最后加1
start[i] = i;
}
while (k--) {
for (int i = 0; i < n; i++) {
end[arr[i] - 1] = start[i];
}
for (int i = 0; i < n; i++) {
start[i] = end[i];
}
}
for (int i= 0; i < n; i++) {
if (i != 0) {
cout << ' ';
}
cout << ss[start[i] / 13] << start[i]%13 + 1;// /13和%13
}
return 0;
}
题目详情 - 1046 Shortest Distance (pintia.cn)
思路:空间换时间,一开始我写的是遍历left到right,取出值;但是容易发生运行超时,因为查询10^4,有10^5数据时,时间复杂度为10^9;所以需要用一个record数组储存每个点到第一个点的距离,不需要循环求值,复杂度就减少为10^4;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
int main() {
int n;
scanf("%d", &n);
int* dis = new int[n+2];//从1开始
int* record = new int[n + 2];
record[1] = 0;//第一个点到第一个点距离为0,以第一个点为基准,record[i]=i到1的距离
int sum=0, min;
for (int i = 0; i < n; i++) {
scanf("%d", &dis[i + 1]);
sum += dis[i + 1];
record[i + 2] = sum;
}
int m;
scanf("%d", &m);
int left, right;
while (m--) {
scanf("%d %d", &left, &right);
min = 0;
if (left > right) {
int temp = left;
left = right;
right = temp;
}
min = record[right] - record[left];
printf("%d\n", (min < sum - min ? min : sum - min));
}
return 0;
}
题目详情 - 1065 A+B and C (64bit) (pintia.cn)
思路:我想的是用字符串输入,使用字符串相加后再比较;书上直接用正负溢出表示,属实聪明;
值得一提的是,用long double可以直接用a+b>c解决,我查的是long double可以表示20位10进制数字,那么尾数部分肯定大于64位,但是sizeof(long double)却是8,属实没搞懂,待进一步学习;
还有如果直接用a+b而不是res=a+b也会出错,待进一步研究,我觉得是编译器的问题;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
int main() {
int n;
cin >> n;
long long a, b, c;
for (int i = 0; i < n; i++) {
int flag = 1;
scanf("%lld %lld %lld", &a, &b, &c);//%lld
long long res = a + b;//不用res不行,why??
if (a>0&&b>0&&res < 0) {//正溢出,a+b>2^63-1,c一定小于这个值
flag = 1;
}
else if (a < 0 && b < 0 && res>=0) {
flag = 0;//负溢出,两个负数相加大于等于0,c一定大于这个值
}
//其他情况不会溢出
else if (res > c) {
flag = 1;
}
else {
flag = 0;
}
if (flag) {
printf("Case #%d: true\n", i + 1);
}
else {
printf("Case #%d: false\n", i + 1);
}
}
return 0;
}
题目详情 - 1010 一元多项式求导 (pintia.cn)
思路:注意0 0;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
int main() {
int k, e;
int flag = 0;
//注意只有一项时打印0 0;否则不打印0 0
//使用flag操作是否打印0 0以及多的空格
while (scanf("%d %d", &k, &e) != EOF) {
if (!e) {
continue;
}
if (flag) {
cout << ' ';
}
cout << k * e << ' ' << e - 1;
flag = 1;
}
if (!flag) {
cout << "0 0";
}
return 0;
}
题目详情 - 1002 A+B for Polynomials (pintia.cn)
思路:数据结构第一周有这题的复杂版,用链表完成;这一题更简单,因为n最大1000,用数组完成,输入a数组,把b数组加进去,即可;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
int main() {
double arr[1001] = { 0 };
int n,m,e;
double k;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> e >> k;
arr[e] = k;
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> e >> k;
arr[e] += k;
}
int ctn = 0;
for (int i = 0; i < 1001; i++) {
if (arr[i]!= 0) {
++ctn;
}
}
cout << ctn;
for (int i = 1000; i >= 0; i--) {
if (arr[i] != 0) {
printf(" %d %.1f", i, arr[i]);
}
}
return 0;
}
题目详情 - 1009 Product of Polynomials (pintia.cn)
思路:同多项式的乘法,简易版,用结构数组即可;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
struct node {
double k;
int e;
};
int main() {
node arr[1001]={0}, res[2001] = {0};
int n, m;
cin >> n;
int e;
double k;
for (int i = 0; i < n; i++) {
cin >> e >> k;
arr[i].e = e;//储存第一个数组的指数
arr[i].k = k;
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> e >> k;
for (int j = 0; j < n; j++) {
res[e + arr[j].e].k += arr[j].k * k;//结果数组用下标表示指数
}
}
int ctn = 0;
for (int i = 0; i < 2001; i++) {
if (res[i].k != 0) {
ctn++;
}
}
cout << ctn;
for (int i = 2000; i >=0; i--) {
if (res[i].k != 0) {
printf(" %d %.1f", i, res[i].k);
}
}
return 0;
}
题目详情 - 1041 考试座位号 (pintia.cn)
思路:我先想的是用结构数组储存num,k,s,然后通过arr[i].s==s查找;这样时间复杂度较高,可以但没必要;直接通过s作为数组下标进行储存和查找更省事;值得再次写;
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
struct node {
long long num;
int k;//考试
};
int main() {
node arr[1001];
int n, k, s;
long long num;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num >> s >> k;
arr[s].num = num;
arr[s].k = k;
}
int m, t;
cin >> m;
while (m--) {
cin >> t;
cout << arr[t].num << ' ' << arr[t].k << endl;
}
return 0;
}
题目详情 - 1004 成绩排名 (pintia.cn)
思路:太简单,看代码即可;
#include<iostream>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
struct node {
string name;
string num;
int score;
};
int main() {
node max, min,temp;
max.score = -1;
min.score = 101;
vector<node>v;
int n;
cin >> n;
int score;
string name, num;
while (n--) {
cin >> temp.name >> temp.num >> temp.score;
v.push_back(temp);
if (max.score < temp.score) {
max.score = temp.score;
max.name = temp.name;
max.num = temp.num;
}
if (min.score > temp.score) {
min.score = temp.score;
min.name = temp.name;
min.num = temp.num;
}
}
cout << max.name << ' ' << max.num<<endl;
cout << min.name << ' ' << min.num;
return 0;
}
题目详情 - 1028 人口普查 (pintia.cn)
思路:用20140906与20130906整数进行比较会更便捷,这也是我上实践课写财务系统时候突然想到的,在这道简单题用上了,比答案简单不少;
#include<iostream>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
int main() {
int n;
cin >> n;
string name, max_name, min_name;
int time,yr, month, dy;//<18140906,>20140906不符
int max_time = 18140905, min_time = 20140907;
int ctn = 0;
while (n--) {
cin >> name;
scanf("%d/%d/%d", &yr, &month, &dy);
time = yr * 10000 + month * 100 + dy;
if (time > 20140906 || time < 18140906) {
continue;
}
++ctn;
if (max_time < time) {//max_time对应年纪最小
max_time = time;
min_name = name;
}
if (min_time > time) {
min_time = time;
max_name = name;
}
}
if(!ctn){//对应测试点4;
cout<<0;
}else{
cout << ctn << ' ' << max_name << ' ' << min_name;
}
return 0;
}