參賽網址：https://oj.33dai.cn/d/TYOI/contest/689ad798c5d9c2f14c20b17f

T2,T4未完成搭建

T1 寄希地【NOIP2025模擬賽T1】

題目傳送門

題目難度：\(\color{#52C41A} 普及+/提高\)

算法標簽：搜索，搜索與剪枝

~首先說 《我將 100 AC 改為 0 RE 這件事》！~

:::info[來源]
來源：2024ICPC亞洲區域賽昆明站G

cf鏈接：https://codeforces.com/gym/105588/problem/G

2024ICPC亞洲區域賽昆明站G題面：https://codeforces.com/gym/105588/attachments/download/28814/2-statement-chinese.pdf

2024ICPC亞洲區域賽昆明站G題解：https://codeforces.com/gym/105588/attachments/download/28803/tutorial.pdf
:::

思路

由于具有明顯提示性，本題沒有大樣例。

首先考慮打表，通過 \(\text {Dp}\) 或搜索。

然后我們發現答案在 \(17\) 以內，搜索時間復雜度 \(O(2^{17})\) ，_結案。

復雜度的證明

標準題解證明詳細過程

設兩數分別為 \(x\),\(y\)。

• 情況1：\(x\) 和 \(y\) 奇偶性不同，

  \(\because\) \(x\) 和 \(y\) 奇偶性不同.

  \(\therefore\) \(\gcd(x,y) \equiv 1 \pmod{2}\).

  設 \(x \equiv 1 \pmod{2}\).

  則如果使 \(x-\gcd(x,y)\).

  那么 \(x\) 和 \(y\) 在二進制下末尾都為 \(0\)，即 \(x \equiv y \equiv 0 \pmod{2}\)，我們可以視為 同時刪除 \(x\) 和 \(y\) 的末尾.

• 情況2：\(x\) 和 \(y\) 奇偶性相同，

  \(\because\) \(x\) 和 \(y\) 奇偶性相同.

  \(\therefore\) \(\gcd(x,y) \equiv 0 \pmod{2}\).

  那么 \(x\) 和 \(y\) 在二進制下末尾都為 \(0\)，即 \(x \equiv y \equiv 0 \pmod{2}\)，同時刪除 \(x\) 和 \(y\) 的末尾對答案相當于 \(+2\).

所以答案最大為 \(2 \times log_2 a+1+1\).

AC Code

std:2ms

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T;
int n,m;
struct node{int n,m,dis;};
queue<node> Q;

int bfs(){
    while (Q.size()>0)  Q.pop();
    Q.push({n,m,0});
    while (Q.size()>0){
        node t=Q.front();Q.pop();
        int x=t.n,y=t.m;
        if (x==0&&y==0) return t.dis;
        int gcd=__gcd(x,y);
        if (x==0)   gcd=y;
        if (y==0)   gcd=x;
        Q.push({x-gcd,y,t.dis+1});
        Q.push({x,y-gcd,t.dis+1});
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while (T--){
        cin>>n>>m;
        cout<<bfs()<<"\n";
    }
    return 0;
}

T2 后綴的前綴之和【NOIP2025模擬賽T2】

題目傳送門

題目難度：\(\color{#3498DB} 提高+/省選-\)

算法標簽：字符串，Trie樹，后綴數據結構，數據結構，Hashing，其他，二分查找，分治

T3 大金幣【NOIP2025模擬賽T3】

題目傳送門

題目難度：\(\color{#9D3DCF} 省選/NOI-\)

算法標簽：模擬，遞推，其他，二分查找，數學，分塊

:::info[來源]
來源：2024ICPC亞洲區域賽昆明站C

cf鏈接：https://codeforces.com/gym/105588/problem/C

2024ICPC亞洲區域賽昆明站題面：https://codeforces.com/gym/105588/attachments/download/28814/2-statement-chinese.pdf

2024ICPC亞洲區域賽昆明站題解：https://codeforces.com/gym/105588/attachments/download/28803/tutorial.pdf
:::

思路

https://oj.33dai.cn/d/TYOI/p/N0740/solution

考慮第 \(i\) 輪淘汰的第一個人，\(a_i=\lceil \frac{a_{i-1}\times k}{k-1} \rceil\)。

可以通過打表得知,_{為什么我沒發現}。

直接暴力太慢了，時間復雜度 \(O(n)\)。

\(a_i=\lceil \frac{a_{i-1}\times k}{k-1} \rceil=a_{i-1}+\lceil \frac{a_{i-1}}{k-1} \rceil\)

所以可以每次考慮增量 \(c=\lceil \frac{a_{i-1}}{k-1} \rceil\)。

二分即可。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=1e7+5;
int T;
int n,k;
int dp[maxn];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while (T--){
        cin>>n>>k;
        dp[1]=1;
        int x=1,num=0,d=0;
        while (1){
            d=(x+k-2)/(k-1);
            int l=0,r=(n-x+d)/d,ans=0;
            while (l<=r){
                int mid=(l+r)>>1;
                if ((x+mid*d+k-2)/(k-1)<=d){
                    l=mid+1;
                    ans=mid;
                }
                else    r=mid-1;
            }
            num=ans+1;
            if (x+num*d>=n){
                x+=((n-x)/d)*d;
                break;
            }
            x+=num*d;
        }
        cout<<x<<"\n";
    }
    return 0;
}

T4 道路定向【NOIP2025模擬賽T4】

題目傳送門

題目難度：\(\color{#0E1D69} NOI/NOI+\)

算法標簽：貪心，搜索，折半搜索，動態規劃，樹形DP