A。 Two Subsequences
按照題意模擬即可
#include
using
namespace
std
；
typedef
long
long
ll
；
void
solve
（）{
string
str
；
cin
>>
str
；
ll
minn
=
0x3f3f3f3f
；
for
（
int
i
=
0
；
i
<
str
。
size
（）；
i
++
）{
minn
=
min
（（
ll
）（
str
［
i
］
-
‘a’
），
minn
）；
}
ll
flag
=
0
；
cout
<<
（
char
）（
minn
+
‘a’
）
<<
“ ”
；
for
（
int
i
=
0
；
i
<
str
。
size
（）；
i
++
）{
if
（
str
［
i
］
==
minn
+
‘a’
&&
flag
==
0
）{
flag
=
1
；
}
else
cout
<<
str
［
i
］；
}
cout
<<
endl
；
}
int
main
（）{
ll
t
；
cin
>>
t
；
while
（
t
——
）
solve
（）；
}
B。 Divine Array
當時感覺就是迴圈到一定程度就會一直不變，我這裡是迴圈了70次，當然你可以一直迴圈直到判斷為陣列不會改變時停止迴圈
#include
using
namespace
std
；
typedef
long
long
ll
；
ll
obj
［
2005
］；
ll
pos
［
2005
］［
80
］；
ll
cnt1
［
2005
］；
void
solve
（）{
memset
（
pos
，
0
，
sizeof
（
pos
））；
ll
n
；
scanf
（
“%lld”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
scanf
（
“%lld”
，
&
obj
［
i
］）；
pos
［
i
］［
0
］
=
obj
［
i
］；
}
//cout << pos［3］［0］ << endl；
ll
cnt
=
1
；
while
（
cnt
<=
70
）{
//cout << pos［3］［0］ << endl；
memset
（
cnt1
，
0
，
sizeof
（
cnt1
））；
//cout << pos［3］［0］ << endl；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
cnt1
［
obj
［
i
］］
++
；
//cout << i << “ ” << obj［i］ << endl；
}
//cout << pos［3］［0］ << endl；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
obj
［
i
］
=
cnt1
［
obj
［
i
］］；
pos
［
i
］［
cnt
］
=
obj
［
i
］；
}
//cout << pos［3］［0］ << endl；
cnt
++
；
}
//cout << ‘*’ << pos［3］［0］ << endl；
ll
q
；
scanf
（
“%lld”
，
&
q
）；
//cout << ‘*’ << pos［3］［0］ << endl；
for
（
int
i
=
1
；
i
<=
q
；
i
++
）{
ll
x
，
k
；
scanf
（
“%lld%lld”
，
&
x
，
&
k
）；
if
（
k
<
69
）{
printf
（
“%lld
\n
”
，
pos
［
x
］［
k
］）；
}
else
printf
（
“%lld
\n
”
，
pos
［
x
］［
69
］）；
}
}
int
main
（）{
ll
t
；
scanf
（
“%lld”
，
&
t
）；
while
（
t
——
）
solve
（）；
}
C。 Array Elimination
按數位拆開，統計每一位的1，之後暴力求32個數的公共因子就可以了（列舉每一個因子看看是否能被這32個數整除），注意全是0的時候輸出1~n。
#include
using
namespace
std
；
typedef
long
long
ll
；
ll
obj
［
200005
］；
ll
num
［
40
］；
void
solve
（）{
memset
（
num
，
0
，
sizeof
（
num
））；
ll
n
；
scanf
（
“%lld”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
scanf
（
“%lld”
，
&
obj
［
i
］）；
ll
x
=
obj
［
i
］；
ll
cnt
=
0
；
while
（
x
）{
if
（
x
&
1
）
num
［
cnt
］
++
；
x
>>=
1
；
cnt
++
；
}
}
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
ll
flag
=
0
；
for
（
int
j
=
0
；
j
<=
32
；
j
++
）{
if
（
num
［
j
］
%
i
！=
0
）{
flag
=
1
；
}
}
if
（
i
==
1
&&
flag
==
0
）
printf
（
“%lld”
，
i
）；
else
if
（
flag
==
0
）
printf
（
“ %lld”
，
i
）；
}
printf
（
“
\n
”
）；
}
int
main
（）{
ll
t
；
scanf
（
“%lld”
，
&
t
）；
while
（
t
——
）
solve
（）；
}
D。 Frog Traveler
仔細閱讀題目我們會發現，青蛙每次跳只需要考慮能夠跳到，但是沒有被跳過的高度，因為青蛙每一個位置的跳躍都是一個區間，只要跳過去了就不可能回來在更新這個位置的步數了（因為這樣步數必然會增多）所以每個點最多隻會被跳一次，時間複雜度為O（n）。路徑的話在跳的過程中注意記錄就可以了，dp寫法我還沒看懂，等看懂了在補上叭。
#include
using
namespace
std
；
typedef
long
long
ll
；
ll
n
；
ll
up
［
300005
］；
ll
down
［
300005
］；
ll
pre
［
300005
］，
from
［
300005
］；
//滑之前的，從哪個點跳過來的
ll
ans
［
300005
］；
queue
<
ll
>
que
；
vector
<
ll
>
vec
；
void
bfs
（）{
ll
minn
=
n
+
1
；
//維護最高能跳的位置
que
。
push
（
n
）；
//將起始位置放上去
memset
（
ans
，
0x3f
，
sizeof
（
ans
））；
ans
［
n
］
=
0
；
for
（
int
i
=
0
；
i
<=
n
；
i
++
）{
pre
［
i
］
=
i
；
from
［
i
］
=
i
；
}
while
（
！
que
。
empty
（）
&&
minn
>
0
）{
ll
p
=
que
。
front
（）；
que
。
pop
（）；
for
（
int
i
=
p
-
up
［
p
］；
i
<
minn
；
i
++
）{
//從最高點向之前最高點這個區間進行bfs
if
（
ans
［
p
］
+
1
<
ans
［
i
+
down
［
i
］］）{
//因為在之前最高點的下面的點都能被之前的點跳到，所以只需要［之前最高點，當前最高點］這個區間進行搜尋
ans
［
i
+
down
［
i
］］
=
ans
［
p
］
+
1
；
//所以每個點只會被搜一遍，時間複雜度是O（N）
pre
［
i
+
down
［
i
］］
=
i
；
//是從滑落位置是從哪個點滑落下來
from
［
i
］
=
p
；
//當前點（未滑落是從哪個點轉移過來）
que
。
push
（
i
+
down
［
i
］）；
//從滿足的點繼續bfs
}
}
minn
=
min
（
minn
，
p
-
up
［
p
］）；
}
if
（
ans
［
0
］
<
0x3f3f3f3f
）{
printf
（
“%lld
\n
”
，
ans
［
0
］）；
ll
now
=
0
；
while
（
from
［
now
］
！=
now
）{
vec
。
push_back
（
now
）；
now
=
from
［
now
］；
now
=
pre
［
now
］；
}
for
（
int
i
=
ans
［
0
］
-
1
；
i
>=
0
；
i
——
）{
if
（
i
==
ans
［
0
］
-
1
）
printf
（
“%lld”
，
vec
［
i
］）；
else
printf
（
“ %lld”
，
vec
［
i
］）；
}
printf
（
“
\n
”
）；
}
else
printf
（
“-1
\n
”
）；
}
void
solve
（）{
scanf
（
“%lld”
，
&
n
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
scanf
（
“%lld”
，
&
up
［
i
］）；
}
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
scanf
（
“%lld”
，
&
down
［
i
］）；
}
bfs
（）；
}
int
main
（）{
solve
（）；
}
E。 Optimal Insertion
透過看樣例猜測或者手寫幾個例子我們會發現，要使得逆序對儘可能少的話，我們需要對b陣列進行排序，理論證明就是你會發現 ——-bi ai aj az bj——-（bi < bj）交換之後逆序對的數量只會與在他們之間的a陣列有關，對於兩邊的數產生的逆序對數是不會被改變的（中間的證明在紙上寫一下就明白了）。
之後我們暴力的想法就是對於每一個bi在a陣列中找到其會產生最小逆序對的位置但是這樣下來時間會暴，但是我們想b陣列是有順序的，其相對位置是確定的，所以我們可以對於b陣列進行分治，先確定b陣列最中間的數在a陣列中的位置，隨後分別確定兩邊的數的位置。這樣時間複雜度就是（n+m）log（n+m）。
#include
using
namespace
std
；
typedef
long
long
ll
；
ll
a
［
1000005
］，
b
［
1000005
］；
ll
c
［
2000005
］，
tmp
［
2000005
］；
ll
pos
［
1000005
］；
ll
ms
（
ll
l
，
ll
r
）{
//歸併排序找逆序對
if
（
l
>=
r
）
return
0
；
ll
mid
=
（
l
+
r
）
/
2
；
ll
lans
=
ms
（
l
，
mid
），
rans
=
ms
（
mid
+
1
，
r
）；
ll
i
=
l
，
j
=
mid
+
1
，
ans
=
0
，
cnt
=
0
；
while
（
i
<=
mid
&&
j
<=
r
）{
if
（
c
［
i
］
>
c
［
j
］）{
tmp
［
cnt
++
］
=
c
［
j
++
］；
ans
+=
mid
-
i
+
1
；
}
else
tmp
［
cnt
++
］
=
c
［
i
++
］；
}
while
（
i
<=
mid
）
tmp
［
cnt
++
］
=
c
［
i
++
］；
while
（
j
<=
r
）
tmp
［
cnt
++
］
=
c
［
j
++
］；
for
（
int
i
=
0
；
i
<
cnt
；
i
++
）
c
［
l
+
i
］
=
tmp
［
i
］；
return
lans
+
rans
+
ans
；
}
void
fz
（
ll
al
，
ll
ar
，
ll
bl
，
ll
br
）{
//分治找b的位置
if
（
bl
>
br
）
return
；
ll
mid
=
（
bl
+
br
）
/
2
；
ll
minn
=
0
，
tmp
=
0
；
pos
［
mid
］
=
al
；
for
（
int
i
=
al
+
1
；
i
<=
ar
；
i
++
）{
//O（n）找逆序對最少的位置，非常神奇！！！
if
（
a
［
i
-
1
］
<
b
［
mid
］）
tmp
——
；
if
（
a
［
i
-
1
］
>
b
［
mid
］）
tmp
++
；
if
（
tmp
<
minn
）{
minn
=
tmp
；
pos
［
mid
］
=
i
；
}
}
fz
（
al
，
pos
［
mid
］，
bl
，
mid
-
1
）；
fz
（
pos
［
mid
］，
ar
，
mid
+
1
，
br
）；
}
void
solve
（）{
ll
n
，
m
；
scanf
（
“%lld%lld”
，
&
n
，
&
m
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
scanf
（
“%lld”
，
&
a
［
i
］）；
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
scanf
（
“%lld”
，
&
b
［
i
］）；
sort
（
b
+
1
，
b
+
1
+
m
）；
fz
（
1
，
n
+
1
，
1
，
m
）；
//a陣列一共有n+1個空讓b插入
ll
cnt
=
0
，
x
=
1
；
for
（
int
i
=
1
；
i
<=
m
；
i
++
）{
//a，b數組合並
for
（
int
j
=
x
；
j
<
pos
［
i
］；
j
++
）{
c
［
++
cnt
］
=
a
［
j
］；
}
c
［
++
cnt
］
=
b
［
i
］；
x
=
pos
［
i
］；
}
while
（
x
<=
n
）{
c
［
++
cnt
］
=
a
［
x
++
］；
}
ll
ans
=
ms
（
1
，
n
+
m
）；
printf
（
“%lld
\n
”
，
ans
）；
}
int
main
（）{
ll
t
；
scanf
（
“%lld”
，
&
t
）；
while
（
t
——
）
solve
（）；
}
F。 Difficult Mountain
想了想還是來更新一下F，因為是個思維題，沒有設計一些東西，第一感覺想了一個假貪心，就是我們找到比當前D大的所有值，之後對a值進行排序，但是第三個樣例就證明了這個的錯誤性，但是題解中說加一個限制條件就是我想的假貪心了， 我直接疑惑，最後明白了為什麼加一個限制條件就是我想的那個假貪心，限制條件是si < ai這樣難道不是很熟悉麼，這不明顯的是區間線段覆蓋問題嘛？起始點，結束點，總長度，最多能放幾條這樣的不相交線段，以結束點排序。（太菜了硬是沒看出來，有大佬說我才明白）。這樣就是一道簡單題目了。
下面來說說正解吧（先去理解理解大佬教我的正解，日後在放上來。。。）
因為d是單調遞增的，所以技巧小於初始高度d的全部篩選掉。
終於看懂大佬的教我的東西了，自己也消化了一下
現在我們已經知道如果加上限制條件那麼就是一道區間最大不相交覆蓋問題，如果不加就會多出一種情況si >= ai，但是我們透過寫這種情況兩兩之間的關係我們會發現他們兩兩之間選了一個就一定能選另一個，舉幾個例子
我們不難發現上面的例子都是選了一個s較小的，另一個s較大的必定能選。所以由部分得整體就是X中的人都能爬上山
我們將si >= ai的情況放進容器X中，si < ai的情況放進容器Y中。X容器中根據s大小排序，Y容器根據a大小排序。
那麼我們就可以產生一個貪心策略，X容器中的必須要選（因為會使得ai變得比當前技巧要低，使得後面登山人數儘可能多）。那麼Y容器中的我們應該如何選呢？讓我們觀察下面的式子
觀察上面式子加上我們自己手寫一個這種類似的關係式，我們會發現只有上述我寫的一種情況Y中的元素不選，因為他們的關係是選了一個上山，另一個就不能上山，那麼我們肯定要貪心的選X中的元素因為這樣會使得d儘可能小，所以我們就雙重貪心得到了我們這道題目的正解（就是Y的某個區間不能將某個X中的區間包含進去，包含進去了那麼Y就不會選擇）之後還有一個問題就是雖然我明白瞭解法，但是我並不能O（n）實現判斷Y中是否含有X中的某個區間，但是我看大佬程式碼中用了一個我完全想不到的非常神奇並且簡單的方法實現了。敲出來ac程式碼如下
#include
using
namespace
std
；
typedef
long
long
ll
；
struct
node
{
ll
s
，
a
；
}
obj
［
500005
］；
ll
n
，
d
，
ans
；
vector
<
node
>
X
，
Y
；
bool
cmp1
（
node
x
，
node
y
）{
if
（
x
。
s
！=
y
。
s
）
return
x
。
s
<
y
。
s
；
return
x
。
a
<
y
。
a
；
}
bool
cmp2
（
node
x
，
node
y
）{
if
（
x
。
a
！=
y
。
a
）
return
x
。
a
<
y
。
a
；
return
x
。
s
<
y
。
s
；
}
void
solve
（）{
scanf
（
“%lld%lld”
，
&
n
，
&
d
）；
//數量，初始難度
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
scanf
（
“%lld%lld”
，
&
obj
［
i
］。
s
，
&
obj
［
i
］。
a
）；
}
sort
（
obj
+
1
，
obj
+
1
+
n
，
cmp1
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）{
if
（
obj
［
i
］。
s
>=
d
）{
if
（
obj
［
i
］。
s
>=
obj
［
i
］。
a
）{
X
。
push_back
（
obj
［
i
］）；
}
else
Y
。
push_back
（
obj
［
i
］）；
}
}
sort
（
Y
。
begin
（），
Y
。
end
（），
cmp2
）；
ll
j
=
0
，
ans
=
0
；
for
（
auto
u
：
X
）{
//這個判斷Y中是否包含X區間程式碼核心
while
（
j
<
Y
。
size
（）
&&
Y
［
j
］。
a
<=
u
。
s
）{
//如果小於
if
（
Y
［
j
］。
s
>=
d
）{
//並且Y［j］。s大於當前的整潔度，則證明沒有X區間包含在Y區間裡面
ans
++
；
//自己可以手畫一下就明白了，因為如果有的話d必定大於Y［j］。s
d
=
Y
［
j
］。
a
；
}
j
++
；
}
//
ans
++
；
d
=
max
（
d
，
u
。
a
）；
}
while
（
j
<
Y
。
size
（））{
if
（
d
<=
Y
［
j
］。
s
）{
ans
++
；
d
=
Y
［
j
］。
a
；
}
j
++
；
}
printf
（
“%lld
\n
”
，
ans
）；
}
int
main
（）{
solve
（）；
}
最後附上全綠圖片嘻嘻嘻
