---
# System prepended metadata

title: 2024 NCPC 清華校內初選

---


2024 NCPC 清華校內初選
===
比賽鏈結
---
No

比賽影片
---
{%youtube fNtHs46RfMo %}

記分板
---

![image](https://hackmd.io/_uploads/BkqPHkxl1x.png)


題解
---
### A. 𝕬𝖓𝖔𝖓 𝕿𝖔𝖐𝖞𝖔
---
#### 題目摘要
![螢幕擷取畫面 2024-09-24 190801](https://hackmd.io/_uploads/Bkj0aMeR0.png)
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 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();
}

```
:::