T1 决斗(duel) 100pts

# include<iostream>
using namespace std;

const int N=1e5+5;
int n,r,a[N],ans;

int main(){
	cin>>n;
	while(n--){
		cin>>r;
		a[r]++;
	}
	for(int i=1;i<=1e5;++i)
		if(a[i]>ans) ans=a[i];
	cout<<ans;
	return 0;
}

T2 超速检测(detect) 100pts

题面

【题目链接】

CSP-S 2024 T2

【题目大意】

有一条最高限速为 $V$，长为 $L$ 的主干道，上有 $m$ 个测速仪，其中第 $j$ 个到道路最南端的距离为 $p_j$，每个测速仪可以设置为开启或关闭。开启的测速仪可以对经过的车（包括恰好驶入和驶出主干道的车）进行测速，如果这辆车的瞬时速度超过了限速 $V$，那么这辆车被判定为超速。

有 $n$ 辆车，其中第 $i$ 辆车将在 $d_i$ 的位置驶入主干道，初速度为 $v_i$，加速度为 $a_i$。当车辆行驶到 $L$ 的位置或速度降为 $0$ 时，认为该车辆驶出主干道。

回答两个问题：

1. 当所有测速仪开启时，将会有多少辆车被判为超速？
2. 关闭尽可能多的测速仪，使得原本被判为超速的车仍然被判为超速。

【数据范围】

题目中出现的所有字母均为整数。

• $1 \le T \le 20$；
• $1 \le n,m \le 10^5$，$1 \le L \le 10^6$，$1 \le V \le 10^3$；
• $0 \le d_i <L$，$1 \le v_i \le 10^3$，$|a_i| \le 10^3$；
• $0 \le p_1<p_2< \cdots <p_m \le L$。

考场思路

1. 由于是匀加速直线运动，所以超速的区间一定是连续的，而且是可以被计算出来的（注意开闭）。
2. 我们可以把超速的区间变成测速仪的分布区间，例如对于样例 $1$，第四辆车的超速区间为 $[5,9)$，转换为测速仪的分布区间为 $[2,3]$。
3. 第二点的实现：首先对 $a_i$ 的正负分类讨论得到车的超速区间：
   • $a_i=0$：若 $v_i>V$，则超速区间为 $[d_i,L]$，否则不超速；
   • $a_i>0$：若 $v_i>V$，则超速区间为 $[d_i,L]$，否则车会在位移为 $x=\frac{v_i^2-V^2}{2a}$ 时达到限速 $V$，之后开始超速，此时超速区间为 $(d_i+x,L]$；
   • $a_i<0$：若 $v_i>V$，则车会在位移为 $x=\frac{v_i^2-V^2}{2a}$ 时降到限速 $V$，之后开始减速，此时超速区间为 $[d_i.d_i+x)$，否则不超速。
4. 在输入 $p_i$ 时，预处理主干道每个位置左侧和右侧距离它最近的测速仪，根据第三点讨论得到车的超速区间后，轻松解决第一小问，然后根据预处理的结果直接转化为测速仪的分布区间（具体流程可参见下方代码）。
5. 于是第二小问可以变成一个多区间的贪心问题：一条长线段上有若干条短线段（可以重叠也可以不完全覆盖长线段），请在长线段上选取尽可能少的点，使得每条短线段上（含端点）都有被选取的点。
6. 贪心的实现：按照右端点排序（从小到大），然后在尽可能少的右端点处开测速仪。

综上，这题有两点，一是计算每辆车的超速区间并转换成测速仪的分布区间，二是贪心。

（橙+橙=绿）

时间复杂度

对于每组数据：

1. 在输入 $p_i$ 时预处理主干道每个位置左侧和右侧距离它最近的测速仪，时间复杂度 $O(L+m)$。
2. 计算每辆车的超速区间，并将超速区间转化为测速仪分布区间，由于需要对 $a_i$ 的正负进行讨论，所以常数可能较大，时间复杂度 $O(kn)$（$k$ 是待定的常数）。
3. 然后进行贪心，需要对数据进行排序，时间复杂度 $O(n\log n)$。

总时间复杂度：$O(T(n\log n+m+L))$。

代码

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

