2024 NCPC 清華校內初選
===
比賽鏈結
---
No
比賽影片
---
{%youtube fNtHs46RfMo %}
記分板
---
題解
---
### A. 𝕬𝖓𝖔𝖓 𝕿𝖔𝖐𝖞𝖔
---
#### 題目摘要
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ godempty's\ imaginary\ waifu: 𝕬𝖓𝖔𝖓$
要GO造出圖，有三種操作：
1. L操作：給你舊點和新點，將兩點連線
2. D操作：複製一條已出現過的邊
3. I操作：將一條邊中間增加一條新點
給你一張$n$點$m$邊簡單連通圖，問在你原先只有點1的情況下，能不能在$m$次操作後GO造出此圖。如果可以請輸出GO造順序
#### 想法
先隨性證明若能用這三種操作做出此圖，則操作數必定是邊數：
對於L操作，就是多增加邊，所以邊數一定+1
對於I操作，相當於減一條邊再加兩條邊，所以邊數+1
對於D操作，複製一條邊就是邊數+1，雖然目前是重邊，但因為最後是簡單圖，所以之後一定有I操作把重邊弄不見
證明這個有什麼用嗎?好像沒有，這頂多是$m$次操作的條件無視而已，與解答無關(~~我證爽的~~)
與其說是增邊，不如來考慮刪邊：
若有個點的度數為1，要刪除它只能用L操作
若度數為2，要刪除它只能用I操作
若有重邊(I操作造成的)，用D操作刪除
因此，可以用拓樸的方式實作：刪除度數為1的點，刪完後再刪度數2的點，若看到重邊馬上刪除，每次刪除點時更新周圍點的度數，注意最後剩下的點要是1，所以在每次記得不要把1列入要刪除的點。最後會得到刪除的順序，反著輸出就是GO圖的順序$!!!!!$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<char, int, int, int> tup;
#define F first
#define S second
const int N=2e5+10;
set<int> v[N];
int in[N];
map<pii, bool> mp;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
v[a].insert(b);
v[b].insert(a);
in[a]++;
in[b]++;
mp[{a, b}]=1;
}
vector<tup> ans(m);
int idx=0;
deque<pii> dq;
for(int i=2;i<=n;i++){
if (in[i]==1) dq.push_front({i, 1});
else if (in[i]==2) dq.push_back({i, 2});
}
while(!dq.empty()){
auto [x, _]=dq.front();
dq.pop_front();
if (_!=in[x]) continue;
if (_==1){
auto &[c, a, b, d]=ans[idx++];
c='L', a=*v[x].begin(), b=x;
v[a].erase(b);
v[b].erase(a);
in[a]--;
in[b]--;
mp.erase(minmax(a, b));
if (a!=1&&in[a]==1) dq.push_front({a, 1});
else if (a!=1&&in[a]==2) dq.push_back({a, 2});
}else if (_==2){
auto &[c, a, b, d]=ans[idx++];
c='I', a=*v[x].begin(), b=*prev(v[x].end()), d=x;
v[a].erase(d);
v[b].erase(d);
v[d].erase(a);
v[d].erase(b);
in[a]--;
in[b]--;
in[d]-=2;
mp.erase(minmax(a, d));
mp.erase(minmax(b, d));
if (mp.find(minmax(a, b))!=mp.end()){
auto &[c2, a2, b2, d2]=ans[idx++];
c2='D', a2=a, b2=b;
if (a!=1&&in[a]==1) dq.push_front({a, 1});
else if (a!=1&&in[a]==2) dq.push_back({a, 2});
if (b!=1&&in[b]==1) dq.push_front({b, 1});
else if (b!=1&&in[b]==2) dq.push_back({b, 2});
}else{
v[a].insert(b);
v[b].insert(a);
in[a]++;
in[b]++;
mp[minmax(a, b)]=1;
}
}
}
bool phlag=(idx==m);
for(int i=1;i<=n;i++) phlag&=(in[i]==0);
if (phlag){
cout << "Yes\n";
reverse(ans.begin(), ans.end());
for(auto [c, a, b, d]:ans){
cout << c << ' ' << a << ' ' << b << ' ';
if (c=='I') cout << d << ' ';
cout << '\n';
}
}else{
cout << "No\n";
}
}
```
:::
### B. BanG Dream! It’s MyGO!!!!!
---
#### 題目摘要
給一張無向圖，定義MyGO path為路徑上的編號要先遞增再遞減(完全遞增或遞減也行)。有$q$筆詢問，每筆詢問給兩點$a, b$，問能不能用MyGO path從$a走到b$
#### 想法
沒想法
:::spoiler 實作
```cpp=
```
:::
### C. Cattus Magi Raana Magica
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### D. Don’t Cross the Circles!
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### E. Euclid Sort
---
#### 題目摘要
給一個長度$n$排列，問能不能在5000次交換內任序列變成由小到大排序，若能則輸出操作，否則輸出-1。交換的條件為兩元素位置差為質數
#### 想法
觀察到只有小於3時要特判無解，其他都可以動動腦構出來
賽中一直亂把1 3 2 4判無解，黑
好好實作就可以在他的範圍裡，一個數字大概可以用三個以內的質數構成
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
void solve() {
int n; cin >> n;
vector<int> a(n);
rep (i, 0, n) cin >> a[i];
if (n < 4) {
if (n == 1) cout << 0 << '\n';
if (n == 2) {
if (a[0] == 1) cout << 0 << '\n';
else cout << -1 << '\n';
}
if (n == 3) {
if (a[1] != 2) cout << -1 << '\n';
else if (a[0] == 1) cout << 0 << '\n';
else cout << 1 << '\n' << 1 << ' ' << 3 << '\n';
}
return;
}
vector<int> p;
vector<bool> vis(n + 1, 0);
rep (i, 2, n + 1) if (!vis[i]) {
p.pb(i);
for (int j = i + i; j <= n; j += i) vis[j] = 1;
}
vector<int> dp(n + 1, 1000005), opt(n + 1, -1);
dp[0] = 0;
for (int j : p) rep (i, 0, n + 1) {
if (i + j > n) break;
if (dp[i + j] > dp[i] + 1) {
dp[i + j] = dp[i] + 1;
opt[i + j] = i;
}
}
vector<vector<int>> way(n + 1);
rep (i, 1, n + 1) {
if (dp[i] == 1000005) dp[i] = -1;
int cur = opt[i];
while (cur != -1) {
way[i].pb(cur);
cur = opt[cur];
}
}
vector<int> pos(n + 1);
rep (i, 0, n) {
a[i]--;
pos[a[i]] = i;
}
vector<pii> ans;
rep (i, 0, n) {
auto upd = [&](int x, int step) -> void {
int cur = pos[x], nxt = pos[x] + step;
ans.pb({cur + 1, nxt + 1});
pos[a[nxt]] -= step;
pos[x] += step;
swap(a[cur], a[nxt]);
};
if (pos[i] == i) continue;
if (pos[i] - i == 1) {
if (pos[i] >= n - 2) {
if (pos[i] - 3 < 0) {
upd(i, -2);
upd(i, 3);
upd(i, -2);
upd(a[pos[i] + 1], -2);
} else {
upd(i, -3);
upd(i, 2);
upd(a[pos[i] + 1], -3);
}
} else {
upd(i, 2);
upd(i, -3);
}
} else {
int gap = pos[i] - i, pre = gap;
for (int w : way[gap]) {
int s = pre - w;
upd(i, -s);
pre = w;
}
}
}
rep (i, 0, n) assert(a[i] == i);
cout << ans.size() << '\n';
for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
int main() {
solve();
}
```
:::
### F. Fibonacci Grid
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### G. Graph Game
---
#### 題目摘要
給你一張簡單連通有向圖，你能做操作使一條簡單路的所有邊方向反轉，問最少需要多少操作?
#### 想法
建一張正常圖和反圖，邊權0，將正常圖的所有點建一條邊權1的邊指向反圖的相對應的點，反圖接回來的邊權是0，跑01bfs
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
const int N=300005, INF=1e9+10;
vector<pair<int, int>> v[N<<1];
int dis[N<<1];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
ll n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
v[a].push_back({b, 0});
v[b+n].push_back({a+n, 0});
}
for(int i=1;i<=n;i++){
v[i].push_back({i+n, 1});
v[i+n].push_back({i, 0});
}
for(int i=2;i<=(n<<1);i++) dis[i]=INF;
dis[1]=0;
deque<int> dq;
dq.push_back(1);
while(!dq.empty()){
int x=dq.front();
dq.pop_front();
for(auto [e, w]:v[x]){
if (w==1){
if (dis[x]+1<dis[e]){
dis[e]=dis[x]+1;
dq.push_back(e);
}
}else{
if (dis[x]<dis[e]){
dis[e]=dis[x];
dq.push_front(e);
}
}
}
}
if (dis[n]==INF&&dis[n+n]==INF){
cout << -1 << '\n';
}else{
cout << min(dis[n], dis[n+n]) << '\n';
}
}
```
:::
### H. Hitoshizuku
---
#### 題目摘要
你能構造多少長度為$N$的multiset，使得某個人的Greedy策略是對的
他會sort從大到小，他想把陣列裡的值分為兩堆，使得兩堆恰好等於
他會優先把值丟到目前值比較小的那邊，如果一樣就隨便丟一邊
答案模$P$
#### 想法
注意到只在乎兩堆的差，因此我們可以定義DP狀態為兩堆差的絕對值，然後他只會從大取到小，因此可以將轉移從大枚舉到小再做DP，整體複雜度為$O(NC^2)$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
int p;
void add(ll &a, ll b) {
a += b;
if (a >= p) a -= p;
}
void solve() {
int n, C; cin >> n >> C >> p;
vector dp(n + 1, vector<ll>(C + 1, 0));
dp[0][0] = 1;
for (int k = C; k > 0; --k) rep (i, 0, n) rep (j, 0, C + 1) {
add(dp[i + 1][abs(j - k)], dp[i][j]);
}
cout << dp[n][0] << '\n';
}
int main() {
solve();
}
```
:::
### I. I Like Short Statements
---
#### 題目摘要
輸出所有$x$滿足，$x\le n$且$f(x)=\sum_{i=1}^{x}(x\ mod\ i)\le m$
$1\le n, m\le 10^{12}$
#### 想法
在$i>\lfloor\frac{x}{2}\rfloor時，x\ mod\ i=x-i$，故$f(x)\ge \frac{\lfloor\frac{x-1}{2}\rfloor\times(\lfloor\frac{x-1}{2}\rfloor+1)}{2}$，所以大約估一下$n>3\times10^6$，$f(n)$就會大於$10^{12}$了。因此，可以往複雜度$O(n\log n)$的方向想
看到好多mod就會讓人想到調和級數，當固定模數$i$，隨著被模數增加，值會從$0, 1,..., i-1再跑回0繼續重複$，所以只要用調和級數跑模數去維護2次差分就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+10;
ll f[N];
int main(){
ll n, m;
cin >> n >> m;
n=min(n, 3000000LL);
for(int i=2;i<=n;i++){
f[i+1]+=1;
for(int j=i+i;j<=n;j+=i){
f[j]-=i;
f[j+1]+=i;
}
}
for(int i=1;i<=n;i++) f[i]+=f[i-1];
for(int i=1;i<=n;i++) f[i]+=f[i-1];
int ans=0;
for(int i=1;i<=n;i++){
if (f[i]<=m) ans++;
}
cout << ans << '\n';
}
```
:::
### J. Journey of the Mysterious Square
---
#### 題目摘要
給你$x^2$的首6位與尾6位並保證$x^2$至少是六位數，輸出一個滿足條件的$x$，不行輸出-1
$1\le x\le 10^{100}$
#### 想法
看到$x$好長，可以將$x$構成中間是一大堆0的數，這樣就不會讓位數低的進位影響高位數。那問題就成前面與後面的數字最大會是多少，也就是$x的個位數\times x$會不會對$x^2$的前六項造成貢獻，以及$x的最高位數\times x$會不會對$x^2$的後六項造成貢獻，可證出$x>10^7$滿足上述情況，因此只要做$x\le 10^7的情況就好$，注意到此題是多筆輸入，要打表預處理。
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast, no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll aa[1000005], bb[1000005];
void solve(){
int a, b;
cin >> a >> b;
if (aa[a]!=-1&&bb[b]!=-1){
cout << aa[a];
for(int i=0;i<50;i++) cout << 0;
cout << bb[b];
}else{
cout << -1;
}
cout << '\n';
}
int main(){
int t;
cin >> t;
for(int i=0;i<1000000;i++){
aa[i]=bb[i]=-1;
}
for(ll i=0;i<100000000;i++){
ll tmp=i*i;
bb[tmp%1000000]=i;
while(tmp>1000000) tmp/=10;
aa[tmp]=i;
}
while(t--) solve();
}
```
:::
Sign in with Wallet
Connect another wallet