DAY1

賽時切了三題，賽后補的B.

A

給定一個序列，每次詢問\([l_1,r_1]\)與\([l_2,r_2]\)的是否同構，題面中對同構的定義是前綴最大值出現的位置在子數組的相對位置是相等的。

考慮處理出每個數左邊的第一個比之大的數的位置，記作\(L_i\)，對于每次區間\([l,r]\)的詢問，這里出現前綴最大值的所有位置都滿足\(l+1\leq j\leq r\land L_j<l\)，假設一開始所有位置都是合法的，當你倒序枚舉\(l\)時，會將\(L_j \geq l\)的位置刪除貢獻，因此可以倒著做掃描線，并將位置看成二進制下的數位，哈希進行匹配，即第\(i\)個位置當其有貢獻時要記作\(2^i\)，最后匹配的時候再額外地右移\(l\)位即可。

綜上，我們可以得到\(O((n+q)\log n)\)的做法。

（翻了翻別人的代碼，感覺掃描線解很少啊）

#include<bits/stdc++.h>
#define fi first 
#define se second
#define pb push_back
#define mt make_tuple
using ll=long long;
using namespace std;
typedef  tuple<int,int,int>ti3;
typedef     pair<int,int>pii;
const int N=3e5+9;
//掃描線 + 哈希
const ll mod=1e15+37;
using i128=__int128;
i128 pw2[N];
i128 invpw2[N];

