?
入门模拟中的题比较简单, 基本上没用到什么算法. 个人觉得比较难的有 :
?
除此之外还需要注意的点 :
在涉及到数组的相关操作时, 记得完成一次操作后要将数组初始化, 否则会影响下一次操作的结果. 如果碰到需要计数器 (例如求数组中有多少个素数等) 时, 操作完后也需要进行初始化
部分题目对输出的空格和换行符有要求, 因此在写算法时要多注意. 例如最后一个数输出后不输出空格等.
写算法时要考虑多种情况, 不要局限于题目样例. 例如查找算法, 要考虑有序或无序; 排序算法要考虑数据重复等
不要在一道题上花太久时间. 一道题如果超过了半个小时(PAT考试共150分钟, 5道题, 平均算下来一道题的时间至少为 30 分钟)还没有思路, 就去找题解, 如果思路相同就看看自己哪里卡壳了; 如果思路不同, 就试试换种思路做. 毕竟刚开始学习数据结构与算法肯定很吃力, 大多数情况下还是要广开言路, 不要闭门造车. 等写的算法多了, 怎么做题使用什么算法自然而言的也就胸有成竹了. 初学者一定要戒骄戒躁
部分题有测试次数, 意思是代码执行一次完整操作的次数超出测试次数的话程序就要停止.
代码运行结果与答案不符, 要记得多多调试逐步跟进, 找出错误
C语言中的函数最好不要和C++混用
?
?
?
?
http://codeup.hustoj.com/problem.php?cid=100000575&pid=0
?
#include <cstdio>
#include <cstdlib>
using namespace std;
int main(void)
{
int l, m;
int *Buffer = nullptr;
while (scanf("%d %d", &l, &m) != EOF)
{
if (l == 0)
continue;
else
{
l = l + 1;
Buffer = (int *)calloc(true, l * sizeof(int)); //出错点
for (int i = 0; i < m; i++)
{
int left, right;
scanf("%d %d", &left, &right);
for (int j = left; j <= right; j++)
{
if (Buffer[j] == true)
{
Buffer[j] = false;
l--;
}
}
}
printf("%d\n", l);
free(Buffer);
}
}
return 0;
}
?
?
using namespace std;
int main(void)
{
int l, m;
int *Buffer = nullptr;
while (scanf("%d %d", &l, &m) != EOF)
{
if (l == 0)
continue;
else
{
l = l + 1;
Buffer = (int *)calloc(l, sizeof(int));
for (int i = 0; i < m; i++)
{
int left, right;
scanf("%d %d", &left, &right);
for (int j = left; j <= right; j++)
{
if (Buffer[j] == 0)
{
Buffer[j] = 1;
l--;
}
}
}
printf("%d\n", l);
free(Buffer);
}
}
return 0;
}
</details>
 
### [返回目录](#-1)
 
<h3 id="0.2">
问题 F:A+B和C
</h2>
http://codeup.hustoj.com/problem.php?cid=100000575&pid=5
 
