文档章节

HZOI20190820模拟27题解

o
 osc_wws45aot
发布于 2019/08/21 13:55
字数 1423
阅读 14
收藏 0

精选30+云产品,助力企业轻松上云!>>>

A. 小奇挖矿2

显然的O(m)dp:$f[i]=max(f[i-4],f[i-7])+a[i]$,当然你要保证i,i-4,i-7都能到达

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
const int MAXN=1e7+5;
int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		f[b[i]]+=a[i];
	}
	for(int i=0;i<=3;i++) f[i]=-1;
	for(int i=5;i<=6;i++) f[i]=-1;
	ans=max(f[4],f[7]);
	for(int i=8;i<=m;i++){
		if(f[i-4]==-1&&f[i-7]==-1){
			f[i]=-1;
			continue;
		}
		f[i]+=max(f[i-4],f[i-7]);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

然后我们优化,我们发现如果两点之间的距离超过18就一定能到达,所以我们把距离压缩一下

具体为什么你需要做一下NOIP2017小凯的疑惑

然后就AC了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
const int MAXN=2e6+5;
int n,m,a[MAXN],b[MAXN],ans=0,f[MAXN];
struct node{
	int a,b;
	friend bool operator < (node x,node y){
		return x.b==y.b?x.a<y.a:x.b<y.b;
	}
}mine[MAXN];
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&mine[i].a,&mine[i].b);
	sort(mine+1,mine+n+1);
	for(int i=1;i<=n;i++){
		if(mine[i].b-mine[i-1].b>17)
			a[i]=mine[i].a,b[i]=b[i-1]+18;
		else a[i]=mine[i].a,b[i]=b[i-1]+(mine[i].b-mine[i-1].b);
	}
	for(int i=1;i<=n;i++) f[b[i]]+=a[i];
	for(int i=0;i<=3;i++) f[i]=-1;
	for(int i=5;i<=6;i++) f[i]=-1;
	m=b[n];
	ans=max(f[4],f[7]);
	for(int i=8;i<=m;i++){
		if(f[i-4]==-1&&f[i-7]==-1){
			f[i]=-1;
			continue;
		}
		f[i]+=max(f[i-4],f[i-7]);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

还有一种解决方法:

将所有矿物排序,f[i]为到第i个矿体能获得的最大原矿数,那么f[i]=max{f[j]}+x[i],其中,i-j满足能拆分成4和7。

这样dp需要n2的复杂度,但是我们发现,相距超过17的一定可达,那么不超过17的范围内暴力,超过17的取个最大值即可,复杂度O(n)

from skyh:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+10;
map<int,int> mp;
int n,m,ans,cnt;
int dp[N],mx[N];
bool ok[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0};//0 4 7 8 11 12 14 15 16  >17
inline int read(register int x=0,register char ch=getchar(),bool ff=0){
	while(!isdigit(ch)) ff=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return ff?-x:x;
}
struct node{
	int val,pos;
	friend bool operator < (const node &a,const node &b){
		return a.pos<b.pos;
	}
}k[N];
int main(){
	//freopen("x.in","r",stdin);
	//freopen("me.out","w",stdout);
	n=read(); m=read();
	for(int i=1,v,p,o;i<=n;++i){
		v=read(),p=read();
		if(!mp[p]) mp[p]=++cnt;
		o=mp[p]; k[o].pos=p; k[o].val+=v; 
	}
	sort(k+1,k+cnt+1);
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=cnt;++i){
		for(int j=i-1;~j;--j){
			if(k[i].pos-k[j].pos<=17&&ok[k[i].pos-k[j].pos]) dp[i]=max(dp[i],dp[j]+k[i].val);
			if(k[i].pos-k[j].pos>17){
				dp[i]=max(dp[i],mx[j]+k[i].val);
				break;
			}
		}
		ans=max(ans,dp[i]);
		mx[i]=max(mx[i-1],dp[i]);
	}
	printf("%d\n",ans);
	return 0;
}

B:小奇的矩阵(matrix)

平均数这玩意显然可拆:令$sum=\sum A_i$,$sqr=\sum A_{i}^{2}$

$Aavg=\frac{sum}{n+m-1}$

所以:原式=$(n+m-1)*sqr-sum^2$,推一下就能推出来

然后。。。我竟然去想了搜索!

正解dp:设$f[s][i][j]$表示到了点(i,j),总和为s时的最小sqr值

所以f[s][i][j]=min(f[s-a[i][j]][i][j-1]+a[i][j]*a[i][j],f[s-a[i][j]][i-1][j]+a[i][j]*a[i][j]);

