热身赛总结题解

赛时思路

因为目标是：求出一直向东以城市 $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;
}

赛时思路

本题有 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;
}

赛时思路

题目中字符串 $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;
}

前言

没有赛时思路,考场上甚至没有来得及看此题 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;
}

热身赛总结题解

赛时思路

改进思路

AC代码

赛时思路

改进思路

注意

AC代码

赛时思路

改进思路

答案推导

AC代码

前言

思路

问题一：二分

问题二：DP

AC代码

相关阅读

本类排行

相关标签

本类推荐

栏目热点

猜你喜欢

热身赛总结 题解

赛时思路

改进思路

AC代码

赛时思路

改进思路

注意

AC代码

赛时思路

改进思路

答案推导

AC代码

前言

思路

问题一：二分

问题二：DP

AC代码

相关阅读

本类排行

相关标签

本类推荐

栏目热点

猜你喜欢

热身赛总结题解