### 我的错误代码
<details>
```C++
#include <cstdio>
using namespace std;
int main(void)
{
long T;
long A, B, C;
while(scanf("%d", &T) != EOF) //测试用例数限制
{
for (int i = 1; i <= T; i++)
{
scanf("%d %d %d", &A, &B, &C);
if(A + B > C)
printf("Case #%d: true\n", i);
else
printf("Case #%d: false\n", i);
}
}
return 0;
}
?
(注 : 该题尽量使用 long long, 防止值溢出)
?
#include <cstdio>
#include <cstring>
using namespace std;
int main(void)
{
long long T;
long long A, B, C;
long long i = 1;
scanf("%d", &T);
while (T--)
{
scanf("%lld %lld %lld", &A, &B, &C);
if (A + B > C)
printf("Case #%lld: true\n", i);
else
printf("Case #%lld: false\n", i);
i++;
}
return 0;
}
?
?
?
http://codeup.hustoj.com/problem.php?cid=100000576&pid=1
?
#include <cstdio>
#include <algorithm>
using namespace std;
int Upper_Bound(int *num, int left, int right, int x) //这里的题目要求是求出 x 的位置, 算法有问题
{
int mid;
while (left < right)
{
mid = (left + right) / 2;
if (x <= num[mid])
right = mid;
else
left = mid + 1;
}
return left;
}
int main(void)
{
int n, x;
while (scanf("%d", &n) != EOF)
{
int *num = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
sort(num, num + n); //不能使用sort排序, 这样会打乱原有数的位置
scanf("%d", &x);
int index = Upper_Bound(num, 0, n, x); //这里应为 n - 1
printf("%d\n", index);
delete[] num;
}
return 0;
}
?
(ps : 感觉这题出的不太严谨, 在无序数列的情况下是无法使用二分法的)
?
#include <cstdio>
using namespace std;
int BinarySearch(int *A, int left, int right, int x)
{
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (A[mid] < x)
left = mid + 1;
else if (A[mid] > x)
right = mid - 1;
else
return mid;
}
return -1;
}
int main(void)
{
int n, x;
while (scanf("%d", &n) != EOF)
{
int *num = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
scanf("%d", &x);
int index = BinarySearch(num, 0, n - 1, x);
printf("%d\n", index);
delete[] num;
}
return 0;
}
?
?
?
http://codeup.hustoj.com/problem.php?cid=100000577&pid=0
?
这道题我是做对了的, 但是当时想了很长时间. 不记得有没有看题解了
?
#include <cstdio>
using namespace std;
int main(void)
{
int h;
int space;
int print;
while (scanf("%d", &h) != EOF)
{
for (int i = 0; i < h; i++)
{
for (space = 0; space < (h - i) * 2 - 2; space++)
printf(" ");
for (print = 0; print < h + 2 * i; print++)
printf("*");
printf("\n");
}
}
return 0;
}
?
?
?
http://codeup.hustoj.com/contest.php?cid=100000577
?
这道题我也是一次就过了, 同样想了很长时间. 不记得有没有看题解了
?
#include <cstdio>
using namespace std;
int main(void)
{
int m;
int h;
while (scanf("%d", &m) != EOF)
{
for (int i = 0; i < m; i++)
{
scanf("%d", &h);
for (int I = 0; I < h; I++)
{
for (int j = 0; j < h - I - 1; j++)
printf(" ");
for (int k = 0; k < h + I * 2; k++)
printf("*");
printf("\n");
}
}
}
return 0;
}
?
?
?
?
这道题一次过, 不过看了题解...
?
#include <cstdio>
using namespace std;
int main(void)
{
int n;
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
printf(" ");
for (int k = 0; k < n - i; k++)
{
printf("*");
if (k < n - i - 1)
printf(" ");
}
printf("\n");
}
for (int i = 1; i < n; i++)
{
for (int k = 0; k < n - 1 - i; k++)
printf(" ");
for (int j = 0; j < 1 + i; j++)
{
printf("*");
if (j < i)
printf(" ");
}
if (i < n - 1)
printf("\n");
}
printf("\n");
}
return 0;
}
?
?
?
?
http://codeup.hustoj.com/problem.php?cid=100000578&pid=0
?
该题在算法笔记上有原题, 请参考算法笔记
?
?
?
?
http://codeup.hustoj.com/problem.php?cid=100000579&pid=0
?
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
int main(void)
{
char StrNum[100];
queue<int> StrToInt;
int szStrToInt = 0;
queue<int> Div;
stack<int> Mod;
int Convert[1000];
int mod;
while (scanf("%s", StrNum) != EOF)
{
for (int i = 0; i < strlen(StrNum); i++) //字符串转换
{
StrToInt.push(StrNum[i] - ‘0‘);
szStrToInt++;
}
while (StrToInt.front() != 0 || StrToInt.size() != 1)
{
for (int i = 0; i < szStrToInt; i++)
{
if (Div.empty())
{
Div.push(StrToInt.front() / 2);
mod = StrToInt.front() % 2;
StrToInt.pop();
if (!StrToInt.empty())
mod = mod * 10 + StrToInt.front();
}
else if (!StrToInt.empty())
{
Div.push(mod / 2);
mod = mod % 2;
StrToInt.pop();
if (!StrToInt.empty())
mod = mod * 10 + StrToInt.front();
}
}
Mod.push(mod);
if (Div.front() == 0)
{
Div.pop();
if (!Div.empty())
{
szStrToInt = Div.size();
for (int i = 0; i < szStrToInt; i++)
{
StrToInt.push(Div.front());
Div.pop();
}
}
else
break;
}
else
{
szStrToInt = Div.size();
for (int i = 0; i < szStrToInt; i++)
{
StrToInt.push(Div.front());
Div.pop();
}
}
}
if (StrToInt.front() == 0 && StrToInt.size() == 1)
printf("0\n");
else
{
while (!Mod.empty())
{
printf("%d", Mod.top());
Mod.pop();
}
printf("\n");
}
}
return 0;
}
?
这里涉及到一个算法, 即大数除法. 具体可参考其他博客
?
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
int main(void)
{
char StrNum[100];
queue<long long> StrToInt;
long long szStrToInt = 0;
queue<long long> Div;
stack<long long> Mod;
long long Convert[1000];
long long mod;
while (scanf("%s", StrNum) != EOF)
{
for (long long i = 0; i < strlen(StrNum); i++) //字符串转换
{
StrToInt.push(StrNum[i] - ‘0‘);
szStrToInt++;
}
while (StrToInt.front() != 0 || StrToInt.size() != 1)
{
for (long long i = 0; i < szStrToInt; i++)
{
if (Div.empty())
{
Div.push(StrToInt.front() / 2);
mod = StrToInt.front() % 2;
StrToInt.pop();
if (!StrToInt.empty())
mod = mod * 10 + StrToInt.front();
}
else if (!StrToInt.empty())
{
Div.push(mod / 2);
mod = mod % 2;
StrToInt.pop();
if (!StrToInt.empty())
mod = mod * 10 + StrToInt.front();
}
}
Mod.push(mod);
if (Div.front() == 0)
{
Div.pop();
if (!Div.empty())
{
szStrToInt = Div.size();
for (long long i = 0; i < szStrToInt; i++)
{
StrToInt.push(Div.front());
Div.pop();
}
}
else
break;
}
else
{
szStrToInt = Div.size();
for (long long i = 0; i < szStrToInt; i++)
{
StrToInt.push(Div.front());
Div.pop();
}
}
}
if (StrToInt.front() == 0 && StrToInt.size() == 1)
{
printf("%d\n", StrToInt.front());
StrToInt.pop();
}
else
{
while (!Mod.empty())
{
printf("%d", Mod.top());
Mod.pop();
}
printf("\n");
}
}
return 0;
}
?
原文：https://www.cnblogs.com/ICeVe/p/15159244.html