0x08 总结与练习

2023-10-17 08:30
文章标签 总结 练习 0x08

本文主要是介绍0x08 总结与练习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1：前面已经搞好了。

2：poj2965 这种开关问题一个点要么点一次要么不点，枚举所有点的方案实行即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;char ss[10];
int main()
{int d=0,tp=0;for(int i=1;i<=4;i++){scanf("%s",ss+1);for(int j=1;j<=4;j++,tp++)if(ss[j]=='+')d+=(1<<tp);}int max_line=(1<<16)-1,ans=999999,zt;for(int i=0;i<=max_line;i++){int k=d,sum=0;for(int j=0;j<=15;j++){if((i&(1<<j))>0){sum++;int h=j/4;for(int _=0;_<=3;_++)k^=(1<<(h*4+_));int l=j%4;for(int _=0;_<=12;_+=4)k^=(1<<(l+_));k^=(1<<(h*4+l));}}if(k==0){if(ans>sum)ans=sum, zt=i;}}printf("%d\n",ans);int x=1,y=1;for(int j=0;j<=15;j++){if((zt&(1<<j))>0)printf("%d %d\n",x,y);y++;if(y==5)y=1,x++;}return 0;
}
poj2965

3、4、10：手残码农题真心不想做，准备NOIP的时候再做吧

5：poj 3714 平面最近点对问题，分治解决，对于当前已有的最小值确定mid上下左右一个四边形的范围，合并区间时就判定这个四边形范围里面的点即可，闻说这个点数是不会超过8个的。具体实行是在确定了横坐标范围后，把这些点取出，判定时将其按纵坐标排序，一个个求值，这个复杂度是n(logn)^2，假如用归并排序顺便把纵坐标排序会少一个log，但是实际上并没有快多少。至于kdtree。。以后再说

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;struct point{double x,y;int z;}a[210000],t[210000];
bool cmp(point p1,point p2){return p1.x<p2.x;}int tt[210000];
bool cmp2(int n1,int n2){return a[n1].y<a[n2].y;}
double getdis(int n1,int n2)
{return sqrt( (double((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x))) + (double((a[n1].y-a[n2].y)*(a[n1].y-a[n2].y))) );
}
double fenzi(int l,int r)
{if(l==r)return (double(1<<30));int mid=(l+r)/2;double mmin=min(fenzi(l,mid),fenzi(mid+1,r));int i=l,j=mid+1,p=l;while(i<=mid&&j<=r){if(a[i].y<=a[j].y)t[p++]=a[i++];else               t[p++]=a[j++];}while(i<=mid)t[p++]=a[i++];while(j<=r)  t[p++]=a[j++];for(int i=l;i<=r;i++)a[i]=t[i];int len=0;tt[++len]=mid;for(int i=l;i<=r;i++)if(( double(abs(a[i].x-a[mid].x)) )<mmin)tt[++len]=i;for(int i=1;i<=len;i++)for(int j=i+1,clc=0;j<=len&&clc<=7;j++,clc++)if(a[tt[i]].z!=a[tt[j]].z)mmin=min(mmin,getdis(tt[i],tt[j]));return mmin;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y), a[i].z=0;for(int i=n+1;i<=n*2;i++)scanf("%lf%lf",&a[i].x,&a[i].y), a[i].z=1;sort(a+1,a+2*n+1,cmp);printf("%.3lf\n",fenzi(1,2*n));}return 0;
}
poj3714

6：bzoj1271 这道是好题啊！突破口一定是在只有一个是奇数这个条件里面的，那么就是奇偶性的不同，这个时候并没有想到前缀和。知道这个以后就二分答案，看看前缀和是奇数还是偶数就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;int n;
struct node
{LL l,r,d;
}a[210000];
bool check(LL tp)
{LL sum=0;for(int i=1;i<=n;i++)if(a[i].l<=tp)sum+=(min(a[i].r,tp)-a[i].l)/a[i].d+1;return (sum%2==1);
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].d);LL l=1,r=2147483647,ans=-1;while(l<=r){LL mid=(l+r)/2,u;if(check(mid)==true){r=mid-1;ans=mid;}else l=mid+1;}if(ans==-1)printf("Poor QIN Teng:(\n");else{LL c=0;for(int i=1;i<=n;i++)if(a[i].l<=ans&&ans<=a[i].r&&(ans-a[i].l)%a[i].d==0)c++;printf("%lld %lld\n",ans,c);}}return 0;
}
bzoj1271

7：poj3179 这题明显就得写个二维前缀和嘛。。相应的就离散化一下。二分答案，然后两个for一个枚举行一个枚举列的后界，前界尽量往前，这个while往前走就好。

 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;int n,C;
