1 模擬賽 把雙向掃描線寫了

2 rabbit_mygo 模擬賽

3 rabbit_mygo 推薦題

4 自己找的題 做兩~四道然后標簽里的

t1

題意

現在有兩個項鏈 \(s\) 和 \(t\)，其中的每一顆珠子都可以用一個小寫英文字母表示。現在，你需要幫敖丙從項鏈 \(s\) 中拿走一些珠子，使得項鏈 \(s\) 不存在一個連續的子串與 \(t\) 相同。

對于所有數據，保證 \(1 \leq |s| \leq 5 \times 10^4\)，\(1 \leq |t| \leq 10^3\)，且 \(s\)、\(t\) 均僅包含小寫英文字母。

題解

考慮設 \(dp_{i,j}\) 為 \(S\) 串匹配到 \(i\)，\(T\) 串匹配到 \(j\)，可以保留的最多點數。那么用 AC自動機 或者 kmp 或者 哈希預處理每種字母選上的匹配變化即可，具體是選或者不選，時間復雜度 \(O(|S||T|)\)。

#include<bits/stdc++.h>
#define int long long
#define m128(a) memset(a,-0x3f,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e3+10,inf=0x3f3f3f3f;
int ch[N][26],f[N],tot=0,dp[2][N],ans;
void add(string s){
    int pl=0,len=s.size()-1;
    rep(i,1,len){
        int num=s[i]-'a';
        if(!ch[pl][num]){
        	ch[pl][num]=++tot;
		}pl=ch[pl][num];
    }
}
void getfail(){
    queue<int> q;
    rep(i,0,25){
    	if(ch[0][i]){
        	q.push(ch[0][i]);
		}
	}while(!q.empty()){
        int u=q.front(); q.pop();
        rep(i,0,25){
            int v=ch[u][i];
            if(!v){
                ch[u][i]=ch[f[u]][i];
                continue;
            }f[v]=ch[f[u]][i];
            q.push(v);
        }
    }
}
string s,t;
signed main(){
    freopen("neck.in","r",stdin);
    freopen("neck.out","w",stdout);
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>s>>t;s=" "+s,t=" "+t;
    add(t),getfail();
    int len=s.size()-1,pl=0;
    m128(dp[pl]);dp[pl][0]=0;
    rep(i,0,len-1){
        pl^=1;
        m128(dp[pl]);
        int to=s[i+1]-'a';
        rep(j,0,tot-1){
            dp[pl][j]=max(dp[pl][j],dp[pl^1][j]);
            dp[pl][ch[j][to]]=max(dp[pl][ch[j][to]],dp[pl^1][j]+1);
        }
    }rep(i,0,tot-1) ans=max(ans,dp[pl][i]);
    cout<<ans;
    return 0;
}

t2

題面

考慮到任意交叉一定可以交換成不交叉的情況，所以我們把圖變成樹，接下來就是一個經典問題，樹上無邊交最大匹配。做法如下：

• 設計 \(dp_{i,0/1}\) 表示到 \(i\) 還是否有點沒匹配，貪心的從下往上做，能匹配就匹配，這樣是對的，順便把答案記下來。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+10;
vector<int> e[N],u,d;
int n,m,k,flg[N],vis[N],f[N],lft[N],dep[N];
vector<pii>ans;
void dfs(int u,int fa){
    vis[u]=1;f[u]=fa;dep[u]=dep[fa]+1;
    int lst=0;for(auto v:e[u]){
        if(vis[v]) continue;
        dfs(v,u);
        if(lft[v]){
            if(lst) ans.pb({lst,lft[v]}),lst=0;
            else lst=lft[v];
        }
    }if(flg[u]){
        if(lst) ans.pb({lst,u}),lst=0;
        else lst=u;
    }lft[u]=lst;
}
void gs(int x,int y){
    u.clear(),d.clear();
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]){
        u.push_back(x);x=f[x];
    }while(x!=y){
        u.pb(x),d.pb(y);
        x=f[x],y=f[y];
    }cout<<u.size()+d.size()+1<<" ";
    for(auto i:u) cout<<i<<" ";
    cout<<x<<" ";
    reverse(d.begin(),d.end());
    for(auto i:d) cout<<i<<" ";
    cout<<'\n';
}
signed main(){
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    rep(i,1,m){
        int u,v;cin>>u>>v;
        e[u].pb(v),e[v].pb(u);
    }rep(i,1,k){
        int x;cin>>x;
        flg[x]=1;
    }rep(i,1,n){
        if(vis[i])continue;
        dfs(i,0);
    }cout<<ans.size()<<'\n';
    for(auto i:ans){
        gs(i.fi,i.se);
    }return 0;
}

