noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]

2024-01-01 07:59
文章标签 路径 dp 分类 运算 压缩 讨论 模拟题 noip hzwer 小奇

本文主要是介绍noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这么颓下去，迟早要完。

这套题只考了2h,感觉还不错，T2做过类似的所以A了，T1和T3基本上也没什么大问题，关键就是要深入挖掘问题特质，学会分类讨论（很多题都可以剪掉大量的枝，比如T1,小奇1的T3,noip2015 day1 T3,都是需要有这种分类意识的。
T1：
题意：在坐标轴上有一些点有收益，问从0开始，每次只能向前跳4（0+4=4）步或7（0+7=7）步，最大收益是。
数据范围：
对于20%的数据n=1，m<=10^5
对于40%的数据n<=15，m<=10^5
对于60%的数据m<=10^5
对于100%的数据n<=10^5，m<=10^9，1<=ai<=10^4，1<=bi<=m
分析：
感觉这道题是数据分斥（还是什么，不知道叫什么）的典型例子，黄学长这两套题出的还是不错的。
20%n=1，只用看能不能去就行了。
60%的数据，m比较小，可以f[i]表示i这个位置的最大值，那么然后去找-4，-7的最大值就可以了。
100%，经过分析发现，>=18的情况是一定可以走到的！那么就可以18以内用数组存能不能走，18以外都可以走，在走的时候更新18以内的最大值就可以了！
下面是碎碎念可以不看：
关键就是发现>=18的那个性质，这个要求我们多手算找规律啊。
按理说发现>=18以后一百分算法应该顺理成章不过我居然没发现，还是没养成这种意识。
而且考这套题的时候太zz了，因为我的算法应该是40分，我想了很久后面那20分怎么拿，结果拿到解题报告才想起来，枚举m的话时间复杂度线性……

60分程序：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "mining"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,ans,f[Maxn];
struct node
{int a,b;
}a[Maxn];
bool cmp(node x,node y)
{return x.a<y.a;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();each(i,n){a[i].b=read();a[i].a=read();}sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{if(cur-pre>=18)return 1;return boo[cur-pre];
}
void work()
{for(int i=1;i<=n;i++){int j=i-1;int flg=1;for(;j>=0;j--)if(check(a[i].a,a[j].a))f[i]=max(f[j]+a[i].b,f[i]);ans=max(ans,f[i]);}printf("%d",ans);
}
void debug()
{//
}
int main()
{freopen("hop.in","r",stdin);freopen("hop.out","w",stdout);init();work();//debug();return 0;
}

100分：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "mining"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,ans,maxn,f[Maxn];
struct node
{int a,b;
}a[Maxn];
bool cmp(node x,node y)
{return x.a<y.a;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();each(i,n){a[i].b=read();a[i].a=read();}sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{if(cur-pre>=18)return 1;return boo[cur-pre];
}
void work()
{for(int i=1;i<=n;i++){int j=i-1;for(;j>=max(0,i-17);j--)if(check(a[i].a,a[j].a))f[i]=max(f[j]+a[i].b,f[i]);if(i>18)maxn=max(maxn,f[i-18]);if(check(a[i].a,0))f[i]=max(f[i],maxn+a[i].b);ans=max(ans,f[i]);}printf("%d",ans);
}
void debug()
{//
}
int main()
{freopen("hop.in","r",stdin);freopen("hop.out","w",stdout);init();work();//debug();return 0;
}

T2:
题意：从带权矩阵左上角走到右下角（只能向下或向右走），求 (n+m−1)∗Σn+m−1i=1(Ai−Aavg)2 的最小值.
分析：首先呢我们可以证明对于一个序列，若平均值错误，V值一定更小（具体怎么证？考虑一个长度为2的序列，把它拆开，看一下，这不是均值不等式吗）。
然后，你看这权值范围<=30，一看就可以做奇怪的事。根据最小精度枚举平均值情况就可以了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1,i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC ""
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=305;
int t,n,m,lim,limi,ans,a[Maxn][Maxn],f[Maxn][Maxn];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();lim=n+m-1;for(int i=2;i<=n;i++)f[i][0]=inf;for(int j=2;j<=m;j++)f[0][j]=inf;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read()*lim;limi=lim*30;ans=2e9;
}
void work()
{for(int i=lim;i<=limi;i++){for(int j=1;j<=n;j++)for(int k=1;k<=m;k++)f[j][k]=min(f[j][k-1],f[j-1][k])+(a[j][k]-i)*(a[j][k]-i);ans=min(ans,f[n][m]);}printf("%d\n",ans/lim);
}
void debug()
{//
}
int main()
{freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);t=read();for(int i=1;i<=t;i++){init();work();}//debug();return 0;
}

