08.28
1、最小公倍数LCM
求法：两个数的乘积，除以他们的最大公因数。所以求最小公倍数实质上还是求最大公因数。
例题：求最小公倍数。
限制：正整数 <= 1000
求解：(a*b) / gcd(a,b)
2、素数筛法
即：判断一个数是否为素数。
方法：除到sqrt√n，看是否能整除。时间复杂度为O(√n)
技巧：
- 先求出边界 sqrt(n) + 1，保存在整数中，而不是在for循环中作为判断条件。这样只会计算一次。如果是在sqrt中，就会计算多次。
- 如果计算一个数组中的数是不是素数，可以单个判断，但是这样时间复杂度较高。做法：将一个素数的倍数都标记为非素数。
例题：找素数
限制：n<= 10000
代码实现：
初始化函数，init()
mark[i]标记为false
primeSize为0
for(int i = 2; i<= 10000; i++){
if(mark[i] == true) continue;
prime[primeSize++] = i; 记录素数
for(int j = i*i; j<= 10000; j+= i){
mark[j] = true; 标记倍数
}
}
main函数中对于每次循环
bool isOutput = false;
用来进行标记。
技巧：
- 在标记时，不必从2i开始标记，因为i*k已经被k标记过了。我们从
开始标记即可。
3、分解素因数
比如：求正整数N的素因数的个数。
例题：
要求：求素因数。输出有多少个素因数。
限制：N <
思路：首先利用素数筛法得到所有素数。输入n后，依次遍历所有素数，判断其是否是n的因数。
例题：求N的所有素因数的个数。
技巧：
- 要求的是
，但是只用自己分解到√10^9即可，如果有大于这个数的不能分解，那么它一定是素因数，并且只有一次。
-
已知素因数，求整因数个数
image.png
例题：整除问题
要求：给定n,a求 最大的 k，使 n!可以 a^k整除， 但不能被 a^(k+1)整除。
限制：n <= 1000, a<= 1000
技巧：
- 首先n!可能很大，不能直接求出数值再分解。
- 求k的方法，只需要分解出素因数之后再进行比较幂的数值求k即可。
实现过程如下：
- 按照之前的步骤，筛选范围内所有的素数。
- 计数器清零。计数器记录的是素因子对应的幂指数。cnt保存prime[]中对应的分解后的幂数。
for(int i = 0; i < primeSize; i++){
cnt[i] = cnt2[i] = 0;
}
- cnt的值计算如下
for(int i = 0; i < primeSize; i++){
int t = n;
while(t){
cnt[i] += t/prime[i];
t = t/prime[i];
}
}
- 对于比较小的a，可以直接分解素因数。
for(int i = 0; i< primeSize; i++){
while(a%prime[i] == 0){
cnt2[i]++ ;
a/= primt[i];
}
if(cnt2[i] == 0) continue;
if(cnt[i] / cnt2[i] < ans){
ans = cnt[i] / cnt2[i];
}
}
4、二分求幂
将指数进行分解即求其二进制。任何高次幂都可以用这种方法
例题：人见人爱A^B
限制：A，B <=10000
要求：求后三位的结果。所以就不用保存整体的，只用保存A和B分别后三位即可。
08.29
1、高精度整数
对于特别大的整数，需要用一个结构体来保存高精度整数
struct bigInteger{
int digit[1000];
int size;
};
例题：计算a+b
要求：a和b的位数不超过1000位
代码实现如下：
头文件：
#include <stdio.h>
#include <string.h>
set()，把str转化为数字，并保存在digit[]中。
int L = strlen(str);
for(int i = L - 1, j = 0, t = 0, c = 1; i>= 0; i--){
t += (str[i] - '0'*c);
j++;
c*= 10;
if(j==4 || i == 0){
digit[size++] = t;
j = 0;
t = 0;
c = 1;
}
}
output输出 printf("%04d",digit[i]);，前置位可能需要补零。
因为是自己定义的数组，需要重载+运算符
bigInteger operator + (const bigInteger &A) const {
bigInteger ret;
ret.init();
int carry;
for(int i = 0; i < A.size || i < size; i++){
int tmp = A.digit[i] + digit[i] + carry;
carry = tmp / 10000;
tmp %= 10000;
ret.digit[ret.size++] = tmp;
}
if(carry != 0){
ret.digit[ret.size++] = carry;
}
return ret;
}
2、高精度乘法
一般是一个高精度整数✖️一个普通的整数。
例题：输出阶乘
限制：N <= 1000
代码实现如下：
对于set()，如果原本的x不大，可以直接操作赋值到digit中，不用由str[]转过来那么麻烦。
void set(int x){
init();
do{
digit[size++] = x % 10000;
x/= 10000;
}while(x != 0);
}
重载*运算符
bigInteger operator * (const int x) const {
bigInteger ret;
ret.init();
int carry = 0;
for(int i = 0; i < size; i++){
int tmp = x * digit[i] + carry;
carry = tmp / 10000;
tmp %= 10000;
ret.digit[ret.size++] = tmp;
}
if(carry != 0){
ret.digit[ret.size++] = carry;
}
return ret;
}
3、综合例题：进制转换
要求：将 M 进的数 X 转换为 N 进制的数出。
限制：M,N <= 36, 输出时小写，且有大数据。
知识点：高精度需要进行：
高精数与普通整数求积，求商，求模
高精数与高精数求和
代码实现如下
头文件
#include <stdio.h>
#include <string.h>
加法和乘法和上面类似，下面重点看 / 和%
bigInteger operator / (int x) const {
bigInteger ret;
ret.init();
int remainder = 0;
for(int i = size - 1; i>= 0; i--){
int t = (remainder*10000 + digit[i])/x;
int r = (remainder*10000 + digit[i])%x;
ret.digit[i] = t;
remainder = r;
} 修改digit[i]的值。
ret.size = 0;
for(int i = 0; i< maxDigits; i++){
if(digit[i] != 0) ret.size = i;
}
ret.size ++; 修改size的值为相应的结果。
return ret;
}
%运算如下
int operator % (int x) const{
int remainder = 0;
for(int i = size - 1; i>= 0; i--){
int t = (remainder*10000 + digit[i])/x;
int r = (remainder*10000 + digit[i])%x;
remainder = r;
}
return remainder;
}
本题结束，难度还是比较大的。
补充：如果求一个高精度的整数除以一个比较小的数后的余数，可以用如下代码
int ans = 0;
for(int i = 0; str[i]; i++){
ans *= 10;
ans += str[i] - '0';
ans %= mod;
}
这个实际上就是除法的运算方法。
注意：高精度运算有时时间复杂度比较高，在估算时间复杂度时不能忽略这个。
4、map
功能是：将一个类型的变量映射为另一个类型
例题：产生冠军
要求：判断能否产生冠军，输出yes 或 no即可
知识点：拓扑排序，生成有向图。如果有结点入度为0并且这个节点唯一，说明是YES！/ 将选手的姓名映射为节点编号，需要标准对象map
代码实现如下：
对于每个测试用例(while中的)
初始化
for(int i = 0 ; i < 2*n; i++){
in[i] = 0;
}
M清空
M.clear();
对输入的进行在in[]中修改。
for(int i = 0; i<n; i++){. 要输入n组
char str1[50],str2[50];
scanf("%s%s",str1,str2);
string a = str1,b = str2;
int idxa,idxb;
if(M.find(a) == M.end()){
idxa = idx; idx是下一个要分配的数字
M[a] = idx++;
}
else idxa = M[a];
if(M.find(b) == M.end()){
idxb = idx;
M[b] = idx++;
}
else idxb = M[b];
这里是找到了idxa和idxb
in[idxb]++;
}
输入完之后，统计所有节点的入度，看看入度为0的节点的个数是不是1即可。
int cnt = 0;
for(int i = 0; i < idx; i++){
if(in[i] == 0) cnt++;
}
puts(cnt == 1? "YES" : "NO");
注意：
使用map,需要包含头文件 需要包含 map<string,int> M;
map的内部实现是红黑树。
5、滚动数组
作用：完成常数量优化和 减少代码量。
对于循环赋值操作，可以使用滚动数组来进行优化
说白了就是，之前的结果不再需要了，那么我可以只使用少数几个数组，每次分别保存在某个数组中，下一次再保存在另外一个数组中。
6、小技巧
- 可以将mod2运算改为位运算，将/2运算改为 >> 1，即右移1
- cin比scanf耗时多很多。输入外挂可以在scanf的基础上再次优化。（了解一下即可，估计我也用不上）
- 流氓剪枝：强行剪去我觉得不是答案的结果。
- 不要在程序中混用printf和cout,因为他们的输出机理不同，混用可能会造成不可预见的后果。
7、排版
根据题目示例来找规律。
例子：
代码实现如下：
#include <stdio.h>
int main(){
int h; 输入h
while(scanf("%d",&h) != EOF){
int maxline = h + (h-1)*2;
for(int i = 1; i<= h; i++){ 外面的，表示一共输出几行，每次循环是一行
for(int j = 1; j <= maxline; j++){ 每行都要输出maxline个字符，但是有的是* ，有的是前面的空格。
if(j < maxline - h - (i-1)*2 + 1){
printf(" ");
}
else
printf("*");
}
printf("\n");
} // end for-i 说明输出一行结束。
} //end while
return 0;
}
这个规律性比较强，对于规律性不强的，要先完成排版，再进行输出。
例子：叠筐
不太容易直接输出，就自己先进行排序。
限制：总的输出边长大小 n <= 80
思路：每次确定圈中内容时：都是先找到左上角的点。
代码实现如下：
#include <stdio.h>
int main(){
int outPutBuf[82][82];
char a,b;
int n;
bool firstCase = true;
while(scanf("%d %c %c",&n,&a,&b) == 3){
if(firstCase == true){
firstCase = false;
}
else
printf("\n"); 由于每次新输出都需要换行，但是第一次不需要换行，最后一次输出之后不需要换行，所以进行这个判断，只有第一行不用换行，其他都需要换行。
for(int i = 1,j = 1; i<= n; i+= 2,j++){ i<=n是因为要输出n行，i可以看作是边长。最开始变长是1，j用来计数，看是第几次输出。
int x = n/2 + 1, y = x; 找到最中心的节点
x = x - (j-1);
y = y - (j-1); //左上角的点
char c = j % 2 == 1? a:b; 要填充的字符是哪个
for(int k = 1; k <= i; k++){ i是最终的变长，k是开始一点一点输出。
outPutBuf[x + k - 1][y] = c;
outPutBuf[x][y + k - 1] = c;
outPutBuf[x + i - 1][y + k - 1] = c;
outPutBuf[x + k - 1][y + i - 1] = c;
} 保存完了
}
if(n!= 1){ 如果n = 1，只用输出一个，也没这么多情况了。
outPutBuf[1][1] = ' ';
outPutBuf[n][1] = ' ';
outPutBuf[1][n] = ' ';
outPutBuf[n][n] = ' ';
}
for(int i = 1; i <= n; i++){
for(int j = 1; i<= n; j++){
printf("%c",outPutBuf[i][j]);
}
printf("\n");
}
}
return 0;
}
8、贪心算法
思想：总是选择当前最好的选择
例题：
房子有N个房间，每个房间含的javabean的重量包含在J[i]中，需要的猫粮是F[i]，如果给的猫粮是F[i] * a%,得到的Javabean也是J[i]*a%.
限制：所有的整数 <= 1000。输出要限制到小数点后三位。
思想：每次都买性价比最高的东西。
代码实现如下：
商品的结构体的实现如下
struct goods{
double j;
double f;
double s;
bool operator < (const goods &A) const{
return s > A.s;
}
}
可以看成包含成本f、收益j，s是j/f，并且重载 < 运算符。这样就会按照性价比降序排列。看的是return s > A.s
main函数实现如下
int idx = 0;
double ans = 0;
while(idx < n && m > 0){
if(m > buf[idx].f){ 钱没花完，我还能买
ans += buf[idx].j;
m -= buf[idx].f;
}
else{
ans += buf[idx].j * m / buf[idx].f; 没钱了
m = 0;
}
idx ++;
}
贪心算法例题2:
要求：已知节目的时间表，如何看尽可能多的完整的节目。
限制：节目数n <= 100.
思想：贪心算法
第一个节目优先选择结束时间最早的，后面的选择 在观看完这个节目之后，仍然可以完整观看的节目中，结束最早的那个。
int currentTime = 0,ans = 0;
for(int i = 0; i < n; i++){
if(currentTime <= buf[i].startTime){
currentTime = buf[i].endTime;
ans ++;
}
}
printf("%d\n",ans);
要保证完整地看，需要currentTime <= buf[i].startTime
可以看出，思想还是比较简单的。但是如果想出难的话还是很难的。
至此，第二章及以后的所有章节均看完！撒花！机试水平有了从0到0.001的提升！
还需要考虑的一个很重要的内容是：时间复杂度的估计。
对于限制1秒，我们不能超过百万级别，即不能超过1000万。
完结撒花！并且九度OJ是不能再用的，牛客网或PAT均可。
PAT (Advanced Level) Practice
08.30
1、A+B Format
要求：输出a+b，多位数字要以，分割
限制： 10 ^(-6)<a , b < 10^6 / 只输入一组数据
难点：如何输出逗号
参考别人的答案，还是把整型数字转为字符串
代码实现如下：
#include <stdio.h>
char sumchar[10]; 保存数组
void change(int number){ 把数字转为字符型
int index = 0, times = 0; index是在数组中的下标，times是数字的位数
while(number != 0){
if(times % 3 == 0 && times != 0){
sumchar[index++] = ','; 加上逗号
}
sumchar[index++] = number % 10 + '0'; 数字
number /= 10;
times = times+1; 是数字，位数加1
}
}
int main(){
int a,b = 0;
int sum,i = 0 , end_index = 0;
scanf("%d %d",&a,&b);
sum = a+b;
if(sum < 0){
printf("-");
sum = -sum;
}
change(sum); //这里不太合适，没有考虑0的情况
for(i = 0; sumchar[i] != 0 && i <= 10; i++){
end_index = i; 找到末尾的数字
}
for(i = end_index; i>= 0; i--){
printf("%c", sumchar[i]); 倒序输出
}
return 0;
}
这个有一个极端的用例会出错。
参考别人的代码实现,发现少了结果是0的情况。如果是0，就不会输出任何东西。
有挺多细节需要考虑，突然想到需要倒序输出，是一个后进先出的例子，如果熟练的话可以用栈来实现。
08.31
1、KY2:查找和排序
要求：成绩按照从低到高和从高到低分别排序、输出
限制：无
知识点：排序
卡在：忘记如何对结构体中的变量进行排序了。
参考代码，分别对两种排序用两个函数实现。输出方法也用一个函数来实现了。排序它内部是使用冒泡排序来完成的。
收获：
- struct前面要加typedef
- 定义数组长度时，大小最好不要弄成变量n，可以设一个较大的绝对不会超过的数。
- 字符串和整型数字是可以在同一个scanf中输入的，
scanf("%s %d",a,&b)即可
但是感觉这种还是比较复杂的，如果可以使用sort()来进行排序，就很简单了。
参考sor()的代码，结构体排序的方法是重新写一个排序函数。如下
bool cmp0(Stu a,Stu b){
if(a.score!=b.score){
return a.score>b.score;
}else{
return a.num<b.num;
}
}
这个是降序排列，如果成绩相等，num小的排在前面
if(temp==1){
std::sort(stu,stu+n,cmp1);
}
else if(temp==0){
std::sort(stu,stu+n,cmp0);
}
如下语句即可完成sort()的调用。
2、求约数的个数
限制：个数n<=1000，每个数字的大小Num<=1000000000
知识点：对大数据的处理
卡在：这么大的数据如何表示
别人代码实现如下：
i*i<num的形式，数值稳定性更好,比sqrt()好
#include<iostream>
using namespace std;
int numOfDivisor(int num)
{
int ans = 0;
int i;
for (i = 1; i*i<num; i++) 遍历所有小于根号下的数
{
if (num%i == 0)
ans += 2; 这里一大一小两个数
}
if (i*i == num) ans++; 正好中间，就+1
return ans;
}
int main()
{
int n, num;
while (cin >> n)
{
for (int i = 0; i<n; i++)
{
cin >> num;
cout << numOfDivisor(num) << endl;
}
}
return 0;
}
输入输出在main函数中，求约数是在numDivisor函数中。
这个是最简单的方法，但是耗时也比较大。
还可以用 质数筛法，筛选出所有的质数。（但是这有什么用呢？）有用：如果是质数，就不用再往下判断它有没有因子了，它除了1和它本身，没有其他约数了就。
/*
* 因数个数（使用到质数筛法）
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
const int MAXN = 4e4;
bool isPrime[MAXN]; //标记数组
vector<int> prime; //保存质数
void initial(){ //初始化
fill(isPrime,isPrime+MAXN,true);
isPrime[0]=false;
isPrime[1]=false;
for(int i = 2;i<MAXN;i++){
if(!isPrime[i]){ //非质数，则跳过该数
continue;
}
prime.push_back(i);
for(int j = i+i;j<MAXN;j+=i){
isPrime[j]=false; //质数的倍数为非质数
}
}
return;
}
int fun(int n){
vector<int> exponent;
for(int i = 0;i<prime.size();i++){
int factor = prime[i];
if(n<factor){
break;
}
if(n%factor == 0){
int num = 0;
while(n%factor == 0){
n = n/factor;
num++;
}
exponent.push_back(num);
}
}
if(n>1){
exponent.push_back(1);
}
int ans = 1;
for(int i = 0;i<exponent.size();i++){
ans*=exponent[i]+1;
}
return ans;
}
int main(){
initial();
int m;
while(scanf("%d",&m)!=EOF){
if(m == 0){
break;
}
for(int i = 0;i<m;i++){
int n;
scanf("%d",&n);
printf("%d\n",fun(n));
}
}
return 0;
}
初始化其实就是素数筛法，找出所有的质数。
fun()就是求因数的函数。
变量：
vector exp
prime里面放的是所有素数
对每一个素数，分别进行如下操作
factor是当前素数
如果n还可以分解为这个素数，统计出现了多少次这个素数，记在exp栈里面。同时n也除去相应的数。
最终的个数根据之前的一个公式来计算：
(e1+1)(e2+1)(e3+1)....(en+1)
- vector除了可以用来当栈操作，在不使用栈的特性时，也可以单纯地用来计数。
09.01
1、A + B 的多项式形式
限制：K <= 10, N(指数) <= 1000
考察：直接用数组记录即可。（位置表示索引，有点类似哈希）
不要一不会就看答案！多思考！思考是进步的过程！！！
09.03
1、多项式相加
- 对于double型，判断是否为0，最好考虑误差
- C++中，abs要使用头文件cmath，C中使用stdlib.h
输出错误，应该倒序输出
现在的问题在 double型系数不能正确读取,刚才不知道为什么错了，重新改为scanf("%lf",&xishu)，即可。
自己代码实现
#include <iostream>
#include <cmath>
using namespace std;
double A[11] = {0},B[11] = {0},ans[11] = {0};
int main(){
int Ka,Kb,i;
scanf("%d",&Ka);
int count_num = 0;
int index;
double xishu;
while(Ka--){
scanf("%d %lf",&index, &xishu);
A[index] = xishu;
}
scanf("%d",&Kb);
while(Kb--){
scanf("%d %lf",&index, &xishu);
B[index] = xishu;
}
for(i = 0; i<= 11; i++){
ans[i] = A[i] + B[i];
if( abs(ans[i] - 0) >= 0.00000001){
count_num ++;
}
}
printf("%d",count_num);
for(i = 11; i >= 0; i--){
if(abs(ans[i] - 0) >= 0.00000001)
printf(" %d %l.1f",i,ans[i]);
}
return 0;
}
其实自己弄的复杂了，并且答案还不对。
K是数字的个数，但是n才是系数的个数，所以数组的大小应为N的个数。
还是不知道自己哪里错了，参考别人的代码
#include<stdio.h>
const int max_n = 1111;
double a[max_n] = {}; 只用一个来实现就够了
int main(){
int k, n, count = 0;
double e;
scanf("%d", &k);
for(int i = 0; i < k; i ++){
scanf("%d%lf", &n, &e);
a[n] = e;
}
scanf("%d", &k);//这里k只是为了存储，所以这儿k是可以重复存放值。
for(int i = 0; i < k; i ++){
scanf("%d%lf", &n, &e);
a[n] += e;//这儿其实就是有相同的就相加，没有相同的就不想加
}
for(int i = 0; i < max_n; i ++){
if(a[i] != 0){
count ++;
}
}
printf("%d", count);
for(int i = max_n - 1; i >=0; i --){
if(a[i] != 0) printf(" %d %.1f", i, a[i]);
}
return 0;
}
2、Emergency
题目：给出图，找出最短路径。
限制：N(节点数)<500
知识点：印象中，图论用邻接矩阵实现
小细节：最后没空格
需要用到Dijkstra 算法。
设置内存，头文件#include <memory.h>
fill函数，可以设定为任意指定的值，头函数<algorithm>
代码实现过程
1、定义变量，初始化
2、Dijk算法{
找出最小的顶点,标记这个顶点已经计算过了
有两种情况会替换掉原来的值
}
不懂Dijkstra算法为什么有个没有用到的i的for循环
3、Counting Leaves
题目：
限制：N节点数量 < 100，M 非叶子结点的数量
知识点：考察🌲的定义和层次遍历
参考别人代码，可以用dfs，也可以用bfs.
dfs实现如下
头文件
#include<iostream>
#include<vector>
#include<algorithm> 后面有一个max()函数，所以需要algorithm头文件
using namespace std;
定义变量
vector<int> v[100];
int book[100];
int maxDepth=-1;
void dfs(int index,int depth){
// 此时第index结点已经没有子结点了，则表明是叶子结点
if(v[index].size()==0){
// 统计该叶子结点
book[depth]++;
// 更新最大层次
maxDepth = max(maxDepth,depth);
return ;
}
// 递归调用
for(int i=0;i<v[index].size();i++){
dfs(v[index].at(i),depth+1);
}
}
int main(){
int N,M;
int node,K;
while(cin>>N>>M){
for(int i=0;i<M;i++){
cin>>node>>K;
for(int j=0;j<K;j++){
int temp;
cin>>temp;
v[node].push_back(temp); 把子树的信息输入到v中
}
}
// 从第一个结点开始，第零层
dfs(1,0);
cout<<book[0];
for(int i=1;i<=maxDepth;i++){
cout<<" "<<book[i];
}
} end while
return 0;
}
还可以使用bfs，不同的是，需要额外的数组来统计每个节点所在的层次
逻辑搞懂了其实也不难
4、Spell It Right
题目：求和，字母输出
限制：N(数字) < 10的100次方
知识点：大数存储，每个数字转换为一个字母，数组实现
一道挺简单的题，编译还是有很多错。
首先字母表的定义
vector不是pop，是pop_back()
原来的结果错误，是因为少了一层digit嵌套。
测试结果发现还有一个段错误，是没有考虑到输出为0的情况，加入为0的情况就正确啦！我人生的第一个AC!!
代码实现如下
#include <iostream>
#include <vector>
using namespace std;
char num[110];
char zimubiao[10][10] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int main(){
int i;
int ans = 0,flag = 0;
scanf("%s",num);
for(i = 0; num[i]!= 0 && i < 110; i++){
ans += num[i] - '0';
}
vector<int> digit;
flag = ans;
while(ans != 0){
digit.push_back(ans%10);
ans /= 10;
}
if(flag != 0){
printf("%s",zimubiao[digit[digit.size()-1]]);
digit.pop_back();
}
else{
printf("%s",zimubiao[0]);
}
while(digit.size()!= 0){
printf(" %s",zimubiao[digit[digit.size()-1]]);
digit.pop_back();
}
return 0;
}
也可以用数组实现，只计算一个数组有效长度即可。
5、Sign In and Sign Out
题目：签到签退，要求找出最早和最晚时间。
限制：ID_number字符串字符 < 15
知识点：对时间格式的数据进行操作的能力
输入的时候 scanf("%s %d:%d:%d %d:%d:%d",ID,&H1,&M1,&S1,&H2,&M2,&S2);，这样输入。
比较的时候，都化为秒数去比较。
收获：
不用所有数据都记录，只记录最开始和最后的数据即可，每次输入之后都进行比较。
字符串赋值的时候，先清空，再赋值
strcpy(in,"");strcpy(in,ID);输出：printf("%s %s",in,out);
6、Maximum Subsequence Sum
题目：最长子序列
知识点：动态规划
限制：数量K <= 10000，如果都是负数，需要特殊处理
j表示以j结尾
变化的过程：dp[i][j] = dp[i][j-1] + v, (❌). dp[i]=max(dp[i],dp[i-1]+a[i])
代码实现如下：
#include<iostream>
#include<cstdio>
using namespace std;
int a[10005],l[10005],r[10005];
int dp[10005];//以a[i]结尾的最大连续区间和
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
dp[i]=a[i];//初始化
} 首先把dp初始化了，所以后面比较的时候就可以拿dp的值比较.
l[0]=r[0]=0;
for(int i=1;i<n;i++)
{
if(dp[i-1]+a[i]>=dp[i])//如果a[i]>=0，且数值变大了
{
dp[i]=dp[i-1]+a[i];
l[i]=l[i-1];//区间左端点不变，右端点更新
r[i]=i;
}
else//如果a[i]是负数，新建一个区间
{
l[i]=i;
r[i]=i;
}
}
int ans=-1,pos=0,flag=0;
for(int i=0;i<n;i++)
{
if(dp[i]>ans)
{
flag=1;
ans=dp[i];
pos=i;
}
}
//cout<<flag<<endl;
if(flag==0)
cout<<0<<' '<<a[0]<<' '<<a[n-1]<<endl;
else
cout<<ans<<' '<<a[l[pos]]<<' '<<a[r[pos]]<<endl;
return 0;
}
也可以用模拟的方法
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
#include<map>
#define MAX 1000000
#define ll long long
using namespace std;
int a[10005];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int ans=-1,l=0,r=n-1;
int temp=0,first=0;
for(int i=0;i<n;i++)
{
temp=temp+a[i];
if(temp<0)
{
temp=0;
first=i+1;
}
else if(temp>ans)
{
ans=temp;
l=first;
r=i;
}
}
if(ans<0)
ans=0;
cout<<ans<<' '<<a[l]<<' '<<a[r]<<endl;
return 0;
}
思想是：每次都加上一个试试，有最好的结果（更新ans），一般的结果（什么也不做）和最差的结果（归0）。
7、Elevator
题意：电梯升降，计算时间。
限制：所有数 < 100
没有难度，数组计算和之前的差即可。但是答案都错啦？
因为：1没有print 2 i改为下标从1开始之后，没有 <= n
更改之后代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n, a[110],diff[110],i;
int ans = 0;
scanf("%d",&n);
a[0] = 0;
for(i = 1; i<= n; i++){
scanf("%d",&a[i]);
diff[i] = a[i] - a[i-1];
}
for(i = 1; i <= n; i++){
if(diff[i] >= 0){
ans += (diff[i]*6) + 5;
}
else
ans += (-diff[i]*4) + 5;
}
printf("%d",ans);
return 0;
}
8、Product of Polynomials
题意：多项式相乘
知识点：仍然是数组的操作
限制： K <= 10，N <= 1000
实现：指数相加，系数相乘
在调试发现输入的方法不对，导致数据篡位
初次代码实现：（有错）
#include <iostream>
#include <algorithm>
#include <cmath>
double A[1100] = {0},B[1100] = {0},ans[2200] = {0};
int Ka,Kb,N,count = 0;
int main(){
int i = 0, j= 0;
scanf("%d",&Ka);
for(i = 1; i<= Ka; i++){
scanf("%d%lf",&N,&A[N]);
}
scanf("%d",&Kb);
for(i = 1; i<= Kb; i++){
scanf("%d %lf",&N,&B[N]);
}
for(j = 1; j <= 1100; j++){
for(i = 1; i<= 1100; i++){
ans[i+j] += B[i]*A[j];
}
}
for(i = 0; i<= 2200; i++){
if(ans[i] != 0) count++;
}
printf("%d",count);
for(i = 2200; i>= 0; i--){
if(abs(ans[i]) > 1e-5) printf("%d %l.1f",i,ans[i]);
}
return 0;
}
错误：
- 应该先输入N，再输入系数，即给数组矩阵赋值，与确定数组的坐标，不能在同一条语句中。
- for循环计算ans时，这时候算的是系数，从0开始。而K输入时，需要的是K次，若从1开始也没关系，只用计数即可。
09.04
1、A*B 多项式相乘
测试用例正确的，但是提交，答案还是错误.
为什么还是错的，我要疯了。
参考别人答案
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
double A[1020]={0.0};
double B[1020]={0.0};
double C[2020]={0.0};
int ka,kb;
cin>>ka;
for(int i = 0;i<ka;i++)
{
int nk;
double a;
cin>>nk>>a;
A[nk] = a;
}
cin>>kb;
for(int i = 0;i<kb;i++)
{
int nk;
double a;
cin>>nk>>a;
B[nk] = a;
}
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++)
{
C[i+j]+=A[i]*B[j];
}
int count = 0;
for(int i=0;i<=2000;i++)
if(C[i]!=0.0)
count++;
cout<<count;
for(int i = 2000;i>=0;i--)
if(C[i]!=0.0){
cout<<" "<<i<<" ";
printf("%.1lf",C[i]);
}
return 0;
}
把scanf 都换位 cout等，就有部分错误了
把最后输出换为printf("%.1lf",ans[i])
部分正确。
还是不知道为什么错，先不管了。
2、Radix
题目：进制转换
限制：N不超过10个数字，
难点：怎么确定进制？要一个一个去试吗？试到最大结束？
参考结果：虽然思路可以，但是超时
可以用二分法来确定
基数的最小值：N2的最大权值 + 1
基数的最大值：N1 + 1
mx用于计算N2的最大权值
真正二分的过程用while来实现
while(l <= r){
......
如果偏大
if(tmp > num1 || tmp < 0)
r = mid - 1;
else if(tmp < num1) {
l = mid + 1;
}
else{
cout << mid;
return 0;
}
}
收获1:
- 该用头文件
#include <bits/stdc++.h>万能头文件 - 进制可能是很大的，用longlong型
- 一个非常巧妙的进制转换的方法
for(int i=0;i<len1;++i){
12 num1*=rad; 每次都这样，最前面的数肯定乘的多。
13 if(s1[i]>='0'&&s1[i]<='9')
14 num1+=s1[i]-'0';
15 else
16 num1+=s1[i]-'a'+10;
17 }
3、World Cup Betting
计算、输出题
每一场都选最大的即可
开心！第一次无改错直接编译通过且答案完全正确！！
#include <bits/stdc++.h>
using namespace std;
double peilv[4][4]; 存放赔率
double ans = 0; 最后结果
char c[3]; 存放标志 WTL
int i = 1,j = 1;
int main(){
for(i = 1; i <= 3; i++){
cin >> peilv[i][j] >> peilv[i][j+1] >> peilv[i][j+2];
peilv[i][0] = max(max(peilv[i][j],peilv[i][j+1]),peilv[i][j+2]);
if (peilv[i][0] == peilv[i][j]) c[i-1] = 'W';
if (peilv[i][0] == peilv[i][j+1]) c[i-1] = 'T';
if (peilv[i][0] == peilv[i][j+2]) c[i-1] = 'L';
}
ans = (peilv[1][0]*peilv[2][0]*peilv[3][0]*0.65 - 1)*2;
cout << c[0] << " " << c[1] << " " << c[2] << " " << ans;
return 0;
}
4、 The Best Rank
题意：找出每个学生最好的排名
限制：N和M < 2000
考察：对数组的操作
思路： A C M E 四门课的N成绩，分别sort排序，结果保存在数组中。
查询的M个人，分别按顺序招，输出排名最靠前的。
我想到的是单纯用数组存储，参考别人，结构体存储更简便。
代码如下
#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
int id, best;
int score[4], rank[4];
}stu[2005];
int exist[1000000], flag = -1;
bool cmp1(node a, node b) {
return a.score[flag] > b.score[flag];
}
int main(void ){
int n, m, id;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
}
for( flag = 0; flag <= 3; flag++) {
sort(stu, stu + n, cmp1);
stu[0].rank[flag] = 1;
for(int i = 1; i < n; i++) {
stu[i].rank[flag] = i + 1;
if( stu[i].score[flag] == stu[i-1].score[flag] )
stu[i].rank[flag] = stu[i-1].rank[flag];
}
}
for( int i = 0; i < n; i++) {
exist[stu[i].id] = i + 1;
stu[i].best = 0;
int minn = stu[i].rank[0];
for( int j = 1; j <= 3; j++) {
if( stu[i].rank[j] < minn) {
minn = stu[i].rank[j];
stu[i].best = j;
}
}
}
char c[5] = {'A', 'C', 'M', 'E'};
for( int i = 0; i < m; i++) {
scanf("%d", &id);
int temp = exist[id];
if( temp ) {
int best = stu[temp-1].best;
printf("%d %c\n", stu[temp-1].rank[best], c[best]);
} else {
printf("N/A\n");
}
}
return 0;
}
5、Battle Over Cities
之前做过
限制：N城市数目 < 1000,
其实就是利用深度遍历，根据一个点，把其相邻的所有点都遍历一遍。
6、Waiting in Line
知识点：考察队列、时间 操作
每过一分钟，进行一次操作
#include <iostream>
#include <queue>
using namespace std;
struct Peo{
int time, constTime, leaveTime, ind;
}p[1001];
queue<Peo> q[21];
int main(int argc, char const *argv[])
{
int N, M, K, Q;
cin >> N >> M >> K >> Q;
for (int i = 1; i <= K; ++i){
cin >> p[i].time;
p[i].ind = i;
p[i].constTime = p[i].time;
}
int index = 1, cnt = 1;
for (int i = 1; i <= 10000; ++i){
while(cnt <= N*M && index<=K){
for (int j = 1; j <= N; ++j){
if(q[j].size()<M) {
q[j].push(p[index++]);
cnt++;
}
}
}
for (int j = 1; j <= N; ++j){
int ind = q[j].front().ind;
p[ind].time--;
if(p[ind].time==0){
p[ind].leaveTime = i;
q[j].pop();
cnt--;
}
}
}
for (int i = 0; i < Q; ++i){
int num; cin >> num;
if(p[num].leaveTime-p[num].constTime<540)
printf("%02d:%02d\n", (p[num].leaveTime+480)/60, (p[num].leaveTime+480)%60);
else printf("Sorry\n");
}
return 0;
}
7、Reversible Primes
题目：素数倒过来也是可逆的
限制：数字N < 10^5 进制D <= 10
写代码：6:53 - 7:10
简单地改错之后，运行超时了。
再改之后，还是答案错误.
疑问：23 ，2这个数组
理解错题意了。
先把23转为二进制，再反过来，再转为10进制，再算是否为素数。
自己写的代码如下：
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;
char kaishi[8];
int index_q = 7, i;
int D;
int quanzhong = 0;
int num = 0;
bool flag = true;
int main(){
cin >> kaishi >> D;
while(kaishi[0] != '-'){
for(i = 0; i < 7; i++){
if(kaishi[i] == 0){
index_q = i;
break;
}
}
quanzhong = 1;
for(i = 0; i < index_q; i++){
num += (kaishi[i] - '0')*quanzhong;
quanzhong *= D;
}
int bianjie = (int)(sqrt(num)+0.5);
for(i = 2; i< bianjie; i++){
if(num % i == 0 || num %2 == 0){
flag = false;
break;
}
}
if(flag) cout << "Yes" <<endl;
else cout << "No" << endl;
cin >> kaishi >> D;
}
return 0;
}
参考别人代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,d;
while(cin>>n){
if(n<0)
break;
cin>>d;
int flag=0;
for(int i=2;i*i<=n;++i)
if(n%i==0)
flag=1;
int a[27]={0};
int cnt=0;
while(n){
a[++cnt]=n%d;
n/=d;
}
int x=0;
for(int i=1;i<=cnt;++i){
x*=d;
x+=a[i];
}
if(x==1)
flag=1;
for(int i=2;i*i<=x;++i)
if(x%i==0)
flag=1;
if(flag)
cout<<"No"<<"\n";
else
cout<<"Yes"<<"\n";
}
return 0;
}
收获
- 不用sqrt，用i*i < n
8、Phone Bills
题意：计算电话账单
输入：24个数
这是一道考察基本功和逻辑的题，没有太多算法，读懂题意就是算法。
题目有点难懂，其次，要使用map
map中的所有数据都是有序的
用法如下
std:map<int, string> personnel;
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
难度略大，如果真实遇到了大概率放弃
前面有点都是这种数据处理题，倒着开始做
9、Heap Paths
之前测过
题意：遍历每一条路径
限制：节点N <= 1000
考察：堆、深度优先遍历
10、Vertex Coloring
做过
限制：N、M < 10^4
代码实现如下：
#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct node { int t1, t2; };
int main() {
int n, m, k, i;
cin >> n >> m;
vector<node> v(m);
for (i = 0; i < m; i++) cin >> v[i].t1 >> v[i].t2;
cin >> k;
while (k--) {
int color[10009] = { 0 };
bool flag = true;
set<int> se;
for (i = 0; i < n; i++) {
cin >> color[i];
se.insert(color[i]);
}
for (i = 0; i < m; i++) {
if (color[v[i].t1] == color[v[i].t2]) {
flag = false;
break;
}
}
if (flag)
printf("%d-coloring\n", se.size());
else
printf("No\n");
}
return 0;
}
收获：
- <set>中的数据是已经排好序的，并且不重复，可以用来计数
11、Decode Registration Card of PAT
限制：N card的数量 < 10^4，M查询的数量 < 100
考察：对数据的处理
思路：用结构体来存储每条信息，根据不同的type输出
参考如下文章：
https://blog.csdn.net/liuchuo/article/details/84973049
收获：
- 如果<map> 超时，换成 unordered_map
- 一些库函数，输出时很方便
- auto
12、Google Recruitment
题意：找某个固定数字的素数
考察：素数筛法吧？
是找素数，但是没用素数筛，直接常规的方法
收获：
- 截一个string字符串
13、LCA in a Binary Tree
给出树的中序和前序遍历，构建出这棵树，再递归查找公共祖先
09.06
1、上题LCA
我恨自己明明有时间为什么不看他！说不定能多对一道题呢！
虽然没写出来，但是很接近了。
头文件如下
#include<iostream>
#include<cstdio>
#include<map> 为了方便映射，用了map
using namespace std;
const int maxn = 10010;
int in[maxn];
int pre[maxn];
定义节点的数据结构，一个数值两个指针
struct node{
int val;
node* left;
node* right;
};
map<int,node*>mp; 定义一个map映射，int型为节点的数值，node*为左节点和右结点
创建，有四个参数，分别是起始位置和终止位置
node* create(int preL,int preR,int inL,int inR){
if(inL>inR) return NULL; 这个是循环结束的终止条件
node* now = new node; 创建一个节点，作为这次找到的节点
now->val = pre[preL]; 这个值是 先序遍历的第一个值
int i;
for(i=inL;i<=inR;i++){
if(in[i]==pre[preL]) break; 在中序遍历中找到根节点的位置
}
int numLeft=i-inL; 左子树的节点的数目。
now->left=create(preL+1,preL+numLeft,inL,i-1); 改变位置，这里的参数要理解。
now->right=create(preL+numLeft+1,preR,i+1,inR);
mp[now->val]=now; 把结点弄到mp中
return now;
}
这个是根据题意来的，就是我们要
node* lca(node* root,node* a,node* b){
if(root==NULL || root==a || root==b) return root; 特殊情况
node* L = lca(root->left,a,b);向下查找
node* R = lca(root->right,a,b);
if(L==NULL) return R;
if(R==NULL) return L;
return root;
}
int main()
{
int m,n;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
} 输入
node* root = create(0,n-1,0,n-1); 建树
for(int i=0;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
if(!mp[a] && !mp[b]) printf("ERROR: %d and %d are not found.\n",a,b);
else if(!mp[a]) printf("ERROR: %d is not found.\n",a);
else if(!mp[b]) printf("ERROR: %d is not found.\n",b);
输出错误提示
else{
node* res = lca(root,mp[a],mp[b]); 找到结果
if(res->val==a)
printf("%d is an ancestor of %d.\n",a,b);
else if(res->val==b)
printf("%d is an ancestor of %d.\n",b,a); 特殊输出
else
printf("LCA of %d and %d is %d.\n",a,b,res->val);
}
}
return 0;
}
留下了悔恨的泪水😢
09.07
1、Travelling Salesman Problem
问题：求最短路径，回到原始点
限制：顶点数N < 200, M < 100, 接下来输出K条路径
不懂Dijkstra算法为什么有个没有用到的i的for循环
1、进制转换
题目要求：十进制转为二进制
限制：数字很大，个数可能为30个数字/ 数字是非负数。
难点：数字很长，不能用普通的整型来表示，需要分割、处理等。
正好是上道题说的 用vector来实现
代码实现如下：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string Divide(string str, int x){
int reminder = 0;
for(int i = 0; i < str.size(); i++){
int current = reminder * 10 + str[i] - '0';
str[i] = current / x + '0';
reminder = current % x;
}
int pos = 0;
while(str[pos] == '0')
pos++;
return str.substr(pos);
}
int main()
{ string str;
while(cin >> str){
vector <int> binary; 对于每次输入，创建一个int 型的binary。
while(str.size() != 0){
int last = str[str.size() - 1] - '0'; 取出来最后的数字
binary.push_back(last % 2); 把最后一位处理，放入
str = Divide(str, 2);
}
for(int i = binary.size() - 1; i >= 0; i--){
cout << binary[i]; 输出
}
cout << endl;
}
return 0;
}
才疏学浅，看不懂。看另一个，通过C语言实现
#include <stdio.h>
int conversion(int x,int y,int s[],int d[],int n)
{
int size=0;
int i,j,k;
i=0;
while(i<n)
{
int carry=0;
for(j=i;j<n;j++)
{
int t=(s[j]+carry*x)%y;
s[j]=(s[j]+carry*x)/y;
carry=t;
}
d[size++]=carry;
while(s[i]==0&&i<n) i++;
}
return size;
}
int main()
{
int dst[1000];
int src[1000];
char str[32];
while(scanf("%s",str)!=EOF)
{
int i;
int len=strlen(str);
for(i=0;i<len;i++)
{
src[i]=str[i]-'0';
}
int n=conversion(10,2,src,dst,len);
for(i=n-1;i>=0;i--) printf("%d",dst[i]);
printf("\n");
}
}
输入的长整型保存在str[]中。使用了一个函数进行转换。把10进制转为2进制。
1、A+B for Polynomials
题目：A和B是多项式，求A+ B
限制：k<=10, N <= 1000
2、例题：给定前序和后序，计算中序有几种情况。
这是一个定式，前序，后序给定，划分子问题时，可能有多种左右子树的划分方式，参见柳神对 PAT 1119 的解答，适当变形即可.
知识点：先序中序后序
限制：节点数N <= 30
代码实现
#include <iostream>
#include <vector>
using namespace std;
vector<int> in, pre, post;
bool unique = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
只剩下一个节点了，直接入即可
if(preLeft == preRight) {
in.push_back(pre[preLeft]);
return;
}
根节点符合情况，
if (pre[preLeft] == post[postRight]) {
int i = preLeft + 1; //左子树的开始
while (i <= preRight && pre[i] != post[postRight-1]) i++; //找到右子树的根节点，即左右子树的分界线，用i表示。
if (i - preLeft > 1) //左子树还能再划分
getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
else //左子树只有一个，或者没有左子树，这个节点来回移动
unique = false; 没懂
in.push_back(post[postRight]);
getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
}
}
int main() {
int n;
scanf("%d", &n);
pre.resize(n), post.resize(n);
for (int i = 0; i < n; i++)
scanf("%d", &pre[i]);
for (int i = 0; i < n; i++)
scanf("%d", &post[i]);
getIn(0, n-1, 0, n-1);
printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
for (int i = 1; i < in.size(); i++)
printf(" %d", in[i]);
printf("\n");
return 0;
}
收获：
- 如果出现
reference to 'xxxxxxx' is ambiguous，可能是定义的变量和库中的某个变量撞名字了，把变量的名字改掉就可以了。 - vector 里面的resize，可以设置内存大小
3、PAT考纲
参考 //www.greatytc.com/p/3814d99bed25
PAT-A总共有4题，时间为3小时。三四大题 是一题图、一题树的概率较大，偶尔动态规划，贪心算法等。 第二题 一般是STL(map,set,vector为主，偶尔队列，堆栈)。第一题小题(逻辑题，字符串处理，数学，枚举)，要么简单，要么读题复杂理解复杂情况不容易想到，但是程序不会太复杂。其他的比如排序、查找、哈希、递归、递推、尺取法、哈夫曼、链表、素数的判断、数学问题、模拟、逻辑什么的，不需要复习，一般都融在题目里，是最基本的，看能力。
浙大2019原题：
happy 数：任给一个数，求其各位平方和，求迭代到 1 所需次数，或者形成圈的起始数
给定无序数组排序给定宽度并用 Zig zag 输出（PAT 原题）
给定前序判断是否是 avl 树（PAT 原题）
给定图，给定顶点子集，排序输出顶点子集图中度前 3 的点，度相同输出编号小的
https://pintia.cn/problem-sets/994805148990160896/problems/994805156145643520
字符串处理
一个很长（长度为 ）的数字字符串，要求删除
（
） 个数，使得得到的数最小。（60/100）
需要思考的较多，写起来很简单。越大的数，越先删除，对于需要删除的同等大小的数，其余的数都不比他大，所以先删除前面的。但是有特殊情况需要考虑，例如 ，删除 1 位的最佳选择应该是直接删除
而不是
，因为这样会使最高位得以降低。这种情况需要优先处理。我当时就没有考虑到。
动态规划
男孩女孩排列问题，要求连续男孩的个数不超过 个的可能的排列个数。（70/100）
动态规划问题，划分子问题求解。当时使用的递归结果超时了。
PAT顶级 1004 To Buy or Not to Buy - Hard Version (35分) 不会做
做题还有：九度教程