t3

題面

這東西在線不太能做，考慮離線掃描。掃描右端點 \(r\)，我們對每個位置 \(l\) 維護一個 \(p_l\) 表示最小的 \(p\) 使得 \([l,p]\) 是 \([l,r]\) 的合法子區間。

考慮如何維護 \(p_l\)。考慮新加入的右端點 \(r\)，加入一個數 \(a_r\)，上一次出現的位置為 \(lst_{a_r}=c\)，那么對于 \(c\) 和以前的位置是沒有影響的；而 \((c,r]\) 這段區間由于沒有 \(a_r\) 這個數，那么直接覆蓋為 \(r\) 即可?？梢杂镁€段樹維護。

考慮查詢，當前掃描到 \(r\)，詢問 \([l,r]\)。令 \(q_l\) 為最大的 \(q\) 使得 \([q,r]\) 合法，那么不難發現答案就是 \(\min\limits_{i\in[l,q_l]}\{p_i-i\}\)。這東西可以線段樹上二分，但是多帶了一半常數，估計過不去。

有一個很妙的并查集做法，學會了。

就是要對每個 \(l\) 維護 \(q_l\)，當插入 \(r\) 前已經有一個 \(lst_{a_r}\) 了，那么直接將 \(q_{lst_{a_r}}\to lst_{a_r}+1\) 即可。因為 \(q_l\) 相當于 \([l,r]\) 所有出現過的數的 \(lst\) 取 \(\min\)， \(lst_{a_r}\) 這個位置可以替換成 \(r\) 了，所以直接求 \(q_{lst_{a_r}+1}\) 即可。

我代碼太糞了，過不了這邊的數據，但是比賽那邊能過。

我的做法就是發現這個 \(q_l\) 實際上就是反著跑的 \(q\) 數組，所以我做了兩遍掃描線。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define pb push_back
#define lbt(x) (x&(-x))
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e6+10;
int n,m,q,k,T,a[N],t[N<<2],laz[N<<2];
int lst[N],c[N],nxt[N],d[N],ans[N];
vector<pii> p1[N],p2[N];
void pushup(int p){
	t[p]=min(t[ls],t[rs]);
}
void pushdown(int p,int l,int r){
	if(laz[p]==0) return;
	int k=laz[p];laz[p]=0;
	int mid=l+r>>1;
	t[ls]=k-mid;t[rs]=k-r;
	laz[ls]=laz[rs]=k;
}
void build1(int p,int l,int r){
	laz[p]=0;
	if(l==r){
		t[p]=n+1-l;return;
	}int mid=l+r>>1;
	build1(ls,l,mid);build1(rs,mid+1,r);
	pushup(p);
} 
void build2(int p,int l,int r){
	laz[p]=0;
	if(l==r){
		t[p]=-l;return;
	}int mid=l+r>>1;
	build2(ls,l,mid);build2(rs,mid+1,r);
	pushup(p);
} 
void upd(int p,int l,int r,int x,int y,int k){
	if(x<=l&&r<=y){
		t[p]=k-r;laz[p]=k;return;
	}int mid=l+r>>1;pushdown(p,l,r);
	if(x<=mid) upd(ls,l,mid,x,y,k);
	if(y>mid) upd(rs,mid+1,r,x,y,k);
	pushup(p);
}
int query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return t[p];
	}int mid=l+r>>1,res=INT_MAX;pushdown(p,l,r);
	if(x<=mid) res=min(res,query(ls,l,mid,x,y));
	if(y>mid) res=min(res,query(rs,mid+1,r,x,y));
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n;
    rep(i,1,n){
		cin>>a[i];lst[i]=c[a[i]];
		c[a[i]]=i;
	}rep(i,1,n) c[i]=n+1;
	per(i,n,1){
		nxt[i]=c[a[i]];
		c[a[i]]=i;
	}cin>>q;rep(i,1,q){
		int l,r;cin>>l>>r;
		p1[l].pb({r,i});p2[r].pb({l,i});
	}build1(1,1,n);
	per(i,n,1){
		upd(1,1,n,i,nxt[i]-1,i);
		for(auto t:p1[i]){
			int v=t.fi,id=t.se;
			d[id]=query(1,1,n,v,v)+v;
		}
	}build2(1,1,n);
	rep(i,1,n){
		upd(1,1,n,lst[i]+1,i,i);
		for(auto t:p2[i]){
			int v=t.fi,id=t.se;
			ans[id]=query(1,1,n,v,d[id])+1;
		}
	}rep(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}