struct node{int x,y;}a[510];
int lsxlen,lsylen,lsx[510],lsy[510];
void LSH()
{lsxlen=0;for(int i=1;i<=n;i++)lsx[++lsxlen]=a[i].x;sort(lsx+1,lsx+lsxlen+1);lsxlen=unique(lsx+1,lsx+lsxlen+1)-lsx-1;for(int i=1;i<=n;i++)a[i].x=lower_bound(lsx+1,lsx+lsxlen+1,a[i].x)-lsx;lsylen=0;for(int i=1;i<=n;i++)lsy[++lsylen]=a[i].y;sort(lsy+1,lsy+lsylen+1);lsylen=unique(lsy+1,lsy+lsylen+1)-lsy-1;for(int i=1;i<=n;i++)a[i].y=lower_bound(lsy+1,lsy+lsylen+1,a[i].y)-lsy;
}
int sum[510][510];
int getsum(int x,int y,int u,int v)
{return sum[x][y]-sum[x][v-1]-sum[u-1][y]+sum[u-1][v-1];
}
bool check(int mid)
{int rl=1;for(int rr=1;rr<=lsxlen;rr++){while(lsx[rr]-lsx[rl]>=mid)rl++;int cl=1;for(int cr=1;cr<=lsylen;cr++){while(lsy[cr]-lsy[cl]>=mid)cl++;if(getsum(rr,cr,rl,cl)>=C)return true;}}return false;
}
int main()
{scanf("%d%d",&C,&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);LSH();memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++)sum[a[i].x][a[i].y]++;for(int i=1;i<=lsxlen;i++)for(int j=1;j<=lsylen;j++)sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];int l=1,r=10000,ans;while(l<=r){int mid=(l+r)/2;if(check(mid)==true){ans=mid;r=mid-1;}else l=mid+1;}printf("%d\n",ans);return 0;
}
poj3179

 

8：bzoj1465 bzoj1045: [HAOI2008] 糖果传递&&bzoj3293: [Cqoi2011]分金币

9：明显x、y分开做，y就是中位数，x的话我一开始也是想要从中位数左右延伸，但是fail掉了。。正确的做法是设排完序以后，起点是a，那么我们就是要求的sum=Σabs(a-(x[i]-i))。a就是(x[i]-i)这东西的中位数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;LL a[11000],b[11000];
LL myabs(LL x){return x<0?-x:x;}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++)a[i]-=i;sort(a+1,a+n+1);LL sum=0;for(int i=1;i<=n;i++)sum+=myabs(a[i]-a[(n+1)/2]);for(int i=1;i<=n;i++)sum+=myabs(b[i]-b[(n+1)/2]);printf("%lld\n",sum);return 0;
}
poj1723

11：poj1050这题暴力二维前缀和n^4可A。。。。但是我还是正直的写个个n^3，f[i][j][k]表示现在枚举到第i行，列的区间是j~k的最大值，那么就相当于每一种列的情况都做一次O(n)的一维最大子串。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;int a[110][110],f[110][110][110];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);int ans=-2147483647;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int sum=0;for(int k=j;k<=n;k++){sum+=a[i][k];f[i][j][k]=max(f[i-1][j][k]+sum,sum);ans=max(ans,f[i][j][k]);}}}printf("%d\n",ans);return 0;
}
poj1050

12：hdu4864 这题超级好题！！！！想了我超久，下午一个小时+晚上两个小时，看到那个价值的算法，肯定觉得会有问题对吧，我发现其实这个价值根本没用，因为价值的大小是按照耗时，耗时相等按照等级排的。思考的时候我类比一下贪心的第1题，那题是一个权，两个限制，现在是两个权，两个限制，不管怎样肯定是先排序，然后在此基础上卡另外一个限制贪心，我写的时候是让机器去找任务，这里就出问题了！不管按照什么排序，怎样的贪心法都会被反例掉，因为在这题里面，机器是为任务服务的，所以应该是任务去找机器，排序过后权值由大到小，一个个找完以后，x区间是单调延伸，前面的机器必然满足x比往后枚举的任务的x大，相当于问题只在于y，那么只需要贪心选择全部中尽量小的即可。再来分析一下正确性，当前任务占用机器，必然比后面的任务占用的机器要多，对于机器被占用，可以视作对答案的贡献均为1，所以可以心安理得的占用机器。对于机器而言，假如不影响当前任务影响后面，那一个替代他的机器一定比他还要优秀，它能影响了当前，肯定在先前也可以影响那个后一种情况中被前一个机器影响的任务。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;struct node
{int x,y;
}a[110000],b[110000];
bool cmp(node n1,node n2)
{if(n1.x==n2.x)return n1.y>n2.y;return n1.x>n2.x;
}
multiset<int>s;
multiset<int>::iterator o;int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);for(int i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);sort(a+1,a+n+1,cmp);sort(b+1,b+m+1,cmp);s.clear();int ans=0,tp=1;long long val=0;for(int i=1;i<=m;i++){while(tp<=n&&a[tp].x>=b[i].x)s.insert(a[tp].y),tp++;if(!s.empty()){if(*--s.end()>=b[i].y){int k=*s.lower_bound(b[i].y);int c=s.count(k);s.erase(k);for(int j=1;j<c;j++)s.insert(k);//    for(o=s.begin();o!=s.end();o++)printf("%d\n",*o);ans++;val+=b[i].x*500+2*b[i].y;}}}printf("%d %lld\n",ans,val);}return 0;
}
hdu4864 （因为y的范围只有100所以可以暴力枚举，我没想就搞了个set，跑得还比暴力慢-_-!）

 

转载于:https://www.cnblogs.com/AKCqhzdy/p/9245508.html

这篇关于0x08 总结与练习的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Python中连接不同数据库的方法总结

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo
阅读更多...
Git提交代码详细流程及问题总结

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》：本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push
阅读更多...
Kubernetes常用命令大全近期总结

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes（有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes？Kubernetes常用命令总
阅读更多...
Python中实现进度条的多种方法总结

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres
阅读更多...
Android数据库Room的实际使用过程总结

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象（DAO）和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类（Entity）3.创建数据访问对象（DAO
阅读更多...
Java向kettle8.0传递参数的方式总结

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的
阅读更多...
C# Task Cancellation使用总结

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2