NFLS 训练总结 2（updating）-526互联

前言

接上周。

Day 6

总体情况

1000+1200+1400+1700+1800+1408+0+300=8808，rk83

大寄，为什么他们分都那么高啊！

T1

从 T1 就开始卡。

简单的贪心，买票最少就是每个大人都尽量带孩子，而最多就是所有孩子都由一个大人带。

如果没有大人只有孩子，就是 “Impossible”。

然后有人 Impossible 的 I 没有大写，被 WA 懵了。

T2

勉强做的还算顺的一道题。

首先四个人的一辆车，然后三个人的尽量和一个人的匹配，配不完只能单独，两个人的两两匹配，若有剩余则继续和一个人的匹配。

T3

这题就比较简单了。

按左端点排序，一个一个合并，若新加的区间与之前的无交，就算上之前合并的贡献，然后继续合并，最后加上最后一段区间的贡献。

sort(a+1,a+n+1);
l=a[1].s,r=a[1].t;
for(int i=2;i<=n;++i){
	if(a[i].s<=r) r=max(r,a[i].t);
	else{
		ans+=(r-l+1); l=a[i].s,r=a[i].t;
	}
}
ans+=(r-l+1);

T4

卡在这题上了，之前一直想了一个错误的贪心思路，想了半天。

后来才发现可以 dp。

设 \(dp[i][0/1]\) 表示将 \(i\) 位之前的数都变成 \(A/B\) 的最小代价，转移即可。

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n,l,r,ans=0,dp[maxn][2]; char s[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>s[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=dp[0][1]=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='A'){
			dp[i][0]=min(dp[i-1][0],dp[i-1][1]+2);
			dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1);
		}
		else{
			dp[i][1]=min(dp[i-1][1],dp[i-1][0]+2);
			dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);
		}
	}
	printf("%d\n",dp[n][0]);
	return 0;
}

T5

有一点用到 prim 的思想，每个点以最小的代价接到树里面，但是用 kruskal 实现。

可以发现要让每个点接到树里面的边尽量小，所以每个点与和自己某个坐标最近的点连边，一定比与此坐标离它更远的点连这个坐标的距离，要更优。（感性理解

并且这样可以保证连通。

所以将三个坐标分别排序，然后相邻的点连权值为这个坐标的差的边，一共 \(3\cdot(n-1)\) 条边，用 kruskal 跑最小生成树。



#include<bits/stdc++.h>
#define maxn 100010
#define int long long
using namespace std;
struct planet{int x,y,z,id;}a[maxn];
struct edge{int u,v,w;}eg[maxn*10];
bool operator <(edge a,edge b){return a.w<b.w;}
bool cmp1(planet a,planet b){return a.x<b.x;}
bool cmp2(planet a,planet b){return a.y<b.y;}
bool cmp3(planet a,planet b){return a.z<b.z;}
int n,m,x,y,f[maxn],cnt=0,ans=0;
int find(int x){
	if(x!=f[x]) return f[x]=find(f[x]);
	return x;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
		a[i].id=i; f[i]=i;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=2;i<=n;++i)
		eg[++m]=(edge){a[i-1].id,a[i].id,a[i].x-a[i-1].x};
	sort(a+1,a+n+1,cmp2);
	for(int i=2;i<=n;++i)
		eg[++m]=(edge){a[i-1].id,a[i].id,a[i].y-a[i-1].y};
	sort(a+1,a+n+1,cmp3);
	for(int i=2;i<=n;++i)
		eg[++m]=(edge){a[i-1].id,a[i].id,a[i].z-a[i-1].z};
	sort(eg+1,eg+m+1);
	for(int i=1;i<=m;++i){
		x=find(eg[i].u),y=find(eg[i].v);
		if(x==y) continue;
		ans+=eg[i].w; f[x]=y;
		++cnt; if(cnt==n-1) break;
	}
	printf("%lld\n",ans);
	return 0;
}

T6

把原序列翻转，将问题转化为求原序列与翻转序列 LCIS。

求 LCIS 的时候用一些处理，就是不是同一个数的 \(+2\)，其余 \(+1\)，求出来的就是此题要的最长回文的，先上升再下降的，子序列。

设 \(dp_{i,j}\) 表示当前考虑第一个序列 \(i\) 个，以第二个序列 \(j\) 结尾的最长公共上升子序列的长度（此题特殊的 \(\times 2\)）

核心代码如下（\(a\) 是原序列，\(b\) 是翻转后的序列）：

for(int i=1;i<=n;++i){
		int mx=0;
		for(int j=1;j<=n-i+1;++j){
			if(a[i]==b[j]) dp[j]=max(dp[j],mx+1+(j!=n-i+1));
			else if(a[i]>b[j]) mx=max(mx,dp[j]);
			ans=max(ans,dp[j]);
		}
	}