热身赛总结题解

大四都 發表於 2025-11-12 14:41:00

<h1 id="1-旅行计划">1. 旅行计划</h1>
<h2 id="赛时思路">赛时思路</h2>
因为目标是：求出一直向东以城市 $i$ 为终点最多能够游览多少个城市，我进行逆向思维，转换题意，将目标改成：以城市 $i$ 为起点一直向西最多能够游览多少个城市，再看题目的数据范围：$n \le 10^5 $，因此便直接用 dfs 进行搜索，最后 TLE 了4个点 QwQ 。
<h2 id="改进思路">改进思路</h2>
因为题目中说图中没有环，因此我们可以通过 DP 解决此题，所以我们就可以通过记忆化递归防止进行无效的 dfs 。
<h2 id="ac代码">AC代码</h2>
<details>
<summary>点开有惊喜</summary>
<pre><code>#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,x,y,dp;
vector<ll>t;
ll dfs(ll x,ll val){
if(!t.size()) return val;
ll mx=0;
for(auto y:t){
if(!dp) dp=dfs(y,val);
mx=max(mx,dp);
}
return mx+1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
t.push_back(x);
}
for(int i=1;i<=n;i++){
ll mx=0;
mx=dfs(i,1);
cout<<mx<<"\n";
}
return 0;
}
</code></pre>
</details>
<hr>
<h1 id="2-鬼子进村">2. 鬼子进村</h1>
<h2 id="赛时思路-1">赛时思路</h2>
本题有 3 个最本质的操作：单点修改和查询加区间查询，因此我考虑使用线段树解决此题。 
单点修改和查询比较简单，只需遍历到叶子节点，修改或查询其信息，因此区间查询便十分重要，以至于此题没有做出来 QwQ 。
<h2 id="改进思路-1">改进思路</h2>
略微借鉴本题题解便会发现，我们只需找出此节点右边第一个"被摧毁房子"的位置 $r$ 和左边第一个"被摧毁房子"的位置 $l$ ，而士兵可移动的距离则是 $r-l+1$。 
那如何判断此区间是否存在 $l$ 或 $r$ ，我们只需要统计区间长度 $len$ 以及区间未被摧毁房子的个数 $sum$ , 看 $sum$ 是否比 $len$ 小，如果是，则此区间存在 $l$ 或 $r$ 的位置；相应的，如果都没有被摧毁的房子则返回 -1（ $l$ ）或 $n+$1（ $r$ ）。
<h2 id="注意">注意</h2>
<ul>
<li>在寻找 $l$ 和 $r$ 之前，要先判断这个"房子"是否"被摧毁"，否则答案会出错；</li>
<li>在进行修改之前，需要进行建树，统计每个节点的 $len$ , 并将所有 $sum$ 赋值为 1 ，方便后面进行修改以及查询；</li>
</ul>
<h2 id="ac代码-1">AC代码</h2>
<details>
<summary>点开有惊喜</summary>
<pre><code>
#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;
ll n,m,x,zh,cnt;
char ch;
void build(ll x,ll l,ll r){
t.len=r-l+1;
if(l==r){
t.sum=1;
return;
}
ll mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
t.sum=t.sum+t.sum;
}
void cxa(ll x,ll l,ll r,ll mb,ll k){
if(l==r){
t.len=1;
t.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.len=t.len+t.len;
t.sum=t.sum+t.sum;
}
ll check(ll x,ll l,ll r,ll pos){
if(l==r)
return t.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.sum==t.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.sum==t.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,0);
}
return 0;
}
</code></pre>
</details>
<hr>
<h1 id="3-radio-transmission-无线传输">3. Radio Transmission 无线传输</h1>
<h2 id="赛时思路-2">赛时思路</h2>
题目中字符串 $s_1$ 是由某个子串 $s_2$ 重复至少 2 次形成的。我们需要找到$s_2$ 的最短长度，本质是寻找 $s_1$ 中能构成其重复结构的最小单元长度。因此我便认为此题所用到的算法应包括 KMP ，可惜后来没时间继续想了 QwQ 。
<h2 id="改进思路-2">改进思路</h2>
问题的本质确实已经被我想到了，可还有几点不全； 
在 KMP 中，我们常定义 nex 表示最长前缀及后缀的子串长度。
<h3 id="答案推导">答案推导</h3>
若字符串 $t$ 是由子串 $s$ 重复 $k$ 次构成（ $k\ge 2$ ），则：
<ul>
<li>总长度 $len = k \times len(s)$ ；</li>
<li>$nex$ 本质是 $s$ 重复 $k-1$次的长度，即 $nex = (k-1) \times len(s)$ ；</li>
<li>两式相减得：$len - nex = len(s)$ ，即最短重复子串 $s$ 的长度。</li>
</ul>
<h2 id="ac代码-2">AC代码</h2>
<details>
<summary>点开有惊喜</summary>
<pre><code>#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5;
char t;
ll nex,len;
int main(){
cin>>len>>t+1;
nex=0;
for(int i=2,j=0;i<=len;i++){
while(j&&t!=t) j=nex;
if(t==t) j++;
nex=j;
}
cout<<len-nex;
return 0;
}
</code></pre>
</details>
<hr>
<h1 id="4木棍分割">4.木棍分割</h1>
<h2 id="前言">前言</h2>
没有赛时思路,考场上甚至没有来得及看此题 QwQ 。
<h2 id="思路">思路</h2>
本题主要由两个问题组成：最长段的最小长度和组成此长度的方案数量，而且前者答案还为后者的限定条件的这么一个问题，当我们找到问题的根本后，就要去思考解决此类问题的算法有哪些，因此我们确定了此题我们的算法：二分加 DP （"最长的最短"肯定可以直接想到二分，而"方案数量则一般用 DP 解决"）。
<h3 id="问题一二分">问题一：二分</h3>
因为最长的最短长度具有单调性（当长度 $x$ 可以，则 $x+1$ ~ $\infty$之间的答案也都能成立），所以我们可以二分长度，而 check 函数也比较简单，能不分割就不分割，看最后分割次数是否大于 $m$ 即可。 
！注意
<ul>
<li>$l$的初始值为 a 的最大值，而 $r$ 的值则为 $\sum$ a，这样可以防止一些没用的判断，降低点时间复杂度（毕竟这题卡常）。</li>
<li>时间复杂度：$O(n\ log\ S)$，其中S是所有木棍的总长度</li>
</ul>
<h3 id="问题二dp">问题二：DP</h3>
状态申明
<ul>
<li>$dp$：前i根木棍分割成若干段，每段长度不超过 ans 的方案数</li>
</ul>
状态转移方程
<ul>
<li>$dp = sum( dp )$，其中j满足 $a + a +...+ a$ $\le ans$</li>
<li>即所有满足最后一段长度不超过ans的j的位置</li>
</ul>
前缀和优化
<ul>
<li>计算前缀和数组 $s$ ，其中 $s = dp + dp +...+ dp$</li>
<li>则 $dp = s - s$，其中 $left$ 是满足 $sum \le ans $ 的最小 $j$</li>
</ul>
滑动窗口确定 $left$
<ul>
<li>使用双指针维护 $left$ 的位置，避免重复计算</li>
</ul>
遍历顺序
<ul>
<li>外层循环：遍历段数 $j$ ，从 $1$ 到 $m+1$（需要计算不同段数下的方案数，并累加得到总方案数）</li>
<li>内层循环：遍历前 $i$ 根木棍，从 $1$ 到 $n$（按顺序计算每个状态 $dp$ ，确保在计算 $dp$ 时，所有依赖的状态$dp$ 已经计算完成）</li>
</ul>
边界条件
<ul>
<li>$s=1$，表示空分割方案数为 $1$</li>
<li>当 $i=0$ 时，$dp=1$ ，表示前 $0$ 根木棍的分割方案数为 $1$</li>
</ul>
最终答案： 
$dan=\sum_{j=1}^{m+1}dp$ 
$dan\mod 10^4+7$
<h2 id="ac代码-3">AC代码</h2>
<details>
<summary>点开有惊喜</summary>
<pre><code>#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll Mod=1e4+7;
ll n,m,a,l,r,ans;
ll dp,s,lef,nw,dan;
bool check(ll x){
ll cnt=1,len=0;
for(int i=1;i<=n;i++){
if(len+a>x)cnt++,len=a;
else len+=a;
if(cnt>m+1)return 0;
}
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a;
l=max(l,a);
r+=a;
}
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+=a;
for(int i=1;i<=n;i++){
while(a-a>ans) nw++;
lef=nw;
}
for(int i=0;i<=n;i++)
s=1;
for(int j=1;j<=m+1;j++){
for(int i=1;i<=n;i++)
dp=(s-s-1]+Mod)%Mod;
s=0;
for(int i=1;i<=n;i++)
s=(s+dp)%Mod;
dan=(dan+dp)%Mod;
}
cout<<dan;
return 0;
}
</code></pre>
</details> 
来源：https://www.cnblogs.com/chenxuan11/p/19128778

頁: [1]

琼殿技术论坛's Archiver

热身赛总结 题解

热身赛总结题解