1. 旅行計劃
賽時思路
因為目標是：求出一直向東以城市 \(i\) 為終點最多能夠遊覽多少個城市，我進行逆向思維，轉換題意，將目標改成：以城市 \(i\) 為起點一直向西最多能夠遊覽多少個城市，再看題目的數據範圍：$n \le 10^5 $，因此便直接用 dfs 進行搜索，最後 TLE 了4個點 QwQ 。
改進思路
因為題目中説圖中沒有環，因此我們可以通過 DP 解決此題，所以我們就可以通過記憶化遞歸防止進行無效的 dfs 。
AC代碼
點開有驚喜
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,x,y,dp[100005];
vector<ll>t[100005];
ll dfs(ll x,ll val){
if(!t[x].size()) return val;
ll mx=0;
for(auto y:t[x]){
if(!dp[y]) dp[y]=dfs(y,val);
mx=max(mx,dp[y]);
}
return mx+1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
t[y].push_back(x);
}
for(int i=1;i<=n;i++){
ll mx=0;
mx=dfs(i,1);
cout<<mx<<"\n";
}
return 0;
}
2. 鬼子進村
賽時思路
本題有 3 個最本質的操作：單點修改和查詢加區間查詢，因此我考慮使用線段樹解決此題。
單點修改和查詢比較簡單，只需遍歷到葉子節點，修改或查詢其信息，因此區間查詢便十分重要，以至於此題沒有做出來 QwQ 。
改進思路
略微借鑑本題題解便會發現，我們只需找出此節點右邊第一個"被摧毀房子"的位置 \(r\) 和左邊第一個"被摧毀房子"的位置 \(l\) ，而士兵可移動的距離則是 \(r-l+1\)。
那如何判斷此區間是否存在 \(l\) 或 \(r\) ，我們只需要統計區間長度 \(len\) 以及區間未被摧毀房子的個數 \(sum\) , 看 \(sum\) 是否比 \(len\) 小，如果是，則此區間存在 \(l\) 或 \(r\) 的位置；相應的，如果都沒有被摧毀的房子則返回 -1（ \(l\) ）或 $n+$1（ \(r\) ）。
注意
- 在尋找 \(l\) 和 \(r\) 之前，要先判斷這個"房子"是否"被摧毀"，否則答案會出錯；
- 在進行修改之前，需要進行建樹，統計每個節點的 \(len\) , 並將所有 \(sum\) 賦值為 1 ，方便後面進行修改以及查詢；
AC代碼
點開有驚喜
#include<bits/stdc++.h>
#define ll long long
#define lc x*2
#define rc x*2+1
using namespace std;
const ll N=1e5+5;
struct node{
ll sum,len;
}t[4*N];
ll n,m,x,zh[N],cnt;
char ch;
void build(ll x,ll l,ll r){
t[x].len=r-l+1;
if(l==r){
t[x].sum=1;
return;
}
ll mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
t[x].sum=t[lc].sum+t[rc].sum;
}
void cxa(ll x,ll l,ll r,ll mb,ll k){
if(l==r){
t[x].len=1;
t[x].sum=(k?0:1);
return;
}
ll mid=(l+r)/2;
if(mb<=mid)cxa(lc,l,mid,mb,k);
else cxa(rc,mid+1,r,mb,k);
t[x].len=t[lc].len+t[rc].len;
t[x].sum=t[lc].sum+t[rc].sum;
}
ll check(ll x,ll l,ll r,ll pos){
if(l==r)
return t[x].sum;
ll mid=(l+r)/2;
if(pos<=mid)return check(lc,l,mid,pos);
else return check(rc,mid+1,r,pos);
}
ll fidle(ll x,ll l,ll r,ll qr){
if(r<1||l>qr) return -1;
if(t[x].sum==t[x].len) return -1;
if(l==r) return l;
ll mid=(l+r)/2;
ll res=fidle(rc,mid+1,r,qr);
if(res!=-1) return res;
return fidle(lc,l,mid,qr);
}
ll fidrt(ll x,ll l,ll r,ll ql){
if(l>n||r<ql) return-1;
if(t[x].sum==t[x].len) return-1;
if(l==r) return l;
ll mid=(l+r)/2;
ll res=fidrt(lc,l,mid,ql);
if(res!=-1) return res;
return fidrt(rc,mid+1,r,ql);
}
int main(){
cin>>n>>m;
build(1,1,n);
while(m--){
cin>>ch;
if(ch=='D'){
cin>>x;
zh[++cnt]=x;
cxa(1,1,n,x,1);
}
else if(ch=='Q'){
cin>>x;
if(!check(1,1,n,x)){
cout<<"0\n";
continue;
}
ll le=fidle(1,1,n,x-1);
if(le==-1) le=0;
ll rt=fidrt(1,1,n,x+1);
if(rt==-1) rt=n+1;
cout<<rt-le-1<<"\n";
}
else
cxa(1,1,n,zh[cnt--],0);
}
return 0;
}
3. Radio Transmission 無線傳輸
賽時思路
題目中字符串 \(s_1\) 是由某個子串 \(s_2\) 重複至少 2 次形成的。我們需要找到 \(s_2\) 的最短長度，本質是尋找 \(s_1\) 中能構成其重複結構的最小單元長度。因此我便認為此題所用到的算法應包括 KMP ，可惜後來沒時間繼續想了 QwQ 。
改進思路
問題的本質確實已經被我想到了，可還有幾點不全；
在 KMP 中，我們常定義 nex[x] 表示最長前綴及後綴的子串長度。
答案推導
若字符串 \(t\) 是由子串 \(s\) 重複 \(k\) 次構成（ \(k\ge 2\) ），則：
- 總長度 \(len = k \times len(s)\) ；
- \(nex[len]\) 本質是 \(s\) 重複 \(k-1\)次的長度，即 \(nex[len] = (k-1) \times len(s)\) ；
- 兩式相減得：\(len - nex[len] = len(s)\) ，即最短重複子串 \(s\) 的長度。
AC代碼
點開有驚喜
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5;
char t[N];
ll nex[N],len;
int main(){
cin>>len>>t+1;
nex[1]=0;
for(int i=2,j=0;i<=len;i++){
while(j&&t[j+1]!=t[i]) j=nex[j];
if(t[j+1]==t[i]) j++;
nex[i]=j;
}
cout<<len-nex[len];
return 0;
}
4.木棍分割
前言
沒有賽時思路,考場上甚至沒有來得及看此題 QwQ 。
思路
本題主要由兩個問題組成：最長段的最小長度和組成此長度的方案數量，而且前者答案還為後者的限定條件的這麼一個問題，當我們找到問題的根本後，就要去思考解決此類問題的算法有哪些，因此我們確定了此題我們的算法：二分加 DP （"最長的最短"肯定可以直接想到二分，而"方案數量則一般用 DP 解決"）。
問題一：二分
因為最長的最短長度具有單調性（當長度 \(x\) 可以，則 \(x+1\) ~ \(\infty\)之間的答案也都能成立），所以我們可以二分長度，而 check 函數也比較簡單，能不分割就不分割，看最後分割次數是否大於 \(m\) 即可。
！注意
- \(l\)的初始值為 a[i] 的最大值，而 \(r\) 的值則為 \(\sum\) a[i]，這樣可以防止一些沒用的判斷，降低點時間複雜度（畢竟這題卡常）。
- 時間複雜度：\(O(n\ log\ S)\)，其中S是所有木棍的總長度
問題二：DP
狀態申明
- \(dp[i]\)：前i根木棍分割成若干段，每段長度不超過 ans 的方案數
狀態轉移方程
- \(dp[i] = sum( dp[j] )\)，其中j滿足 \(a[j+1] + a[j+2] +...+ a[i]\) \(\le ans\)
- 即所有滿足最後一段長度不超過ans的j的位置
前綴和優化
- 計算前綴和數組 \(s\) ，其中 \(s[i] = dp[0] + dp[1] +...+ dp[i]\)
- 則 \(dp[i] = s[i-1] - s[left-1]\)，其中 \(left\) 是滿足 $sum[j+1 ~ i] \le ans $ 的最小 \(j\)
滑動窗口確定 \(left\)
- 使用雙指針維護 \(left\) 的位置，避免重複計算
遍歷順序
- 外層循環：遍歷段數 \(j\) ，從 \(1\) 到 \(m+1\)（需要計算不同段數下的方案數，並累加得到總方案數）
- 內層循環：遍歷前 \(i\) 根木棍，從 \(1\) 到 \(n\)（按順序計算每個狀態 \(dp[i]\) ，確保在計算 \(dp[i]\) 時，所有依賴的狀態\(dp[j]\) 已經計算完成）
邊界條件
- \(s[0]=1\)，表示空分割方案數為 \(1\)
- 當 \(i=0\) 時，\(dp[0]=1\) ，表示前 \(0\) 根木棍的分割方案數為 \(1\)
最終答案：
\(dan=\sum_{j=1}^{m+1}dp[n]\)
\(dan\mod 10^4+7\)
AC代碼
點開有驚喜
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll Mod=1e4+7;
ll n,m,a[50005],l,r,ans;
ll dp[50005],s[50005],lef[50005],nw,dan;
bool check(ll x){
ll cnt=1,len=0;
for(int i=1;i<=n;i++){
if(len+a[i]>x)cnt++,len=a[i];
else len+=a[i];
if(cnt>m+1)return 0;
}
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
while(l<=r){
ll mid=(l+r)/2;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<" ";
for(int i=1;i<=n;i++)
a[i]+=a[i-1];
for(int i=1;i<=n;i++){
while(a[i]-a[nw]>ans) nw++;
lef[i]=nw;
}
for(int i=0;i<=n;i++)
s[i]=1;
for(int j=1;j<=m+1;j++){
for(int i=1;i<=n;i++)
dp[i]=(s[i-1]-s[lef[i]-1]+Mod)%Mod;
s[0]=0;
for(int i=1;i<=n;i++)
s[i]=(s[i-1]+dp[i])%Mod;
dan=(dan+dp[n])%Mod;
}
cout<<dan;
return 0;
}
