热身赛总结 题解

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";}elsecxa(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;
}