[新手][PAT乙級][C]刷題記1045-1048
//題目連結
https：//www。
patest。cn/contests/pat-
b-practise
；
//語言：
C
//一起刷，討論的dalaoes私信加好友！評論！
//ide：vs2017，
VS牛逼
！
//所有程式碼都是能在VS下正常透過編譯而非正常提交到PAT，正常提交僅略微修改適應提交（具體就是一些_s，C和C++的部分差異問題，詳見專欄中某些前文pat刷題記）
//程式碼執行時間來源於提交（經多次提交確認取非香港主機的結果）
//持續更新中~
//透過率參考：
![[新手][PAT乙級][C]刷題記1045-1048](https://img.beesask.com/upload/website_attach/9MR01F87MYs-MV=VNp=3pr1vrOPumjtiFz0wOjezOBnOLm=Ca0U+=-cPV7GyXQ6PkQhkZjP5mCmOXksZNH=+on=RY.jpeg)
1045是真的還好。1048是真的有毒。——你看今天專欄換的頭像就知道了、
#include
int main（）
{
1045：
寫完後我又想了想這題為什麼0。18，挖了一個小坑（還拉你一把）肯定不是主要原因（後面再寫），可能是正好打中了我們的慣性思維；
這題擺明了就是比一下前面數的最大值，後面數的最小值。兩個條件都ok就存到一個新的數組裡，然後再排序。然而10W資料量200ms，怎麼操作才能得到前面的最大值和後面的最小值？硬來是斷然不行的，每次都要遍歷所有的n^2+，斷然超時。進行排序也不行，整個陣列分成了兩節還要除去一個元素，勢必要涉及陣列元素的刪除重組——這不是C乾的事兒。想過計算，感覺也並沒有什麼頭緒。剩下就剩一個雙向遞迴——我覺得這不是人乾的事兒，而且還很有可能也超時。似乎走進了死衚衕？；
後來冷靜下來就發現自己掉進了自己的慣性思維：沉迷於一步到位的最佳化。什麼意思呢？假設要錄入兩個等長的陣列，我恨不得就遍歷一圈，一次錄兩個——這樣只錄一圈就錄好了。這確實在複雜度上有了最佳化，但我要付出非邏輯順序的代價（不是一次打完陣列a再陣列b，而是一個a［i］一個b［i}往裡輸）；插排和冒泡對每個數都一次到位了，也不需要太多額外空間，但相比不是一次到位的快排而言就慢多了。演算法從來沒有完爆，只有平衡和選擇；
簡而言之，這題的思路就類似於把冒泡改快排——可以不要一次到位，可以給你點空間，但你得整快點：
將原來陣列定義成結構體，每個搭個bool型的小尾巴（寫C++的資料庫老師新講的，感覺很適合這裡和cmp就用了，省空間）。首先從頭到尾遍歷一圈，將左邊的最大值大於這個數的bool值改成false，再從尾到頭遍歷一圈，將右邊最小值小於這個數的改成false。於是這個題目就改成了德才論（［新手］［PAT乙級］［C］刷題記1013-1016——1015：qsort多條件排序）；
於是（？）考慮最佳化，第一遍遍歷可以直接跟著錄入，時間又短了，哇咔咔；
我是事先注意看了這個0。18的，一全想通感覺整個人都飄了。好久沒寫過cmp（一直對這個似懂非懂每次對著寫的），這次寫一個陌生樣式的，就跟著感覺走居然直接寫對了，感覺自己好像靈魂出竅換了個人一樣；
在後面具體過程就不寫了，腦子裡就一把過三個字了。最後除錯了下沒有點的：2\n2 1結果輸出0\n1，（Ak什麼都算到了。jpg）於是加了個等於0就直接跳過輸出模組return 0；（\n是回車換行的意思別想多了）
提交氣死咱了，掉了個活久見的錯誤：
![[新手][PAT乙級][C]刷題記1045-1048](https://img.beesask.com/upload/website_attach/aCiDrOCKpXl7MVDA8v3sYnP4FDk5pf=gMbmkoNLUqAxcLlDAWJJBWfx6AEe-TXdNZAF+UKw0FI0nL==Y8B37XJR_W.jpeg){kind=small}
仔細看了一圈程式碼，感覺完全沒有格式錯誤的點，重新看題，他沒有怎麼說為0如何，就說第一行第二行，感覺應該是這個0也要來第二行直接\n吧，遂加一個printf（“\n”）；，AC；
C++AC，交C報unknown type name ‘bool’，遂百度之，error： unknown type name ‘bool’，加一行#include
程式碼（C 32ms 1900kb， C++ 32ms 1896kb 測試點2：沒有主元符合條件）
#include
“stdafx。h”
#include
#include
#include
typedef
struct
Node
{
int
data
；
bool
possible
；
}
Num
；
int
cmp
（
const
void
*
p1
，
const
void
*
p2
）
{
Num
*
p
=
（
struct
Node
*
）
p1
；
Num
*
q
=
（
struct
Node
*
）
p2
；
if
（
p
->
possible
==
q
->
possible
）
{
return
p
->
data
-
q
->
data
；
}
else
{
return
q
->
possible
；
//這個地方是誰幫我寫的？？我不知道為啥要這樣寫啊！有沒有dalao教教我！！
}
}
int
main
（）
{
static
Num
a
［
100001
］；
int
len
，
i
；
int
leftmax
=
-
1
；
scanf_s
（
“%d”
，
&
len
）；
int
count
=
len
；
scanf_s
（
“%d”
，
&
a
［
0
］。
data
）；
a
［
0
］。
possible
=
true
；
//左檢第一個不用管單獨拿出來，進遍歷會燙，同理右檢的最後一個。
for
（
i
=
1
；
i
<
len
；
i
++
）
{
/*錄入+左檢*/
scanf_s
（
“%d”
，
&
a
［
i
］。
data
）；
if
（
leftmax
<
a
［
i
-
1
］。
data
）
{
leftmax
=
a
［
i
-
1
］。
data
；
}
if
（
leftmax
<
a
［
i
］。
data
）
{
a
［
i
］。
possible
=
true
；
}
else
{
a
［
i
］。
possible
=
false
；
count
——
；
}
}
int
rightmin
=
a
［
len
-
1
］。
data
；
for
（
i
=
len
-
2
；
i
>=
0
；
i
——
）
{
/*右檢*/
if
（
rightmin
>
a
［
i
+
1
］。
data
）
{
rightmin
=
a
［
i
+
1
］。
data
；
}
if
（
a
［
i
］。
possible
==
true
）
{
if
（
a
［
i
］。
data
>
rightmin
）
{
a
［
i
］。
possible
=
false
；
count
——
；
}
}
}
qsort
（
a
，
len
，
sizeof
（
a
［
0
］），
cmp
）；
printf
（
“%d
\n
”
，
count
）；
if
（
count
==
0
）
{
printf
（
“
\n
”
）；
//測試點2：沒有節點輸出
return
0
；
}
for
（
i
=
0
；
i
<
count
-
1
；
i
++
）
{
printf
（
“%d ”
，
a
［
i
］。
data
）；
}
printf
（
“%d
\n
”
，
a
［
i
］。
data
）；
return
0
；
}
1046：
感覺沒什麼好說的，簡單說下最佳化（其實並不需要，400ms）的思路：
1。不要存資料，判斷一次類似雜湊加一下就好；
2。判斷勝負：先判斷兩個是否相等，再判斷相加的和等於A或者B，相對於最後判斷相等再另外操作複雜度低；
程式碼（C 3ms 384kb，C++ 3ms 480kb）
#include
“stdafx。h”
#include
int
main
（）
{
int
times
，
t
；
int
jiasay
，
jiahand
，
yisay
，
yihand
；
int
jia
=
0
，
yi
=
0
；
scanf_s
（
“%d”
，
&
times
）；
while
（
times
>
0
）
{
scanf_s
（
“%d %d %d %d”
，
&
jiasay
，
&
jiahand
，
&
yisay
，
&
yihand
）；
if
（
jiahand
！=
yihand
）
{
t
=
jiasay
+
yisay
；
if
（
t
==
jiahand
）
{
yi
++
；
}
else
if
（
t
==
yihand
）
{
jia
++
；
}
}
times
——
；
}
printf
（
“%d %d
\n
”
，
jia
，
yi
）；
return
0
；
}
1047：
1047理論上說這題可以不走雜湊（最多1W，1k組，如果資料量小而散雜湊最後取1000個裡的最大值相當虧），不過寫起來簡單無腦啊！反正400ms無人權，超不了；
中間第二個值其實是無效的干擾條件，直接%*d喂苟；
程式碼（C 4ms 384kb，C++ 4ms 480kb）
#include
“stdafx。h”
#include
#include
int
main
（）
{
int
team
［
1001
］；
memset
（
team
，
0
，
sizeof
（
team
））；
int
num
，
sco
，
peo
，
i
，
max
；
scanf_s
（
“%d”
，
&
peo
）；
while
（
peo
>
0
）
{
scanf_s
（
“%d-%*d %d”
，
&
num
，
&
sco
）；
team
［
num
］
+=
sco
；
peo
——
；
}
for
（
i
=
2
，
max
=
1
；
i
<
1000
；
i
++
）
{
if
（
team
［
max
］
<
team
［
i
］）
{
max
=
i
；
}
}
printf
（
“%d %d
\n
”
，
max
，
team
［
max
］）；
return
0
；
}
1048：
這題毒性堪比福爾摩斯，我這麼說應該沒有人不服吧。（嚴肅到沒有分號）
扒一扒這題的坑（同志們，看到了作者，一定要警惕啊！！）：
1。專打VS黨，瘋狂報段錯誤（我被坑了兩次）
![[新手][PAT乙級][C]刷題記1045-1048](https://img.beesask.com/upload/website_attach/2+ujze_xcGzAiFyezNOk3OQAyY3o2tdQzsbTMdbC2ZhJ2Yb42LaAd39R1oFuyuz71==jMc4N1YZfdbO5zjOA2AVV2.jpeg)
這個點就在於你錄入字串時候本來錄入的句子scanf_s（“%s %s”， code， 101， str， 101）；交上去你如果只去了_s（還要去掉限定的長度）一般會報編錯：函式引數多了，但這裡他報段錯誤。我看的滿臉問號，折騰了以下。到最後我也不知道為什麼會報段錯誤。——我想這可能是他們挖坑的時候踩出來的一個坑吧？；
2。
對奇數位，對應位的數字相加後對13取餘——這裡用
J代表10、Q代表11、K代表12
；
聽說你撲克玩的很6
？
3。
對
奇數位
，對應位的數字相加後對13取餘——這裡用J代表10、Q代表11、K代表12；對
偶數位
，用B的數字減去A的數字，若結果為負數，則再加10。
什麼是奇數位？難道不是這個數是奇數，就是奇數位嗎？後面還有一句看似莫名其妙，其實
含蓄
的話
這裡令個位為第1位。
//這裡還好的一點是，如果你僅僅沒看到這裡測試例子會發現問題。如果萬一像我一樣同時寫錯了去判斷A的數字的奇偶的話，因為A是1234567，你就會這樣，幾乎萬劫不復：
![[新手][PAT乙級][C]刷題記1045-1048](https://img.beesask.com/upload/website_attach/3YrJjiXlV2YA1AiDkFWUNHaVahcn_qkQg0Ru2WrS9csBcof29GlFCrP9yhmuhrPTg2qJ175_93aAyqg2kgWDCLK81.jpeg)
如果說上面123都是我自己的問題的話，那麼還有；
4。
看例子你明白瞭如果B比A長，長的部分不用處理。那麼如果A比B長，就安心處理B的呢幾位就好？；
這個題最坑的就是你以為如果A的位數比B長就不用管了，其實還是得把B補成跟A一樣長才行。--
PAT乙級-1048。 數字加密（20）-native
5。
什麼，也就這樣了？現在我們考慮以下情況：
輸入01 01會發生什麼？；
輸入在一行中依次給出A和B，均為不超過100位的正整數，其間以空格分隔。
誒，
我一直都說這是正整數啊喂
！你要咋整是你的事兒，但我就100位了，有本事你咬我？你說他是字串就字串？你哪裡看到我提他是字串了？； （@陳越姥姥 如果這裡沒設點的話設一個唄，指不定能超越福爾摩斯啊！（奸笑。jpg））
我是真的佩服這0。24，他們到底經歷了怎樣的折磨才能AC；
我大概的經歷：看出12，被3坑了->看出3，被4坑了->一晚上沒睡好，想出可能是5的問題，重寫，繼續被4坑（
關於5有沒有設點，其實我是不知道的，因為我改了之後提交跟之前結果完全一樣，但不排除這裡設點的可能
）->百度得到4，稍微修改AC；
程式碼（16/20， 掉測試點2 5，包括之前沒有注意5的屍體，AC程式碼思路也基於此）
#include
“stdafx。h”
#include
#include
//交換字元a和b
void
change
（
char
&
a
，
char
&
b
）
{
char
c
=
a
；
a
=
b
；
b
=
c
；
}
//不知道該怎麼說。例：a［6］=“00123\0”，a［5］=“321\0\0\0”，返回有效長度3。
int
reversenumstr
（
char
*
a
，
char
len
）
{
int
i
；
for
（
i
=
0
；
i
<
len
/
2
；
i
++
）
{
change
（
a
［
i
］，
a
［
len
-
1
-
i
］）；
}
for
（
i
=
len
-
1
；
a
［
i
］
==
‘0’
；
i
——
）
{
a
［
i
］
=
‘\0’
；
}
return
i
+
1
；
}
//題中的對應運算，儲存到str［times］中，其中times也為曾經運算次數
void
resave
（
char
code
，
char
&
str
，
int
times
）{
int
t
；
if
（
times
%
2
==
0
）
//從第0次開始，實際第一位
{
t
=
（（
int
）（
code
-
‘0’
）
+
（
int
）（
str
-
‘0’
））
%
13
；
}
else
{
t
=
（
int
）（
str
-
‘0’
）
-
（
int
）（
code
-
‘0’
）；
if
（
t
<
0
）
{
t
+=
10
；
}
}
if
（
t
<=
9
）
{
str
=
（
char
）（
t
+
（
int
）
‘0’
）；
}
else
{
switch
（
t
）
{
case
10
：
str
=
‘J’
；
break
；
case
11
：
str
=
‘Q’
；
break
；
case
12
：
str
=
‘K’
；
break
；
}
}
}
int
main
（）
{
char
code
［
101
］，
str
［
101
］；
scanf_s
（
“%s %s”
，
code
，
101
，
str
，
101
）；
int
len1
=
strlen
（
code
）；
int
len2
=
strlen
（
str
）；
len1
=
reversenumstr
（
code
，
len1
）；
len2
=
reversenumstr
（
str
，
len2
）；
int
len
=
（
len1
>
len2
？
len2
：
len1
）；
int
i
；
for
（
i
=
0
；
i
<
len
；
i
++
）
{
resave
（
code
［
i
］，
str
［
i
］，
i
）；
}
for
（
i
=
len2
-
1
；
i
>=
0
；
i
——
）
{
printf
（
“%c”
，
str
［
i
］）；
}
return
0
；
/*
int begin1， begin2；
for （begin1 = 0； code［begin1］ == ‘0’； begin1++） {}
for （begin2 = 0； str［begin2］ == ‘0’； begin2++） {}
int len1 = strlen（code） - begin1；
int len2 = strlen（str） - begin2；
int len = min（len1，len2）；
int x， y；
int sign；
for （len1——， len2——， sign = 1； len > 0； len——， len1——， len2——）
{
y = （int）（str［len2］ - ‘0’）；
x = （int）（code［len1］ - ‘0’）；
if （sign == 1）
{
str［len2］ = save（（x + y） % 13）；
}
else
{
str［len2］ = save（y - x）；
}
sign *= -1；
}
for （； str［begin2］ ！= ‘\0’； begin2++）
{
printf（“%c”， str［begin2］）；
}
return 0；
*/
}
AC程式碼（基於上面胡亂改的，可能不太合乎最佳化，難受不想想了）（C 3ms 384kb，C++ 3ms 480kb）
#include
“stdafx。h”
#include
#include
//交換字元a和b
void
change
（
char
&
a
，
char
&
b
）
{
char
c
=
a
；
a
=
b
；
b
=
c
；
}
//不知道該怎麼說。例：a［6］=“00123\0”，a［5］=“321\0\0\0”，返回有效長度3。
int
reversenumstr
（
char
*
a
，
char
len
）
{
int
i
；
for
（
i
=
0
；
i
<
len
/
2
；
i
++
）
{
change
（
a
［
i
］，
a
［
len
-
1
-
i
］）；
}
for
（
i
=
len
-
1
；
a
［
i
］
==
‘0’
；
i
——
）
{
a
［
i
］
=
‘\0’
；
}
return
i
+
1
；
}
//題中的對應運算，儲存到str［times］中，其中times也為曾經運算次數
void
resave
（
char
code
，
char
&
str
，
int
times
）
{
int
t
；
if
（
times
%
2
==
0
）
//從第0次開始，實際第一位
{
t
=
（（
int
）（
code
-
‘0’
）
+
（
int
）（
str
-
‘0’
））
%
13
；
}
else
{
t
=
（
int
）（
str
-
‘0’
）
-
（
int
）（
code
-
‘0’
）；
if
（
t
<
0
）
{
t
+=
10
；
}
}
if
（
t
<=
9
）
{
str
=
（
char
）（
t
+
（
int
）
‘0’
）；
}
else
{
switch
（
t
）
{
case
10
：
str
=
‘J’
；
break
；
case
11
：
str
=
‘Q’
；
break
；
case
12
：
str
=
‘K’
；
break
；
}
}
}
int
main
（）
{
char
code
［
101
］，
str
［
101
］；
scanf_s
（
“%s %s”
，
code
，
101
，
str
，
101
）；
int
len1
=
strlen
（
code
）；
int
len2
=
strlen
（
str
）；
len1
=
reversenumstr
（
code
，
len1
）；
len2
=
reversenumstr
（
str
，
len2
）；
int
i
；
if
（
len1
>
len2
）
{
for
（
i
=
len2
；
i
<
len1
；
i
++
）
{
str
［
i
］
=
‘0’
；
}
str
［
i
］
=
‘\0’
；
len2
=
len1
；
}
for
（
i
=
0
；
i
<
len1
；
i
++
）
{
resave
（
code
［
i
］，
str
［
i
］，
i
）；
}
for
（
i
=
len2
-
1
；
i
>=
0
；
i
——
）
{
printf
（
“%c”
，
str
［
i
］）；
}
}
//回頭看配圖，感覺好親切；
return 0；
}
1>———— 已啟動生成： 專案： ， 配置： Debug Win32 ————
1>。cpp
1>已完成生成專案“。vcxproj”的操作。
========== 生成： 成功 1 個，失敗 0 個，最新 0 個，跳過 0 個 ==========