Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) A~E
URL： Dashboard - Codeforces Round #749 （Div。 1 + Div。 2， based on Technocup 2022 Elimination Round 1） - Codeforces
A。Windblume Ode
題意：已知一個
的子集
，
，從中找到
，
中所有元素之和是合數，且
最大化。
分析：
先判斷集合所有元素是否滿足條件。如可以則輸出，返回。
隨後列舉去掉其中一個元素是否滿足條件，如可以則輸出，返回。
不需要再列舉其他的情況，理由如下：
因為
，設總和是偶數，則一定是合數。
設總和是奇數，則其中一定含有某奇數，去掉該數後，則和為偶數，（且因為元素個數為
），一定是合數。
程式碼：
bool
prime
（
int
x
）
{
for
（
int
i
=
2
；
i
<=
sqrt
（
x
）；
i
++
）
{
if
（
x
%
i
==
0
）
return
false
；
}
return
true
；
}
void
solve
（）
{
int
n
；
cin
>>
n
；
int
tot
=
0
；
int
a
［
n
+
1
］；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
cin
>>
a
［
i
］，
tot
+=
a
［
i
］；
if
（
！
prime
（
tot
））
{
cout
<<
n
<<
endl
；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
cout
<<
i
<<
“ ”
；
cout
<<
endl
；
return
；
}
else
{
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
{
if
（
！
prime
（
tot
-
a
［
i
］））
{
cout
<<
n
-
1
<<
endl
；
for
（
int
j
=
1
；
j
<=
n
；
j
++
）
{
if
（
i
==
j
）
continue
；
cout
<<
j
<<
“ ”
；
}
cout
<<
endl
；
return
；
}
}
}
}
B。Omkar and Heavenly Tree
題意：請構造一棵
個節點的樹，滿足
個限制條件，且
。
每個限制條件如下：
不能在
的路徑上。
分析：取某沒有作為
出現的節點作為根節點
，根節點連線其他所有節點構成深度為
的樹。
則任何的
一定是經過三個節點：
，不會經過其他的節點，所以條件一定滿足。
程式碼：
void
solve
（）
{
int
n
，
m
；
cin
>>
n
>>
m
；
set
<
int
>
s
；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
s
。
insert
（
i
）；
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
{
int
a
，
b
，
c
；
cin
>>
a
>>
b
>>
c
；
s
。
erase
（
b
）；
}
int
num
=
*
s
。
begin
（）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
{
if
（
i
==
num
）
continue
；
cout
<<
num
<<
“ ”
<<
i
<<
endl
；
}
}
C。 Omkar and Determination
題意：已知一個由‘。’和‘X’構成的迷宮，其中‘。’表示空白格子，‘X’表示有障礙物。從某個格子出發，可以走到
左方或上方的空白格子
。如果從某個格子出發，可以到達最左側的格子或最上方的格子，則該格子是可脫離迷宮的。用E表示。反之，則用N表示。
已知一個迷宮，它有對應一個的EN矩陣，而如果EN矩陣所對應的迷宮是唯一的，則稱該迷宮是“確定”的。現求迷宮的
![[x_1,x_2]](https://img.bearask.com/upload/website_attach/EyJY1YWiwGxg2jgeOb4xOZ=fG_B+kaluB9xYHEkd8e4T3kdKqESIBGp6P9YbFMg+ooIJm.jpeg)
列所對應的子迷宮，是否是確定的。
例如，下方所示的迷宮是不可確定的：
分析：
在整個迷宮中，如果一個點的左方和上方都是‘X’，則其是不可確定的。該點一定是不可脫離的（‘N’），但不論它是‘。’還是‘X’都對應‘N’，所以該點的狀態是不可確定的。我們記這一點是整個迷宮的“
關鍵點
”。如果子迷宮（第一列除外）中有該點，則子迷宮不可確定。
如果一個子迷宮不含有上述性質的點，則迷宮一定是確定的。證明如下：
所有點都可以向左方或上方拓展，則所有‘。’點一定是可脫離的。所以若將‘。’改為‘X’，該點的性質將改變。而若將‘X’改為‘。’，則它也將變為可脫離的，該點的性質將改變。
所以，記錄下所有滿足上述性質的點所對應的列號，查詢即可。
（昨天以為每個點可以向四個方向拓展，結果一直wa。。。。。）
int
main
（）
{
int
n
，
m
；
cin
>>
n
>>
m
；
string
s
［
n
］；
for
（
int
i
=
0
；
i
<
n
；
i
++
）
cin
>>
s
［
i
］；
set
<
int
>
t
；
for
（
int
i
=
0
；
i
<
n
；
i
++
）
for
（
int
j
=
0
；
j
<
m
；
j
++
）
{
if
（
！
（
i
==
0
||
j
==
0
||
s
［
i
-
1
］［
j
］
==
‘。’
||
s
［
i
］［
j
-
1
］
==
‘。’
））
t
。
insert
（
j
+
1
）；
}
t
。
insert
（
9999999
）；
int
q
；
cin
>>
q
；
while
（
q
——
）{
int
x
，
y
；
cin
>>
x
>>
y
；
if
（
*
t
。
upper_bound
（
x
）
<=
y
）
cout
<<
“NO
\n
”
；
else
cout
<<
“YES
\n
”
；
}
return
0
；
}
D。 Omkar and the Meaning of Life
題意：有一個
的排列
，使用最多
次詢問機會，猜出這個排列。
詢問格式如下：選擇一組
，將構造陣列
，返回下標
，使得
![b[i]](https://img.bearask.com/upload/website_attach/6uA56tKm1-MoT87Eo6-e76PLSvML25hgod05J+IC_FTm-2=-8Pdv7CPpOPDMQ.jpeg)
在
陣列中出現了至少兩次。如果有多個下標滿足條件，返回最小的那個；如果沒有下標滿足條件，返回
。
分析：考慮特殊情況，①如果詢問
，其中第
位放
，其餘放
，則一定只能找出一對下標
滿足
，其中應當有
。但是由於函式只會返回一個數據，即
。如果
就能得到
的資訊，反之則無法得到有用的資訊。
對於這種詢問方法，我們可以得知在
左側且比
小
的元素。
②如果詢問
，其中第
位放
，其餘放
，同理可以獲知在
左側且比
大
的元素。
我們對
分別進行上述兩種詢問，正好用了
次詢問機會。這樣，如果兩個元素相差一，則這種關係一定能在上述兩種詢問之一被探尋出——設
，若
，則對於
採用第一種詢問時能得出；若
，則對於
採用第二種詢問時能得出。
得知了比各個數大
的元素的位置後，我們就能很輕鬆地還原出原排列了。
程式碼：
int
main
（）
{
cin
>>
n
；
int
next
［
n
+
1
］，
ans
［
n
+
1
］；
//next陣列表示比當前位置值大1的位置。
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
{
cout
<<
“？ ”
；
for
（
int
j
=
1
；
j
<=
n
；
j
++
）
if
（
i
==
j
）
cout
<<
1
<<
“ ”
；
else
cout
<<
2
<<
“ ”
；
cout
<<
endl
；
int
tmp
；
cin
>>
tmp
；
if
（
tmp
！=
i
）
next
［
tmp
］
=
i
；
//分別對應兩種詢問
cout
<<
“？ ”
；
for
（
int
j
=
1
；
j
<=
n
；
j
++
）
if
（
i
==
j
）
cout
<<
2
<<
“ ”
；
else
cout
<<
1
<<
“ ”
；
cout
<<
endl
；
cin
>>
tmp
；
if
（
tmp
！=
i
）
next
［
i
］
=
tmp
；
}
int
cnt
=
0
，
now
=
next
［
0
］；
while
（
now
）
ans
［
now
］
=
++
cnt
，
now
=
next
［
now
］；
cout
<<
“！ ”
；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
cout
<<
ans
［
i
］
<<
“ ”
；
return
0
；
}
E。 Moment of Bloom
題意：已知無向連通圖，其中指定
組點對，為每組
分配一條路徑，並使路徑上所有的邊權值加一，問是否有方法使得圖中的每條邊的權值均為偶數，如有，給出方法；如沒有，給出最少需要額外新增的點對數量，使得條件成立。
分析：題述條件成立，當且僅當每個點在點對中都出現了偶數次。證明如下：
記某一點
在點對中出現的次數為
。
①反設某一點
出現了奇數次，則考慮以
為端點的邊的權值和
——
一條以
開始的路徑或一條以
結尾的路徑將帶來
的貢獻
一條穿過
（不以它結尾）的路徑將帶來
的貢獻；沒有穿過則帶來
的貢獻。
所以，
一定是奇數。所以其中至少有一條邊的權值是奇數。
②設每一點都出現了偶數次，取包含這些點的某一生成樹。
反設某條邊
被經過奇數次——我們設這條邊將樹分成兩個部分，有奇陣列點從該邊的一側到達另一側。考慮其中一側的所有點出現的次數
之和
——
從這一側到達另一側的一條路徑將帶來
的貢獻
從這一側某點到另一點的一條路徑將帶來
的貢獻
所以，這個和一定是奇數，即一定有某一點
滿足
是奇數，矛盾。
綜上，若每一點的
都是偶數，則條件成立，取任意生成樹和某一根，輸出兩點在樹上的路徑即可。若某一點的
是奇數，則條件不成立，輸出NO。需要補充一些詢問使得所有點的出現次數均為偶數。
尋找生成樹的過程，可以用並查集實現。
程式碼：
struct
dsu
{
vector
<
int
>
p
；
dsu
（
int
n
）{
p
。
resize
（
n
+
1
）；
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
p
［
i
］
=
i
；}
int
find
（
int
x
）{
if
（
p
［
x
］
！=
x
）
p
［
x
］
=
find
（
p
［
x
］）；
return
p
［
x
］；}
void
merge
（
int
x
，
int
y
）{
p
［
find
（
x
）］
=
y
；}
}；
//並查集模板
bool
dfs
（
int
now
，
int
fa
，
int
goal
，
int
depth
，
auto
v
）
//查詢並列印路徑
{
if
（
now
==
goal
）
{
cout
<<
depth
<<
‘\n’
；
return
true
；
}
for
（
auto
it
：
v
［
now
］）
{
if
（
it
==
fa
）
continue
；
if
（
dfs
（
it
，
now
，
goal
，
depth
+
1
，
v
））
{
cout
<<
it
<<
“ ”
；
return
true
；
}
}
return
false
；
}
int
main
（）
{
int
n
，
m
；
cin
>>
n
>>
m
；
dsu
s
（
n
）；
vector
<
int
>
v
［
n
+
1
］；
for
（
int
i
=
1
，
x
，
y
；
i
<=
m
；
i
++
）
{
cin
>>
x
>>
y
；
if
（
s
。
find
（
x
）
！=
s
。
find
（
y
））
{
v
［
x
］。
push_back
（
y
）；
v
［
y
］。
push_back
（
x
）；
s
。
merge
（
x
，
y
）；
}
}
int
q
；
cin
>>
q
；
int
cnt
［
n
+
1
］
=
{
0
}；
int
a
［
q
+
1
］，
b
［
q
+
1
］；
for
（
int
i
=
1
；
i
<=
q
；
i
++
）
{
cin
>>
a
［
i
］
>>
b
［
i
］；
cnt
［
a
［
i
］］
++
；
cnt
［
b
［
i
］］
++
；
}
int
num
=
0
；
//統計cnt為奇數的個數
for
（
int
i
=
1
；
i
<=
n
；
i
++
）
num
+=
cnt
［
i
］
%
2
；
if
（
num
==
0
）
{
cout
<<
“YES
\n
”
；
for
（
int
i
=
1
；
i
<=
q
；
i
++
）
{
dfs
（
b
［
i
］，
b
［
i
］，
a
［
i
］，
1
，
v
）；
cout
<<
b
［
i
］
<<
‘\n’
；
}
}
else
{
cout
<<
“NO
\n
”
；
cout
<<
num
/
2
<<
‘\n’
；
}
return
0
；
}