t4

題面

顯然這題的答案滿足可二分性。

問題變成判斷是否存在一種方案，能使所有的葉子節點間的路徑費用小于等于一個定值 \(Value\) 且滿足題目中的限制。

發現一條邊不能經過兩次，顯然當我們進入一棵子樹時，必須要把子樹中所有的葉子節點全部遍歷后才能離開這棵子樹。

考慮判定性相關的 dp ，設 \(f_u(a,b)\) 表示當前節點 \(u\) 的子樹中是否存在一種方案：

• 從 \(u\) 出發到第一個葉子節點的路徑長度為 \(a\) ，從 \(u\) 出發到最后一個葉子節點的路徑長度為 \(b\)。

• 所有的路徑長度都不大于 \(Value\)。

• 在滿足所有以上限制的情況下，遍歷完 \(u\) 的整棵子樹。

對于這個 dp，可以考慮從 \(u\) 的左兒子和右兒子處進行轉移。

設 \(u\) 的左兒子為 \(lson_u\)，\(u\) 到左兒子的距離為 \(val_l\)，右兒子為 \(rson_u\) ，\(u\) 到右兒子的距離為 \(val_r\)。

有轉移式 \(f_u(a,b)=f_{lson_u}(a,i) \ \& \ f_{rson_u}(j,b) \ (i+j+val_l+val_r \le Value)\)

（對轉移式的解釋：從 \(u\) 出發到 \(lson_u\) 的第一個葉子節點，從該葉子節點到 \(lson_u\) 的最后一個葉子節點，從該葉子節點出發到 \(rson_u\) 的第一個葉子節點）

復雜度爆炸，考慮怎么優化這個 dp。

發現當 \(f_u(a_1,b_1)\) 和 \(f_u(a_2,b_2)\) 滿足 \(a_1\le a_2,b_1\le b_2\) 的時候，\(f_u(a_2,b_2)\) 是顯然不必要存在的。

考慮把 \(f_u\) 的狀態按 \(a\) 排序，根據上面的性質，排序后的 \(f_u\) 狀態在 \(b\) 遞減時是最少的。

顯然，對于每一個 \(f_{lson_u}(a_1,b_1)\) 都只需要考慮一個令 \(b_2\) 最小且滿足轉移式的 \(f_{rson_u}(a_2,b_2)\)。所以，每一個 \(f_{lson_u}\) 對應的狀態只需要與一個對應的 \(f_{rson_u}\) 的狀態轉移到 \(f_u\) 上，每次轉移增加的狀態數是 \(2\times \min(x,y)\) （\(x\) 是 \(f_{lson_u}\) 的狀態數，\(y\) 是 \(f_{rson_u}\) 的狀態數，注意 \(lson_u\) 和 \(rson_u\) 是可以反過來再轉移一次的），顯然狀態總數是 \(n \log n\) 的。

至于如何找到這個最小的 \(b_2\)，直接 two-points 即可。（至于為什么可以 two-points 是因為 \(a\) 遞增而 \(b\) 遞減）

時間復雜度 \(\mathcal{O}(n \log^2 n \log v)\)，其中 \(v\) 是二分答案中 \(r\) 的權值。