i128 qpow(i128 x,i128 y){
    i128 res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
i128 inv(i128 x){
    return qpow(x,mod-2);
}
void init(){
    pw2[0]=1;
    for(int i=1;i<N;i++)pw2[i]=pw2[i-1]*2ll%mod;
}
i128 mo(i128 x){
    return (x%mod+mod)%mod;
}
class Bit{
#define lowbit(x) x&-x
public:
    vector<i128>c;
    int n;
    Bit(int n):n(n){
        c.assign(n+1,0);
    }
    i128 Sum(int x){
        i128 sum=0;
        for(int i=x;i>0;i-=lowbit(i)){
            sum=(sum+c[i])%mod;
        }
        return sum;
    }
    i128 cal(int x,int y){
        return mo(Sum(y)-Sum(x-1));
    }
    void add(int x,i128 y){
        for(int i=x;i<=n;i+=lowbit(i))c[i]=(c[i]+y)%mod;
    }
    #undef lowbit
};
void Silverwolf(){
    int n,q;
    cin>>n>>q;
    vector<int>a(n+1),L(n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>stk;//維護單調遞減棧？
    for(int i=n;i>=1;i--){
        while(stk.size()&&a[i]>a[stk.back()]){
            L[stk.back()]=i;
            stk.pop_back();
        }
        stk.pb(i);
    
    }
    // for(int i=1;i<=n;i++)cout<<L[i]<<" ";cout<<'\n';
    vector<vector<int>>del(n+1);//需要刪除的貢獻的位置
    for(int i=1;i<=n;i++)del[L[i]].pb(i);
    //找到左邊第一個比它大的位置
    vector<vector<ti3>>qry(n+1);//l:[r,j,0/1] //掃描線
    vector<vector<ll>>ask(q+1,vector<ll>(2,0)); //這里是離線的詢問吧
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        qry[l].pb(mt(r,i,0));
        cin>>l>>r;
        qry[l].pb(mt(r,i,1));
    }
    Bit bit(n);
    for(int i=1;i<=n;i++)bit.add(i,pw2[i]);
    for(int l=n;l>=1;l--){
        for(auto j:del[l]){
            bit.add(j,-pw2[j]);
        }
        for(auto [r,j,id]:qry[l]){
            i128 tmp=0;
            if(l<r)tmp=bit.cal(l+1,r);
            tmp=tmp*inv(pw2[l-1])%mod;
            ask[j][id]=tmp;
        }
    }
    for(int i=1;i<=q;i++){
        if(ask[i][0]==ask[i][1])cout<<"Yes\n";
        else cout<<"No\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    // int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}
/*
10 6
3 1 4 1 5 9 2 6 5 3
1 3 3 5
1 5 6 10
1 1 9 9
1 9 1 9
1 3 6 8
5 8 7 10
0 1 0 3 0 0 6 6 8 9 


10 1
3 1 4 1 5 9 2 6 5 3
5 8 7 10
*/

B

對于一個括號序列，合法的一個必要條件是：對于前\(2i-1\)個位置，至少要有\(i\)個左括號。

那么對于\(n\)個括號序列，一定要求前\(2i-1\)個位置，左括號的數量至少是\(i\times n\)個。

這個必要條件保證了，構造這\(n\)個括號不會出現前面某個位置右括號比左括號多的情況，再加上\(\sum a_i=k\times n\)即為答案。

時間復雜度\(O(n)\)。

#include<bits/stdc++.h>
#define int long long 
#define fi first 
#define se second
#define pb push_back
using ll=long long;
using namespace std;
const int N=1e6+10;



void Silverwolf(){
    ll n;
    int k;
    cin>>n>>k;
    ll cnt=0,sum=0;
    vector<ll>a(2*k+1,0),pre(2*k+1,0);
    for(int i=1;i<=2*k;i++)cin>>a[i],sum+=a[i],pre[i]=pre[i-1]+a[i];
    if(sum!=n*k)return cout<<"No\n",void();
    for(int i=1;i<2*k;i+=2){
        if(pre[i]<n*(i+1)/2)return cout<<"No\n",void();
    }
    cout<<"Yes\n";

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}
/*
2
3 3
3 2 2 0 2 0
3 3
3 0 2 3 1 0


10
3 3
3 3 1 1 1 0 
3 3
3 2 2 2 0 0 
3 3
3 2 2 1 1 0 
3 3
3 2 1 2 1 0 
3 3
3 2 2 1 1 0 
3 3
3 2 2 0 2 0
3 3
3 2 1 1 2 0
3 3
3 1 3 1 1 0
3 3
3 1 2 2 1 0
3 3
3 1 2 1 2 0

2
3 3
3 2 0 2 2 0
3 3
3 2 0 3 1 0


3 3
3 2 0 2 2 0

a_i-(n-a_i)

3 1 -3....

*/

M

合法的樹一定是最小生成樹。

構造出最小生成樹，枚舉非樹邊，看看是否都滿足\(w\geq dis_{u,v}\)即可。

時間復雜度\(O(m\log n)\)。

#include<bits/stdc++.h>
#define fi first 
#define se second
#define pb push_back
using ll=long long;
using namespace std;
const int N=1e6+10;
typedef pair<int,int>pii;
class Tree{
public:
    vector<int>dep;
    vector<vector<int>>fa;
    vector<vector<pii>>e;
    vector<ll>dp;
    Tree(int n){
        dep.assign(n+1,0);
        e.resize(n+1);
        fa.assign(n+1,vector<int>(20,0));
        dp.assign(n+1,0);
    }
    void dfs(int u,int f){
        dep[u]=dep[f]+1;
        fa[u][0]=f;
        
        for(int i=1;i<=19;i++){
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
        for(auto [v,w]:e[u]){
            if(v!=f){
                dp[v]=w;
                dfs(v,u);
            }
        }
    }

    void dfs2(int u,int f){
        for(auto [v,w]:e[u]){
            if(v==f)continue;
            dp[v]+=dp[u];
            dfs2(v,u);
            
        }
    }
    void work(){
        dfs(1,0);
        dfs2(1,0);
    }
    void add(int u,int v,int w){
        e[u].pb({v,w});
        e[v].pb({u,w});
    }
    int lca(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        for(int i=19;i>=0;i--){
            if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
            if(u==v)return v;

        }
        for(int i=19;i>=0;i--){
            if(fa[u][i]!=fa[v][i]){
                u=fa[u][i],v=fa[v][i];
            }
        }
        return fa[u][0];
    }
    ll dis(int u,int v){
        return dp[u]+dp[v]-2*dp[lca(u,v)];
    }
};
struct edge{
    int u,v,w;
    edge(){}
    edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator<(const edge& t){
        return w<t.w;
    }
};
struct Bin{
    vector<int>f;
    Bin(int n){
        f.assign(n+1,0);
        for(int i=1;i<=n;i++)f[i]=i;
    }
    int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);
    }
    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fy==fx)return false;
        f[fy]=fx;
        return true;
    }
};
void Silverwolf(){
    int n,m;
    cin>>n>>m;
    vector<edge>edg(m+1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edg[i]=edge(u,v,w);
    }
    sort(edg.begin()+1,edg.end());
    vector<edge>e2;
    Bin b(n);
    Tree tr(n);
    for(int i=1;i<=m;i++){
        auto [u,v,w]=edg[i];
        if(!b.merge(u,v)){
            e2.pb(edge(u,v,w));
        }else{
            tr.add(u,v,w);
        }
    }
    tr.work();
    for(auto [u,v,w]:e2){
        if(w<tr.dis(u,v))return cout<<"No\n",void();
    }
    cout<<"Yes\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}
/*

3 3
1 2 3
2 3 4
3 1 100

3 3
1 2 3
2 3 4
3 1 2
*/

Q

長度不足\(3\)的一定可以建出唯一的二次函數。

否則，檢查相鄰三項的二次函數\(A,B,C\)值，看看是否可以擴展即可。

隊友寫的。

#include<bits/stdc++.h>
#define int long long
#define fi first 
#define se second
#define pb push_back
using ll=long long;
using namespace std;
const int N=1e6+10;
vector<int> getABC(int p0,int p1,int p2){
    //vector<pair<int,int>> ans(3,{-1,-1});
    //這里令p0的x值歸0
    int c=p0;
    //a+b+c==p1
    //4a+2b+c==p2
    //2a+2b+2c==2p1
    //=>
    //a=(p2-2*p1+c)/2
    int a_up=p2-2*p1+c;
    int a_down=2;
    //4a+4b+4c==4p1
    //=>
    //2b+3c==4p1-p2
    //b=(4*p1-p2-3c)/2
    int b_up=4*p1-p2-3*c;
    int b_down=2;

    //不如直接c*2上去
    return {a_up,b_up,c*2};
}

void Silverwolf(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(auto &x:nums)
        cin>>x;

    if(n<=3){
        cout<<1<<endl;
        return;
    }

    int ans=1;
    vector<int> cur_abc=getABC(nums[0],nums[1],nums[2]);
    for(int i=3;i<n;++i){
        vector<int> rst=getABC(nums[i-2],nums[i-1],nums[i]);
        if(rst[0]==cur_abc[0])
            continue;
        ++ans;
        if(i+3>=n)
            break;
        cur_abc=getABC(nums[i],nums[i+1],nums[i+2]);
        i+=2;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}

DAY2

不好玩！討厭數學題！

賽時切了六個題，這里按題目順序稍微寫點題解吧，計劃補一下\(\text{F}、\text{K}\).

B

考慮貪心策略。

如果出現了某個點被兩個區間覆蓋，結果一定是無解，所以我們將\((l,-1)\)和\((-1,r)\)先填成\((l,l)\)和\((r,r)\)，判定一下是否出現了一個點被兩個及以上區間覆蓋的情況，可以直接按左端點排序，也可以離散化后差分。

對于\((-1,-1)\)，我們可以在任意位置填上這個東西，記錄一下其數量，假設為\(cnt\).

對于剩余要填的\((l,-1)\)和\((-1,r)\)，假設當前空余區間是\([L,R]\)，貪心處理一下整段的最小貢獻，假設按端點排序后的待處理隊列為\(vt\)：

• 當\(vt_0=(l,-1)\land l\not=L\)，我們需要用\((-1,-1)\)填上\([L+1,l]\)的貢獻
• 當\(vt_{m-1}=(-1,r)\land r\not=R\)，我們需要用\((-1,-1)\)填上\([r+1,R]\)的貢獻
• 當\(vt_i=(-1,r)\land vt_{i+1}=(l,-1)\land r+1\not=l\)，我們需要填上\((r+1,l)\)的貢獻

若我們剩余的\((-1,-1)\)段數不足了，直接判無解。

復雜度瓶頸在于排序，因此我們得到了\(O(n\log n)\)的做法，代碼實現不難。

D

當\(k\)是奇數的情況，那么序列中間的數必須是\(mid\)本身，枚舉位置，檢查前后是否各有\(\frac{k-1}{2}\)個位置即可。

當\(k\)是偶數，那么序列中間的兩個數必須滿足\(x_1+x_2=2\times mid\)，設\((x_1<x_2)\)，枚舉\(x_1\)找最近的\(x_2\)的位置，檢查前后是否各有\(\frac{k-2}{2}\)個位置即可。

F

考慮到，斐波那契數列的增長速率是非常快的，在\(n\)比較大的時候，恰好有$\frac{F_{n+1}}{F_{n}}\approx \phi $，其中 $\phi=\frac{\sqrt 5+1}{2} $。

在\(n\)較大的時候，可以用\(F_n\approx \frac{\phi^n}{\sqrt 5}\)擬合。

這種計數顯然和位置無關，因此我們可以對序列從小到大排序，枚舉大的那個，打表發現，滿足\(x<y\land x+y∈Fib\)的\(x\)最多兩個，不妨將這兩個都找出來，將斐波那契序列前\(10^8\)項求出，并哈希處理，取一個大質數，接下來我們只需要估算\(y\)附近的斐波那契項，這樣已經轉化成了前綴\(\text{map}\)表經典問題。

設\(y=\frac{\phi ^n}{\sqrt 5}\)，那么就有\(n=log_{\phi} \sqrt 5y =\log_{\phi} \sqrt{5}+\log_{\phi} y=\frac{\lg \sqrt 5}{\lg \phi}+\frac{\lg y}{\lg \phi}\)。

其中所有項都可以暴力求出 ，而\(\lg y\)的大小實際上就是\(y\)對應的高精度字符串的\(len-1\)。

為保證正確性，我們在\(n\)附近枚舉\(25\)項左右。

時間復雜度\(O(10^8+50\times n+n\log n)\)。

G

零和博弈。

\(\text{Bob}\)的策略是刪掉每一列中較大數，留給\(\text{Alice}\)的就只能是每一行的最小數，取最大值即可。

J

\(O(n^3)\)暴力枚舉即可。

K

首先出現環一定無解。

對于一個\(x\)，其鄰邊一定是\(2x\)，\(2x+1\)或\(\lfloor \frac{x}{2} \rfloor\)，所以當某個點度數超過\(3\)的時候也無解。

不妨考慮\(dp\)，以某個點為根，保證根節點的度數一定為\(1\)或\(2\)。

設：\(dp_{u,0/1}\)分別表示以\(u\)為根的子樹，根節點設為\(0/1\)時的最小貢獻，當選作\(0\)時，它的子節點的數量只能選取\(1\)個，當選作\(1\)時候，它的子節點的數量可以是\(1\)或\(2\)個。

不難發現，每顆子樹內的答案與根的選擇有關，我們\(dp\)維護一個線性函數：\(ax+b\)表示根節點選\(x\)時以它為根的子樹的貢獻。

討論一下轉移：

• 若子節點個數為\(1\)，設其子節點為\(v\)，且\(dp_{v,1}=ax+b\)，則\(dp_{u,0}=a(x+1)+b,dp_{u,1}=a(2x)+b\)。且該情況可取當且僅當子樹深度不超過\(32\)。
• 否則設其子節點為\(v_1,v_2\)，且\(dp_{v_1,1}=a_1x+b_1,dp_{v_2}=a_2x+b_2\)，則\(dp_{u,1}=a_1(2x)+b_1+a_2(2x+1)+b_2\)，翻轉一下\(v_1,v_2\)的位置也是一樣的。該情況可取當且僅當子樹深度不超過\(31\)。

換根\(dp\)再跑一遍。

代碼實現將\(dp\)采用\(Info\)類的方式實現會比較簡單。

L

由于排列是隨機生成的，那么下一格期望的增長量是\(\frac{n}{2}\)。

那么\(len^2=\frac{n}{2}len\)的解將取在\(len=\frac{n}{2}\)附近。

我們的策略是，在\(\frac{n}{2}\)和原點附近各取\(D\)個點枚舉判斷，\(D=1000\)可以容易通過。

時間復雜度\(O(Dn)\)。

M

貪心，從大到小排序，取前\(2^i(0\leq i\leq n)\)的最大值即為答案。

Moscow

還算一個比較有意思的場吧，感覺賽時狀態不是特別好。

A

二維序列，\((a_i\% m_1,a_i\% m_2)\)，按前者升序排序，相同時候后者降序排序。

如果第二維出現了\(j>i\land a_j>a_i\)的位置則構造不出方案，否則一定可以。

劃分出若干個區間\([l,r]\)全相等，其方案數就是\(\prod (r-l+1)!\)。

B

手玩一下樣例，發現前\(\frac{n}{2}\)和后\(\frac{n}{2}\)個數不會跨過中間的分界線，且\(\text{R}\)操作后后一定是按前一半降序且后一半升序。

最后一次\(\text{R}\)操作排序一下，否則模擬即可。

E

考慮枚舉將哪個位置用完后，分配給另外一個位置使用。

直接寫個暴力遞歸。

這樣可以得到一個\(O(24^2 T)\)的做法。

F

考慮樸素版本的區間\(dp\)，設計\(dp\)狀態為：\(dp_{l,r}\)表示區間\([l,r]\)已經被完全檢測過的最小貢獻值，答案即為\(dp_{1,n}\)。

轉移時枚舉傳送門，要么劃分成兩個更小的區間，設其為\([l_1,r_1],[l_2,r_2]\)，這時的轉移式是\(dp_{l_r}=min(max(dp_{l_1,r_1},dp_{l_2,r_2})+a_i)\)，這部分的轉移是無后效性的。

要么劃分成另一個長度相等的區間，設其為\([l_3,r_3]\)，這時的轉移為 \(dp_{l,r}=min(dp_{l_3,r_3}+a_i)\)，這部分的轉移是有后效性的，所以要對這些區間跑最短路。

前者復雜度 \(O(n^3)\)，后者遠無法跑到的復雜度上限是\(O(n^3\log n)\)。

I

通信題。

首先，貢獻的上界在\(2\times 10^6\)，題目啟發我們可以用\(2000\times x+y\)來表示。

每\(2000\)個位置中一定存在至少一個位置，\(y\)的取值是\(0\)或\(1\)。

那么，用\(\text{Info}\)的前\(1000\)個位置\(([0,999])\)用來做\(x\)的碼，剩下一個位置\(1000\)，用來做奇偶校驗碼，檢查\(y=0\)還是\(y=1\)即可。

M

貪心的，顯然從最大值往四周吞。

貢獻就是\(\sum a_i-max \ a_i\)。

[The 3rd Universal Cup. Stage 1: St. Petersburg ](The 3rd Universal Cup. Stage 1: St. Petersburg )

C

考慮從后往前添加點，記沒加入的點為\(0\)，加入的點中若為\(1\)則記作\(1\)，否則記作\(-inf\)，線段樹維護最大子段和。

D

由于要求必須有序，所以二分是行不通的。

前半天，我們按照\(49,48,47.....32\)這樣詢問，找到第一次斷點的位置。

然后在第二次后半天暴力詢問。

次數剛好是\(50\)次。

H

\(10\)一定不會出現，所以答案是\(min(n+1,10)\)。

J

留坑，還不會。

K

模擬題。

N

首先題目給的范圍提示的比較明顯，將原圖的形態先存在來。

然后用\(\lceil{log_2 n}\rceil\)存二進制編號。

設我當前在使用\(n+1,n+2,n+3\)這三個多余的節點。

考慮構造一個只有一個點的度數為\(n\)的圖，我們將\(n+1\)連向所有\([1,n]\)的節點，如果連完后存在\([1,n]\)中的某個節點的度數恰好是\(n\)，將那個點連向\(n+2\)。

這樣我們確定了圖的形態。

接下來我們將\(n+3\)指向二進制最高位的節點，并且將二進制的相鄰兩位之間連邊，這樣就解開了所有的二進制編碼。

但是這種情況當\(n=3\)時要特判，我們將一行的度數\([0,7]\)二進制壓縮，分別代表\((1,2)、(1,3)、(2、3)\)這三條邊即可。

O

類似斐波那契數列，遞歸解一下\(f_2\)，再遞推回來即可。

The 3rd Universal Cup. Stage 18: Southeastern Europe

A

設選定根，操作次數為\(n-cnt[dep_i\leq 2]\)，所以選度數最大的節點作為根遍歷即可。

C

設你當前有兩個集合\(A、B\)，設\(near(A,B)\)表示\(A、B\)兩集合是否相鄰，設\(connect(A,B)\)表示兩集合是否中間恰好有一個點將其聯通了起來。

考慮到\(ask(A)+ask(B)=ask(\{A,B\})-k_1near(A,B)-k_2connect(A,B)\)，即當\(ask(A)+ask(B)-ask(\{A,B\})>0\)時，這兩個集合處在不同的聯通塊中。

我們維護一個聯通塊，每次從剩余節點，看看能不能二分得到一個新的未聯通節點，并加入。

這樣的次數瓶頸是\(O(n\log n)\)。

D

先手的策略一定是將最大的那個數拿走。

那么對于后手，只需要判斷剩下的\(sum\geq n\)是否成立即可。

F

（感覺思路基本上都有，但是差了點火候，看了點提示切的）。

首先，判斷\((i,j)\)對是否好的，只需要拿出分別的最小、最大值，很好證明，當且僅當\([mn_1,mx_1],[mn_2,mx_2]\)有交的情況，這個對是好的，所以將所有的袋子只選出最小值\(mn\)和最大值\(mx\)，\((i,j)\)是否好，不會有變化，這樣我們已經將答案約束在了\(2n\)。

我們可以選擇將一些區間刪除，留下袋子中的某個點。

當刪除某個區間時，必須滿足，覆蓋該點的區間的數量\(cnt_1\)=和該區間相交的區間數量\(cnt_2\)（包含也算的）。

且，當刪除某個區間時，其他與該區間覆蓋的區間就不能被刪除了。

對于\(cnt_1\)，我們可以差分加前綴和求出。

對于\(cnt_2\)，這是個很經典的問題，設當前的區間為\([l,r]\)，不妨算出滿足\(R< l\)的區間數量和\(L>r\)的區間數量，用總數去減。

這樣判定一個區間是否用一個點替換我們就做完了。

將這些區間按左端點排序，設\(dp_{i}\)記錄當前已經確定了前\(i\)個區間的最大貢獻，我們維護一下與當前區間還有交集的區間，可以用\(\text{set}\)維護，不難想到的轉移方程：\(dp_{i}=max (dp_{j})[\text{i and j are disjoint}]+1\)，我們用\(set\)維護出來的位置就是不能被轉移的位置，對于可以轉移的位置，維護一下最大值即可。

綜上，我們在\(O(n\log n)\)時間復雜度內得到了答案。

G

設\(dp_{i,0/1}\)表示當前以值域\(i\)結尾，且當前和上一個位置相等、不等的最大貢獻。

線性\(dp\)。

H

問題可以轉化成，是否可以找到\(n\)個逆序對。

貪心地考慮相鄰兩列，將當前列從小到大排序，然后從前面的所有剩下的數中，用\(set\)維護一下當前數的后繼，放不下則留給后面的列。

J

考慮\(cnt_X\)記錄的是\(X\)這個溫度出現的次數。

考慮相鄰的三項，若當前數既不為最大值又不為最小值，則將\(X\)值域的貢獻更新為\(n-cnt_X\)。

否則更新為\(n-cnt_X+1\)。

即用最小值更新最大值，然后當前值就變成最大值了。

K

不難發現，這樣的操作序列實質上是將原串轉化成了這種形式：\([cnt,ch]\)表示連續\(cnt\)個\(ch\)這個字符。

線段樹，維護當前的前綴和。

考慮\([l,r]\)完全包含的區間\([L,R]\)，這之間有：\(pre_{i}=2\times (pre_{i}-pre_{L-1})\)，可以拆成區間乘\(2\)和區間加操作。

L

保留某個后綴\(m,m+1...n-1,n\)不動，將剩余部分都移到\(1\)，用值域線段樹維護某個值的位置即可。

2024ICPC上海/The 3rd Universal Cup. Stage 29: Metropolis

比較edu的一場，感覺是吸取了很多教訓吧。

被陳隊長帶飛的一級，vp銀牌倒三。五題罰時879。

我很戰犯啊！

B

由于行為是未定義的，我們可以選擇遍歷的順序。

我們用一個\(\text{set}\)維護點的連邊。

若當前\(\text{set}\)已經空了，那我們直接退出是沒問題的。

若當前非空，且當前\(\text{set}\)中沒有當前訪問點，我們這條邊必須加。

當訪問到一個點，將其從其所有鄰邊中刪除。

時間復雜度\(O(n\log n)\)。

C

隊友寫的。

分類討論題。

拿奇數的那個人，可以通過一次操作去干擾對手，改變勝負狀況。

即，考慮最小的奇數為\(x\)，檢查\(2x\leq r\)是否成立即可。

D

隊友打表打出了一些后\(6\)位的結論。

我們只需要貪心地將前面的\(1\)盡可能往后移動，檢查后\(6\)位的\(mask\)值。

（此處我半小時內實現了三個假做法）

注意到，我們可以這樣執行操作：

\(111100000->1011100000\)......

這等價于將第二個\(1\)和第一個\(0\)交換位置，可以快慢指針維護。

事實上，有解性，只與最后四位有關。（我開局口胡了這個結論，但是自己都不信，然后滾去簽到了）

當最后四位=\(??00\)時，顯然有解。

當最后一位為\(1\)，只需要滿足：\(1xy1\)就有解，只要\(x>0\lor y>0\)就有解。

流程如下：

\((inf,inf,0,inf)=(inf,inf-1,inf,0)=(inf,1,inf,0)=(inf-1,inf,0,0)\)

\((inf,0,inf,inf)=(inf-1,inf-1,0,inf)\)，然后重復上過程。

\((inf,inf,inf,inf)=(inf,0,inf,inf)\)，然后重復上過程。

當倒數第二位為\(1\)，只需要倒數第四位為\(1\)就有解。

\((inf,0,inf,0)=(inf-1,inf,0,0)\)。

\((inf,inf,inf,0)=(inf,0,inf,0)\)，然后重復上過程。

\(O(n)\)。

G

考慮二分答案，二分是否有\(\lceil\frac{n}{2}\rceil\)個數是\(\geq mid\)的。

不妨對于每條斜線匹配一些豎線。

當\(a=0\)，只需檢查\(b\geq mid\)是否成立。

當\(a>0\)，合法的位置是\(ax+b\geq mid\)，即\(x\geq \lceil \frac{mid-b}{a}\rceil\)。

當\(a<0\)，合法的位置是\(ax+b\geq mid\)，即\(x\leq \lfloor\frac{b-mid}{-a}\rfloor\)。

發現這是按\(c_i\)排序后的一段前綴或后綴，所以貪心地優先分配小區間是不劣的。

本題的一個坑點是：除法是向零取整，而不是向下取整的，所以這部分需要一堆分討。

\(O(n\log A\log n)\)。

I

從大到小排序。貪心分配。

\(10^9>998244353\)，所以要格外注意取模。

且，判斷是否有\(0\)也不能檢查最大的\(k\)個乘積乘起來。

The 3rd Universal Cup. Stage 13: Sendai

B

對于每個點，找到左邊第一個比它大的位置，\(l_i\)，

E

注意到\(2\)操作往前推至多\(60\)次，將操作存在下模擬即可。

時間復雜度\(O(60n)\)。

H

隊友寫的。

每次取\(i\mod n\)最大的位置，然后令\(i+1\)。

I

隊友寫的。

考慮選擇一個點，構造一個菊花圖，這樣將圖劃分成了兩個部分。

剩下的\(n\)次操作，每次拿出一個紅和一個藍，去詢問這兩個點，不管是紅或藍，都可以減少一個不和中間塊聯通的點。

\(2n\)次詢問是足夠的。

M

如果沒有不允許兩步走同一條邊的限制，那么就是矩陣快速冪板子。

考慮容斥一下重復的路徑，即\(u->v->u\)的路徑。

設\(dp_i\)是經過\(i\)條邊，且到\([1,n]\)中的每個點的距離是\([1,n]\)的方案數。

這里，\(d_i\)指的是每個點的度。

值得注意的是，對于第一次后的\(d_i\)要全部減去\(1\)，因為不可能從上一個位置轉移過來。

考慮怎么優化這個式子，經典地，將其寫成分塊矩陣，其中\(A\)是連邊矩陣，\(D\)是度數的矩陣。

我們得到了\(O(n^3\log k)\)的做法。

The 2nd Universal Cup. Stage 2: SPb

A

容易證明，最后將這五個字符移動到目前\('b'\)所在的位置是不劣的。

B

模擬。

D

考慮\(n<m\)的情況

將第一列和最后一列填滿。

若\(n\)是奇數，用最中間那行填成一排。

若\(n\)是偶數，用最中間那行填\(2\)個空兩\(2\)個構造。

\(n>m\)同理。

特判\(n\leq 2,m\leq 2,n=m\)的情況。

G

賽時居然想了一個線段樹+根號分治的離譜做法，還收到了wrong answer！那真的是一點兒沒招了！

根號分治是正確的，設\(B\)是分界點。

當一個點的度數滿足\(du_u\leq B\)時，不妨直接暴力，這樣的復雜度是\(O(qB)\)。

一個邊被連接的狀態可以被表示成\(0,1,2\)，發現\(0,2\)是等價的，我們不關心，所以不妨用\(\text{bitset}\)的異或操作快速維護。

\(du>B\)的點不會超過\(\frac{2m}{B}\)個，這部分的復雜度是\(O(\frac{qn}{w})\)。

根號分治的原因主要是下半部分會超內存，所以\(B\)差不多取個\(\sqrt {2m}\)就可以了。

I

手玩樣例，分奇偶討論。

J

兩個傳送門必然有交。

枚舉\(A\)到哪個傳送門，枚舉\(B\)到哪個傳送門，暴力構造方案即可。

2025ICPC西安

好像不太能放鏈接，能寫個人題解嗎，反正我很菜就是了

vp被隊友帶銀了！

五題罰時562吧。

F

仔細分析一下約束，兩只企鵝要相遇，一定滿足：兩只企鵝相向行走，或一只企鵝已經靜止。

不妨按\((time,type,u,v)\)，表示當前時間，當前相遇的類型\(type\)，\(type=1\)表示是相向行走，否則表示后者已靜止。

寫了個超級奇怪的\(bfs\)。

隨手一交三臉懵逼！

時間復雜度\(O(n\log n)\)。

G

從小到大排序、從大到小排序模擬一下即可。

I

一個性質是，若\((i,j)\)是相連的，那么有：

• \(f_{i,j}\oplus f_{i,i}= j\)
• \(f_{i,j}\oplus f_{j,j}=i\)
• 對于其他\(k\not=i\land k\not =j\)，滿足\(f_{i,k}\oplus f_{j,k}=i\)或\(f_{i,k}\oplus f_{j,k}=j\)

這樣可以處理出每個點的鄰邊。

我分析了下復雜度，可能是\(O(n^2\sqrt n)\)的，就讓隊友交了。

J

隊友討論/寫這題的時候我在被\(L\)控到超級紅溫，不知道題意、做法。

L

多邊形非退化的條件是，\(n-1\)條較短邊的和大于最長的邊。

首先，處理一下每個位置往前能擴展成多邊形的最短長度，二分可維護。

然后貪心地選最右邊那個這種位置。

選不了就往左擴展左端點。

時間復雜度\(O(n\log n)\)。

笑點解析：這題我狀態真有點崩盤，\(\text{100 min}\)才過這個題。

2024ICPC昆明

C

打表觀察貢獻的轉移是：\(x=x+\lceil \frac{x}{k-1}\rceil\)。

整出分塊的性質可得：\(\lceil \frac{x}{k-1}\rceil\)的取值至多有\(\sqrt n\)個。

設當前\(t=\lceil \frac{x}{k-1}\rceil\)，此時，\(x\)的取值將在\([(k-1)\times t,k\times t-1]\)，因此發生改變的位置發成在$cnt=\lceil \frac{k\times t-1-x}{k-1}\rceil $的位置。

當\(x+cnt\times t>n\)，這時，我們可以記錄答案。

綜上，我們得到了\(O(\sqrt n)\)的做法。

E

和交互一點沒有關系的交互題。

首先，不妨先考慮將所有距離為\(k\)的點處理出來。

然后貪心地將其放入方程組中，這一步可以用線性基維護。

然后高斯消元解方程即可。

時間復雜度\(O(30\times \frac{n^3}{w})\)

G

首先打了個\(n^2\)的\(dp\)，找找\(i,j\leq 5000\)最多的次數，發現最多是\(14\)次.

類似地，你想想，將整個序列消掉的貢獻也不會要太多次.

暴力模擬剪枝即可.

H

你對這\(n\)個點做個極角排序,然后的貢獻就是相鄰的\(k\)個點之間的角度.

J

簽到,沒太看思路.

L

首先,你的怪物肯定會貪心地盡可能地去打對方血量小的,直至其能爆炸.

我們不妨記錄一下我們能攻擊的次數\(cnt\).

雙指針搞一下,假設當前已經能爆炸的怪物是\(boom\),若\(a_i\leq boom+1\),則說明這只怪物能爆炸,若\(b_j\leq boom\)則說明對手的怪物能爆掉,若不能我們就將其補到\(boom\)即可.

時間復雜度是\(O(n+m)\).

M

不難發現，按著如下方式構造即可：
\(1,2,4,7\\3,5,8,11\\6,9,12,14\\10,13,15,16\)

這樣斜著構造就行.