const int N=1e5+2,L=1e6+2;
int t,n,m,l,V,tmp,ans1,ans2;
int d[N],v[N],a[N],p[N];
int lft[L],rgt[L]; //距离最近的测速仪编号 
int ld[N],rd[N]; //每辆车超速区间的左、右端点
int g[N]; //所有超速的车的编号
int id; //后面贪心用的 

bool cmp(int x,int y){
	return rd[x]<rd[y];
}

void solve(){
	//1.常规读入+初始化
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	ans1=ans2=0,id=-1;
	cin>>n>>m>>l>>V;
	for(int i=1;i<=n;++i)
		cin>>d[i]>>v[i]>>a[i];
	for(int i=1;i<=m;++i){
		cin>>p[i];
		lft[p[i]]=rgt[p[i]]=i; //这一行是2.的步骤，提前到这 
	}
	//2.预处理距离最近的测速仪编号 
	p[0]=0,p[m+1]=l+1;
	for(int i=0;i<=m;++i)
		for(int j=p[i]+1;j<p[i+1];++j)
			lft[j]=i,rgt[j]=i+1;
	//3.计算每辆车的超速区间（本题核心）
	for(int i=1;i<=n;++i){
		if(d[i]>p[m]) continue; //如果驶入的位置之后没有测速仪就不理它了 
		if(a[i]==0){
			if(v[i]>V){
				g[++ans1]=i;
				ld[i]=rgt[d[i]];
				rd[i]=m;
			} //一开始就超速 
		}
		else if(a[i]>0){
			if(v[i]>V){
				g[++ans1]=i;
				ld[i]=rgt[d[i]];
				rd[i]=m;
			} //一开始就超速
			else{
				//开始超速的地方是：d[i]+位移向下取整+1
				tmp=V*V-v[i]*v[i];
				tmp=d[i]+tmp/(2*a[i])+1;
				//对超速的位置判断 
				if(tmp<=p[m]){
					g[++ans1]=i;
					ld[i]=rgt[tmp];
					rd[i]=m;
				} 
			} //加速了一会儿才超速 
		}
		else{
			if(v[i]>V){
				//开始超速的地方是：d[i]+位移向上取整-1
				tmp=v[i]*v[i]-V*V;
				if(tmp%(-2*a[i])==0)
					tmp=d[i]+tmp/(-2*a[i])-1;
				else
					tmp=d[i]+tmp/(-2*a[i]);
				//对超速的位置判断
				if(tmp>=p[m]){
					g[++ans1]=i;
					ld[i]=rgt[d[i]];
					rd[i]=m;
				}
				else{
					ld[i]=rgt[d[i]];
					rd[i]=lft[tmp];
					//有可能出现超速区间恰好夹在两个测速仪之间的情况 
					if(rd[i]>=ld[i]) g[++ans1]=i;
				}
			} //一开始超速，后面减速 
		} 
	}
	//4.计算最少需要开启的测速仪数量（贪心）
	sort(g+1,g+1+ans1,cmp); //按照右端点从小到大排序
	for(int i=1;i<=ans1;++i)
		if(ld[g[i]]>id){
			id=rd[g[i]];
			++ans2;
		} //如果左端点没有被覆盖到，那就在右端点覆盖 
	cout<<ans1<<" "<<m-ans2<<endl;
}

int main(){
	cin>>t;
	while(t--) solve(); 
	return 0;
}

T3 染色(color) 50pts

# include<iostream>
# include<cstring>
using namespace std;

const int N=2002;
int t,n,a[N],ans;
int dp[N][N]; //到第i个数，最近的异色数 

void solve(){
	ans=0;
	memset(dp,0,sizeof(dp));
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=2;i<=n;++i){
		//1.和上一个数同色
		for(int j=0;j<=i-2;++j)
			dp[i][j]=max(dp[i][j],dp[i-1][j]+(a[i]==a[i-1]?a[i]:0));
		//2.和上一个数异色
		for(int j=0;j<=i-2;++j)
			dp[i][i-1]=max(dp[i][i-1],dp[i-1][j]+(a[i]==a[j]?a[i]:0));
	} 
	for(int i=0;i<n;++i) ans=max(ans,dp[n][i]);
	cout<<ans<<endl;
}

int main(){
	cin>>t;
	while(t--) solve(); 
	return 0;
}