代碼如下：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<ll,ll>
#define fi first
#define se second
typedef long long ll;
const int N=2e5+5;
int ch[N][2],val[N][2];
vector<pii> v[N];
void dfs(int x,ll Value){
	v[x].clear();
	if(!ch[x][0]) return (void)(v[x].pb({0,0}));
	for(int i=0;i<2;++i)
		if(ch[x][i]) dfs(ch[x][i],Value);
	vector<pii> vec;
	for(int dy=0;dy<2;++dy){
		int ls=ch[x][0^dy],rs=ch[x][1^dy];
		ll tmp=Value-val[x][0]-val[x][1];
		for(int i=0,j=0;i<v[ls].size();++i){
			while(j+1<v[rs].size() && v[rs][j+1].fi<=tmp-v[ls][i].se) ++j;
			if(j>=v[rs].size() || v[rs][j].fi>tmp-v[ls][i].se) continue;
			vec.pb({v[ls][i].fi+val[x][0^dy],v[rs][j].se+val[x][1^dy]});
		}
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();++i){
		if(!v[x].empty() && v[x].back().se<=vec[i].se) continue;
		v[x].pb(vec[i]);
	}
}
bool check(ll mid){
	dfs(1,mid);
	return v[1].size()>=1;
}
signed main(){
	int n,fa,Val;
	cin>>n;
	ll l=0,r=0,ans=0,mid;
	for(int i=2;i<=n;++i){
		cin>>fa>>Val;
		r+=Val;
		if(ch[fa][0]) ch[fa][1]=i,val[fa][1]=Val;
		else ch[fa][0]=i,val[fa][0]=Val;
	}
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

rabbit_mygo 10.25

t1

bfs 跑出來第一天的答案，剩下每個點 \(O(1)\) 計算，注意特判即可。

t2

挺好一道題，第三個包確實難，交互庫怎么要用主席樹實現。

對于 \(1≤n≤10^3,1≤Q≤10^4\)：

應該是 \(n\log n\) 左右的東西?？紤]從左到右掃，那么到這個點時，前面不考慮這個點的匹配有多少個顏色已經處理好了，那么二分找出第一個顏色相同的就可以了，代碼實現有點難。

對于 \(1≤n,Q≤10^3\)，保證顏色段連續：

水包，考慮雙指針。

\(1≤n≤10^4,1≤Q≤2\times 10^4\)，保證至多有 \(4\) 種不同的顏色 或者 至少也有 \(n?1\) 種不同的顏色：

如果均異色隨便做，如果有兩個同色就直接二分存在點同色的最大左端點和最小右端點，然后就可以得出同色點對，至多詢問 \(2\log? n\) 次，可以通過，考慮第一種情況。

考慮維護 \(lst_{col}\)，然后你分類討論，可以證明訪問數不超過 \(2n\)。

t3

OI 一定不能考純數學題！

給定常數 \(T\) 和 \(n\) 個點的 \(t_i\)，其坐標為 \((\cos(\dfrac{2 \pi t_i}{T}),\sin(\dfrac{2 \pi t_i}{T}))\)，求任取三點得到的三角形的內心期望橫坐標和縱坐標，\(t_i\) 嚴格不同。

記 \(a_i = \dfrac{2 \pi t_i}{T}\)，然后排序。

不妨設 \(a_1 \lt a_2 \lt a_3\)，則有內心橫坐標為 \(\cos(t_1+t_2)+\cos(t_2+t_3)-\cos(t_1+t_3)\)，縱坐標為 \(\sin(t_1+t_2)+\sin(t_2+t_3)-\sin(t_1+t_3)\)。
我學過都不知道咋來的。但是大概是用角平分線的性質暴算出來的。

然后用和角公式直接加起來維護一些東西就好了，用線段樹區間加。

t4

詐騙題，就是刪掉最小的點，使其不存在 \((奇,偶) \to (偶，偶) \to (偶，奇) \to (奇，奇)\) 這樣的路徑，考慮拆點然后按照這樣的路徑連邊。然后將源點向 \((奇，偶)\) 的點連正無窮的邊，將 \((奇，奇)\) 點的向匯點連正無窮的邊，對于滿足上述路徑的點對將他們的出點和入點對應連正無窮的邊，跑最大流即可。

P4899

最開始讀錯題了，以為還有一個部分點不可到達的限制，倒閉了。

讀對之后又被自己唐唐的重構樹理解做局了。

題面

肯定是做兩個重構樹，一個最大生成樹，一個最小生成樹。

考慮有什么性質，就是你可以從 \(s\) 倍增找到第一步的限制點，那么這個子樹里的點都是 \(s\) 可以到達的。\(t\) 同理。

所以你找的就是兩個子樹之間有沒有交。考慮 \(dfs\) 序。滿足如下條件：

考慮在線離線都是二維數點，直接用 bit 維護就好啦。

P7424

題面

挺板子的，想到對于每個木板單獨計算貢獻接下來就會想到整體二分/樹套樹。用 BIT 做前綴和就好了。