发布于

NOIP2018 赛道修建

一道树形DP裸题。
因为部分分给得很足，所以我在考场上先打了一堆部分分，建了5个命名空间。
然后在打二叉树的部分分的时候想到了正解。（虽然可能二分写挂了）
题目大意：给定一棵带权树，将它的一部分拆成\(m\)条链，使得权值最短的链的权值最大。
最小的求最大，当然满足无后效性，所以我们考虑二分答案。
然后我们考虑检验。首先，很容易可以发现答案具有无后效性。换句话说，每个子树在计算出它对答案的贡献之后，就只需要计算出它对父节点的贡献。
这是因为，每一个父节点，它能使用的仅有子树的一条链，而不是整个子树的信息。
故而，我们只需要「可以提供给父节点的那条链」的值更新上去即可。我们用\(f_{x}\)表达这个上传的值。
并且，对于每棵子树是可以贪心地处理的——如果一棵子树中的一条链可以和另一条链组成一条合法的链，那就没必要把它上传了。
这是因为，如果不上传，一定可以对答案产生1的贡献；如果上传了，仅仅是有可能对答案产生1的贡献。
那么我们对每个子树分别考虑。这就转化为了一个新的问题：
「对于一个长度为\(n\)的序列，取出其中尽可能多的数对或数，使得数对的和或数的值大于给定值，并且在有遗留数的情况下使得遗留的数的值最大。」
这个问题要怎么做呢？将它们从小到大排序，那么对于大于给定值的数，单独选取是更优的。
然后处理剩下来的数。用双指针做。
如果右指针的数可以与左指针指的数组成合法数对就把右指针推入栈中，直到没有合法的右指针，就考虑栈中是否为空。
如果不为空就说明存在一个可以和左指针匹配的数，那么就将答案加一，否则左指针就找不到数和它匹配了，那么就用它来更新\(f{x}\)左指针往右推。一直到序列为空。
然后，对于剩下的数，它们一定都可以组成合法数对——这是因为所有被推入栈中的数，都可以和一个比栈中最小数还要小的数组成合法数对。
那么，我们考虑剩下的数的数量的奇偶性。如果是奇数个，那么就计算答案之后用最大值来更新\(f_{x}\)。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
struct ee{
	int v;
	int w;
	int nxt;
}e[50005];
int h[50005],et=0;
int n,m;
inline void add(int u,int v,int w){
	e[++et]=(ee){v,w,h[u]};
	h[u]=et;
}
int MN,rt=0,f[50005],nw;
int st[50005],tp=0,st2[50005],tp2=0;
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
	}
	tp=0,tp2=0;
	for(int i=h[X];i;i=e[i].nxt){
		st[++tp]=f[e[i].v]+e[i].w;
	}
	std::sort(st+1,st+1+tp);
	while(tp&&st[tp]>=MN){
		--tp;
		++rt;
	}
	for(int i=1;i<=tp;++i){
		while(i<tp&&st[i]+st[tp]>=MN){
			st2[++tp2]=st[tp];
			--tp;
		}
		if(tp2){
			--tp2;
			++rt;
		}else{
			f[X]=st[i];
		}
	} 
	if(tp2&1){
		f[X]=st2[1];
	}
	rt+=(tp2>>1);
} 
inline bool chck(int X){
	std::memset(f,0,sizeof(f));
	MN=X;
	rt=0;
	dfs(1);
	if(rt>=m){
		return 1;
	}else{
		return 0;
	}
}
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		if(u>v){
			u^=v^=u^=v;
		}
		add(u,v,w);
	}
	int l=0,r=0x3f3f3f3f,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(chck(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

发布于

NOIP2018 货币系统

一道看起来像数论题的完全背包问题。
幸好我前一天没有仔细看数论，使得我想的是写暴力…要不然我可能真的会推一个小时的\(EXGCD\)或\(CRT\)或者高斯消元之类的东西。
总之是小凯的疑惑迷惑了我，以为是一道数论题，所以到最后我都以为自己写的是暴力。
结果发现其实是正解思路的，已经写到了正解的倒数第二步，随便一优化就通过了。
但是始终以为是打暴力。
果然还是太菜了。
题意简述：你有\(n\)个正整数，要求，确定一个最小的\(m\)，使得用\(m\)种正整数数能够表示的数集与题目给出数能够表示的数集的完全一致。
首先我们证明一个定理：答案的\(m\)个数一定是原有数的子集。
下面我们分两类考虑这个问题。
如果新的数可以被原有数表示，那么显然它是没有意义的。
如果新的数不能被原有数表示，那么显然它是不合法的。
那么我们只需要考虑删除哪些数即可。
我们发现，一个数需要删除，当且仅当它可以被其他数表达出来。
反证法：如果它不可被其他数表示的话，那么删除它以后它就无法表示出来了。
并且，我们可以发现，这个问题满足最优子结构：如果一个数可以被当前的系统表达出来，那么删除当前系统中任意一些可以被表达出来的数，都不会导致这个数不能被表达出来。
故而，先删哪个其实都不影响答案的正确性。
因此我们可以从小往大删（可能可以节省时间）
暴力地考虑，我们需要枚举值域内每一个已经可以被表达出来的数，然后将这个数加上当前数的任意倍（值域范围内）
这么做最坏可能是\(O(T*n*a^2)\)的。
考虑优化。用欧拉筛的思想，对于每一个数，我们只需要加上当前数的一倍即可。
因为，如果加上当前数的两倍的话，就会在之后再一次访问到这个数，这时候就产生了访问次数上的浪费。
这样做是\(O(T*n*a)\)。
那就做完了。

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<cstring>

int n,a[105];
bool usf[25005];
void init(){
	std::memset(usf,0,sizeof(usf));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	if(n==1){
		puts("1");
		return;
	}
	std::sort(a+1,a+1+n);
	int cnt=n;
	usf[0]=1;
	for(int i=1;i*a[1]<=25000;++i){
		usf[i*a[1]]=1;
	}
	for(int i=2;i<=n;++i){
		if(usf[a[i]]){
			a[i]=0;
			--cnt;
		}else{
			for(int j=0;j+a[i]<=25000;++j){
				if(!usf[j]){
					continue;
				}else{
					usf[j+a[i]]=1;
				}
			}
		}
	}
	printf("%d\n",cnt);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

 

发布于

NOIP2018 铺设道路

题意简述：
有一个序列，你可以一次将一个连续的段-1，但是不能让一个段变成0，求最小变成全零的操作次数。
方法有很多，个人的做法是差分以后把所有正值加起来。
没有细节，NOIP2013原题，完全就是为了送分。
感谢良心出题人。

#include<iostream>
#include<cstdio>
int n,a[100010],da[100010];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;++i){
		da[i]=a[i]-a[i-1];
	}
	int sm=0;
	for(int i=1;i<=n;++i){
		da[i]=std::max(da[i],0);
		sm+=da[i];
	}
	printf("%d\n",sm);
}
int main(){
	init();
	return 0;
}