本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-24 10:10:49

T1幸运字符:

考察点：字符串。入门题目。

方法： 两种情况： 找出连续的"vv",把第二个v替换为k即可。 找出连续的"KK",把第一个k替换为v即可。

有同学用了$o(n^2)$的算法。 参考代码：

#include<bits\/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

int n;
string s; 

int ans = -1;

char change(char ch){
	if(ch == 'V') return 'K';
	if(ch == 'K') return 'V';
}
int sum(){
	int res = 0;
	for(int i = 0; i < n-1; i ++){
		if(s[i] == 'V' && s[i+1] == 'K'){
			res++;
		}
	}
	return res;
}

signed main(void){
	cin >> n;
	cin >> s;
	int cnt = sum();
	ans = max(ans, cnt);
	for(int i = 0; i < n; i ++){
		s[i] = change(s[i]);
		int cnt = sum();
		ans = max(ans, cnt);
		s[i] = change(s[i]);
	}
	cout << ans << endl;
	return 0;
}

实际这个题目$o(n)$的算法即可以解决。 第一遍先找VK,找到的打标记。，第二遍找没打标记的连续“VV”或“KK”。

参考代码：

#include<bits\/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

int n,ans;
string a;


signed main(void){
	cin >> n;
	cin >> a;
	for(int i=0;i<n-1;i++)
		if(a[i]=='V'&&a[i+1]=='K')ans++,a[i]=a[i+1]='.';
	for(int i=0;i<n-1;i++){
		if(a[i]!='.'&&a[i]==a[i+1]){
			ans++;break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2 慢跑

考察点：模拟、数学。 在这个超长跑道上。起始坐标大、速度慢的会挡住起始坐标小速度快的人。

有同学贪心，先计算出T时刻后的最终速度。看坐标小的会不会被下一个坐标大的挡住，这样的方法是错的，因为下一个坐标大的速度也可能被前面的挡住，直接计算的最终坐标点并不是其真正的坐标点。例如新增加的第二组样例数据。

• 方法一：根据坐标的大小逆序来，记录逆序的最小真正终点。 参考代码：

\/\/ liqianzuo
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6;
long long n,t;
long long lo[N+3],loc,v;
int main()
{
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&loc,&v);
		lo[i]=loc+v*t;
	}
	long long ans=1;
	for(int i=n-1;i>0;i--)
	{
		if(lo[i-1]>=lo[i])
		{
			lo[i-1]=lo[i];
		}
		else
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

• 方法二： 也可以正序做，但是要把前面挡住的作为并查集来处理 例如A-B,B-C，那么他们就组成一个集合。 参考代码：

\/\/刘chenkai
#include<bits\/stdc++.h>
#include<unistd.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
const int N=1e5+1;
const ull INF=0x7f7f7f7f7f7f7f7f;
int fa[N];
bool b[N];
void init(int n)
{
	for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int i)
{
	return fa[i]==i?i:fa[i]=find(fa[i]);
}
void unionn(int i,int j)
{
	fa[find(i)]=find(j);
}
struct node
{
	ll x,v;
	bool operator < (node b)
	{
		return x<b.x;
	}
}a[N];
inline ll read()
{
	ll x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

int main()
{
	ll n=read(),T=read(),ans=0;
	ull num1=INF,num2=INF;
	init(n);
	for(int i=1;i<=n;i++)
	{
		a[i].x=read();a[i].v=read();
	}
	for(int i=n;i>=1;i--)
	{
		if(i%2==0) 
		{
			num2=a[i].x+a[i].v*T;
			num2=min(num1,num2);
			if(num2>=num1) unionn(i,i+1);
		}
		else 
		{
			num1=a[i].x+a[i].v*T;
			num1=min(num1,num2);
			if(num1>=num2) unionn(i,i+1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!b[find(i)])
		{
			b[find(i)]=1;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}	

T3 子段和

枚举子段区间$[l,r]$,再计算修改，有$o(n^3)$暴力算法。

不带修改：枚举子段区间$[l,r]$,利用前缀和，有$o(n^2)$算法。

最大子段和： 动态规划：当前点和前面的连接更优秀吗？更优秀和前面连，否则就自己开始。

• 设$f[i]$为以$i$为结束点的最大子段和长度。
• 那么 $f[i]=max(f[i-1]+a[i],a[i])$
• 最终的结果为： $ans=max(f[i]),1\leq i \leq n$;
• 时间复杂度为$o(n)$

最大子段和再变形，只有一次修改机会，调用$n$次最大子段和算法即可。

参考代码：

\/\/zhou zu hao
#include<bits\/stdc++.h>
using namespace std;
int n,a[100005],x,dp[1006],maxx=-0x3f3f3f3f;
signed main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int j=1;j<=n;j++){
		int kun=a[j];
		a[j]=x;
		for(int i=1;i<=n;i++){
			dp[i]=max(dp[i-1]+a[i],a[i]);
			maxx=max(maxx,dp[i]);
		} 
		a[j]=kun;
	} 
	cout<<maxx;
	return 0;
} 

• 如果数据范围更大，比如$n=10^5$怎么解决？

还有$o(n)的算法$ 设$dp[i][0/1]$为打当前点是否用了这次修改机会的最大值。

\\\liu xi
#include <bits\/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,begin,end) for(ll i=(begin);i<=(end);++i)
const ll maxn=1e6+5;
inline ll read(){
	ll f=0, k=1; char ch=getchar();
	while(ch<'0' || ch>'9'){ if(ch=='-') k=-1; ch=getchar();}
	while(ch>='0' && ch<='9'){ f=(f<<1)+(f<<3)+(ch-'0'); ch=getchar();}
	return f*k;
}
ll n, x, a[maxn], dp[maxn][2], ans;
int main(){
	n=read();
	x=read();
	FOR(i,1,n){
		a[i]=read();
	}
	dp[0][0]=0;
	FOR(i,1,n){
		dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
		dp[i][1]=max(dp[i-1][0]+x,max(dp[i-1][1]+a[i],x));
		ans=max(dp[i][1],ans);
	}
	cout << ans;
	
	return 0;
}

T4修栅栏

数学知识：

在长度确定的情况下，如何构成的长方形面积最大？

长宽越接近，面积越大？你会证明吗？

结论

按照长度排序，用长度尽可能接近的木棍来修栅栏。 要找相同数目的，数据范围$10^6$首选桶排序。

桶内数值为偶数的直接使用。 用不上的只能是奇数中的1个，就把这1个就削去1，放入下一个桶，因为木棍只可以被削1次，因此还要做一个削后木棍数量的标记，防止重复。

参考代码：

\/\/李jinhan
#include<iostream>
using namespace std;
long long a[1000050],mp1[1000050],mp2[1000050];
long long b[1000050],cnt=0;
int main()
{
	int n;
	long long maxx=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp1[a[i]]++;
		maxx=max(maxx,a[i]);
	}
	for(int i=maxx;i>=1;i--)
	{
		if((mp1[i]+mp2[i])%2==1&&mp1[i]>0) mp1[i]--,mp2[i-1]++;
		\/\/for(int j=1;j<=((mp1[i]+mp2[i])\/2);j++) b[++cnt]=i;
		while((mp1[i]+mp2[i])>=2)
		{
			if(mp1[i]) mp1[i]--;
			else mp2[i]--;
			if(mp1[i]) mp1[i]--;
			else mp2[i]--;
			b[++cnt]=i;
		}
	}
	long long ans=0;
	\/\/cout<<cnt<<'\n';
	\/\/for(int i=1;i<=cnt;i++) cout<<b[i]<<' ';
	for(int i=1;i<cnt;i+=2)
	{
		long long x=b[i];
		long long y=b[i+1];
		ans+=x*y;
		\/\/cout<<"ans+="<<x<<'*'<<y<<'\n';
	}
	cout<<ans;
	return 0;
}

T5 飞行

图论题目。最短路，而且是边权为固定值的最短路，可以用BFS。 可以跑从$n$到其他所有点的最短路。 然后枚举中转点计算。设其AB单独走到C点,再从C点到N点。