然后就做出来了

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#define re register
using namespace std;
int t,n,m,a[35][35],ans,f[1805][35][35];
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(re int i=1;i<=n;i++)
			for(re int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		ans=inf;
		memset(f,0x3f,sizeof(f));
		f[a[1][1]][1][1]=a[1][1]*a[1][1];
		for(re int i=1;i<=n;i++){
			for(re int j=1;j<=m;j++)
				for(re int k=1;k<=1800;k++){
					if(k<a[i][j]) continue;
					f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i-1][j]+a[i][j]*a[i][j]);
					f[k][i][j]=min(f[k][i][j],f[k-a[i][j]][i][j-1]+a[i][j]*a[i][j]);
				}
		}
		for(re int k=1;k<=1800;k++){
			if(f[k][n][m]>=inf) continue;
			ans=min(ans,(n+m-1)*f[k][n][m]-k*k);
		}
		printf("%d\n",ans);
	}
	return 0;
}

C:小奇的仓库(warehouse)

美妙的换根dp

设f[i][j]表示i到其他点,后4位状态为j的路径数

f[x][0]=1

f[x][(j+w)%16]+=f[y][j]

f[y][(j+w)%16]+=(f[x][j]-f[y][((j-w)%16+16)%16])

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#define MAXN 100005
#define int long long
using namespace std;
int n,m,ans=0;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0,w[MAXN<<1];
void add(int u,int v,int val){
	cnt++,to[cnt]=v,w[cnt]=val,nxt[cnt]=pre[u],pre[u]=cnt;
}
int g[MAXN],f[MAXN][17],t[MAXN][17];
void DFS(int x,int fa){
	f[x][0]=1;
	for(int i=pre[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		DFS(y,x);
		g[x]+=g[y];
		for(int j=0;j<16;j++){
            f[x][(j+w[i])&15]+=f[y][j];
			g[x]+=f[y][j]*w[i];
		}
	}
}
void dfs(int x,int fa){
	for(int i=pre[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		int size=0;
		for(int j=0;j<16;j++){
			t[y][(j+w[i])&15]+=f[x][j]-f[y][((j-w[i])&15+16)&15];
			size+=f[y][j];
		}
		g[y]=g[x]+(n-size*2)*w[i];
		for(int j=0;j<16;j++) f[y][j]+=t[y][j];
		dfs(y,x);
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,u,v,val;i<n;i++){
		scanf("%lld%lld%lld",&u,&v,&val);
		add(u,v,val),add(v,u,val);
	}
	DFS(1,0);
	dfs(1,0);
	for(int i=1;i<=n;i++){
		for(int j=0;j<16;j++){
            int k=j^m;
            g[i]+=(k-j)*f[i][j];
        }
        printf("%lld\n",g[i]-m);
	}
	return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
2019CCPC湖南全国邀请赛(广东省赛、江苏省赛)重现赛

2019CCPC湖南全国邀请赛(广东省赛、江苏省赛) Can you raed it croretcly?(模拟) 题解:模拟即可 SSY and JLBD(模拟) 题解:模拟即可 Hello XTCPC(贪心) 1.题解:用map<string,int>记录当前...

osc_s5ssp1ty
2019/05/19
1
0
AGC005 补题小结

Problem A STring 简要题意:有一个字符串 $X$ ,对它进行操作。 该串只含字符 $'S'$ 和 $'T'$ ,凡是 $'S'$ 与 $'T'$ 连在一起都要将它们一起去掉 现在进行若干次操作直到该串中没有连在一起......

osc_mlwropg6
2019/05/17
0
0
[ 题解列表 ] GDUT-ACM集训题目

放在Virtual Judge上的专题: sum = 7 ; [ 题解 ] [ 树状数组 ] POJ 2352 - Stars https://www.cnblogs.com/Kaidora/p/10389073.html [ 题解 ] [ BFS ] POJ 1426 - Find The Multiple https......

osc_ox6w5nxo
2019/02/17
1
0
Codeforces 刷题记录(已停更)

Codeforces 每日刷题记录 (已停更) 打‘+’是一些有启发意义的题目,部分附上一句话题解,每日更新3题,大部分题目较水。 Day ID Problem Tutorial Note 1 1 +CF1073E 状压,数位dp,官方题解...

osc_gfiuebly
2018/12/10
2
0
python数据挖掘系列教程——优化(独立变量优化)

全栈工程师开发手册 (作者:栾鹏) python数据挖掘系列教程 今天来学习变量优化问题。寻找使成本函数最小的题解。适用于题解相互独立的情况,设计随机优化算法、爬山法、模拟退火算法、遗传...

luanpeng825485697
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
26
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
16
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0
ubuntu下minicorba例子

一、开发环境安装 sudo apt install omniorb omniorb-idl omniidl libomniorb4-dev libomniorb4-2 omniorb-nameserver libomnithread4 libomnithread4-dev 二、源文件: Hi.idl module ......

wangxuwei
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部