08.28
1、最小公倍數(shù)LCM
求法：兩個數(shù)的乘積，除以他們的最大公因數(shù)。所以求最小公倍數(shù)實質上還是求最大公因數(shù)。
例題：求最小公倍數(shù)。
限制：正整數(shù) <= 1000
求解：(a*b) / gcd(a,b)
2、素數(shù)篩法
即：判斷一個數(shù)是否為素數(shù)。
方法：除到sqrt√n，看是否能整除。時間復雜度為O(√n)
技巧：
- 先求出邊界 sqrt(n) + 1，保存在整數(shù)中，而不是在for循環(huán)中作為判斷條件。這樣只會計算一次。如果是在sqrt中，就會計算多次。
- 如果計算一個數(shù)組中的數(shù)是不是素數(shù)，可以單個判斷，但是這樣時間復雜度較高。做法：將一個素數(shù)的倍數(shù)都標記為非素數(shù)。
例題：找素數(shù)
限制：n<= 10000
代碼實現(xiàn)：
初始化函數(shù)，init()
mark[i]標記為false
primeSize為0
for(int i = 2; i<= 10000; i++){
if(mark[i] == true) continue;
prime[primeSize++] = i; 記錄素數(shù)
for(int j = i*i; j<= 10000; j+= i){
mark[j] = true; 標記倍數(shù)
}
}
main函數(shù)中對于每次循環(huán)
bool isOutput = false;
用來進行標記。
技巧：
- 在標記時，不必從2i開始標記，因為i*k已經(jīng)被k標記過了。我們從
開始標記即可。
3、分解素因數(shù)
比如：求正整數(shù)N的素因數(shù)的個數(shù)。
例題：
要求：求素因數(shù)。輸出有多少個素因數(shù)。
限制：N <
思路：首先利用素數(shù)篩法得到所有素數(shù)。輸入n后，依次遍歷所有素數(shù)，判斷其是否是n的因數(shù)。
例題：求N的所有素因數(shù)的個數(shù)。
技巧：
- 要求的是
，但是只用自己分解到√10^9即可，如果有大于這個數(shù)的不能分解，那么它一定是素因數(shù)，并且只有一次。
-
已知素因數(shù)，求整因數(shù)個數(shù)
image.png
例題：整除問題
要求：給定n,a求 最大的 k，使 n!可以?? a^k整除， ????但不能??被 a^(k+1)????整除。
限制：n <= 1000, a<= 1000
技巧：
- 首先n!可能很大，不能直接求出數(shù)值再分解。
- 求k的方法，只需要分解出素因數(shù)之后再進行比較冪的數(shù)值求k即可。
實現(xiàn)過程如下：
- 按照之前的步驟，篩選范圍內(nèi)所有的素數(shù)。
- 計數(shù)器清零。計數(shù)器記錄的是素因子對應的冪指數(shù)。cnt保存prime[]中對應的分解后的冪數(shù)。
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，可以直接分解素因數(shù)。
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、二分求冪
將指數(shù)進行分解即求其二進制。任何高次冪都可以用這種方法
例題：人見人愛A^B
限制：A，B <=10000
要求：求后三位的結果。所以就不用保存整體的，只用保存A和B分別后三位即可。
08.29
1、高精度整數(shù)
對于特別大的整數(shù)，需要用一個結構體來保存高精度整數(shù)
struct bigInteger{
int digit[1000];
int size;
};
例題：計算a+b
要求：a和b的位數(shù)不超過1000位
代碼實現(xiàn)如下：
頭文件：
#include <stdio.h>
#include <string.h>
set()，把str轉化為數(shù)字，并保存在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]);，前置位可能需要補零。
因為是自己定義的數(shù)組，需要重載+運算符
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、高精度乘法
一般是一個高精度整數(shù)??一個普通的整數(shù)。
例題：輸出階乘
限制：N <= 1000
代碼實現(xiàn)如下：
對于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 進??的數(shù) X ????轉換為 N 進制??的數(shù)??出。
限制：M,N <= 36, 輸出時小寫，且有大數(shù)據(jù)。
知識點：高精度需要進行：
高??精??數(shù)與普通整數(shù)????????求積，????求商，求模
高精數(shù)與高精數(shù)求和
代碼實現(xiàn)如下
頭文件
#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;
}
本題結束，難度還是比較大的。
補充：如果求一個高精度的整數(shù)除以一個比較小的數(shù)后的余數(shù)，可以用如下代碼
int ans = 0;
for(int i = 0; str[i]; i++){
ans *= 10;
ans += str[i] - '0';
ans %= mod;
}
這個實際上就是除法的運算方法。
注意：高精度運算有時時間復雜度比較高，在估算時間復雜度時不能忽略這個。
4、map
功能是：將一個類型的變量映射為另一個類型
例題：產(chǎn)生冠軍
要求：判斷能否產(chǎn)生冠軍，輸出yes 或 no即可
知識點：拓撲排序，生成有向圖。如果有結點入度為0并且這個節(jié)點唯一，說明是YES！/ 將選手的姓名映射為節(jié)點編號，需要標準對象map
代碼實現(xiàn)如下：
對于每個測試用例(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是下一個要分配的數(shù)字
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]++;
}
輸入完之后，統(tǒng)計所有節(jié)點的入度，看看入度為0的節(jié)點的個數(shù)是不是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的內(nèi)部實現(xiàn)是紅黑樹。
5、滾動數(shù)組
作用：完成常數(shù)量優(yōu)化和 減少代碼量。
對于循環(huán)賦值操作，可以使用滾動數(shù)組來進行優(yōu)化
說白了就是，之前的結果不再需要了，那么我可以只使用少數(shù)幾個數(shù)組，每次分別保存在某個數(shù)組中，下一次再保存在另外一個數(shù)組中。
6、小技巧
- 可以將mod2運算改為位運算，將/2運算改為 >> 1，即右移1
- cin比scanf耗時多很多。輸入外掛可以在scanf的基礎上再次優(yōu)化。（了解一下即可，估計我也用不上）
- 流氓剪枝：強行剪去我覺得不是答案的結果。
- 不要在程序中混用printf和cout,因為他們的輸出機理不同，混用可能會造成不可預見的后果。
7、排版
根據(jù)題目示例來找規(guī)律。
例子：
代碼實現(xiàn)如下：
#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++){ 外面的，表示一共輸出幾行，每次循環(huán)是一行
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;
}
這個規(guī)律性比較強，對于規(guī)律性不強的，要先完成排版，再進行輸出。
例子：疊筐
不太容易直接輸出，就自己先進行排序。
限制：總的輸出邊長大小 n <= 80
思路：每次確定圈中內(nèi)容時：都是先找到左上角的點。
代碼實現(xiàn)如下：
#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用來計數(shù)，看是第幾次輸出。
int x = n/2 + 1, y = x; 找到最中心的節(jié)點
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%.
限制：所有的整數(shù) <= 1000。輸出要限制到小數(shù)點后三位。
思想：每次都買性價比最高的東西。
代碼實現(xiàn)如下：
商品的結構體的實現(xiàn)如下
struct goods{
double j;
double f;
double s;
bool operator < (const goods &A) const{
return s > A.s;
}
}
可以看成包含成本f、收益j，s是j/f，并且重載 < 運算符。這樣就會按照性價比降序排列?？吹氖?code>return s > A.s
main函數(shù)實現(xiàn)如下
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:
要求：已知節(jié)目的時間表，如何看盡可能多的完整的節(jié)目。
限制：節(jié)目數(shù)n <= 100.
思想：貪心算法
第一個節(jié)目優(yōu)先選擇結束時間最早的，后面的選擇 在觀看完這個節(jié)目之后，仍然可以完整觀看的節(jié)目中，結束最早的那個。
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
可以看出，思想還是比較簡單的。但是如果想出難的話還是很難的。
至此，第二章及以后的所有章節(jié)均看完！撒花！機試水平有了從0到0.001的提升！
還需要考慮的一個很重要的內(nèi)容是：時間復雜度的估計。
對于限制1秒，我們不能超過百萬級別，即不能超過1000萬。
完結撒花！并且九度OJ是不能再用的，?？途W(wǎng)或PAT均可。
PAT (Advanced Level) Practice
08.30
1、A+B Format
要求：輸出a+b，多位數(shù)字要以，分割
限制： 10 ^(-6)<a , b < 10^6 / 只輸入一組數(shù)據(jù)
難點：如何輸出逗號
參考別人的答案，還是把整型數(shù)字轉為字符串
代碼實現(xiàn)如下：
#include <stdio.h>
char sumchar[10]; 保存數(shù)組
void change(int number){ 把數(shù)字轉為字符型
int index = 0, times = 0; index是在數(shù)組中的下標，times是數(shù)字的位數(shù)
while(number != 0){
if(times % 3 == 0 && times != 0){
sumchar[index++] = ','; 加上逗號
}
sumchar[index++] = number % 10 + '0'; 數(shù)字
number /= 10;
times = times+1; 是數(shù)字，位數(shù)加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; 找到末尾的數(shù)字
}
for(i = end_index; i>= 0; i--){
printf("%c", sumchar[i]); 倒序輸出
}
return 0;
}
這個有一個極端的用例會出錯。
參考別人的代碼實現(xiàn),發(fā)現(xiàn)少了結果是0的情況。如果是0，就不會輸出任何東西。
有挺多細節(jié)需要考慮，突然想到需要倒序輸出，是一個后進先出的例子，如果熟練的話可以用棧來實現(xiàn)。
08.31
1、KY2:查找和排序
要求：成績按照從低到高和從高到低分別排序、輸出
限制：無
知識點：排序
卡在：忘記如何對結構體中的變量進行排序了。
參考代碼，分別對兩種排序用兩個函數(shù)實現(xiàn)。輸出方法也用一個函數(shù)來實現(xiàn)了。排序它內(nèi)部是使用冒泡排序來完成的。
收獲：
- struct前面要加typedef
- 定義數(shù)組長度時，大小最好不要弄成變量n，可以設一個較大的絕對不會超過的數(shù)。
- 字符串和整型數(shù)字是可以在同一個scanf中輸入的，
scanf("%s %d",a,&b)即可
但是感覺這種還是比較復雜的，如果可以使用sort()來進行排序，就很簡單了。
參考sor()的代碼，結構體排序的方法是重新寫一個排序函數(shù)。如下
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、求約數(shù)的個數(shù)
限制：個數(shù)n<=1000，每個數(shù)字的大小Num<=1000000000
知識點：對大數(shù)據(jù)的處理
卡在：這么大的數(shù)據(jù)如何表示
別人代碼實現(xiàn)如下：
i*i<num的形式，數(shù)值穩(wěn)定性更好,比sqrt()好
#include<iostream>
using namespace std;
int numOfDivisor(int num)
{
int ans = 0;
int i;
for (i = 1; i*i<num; i++) 遍歷所有小于根號下的數(shù)
{
if (num%i == 0)
ans += 2; 這里一大一小兩個數(shù)
}
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函數(shù)中，求約數(shù)是在numDivisor函數(shù)中。
這個是最簡單的方法，但是耗時也比較大。
還可以用 質數(shù)篩法，篩選出所有的質數(shù)。（但是這有什么用呢？）有用：如果是質數(shù)，就不用再往下判斷它有沒有因子了，它除了1和它本身，沒有其他約數(shù)了就。
/*
* 因數(shù)個數(shù)（使用到質數(shù)篩法）
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
const int MAXN = 4e4;
bool isPrime[MAXN]; //標記數(shù)組
vector<int> prime; //保存質數(shù)
void initial(){ //初始化
fill(isPrime,isPrime+MAXN,true);
isPrime[0]=false;
isPrime[1]=false;
for(int i = 2;i<MAXN;i++){
if(!isPrime[i]){ //非質數(shù)，則跳過該數(shù)
continue;
}
prime.push_back(i);
for(int j = i+i;j<MAXN;j+=i){
isPrime[j]=false; //質數(shù)的倍數(shù)為非質數(shù)
}
}
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;
}
初始化其實就是素數(shù)篩法，找出所有的質數(shù)。
fun()就是求因數(shù)的函數(shù)。
變量：
vector exp
prime里面放的是所有素數(shù)
對每一個素數(shù)，分別進行如下操作
factor是當前素數(shù)
如果n還可以分解為這個素數(shù)，統(tǒng)計出現(xiàn)了多少次這個素數(shù)，記在exp棧里面。同時n也除去相應的數(shù)。
最終的個數(shù)根據(jù)之前的一個公式來計算：
(e1+1)(e2+1)(e3+1)....(en+1)
- vector除了可以用來當棧操作，在不使用棧的特性時，也可以單純地用來計數(shù)。
09.01
1、A + B 的多項式形式
限制：K <= 10, N(指數(shù)) <= 1000
考察：直接用數(shù)組記錄即可。（位置表示索引，有點類似哈希）
不要一不會就看答案！多思考！思考是進步的過程！?。?/p>
09.03
1、多項式相加
- 對于double型，判斷是否為0，最好考慮誤差
- C++中，abs要使用頭文件cmath，C中使用stdlib.h
輸出錯誤，應該倒序輸出
現(xiàn)在的問題在 double型系數(shù)不能正確讀取,剛才不知道為什么錯了，重新改為scanf("%lf",&xishu)，即可。
自己代碼實現(xiàn)
#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是數(shù)字的個數(shù)，但是n才是系數(shù)的個數(shù)，所以數(shù)組的大小應為N的個數(shù)。
還是不知道自己哪里錯了，參考別人的代碼
#include<stdio.h>
const int max_n = 1111;
double a[max_n] = {}; 只用一個來實現(xià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(節(jié)點數(shù))<500
知識點：印象中，圖論用鄰接矩陣實現(xiàn)
小細節(jié)：最后沒空格
需要用到Dijkstra 算法。
設置內(nèi)存，頭文件#include <memory.h>
fill函數(shù)，可以設定為任意指定的值，頭函數(shù)<algorithm>
代碼實現(xiàn)過程
1、定義變量，初始化
2、Dijk算法{
找出最小的頂點,標記這個頂點已經(jīng)計算過了
有兩種情況會替換掉原來的值
}
不懂Dijkstra算法為什么有個沒有用到的i的for循環(huán)
3、Counting Leaves
題目：
限制：N節(jié)點數(shù)量 < 100，M 非葉子結點的數(shù)量
知識點：考察??的定義和層次遍歷
參考別人代碼，可以用dfs，也可以用bfs.
dfs實現(xiàn)如下
頭文件
#include<iostream>
#include<vector>
#include<algorithm> 后面有一個max()函數(shù)，所以需要algorithm頭文件
using namespace std;
定義變量
vector<int> v[100];
int book[100];
int maxDepth=-1;
void dfs(int index,int depth){
// 此時第index結點已經(jīng)沒有子結點了，則表明是葉子結點
if(v[index].size()==0){
// 統(tǒng)計該葉子結點
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，不同的是，需要額外的數(shù)組來統(tǒng)計每個節(jié)點所在的層次
邏輯搞懂了其實也不難
4、Spell It Right
題目：求和，字母輸出
限制：N(數(shù)字) < 10的100次方
知識點：大數(shù)存儲，每個數(shù)字轉換為一個字母，數(shù)組實現(xiàn)
一道挺簡單的題，編譯還是有很多錯。
首先字母表的定義
vector不是pop，是pop_back()
原來的結果錯誤，是因為少了一層digit嵌套。
測試結果發(fā)現(xiàn)還有一個段錯誤，是沒有考慮到輸出為0的情況，加入為0的情況就正確啦！我人生的第一個AC!!
代碼實現(xiàn)如下
#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;
}
也可以用數(shù)組實現(xiàn)，只計算一個數(shù)組有效長度即可。
5、Sign In and Sign Out
題目：簽到簽退，要求找出最早和最晚時間。
限制：ID_number字符串字符 < 15
知識點：對時間格式的數(shù)據(jù)進行操作的能力
輸入的時候 scanf("%s %d:%d:%d %d:%d:%d",ID,&H1,&M1,&S1,&H2,&M2,&S2);，這樣輸入。
比較的時候，都化為秒數(shù)去比較。
收獲：
不用所有數(shù)據(jù)都記錄，只記錄最開始和最后的數(shù)據(jù)即可，每次輸入之后都進行比較。
字符串賦值的時候，先清空，再賦值
strcpy(in,"");strcpy(in,ID);輸出：printf("%s %s",in,out);
6、Maximum Subsequence Sum
題目：最長子序列
知識點：動態(tài)規(guī)劃
限制：數(shù)量K <= 10000，如果都是負數(shù)，需要特殊處理
j表示以j結尾
變化的過程：dp[i][j] = dp[i][j-1] + v, (?). dp[i]=max(dp[i],dp[i-1]+a[i])
代碼實現(xiàn)如下：
#include<iostream>
#include<cstdio>
using namespace std;
int a[10005],l[10005],r[10005];
int dp[10005];//以a[i]結尾的最大連續(xù)區(qū)間和
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，且數(shù)值變大了
{
dp[i]=dp[i-1]+a[i];
l[i]=l[i-1];//區(qū)間左端點不變，右端點更新
r[i]=i;
}
else//如果a[i]是負數(shù)，新建一個區(qū)間
{
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
題意：電梯升降，計算時間。
限制：所有數(shù) < 100
沒有難度，數(shù)組計算和之前的差即可。但是答案都錯啦？
因為：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
題意：多項式相乘
知識點：仍然是數(shù)組的操作
限制： K <= 10，N <= 1000
實現(xiàn)：指數(shù)相加，系數(shù)相乘
在調試發(fā)現(xiàn)輸入的方法不對，導致數(shù)據(jù)篡位
初次代碼實現(xiàn)：（有錯）
#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，再輸入系數(shù)，即給數(shù)組矩陣賦值，與確定數(shù)組的坐標，不能在同一條語句中。
- for循環(huán)計算ans時，這時候算的是系數(shù)，從0開始。而K輸入時，需要的是K次，若從1開始也沒關系，只用計數(shù)即可。
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個數(shù)字，
難點：怎么確定進制？要一個一個去試嗎？試到最大結束？
參考結果：雖然思路可以，但是超時
可以用二分法來確定
基數(shù)的最小值：N2的最大權值 + 1
基數(shù)的最大值：N1 + 1
mx用于計算N2的最大權值
真正二分的過程用while來實現(xiàn)
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; 每次都這樣，最前面的數(shù)肯定乘的多。
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
考察：對數(shù)組的操作
思路： A C M E 四門課的N成績，分別sort排序，結果保存在數(shù)組中。
查詢的M個人，分別按順序招，輸出排名最靠前的。
我想到的是單純用數(shù)組存儲，參考別人，結構體存儲更簡便。
代碼如下
#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城市數(shù)目 < 1000,
其實就是利用深度遍歷，根據(jù)一個點，把其相鄰的所有點都遍歷一遍。
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
題目：素數(shù)倒過來也是可逆的
限制：數(shù)字N < 10^5 進制D <= 10
寫代碼：6:53 - 7:10
簡單地改錯之后，運行超時了。
再改之后，還是答案錯誤.
疑問：23 ，2這個數(shù)組
理解錯題意了。
先把23轉為二進制，再反過來，再轉為10進制，再算是否為素數(shù)。
自己寫的代碼如下：
#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個數(shù)
這是一道考察基本功和邏輯的題，沒有太多算法，讀懂題意就是算法。
題目有點難懂，其次，要使用map
map中的所有數(shù)據(jù)都是有序的
用法如下
std:map<int, string> personnel;
這樣就定義了一個用int作為索引,并擁有相關聯(lián)的指向string的指針.
難度略大，如果真實遇到了大概率放棄
前面有點都是這種數(shù)據(jù)處理題，倒著開始做
9、Heap Paths
之前測過
題意：遍歷每一條路徑
限制：節(jié)點N <= 1000
考察：堆、深度優(yōu)先遍歷
10、Vertex Coloring
做過
限制：N、M < 10^4
代碼實現(xiàn)如下：
#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>中的數(shù)據(jù)是已經(jīng)排好序的，并且不重復，可以用來計數(shù)
11、Decode Registration Card of PAT
限制：N card的數(shù)量 < 10^4，M查詢的數(shù)量 < 100
考察：對數(shù)據(jù)的處理
思路：用結構體來存儲每條信息，根據(jù)不同的type輸出
參考如下文章：
https://blog.csdn.net/liuchuo/article/details/84973049
收獲：
- 如果<map> 超時，換成 unordered_map
- 一些庫函數(shù)，輸出時很方便
- auto
12、Google Recruitment
題意：找某個固定數(shù)字的素數(shù)
考察：素數(shù)篩法吧？
是找素數(shù)，但是沒用素數(shù)篩，直接常規(guī)的方法
收獲：
- 截一個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];
定義節(jié)點的數(shù)據(jù)結構，一個數(shù)值兩個指針
struct node{
int val;
node* left;
node* right;
};
map<int,node*>mp; 定義一個map映射，int型為節(jié)點的數(shù)值，node*為左節(jié)點和右結點
創(chuàng)建，有四個參數(shù)，分別是起始位置和終止位置
node* create(int preL,int preR,int inL,int inR){
if(inL>inR) return NULL; 這個是循環(huán)結束的終止條件
node* now = new node; 創(chuàng)建一個節(jié)點，作為這次找到的節(jié)點
now->val = pre[preL]; 這個值是 先序遍歷的第一個值
int i;
for(i=inL;i<=inR;i++){
if(in[i]==pre[preL]) break; 在中序遍歷中找到根節(jié)點的位置
}
int numLeft=i-inL; 左子樹的節(jié)點的數(shù)目。
now->left=create(preL+1,preL+numLeft,inL,i-1); 改變位置，這里的參數(shù)要理解。
now->right=create(preL+numLeft+1,preR,i+1,inR);
mp[now->val]=now; 把結點弄到mp中
return now;
}
這個是根據(jù)題意來的，就是我們要
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
問題：求最短路徑，回到原始點
限制：頂點數(shù)N < 200, M < 100, 接下來輸出K條路徑
不懂Dijkstra算法為什么有個沒有用到的i的for循環(huán)
1、進制轉換
題目要求：十進制轉為二進制
限制：數(shù)字很大，個數(shù)可能為30個數(shù)字/ 數(shù)字是非負數(shù)。
難點：數(shù)字很長，不能用普通的整型來表示，需要分割、處理等。
正好是上道題說的 用vector來實現(xiàn)
代碼實現(xiàn)如下：
#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; 對于每次輸入，創(chuàng)建一個int 型的binary。
while(str.size() != 0){
int last = str[str.size() - 1] - '0'; 取出來最后的數(shù)字
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語言實現(xiàn)
#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[]中。使用了一個函數(shù)進行轉換。把10進制轉為2進制。
1、A+B for Polynomials
題目：A和B是多項式，求A+ B
限制：k<=10, N <= 1000
2、例題：給定前序和后序，計算中序有幾種情況。
這是一個定式，前序，后序給定，劃分子問題時，可能有多種左右子樹的劃分方式，參見柳神對 PAT 1119 的解答，適當變形即可.
知識點：先序中序后序
限制：節(jié)點數(shù)N <= 30
代碼實現(xiàn)
#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) {
只剩下一個節(jié)點了，直接入即可
if(preLeft == preRight) {
in.push_back(pre[preLeft]);
return;
}
根節(jié)點符合情況，
if (pre[preLeft] == post[postRight]) {
int i = preLeft + 1; //左子樹的開始
while (i <= preRight && pre[i] != post[postRight-1]) i++; //找到右子樹的根節(jié)點，即左右子樹的分界線，用i表示。
if (i - preLeft > 1) //左子樹還能再劃分
getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
else //左子樹只有一個，或者沒有左子樹，這個節(jié)點來回移動
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;
}
收獲：
- 如果出現(xiàn)
reference to 'xxxxxxx' is ambiguous，可能是定義的變量和庫中的某個變量撞名字了，把變量的名字改掉就可以了。 - vector 里面的resize，可以設置內(nèi)存大小
3、PAT考綱
參考 http://m.itdecent.cn/p/3814d99bed25
PAT-A總共有4題，時間為3小時。三四大題 是一題圖、一題樹的概率較大，偶爾動態(tài)規(guī)劃，貪心算法等。 第二題 一般是STL(map,set,vector為主，偶爾隊列，堆棧)。第一題小題(邏輯題，字符串處理，數(shù)學，枚舉)，要么簡單，要么讀題復雜理解復雜情況不容易想到，但是程序不會太復雜。其他的比如排序、查找、哈希、遞歸、遞推、尺取法、哈夫曼、鏈表、素數(shù)的判斷、數(shù)學問題、模擬、邏輯什么的，不需要復習，一般都融在題目里，是最基本的，看能力。
浙大2019原題：
happy 數(shù)：任給一個數(shù)，求其各位平方和，求迭代到 1 所需次數(shù)，或者形成圈的起始數(shù)
給定無序數(shù)組排序給定寬度并用 Zig zag 輸出（PAT 原題）
給定前序判斷是否是 avl 樹（PAT 原題）
給定圖，給定頂點子集，排序輸出頂點子集圖中度前 3 的點，度相同輸出編號小的
https://pintia.cn/problem-sets/994805148990160896/problems/994805156145643520
字符串處理
一個很長（長度為 ）的數(shù)字字符串，要求刪除
（
） 個數(shù)，使得得到的數(shù)最小。（60/100）
需要思考的較多，寫起來很簡單。越大的數(shù)，越先刪除，對于需要刪除的同等大小的數(shù)，其余的數(shù)都不比他大，所以先刪除前面的。但是有特殊情況需要考慮，例如 ，刪除 1 位的最佳選擇應該是直接刪除
而不是
，因為這樣會使最高位得以降低。這種情況需要優(yōu)先處理。我當時就沒有考慮到。
動態(tài)規(guī)劃
男孩女孩排列問題，要求連續(xù)男孩的個數(shù)不超過 個的可能的排列個數(shù)。（70/100）
動態(tài)規(guī)劃問題，劃分子問題求解。當時使用的遞歸結果超時了。
PAT頂級 1004 To Buy or Not to Buy - Hard Version (35分) 不會做
做題還有：九度教程
