【csplus-s】20191009【01背包】【单调队列二分】【最小生成基环树】

woj4743

一眼水题。数据又小，预处理一下背包完事。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int s;
int sum[1003];
int dp[1003][1003];
int key[1003];
int main(){
//	freopen("sum.in","r",stdin);
//	freopen("sum.out","w",stdout);
	s=in;
	for(int i=2;i<=s;i++){
		sum[i]=1;
		for(int j=2;j<i;j++)
		if(i%j==0)sum[i]+=j;
		key[i]=sum[i];
	}
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=s;i++){
		for(int j=s;j>=i;j--){
			sum[j]=max(sum[j],sum[j-i]+key[i]);
		}
	}cout<<sum[s];

	return 0;
}

woj4744 最佳序列

看到L到R长度一眼滑动窗口型单调队列，代码简单，注意精度。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int n,l,r;
double a[1000003];
double L=1,R=1e9;
double eps=1e-7;
double sum[1000003];
deque<int> q;
bool check(double x){
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-x;
	while(!q.empty())q.pop_back();
	for(int i=l;i<=r-1;i++){
		while(!q.empty()&&sum[i]>sum[q.back()])q.pop_back();
		q.push_back(i);
	}
	for(int i=1;i<=n-l+1;i++){
		while(!q.empty()&&q.front()<i+l-1)q.pop_front();
		if(i+r-1<=n){
			while(!q.empty()&&sum[i+r-1]>sum[q.back()])q.pop_back();
			q.push_back(i+r-1);
		}
		if((sum[q.front()]-sum[i-1])>=0)return true;
	}return false;
}double mx;
int main(){
	//freopen("sequence.in","r",stdin);
	//freopen("sequence.out","w",stdout);
	n=in;l=in;r=in;
	for(int i=1;i<=n;i++)mx=max(mx,a[i]=in);R=mx;
	while(R-L>eps){
		double mid=(L+R)/2;
		if(check(mid))L=mid;
		else R=mid;
	}
	printf("%.4lf",L);
	return 0;
}

woj4097

不需要图了。

每个点入度为1。所以这是个基环树。所以这最小生成基环树。

在克鲁斯卡尔的基础上看一下有没有环，都有非法。

完了

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int n,m,fa[500003];
struct node{
	int u,v,w;
}que[500003];
bool cmp(node a,node b){
	return a.w<b.w;
}
int cnt;
long long ans;
int find(int x){
	if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
int is[500003];
int main(){
	n=in;m=in;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		que[i].u=in;que[i].v=in;que[i].w=in;
	}
	sort(que+1,que+m+1,cmp);
	for(int i=1;i<=m;i++){
		int u=que[i].u,v=que[i].v;
		int x=find(u),y=find(v);
		if(x==y){
			if(!is[x]){
				is[x]=1;ans+=que[i].w;++cnt;
			}
		}else{
			if(is[x]&&is[y])continue;
			fa[x]=y;is[y]=is[x]|is[y];
			ans+=que[i].w;++cnt;
		}
	}
	if(cnt!=n){
		cout<<"No";return 0;
	}
	cout<<ans;
	return 0;
}