T3:
题意：对于一棵树，对于每个点，求其他点到这个点的距离分别异或一值的和。
分析：
其实吧，多法图你就会发现，这个东西，其实可以通过统计最后几位的01来解决。具体的实现就是，用处理0那种情况（也就是两次dfs记两个数组）的方法，再同时处理个01就可以了，然而我当初太天真，写了个暴力。
碎碎念：多fa图。
暴力：（好像m!=0处理有错WA了一组，求大神指点。）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC ""
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,a,b,ans,roa[Maxn],g[Maxn],son[Maxn];
int f[Maxn],fr[Maxn],tov[2*Maxn],des[2*Maxn],wor[2*Maxn];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void addedge(int cur)
{a=read();b=read();wor[2*cur]=wor[2*cur-1]=read();tov[2*cur-1]=fr[a];fr[a]=2*cur-1;des[2*cur-1]=b;tov[2*cur]=fr[b];fr[b]=2*cur;des[2*cur]=a;
}
void dfs(int u,int fath,long long dis)
{if(dis)ans+=dis^m;for(int i=fr[u];i;i=tov[i])if(des[i]!=fath)dfs(des[i],u,dis+(long long)wor[i]);
}
void dfs2(int u,int fath)
{for(int i=fr[u];i;i=tov[i])if(des[i]!=fath){dfs2(des[i],u);roa[des[i]]=wor[i];son[u]+=1+son[des[i]];f[u]+=f[des[i]]+wor[i]*(son[des[i]]+1);}
}
void dfs3(int u,int fath)
{g[u]=f[fath]-f[u]+g[fath]+roa[u]*(n-son[u]*2-2);for(int i=fr[u];i;i=tov[i])if(des[i]!=fath)dfs3(des[i],u);
}
void init()
{n=read();m=read();for(int i=1;i<n;i++)addedge(i);
}
void work()
{if(m){for(int i=1;i<=n;i++){ans=0;dfs(i,0,0LL);printf("%d\n",ans);}}else{dfs2(1,0);f[0]=f[1];dfs3(1,0);for(int i=1;i<=n;i++)printf("%d\n",f[i]+g[i]);}
}
void debug()
{//
}
int main()
{freopen("tree1.in","r",stdin);freopen("tree1.out","w",stdout);init();work();//debug();return 0;
}

这篇关于noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/558603。

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
一文详解SpringBoot响应压缩功能的配置与优化

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML
阅读更多...
Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录，并压缩为zip文件到另一个
阅读更多...
Linux修改pip和conda缓存路径的几种方法

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓
阅读更多...
MySQL中闪回功能的方案讨论及实现

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回（flashback）功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回（flashb
阅读更多...
Windows系统下如何查找JDK的安装路径

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》：本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK，或者在别人的电脑上，想
阅读更多...
Python中Windows和macOS文件路径格式不一致的解决方法

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1：使用 os.path 模块方法 2：使用 pathlib 模块（推荐）方法 3：统一使
阅读更多...
一文教你解决Python不支持中文路径的问题

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod
阅读更多...
MySQL9.0默认路径安装下重置root密码

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径，
阅读更多...
Python利用PIL进行图片压缩

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时，由于文件中的图片太大，导致文件也太大，无法发送，所有可以对文件中的图
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2