NFLS 训练总结 2（updating）

前言

接上周。

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]);
		}
	}

T7

来源：P5038

网络流，稍微有一点难的。

每次操作都是相邻的两个点，所以考虑对原图黑白染色，每次操作一定是一个黑点和一个白点。

设 \(sa,sb\) 表示所有黑点和白点的值的和，\(ca,cb\) 表示黑点和白点的个数。

设最终所有数都等于 \(x\)。

每次操作都是黑白点权值各加一，所以如果要操作成功，必须满足的条件是 \(ca\cdot x-sa=cb\cdot x-sb\)。

发现当 \(ca\neq cb\) 时，\(x\) 可以直接解出来。所以源点向黑点连权值为 \(x-a_{i,j}\) 的边，黑点和相邻的白点连权值为 \(\inf\) 的边，白点向汇点连权值为 \(x-a_{i,j}\) 的边，跑最大流。若最大流等于 \(ca\cdot x-sa\) 就可行。

当 \(ca=cb\) 时，由于白点黑点一样多，发现答案满足单调性，如果 \(x\) 可行，那么在用 \(\frac{n\cdot m}{2}\) 次操作每个点加一，所以 \(x+1\) 一定可行。二分 \(x\)，与上面用同样的判断即可。

注意一些细节，染色的时候黑色是 \((i+j)\equiv 1 \pmod 2\) 而不是 \(id_{i,j}\equiv 1 \pmod 2\)。还有这题是长方形，别把 \(m\) 写成 \(n\)。

还有！Dinic 板子不能写错！！！

CODE

一些有趣的逝：

某一些无聊的同学（包括我）在 AC 了这道题之后，开始比谁的常数小，经过一些开小数组，适当减小二分上界等玄学方法，我卡出了不开 O2 5.80s，开 O2 2.34s 的好成绩。

然而 hsy 随便交一发，就 2.29s，被吊打的很彻底。果然人傻常数大。

然后发现他不开全局 \(long long\) ，一些能用位运算的用位运算解决。

准备改变代码习惯，但全局 \(long long\) 不准备改。

其他

开学了，分在 7 班，4楼。

刚准备高兴，突然意识到机房在 5 楼，跑得更远。（恼

不管了，反正上学让我少爬一层就行了。

然后这几天感觉用脑超负荷，回家直接先睡个 \(30min\)。

困。