首页 > 代码库 > 又是一个二模02,不过day2
又是一个二模02,不过day2
话说比较简单.除了第三题不会写平衡树啊你妹!!边做边写吧.
仍然是机智的链接
第一题:
题目的数据范围非常小,来个 大法狮 吧.$6^6$只有$46656$,加上浮点运算的超大常数也不多嘛 ╮(╯_╰)╭
实现有点恶心,暴力你懂得.
#include <cstdio>#include <cmath>#define PI 3.1415926535897932384626inline double ab(double x){ return (((x)>=0)?(x):(-x));}inline double mi(double x,double y){ y=ab(y); return (x<y?x:y);}inline double ma(double x,double y){ y=ab(y); return (x>y?x:y);}int n;double x[8],y[8],r[8],s[8],minLeft;bool f[8];void dfs(int p,int d,double si){ double a,b,c; int i; b=ab(x[p]-x[0]); b=mi(b,x[p]-x[1]); b=mi(b,y[p]-y[1]); b=mi(b,y[p]-y[0]); for(i=2;i<=n;++i){ if(f[i]) b=mi(b,hypot(x[p]-x[i],y[p]-y[i])-r[i]); } f[p]=true; si+=PI*b*b; r[p]=b; if(d==n-1){ si=s[0]-si; if(si<minLeft){ minLeft=si; } r[p]=0.0; f[p]=false; return; } for(i=2;i<=n;++i){ if(!f[i]){ dfs(i,d+1,si); } } r[p]=0.0; f[p]=false;}int main(){ freopen("box2.in","r",stdin); freopen("box2.out","w",stdout); scanf("%d%lf%lf%lf%lf",&n,x,y,x+1,y+1); minLeft=s[0]=s[1]=ab((x[1]-x[0])*(y[1]-y[0])); ++n; int i; for(i=2;i<=n;++i) scanf("%lf%lf",x+i,y+i); for(i=2;i<=n;++i){ dfs(i,1,0.0); } printf("%.0lf",minLeft); return 0;}
~!~!@~!@@!@!##@@#@!@##@@@#@#%^&^%##@!@@我是机智的分割线~~~
第二题:
简单的动规.DP方程:
DP F[i,j]=max(F[i-1,j]+same(c[i],i-j),F[i-1,j-1])
# F[i,j]表示前i个数删去j个的最大匹配数,c[i]表示第i个数字
# same(a,b)=(a==b?1:0)
return MaxAmong(F,lengthof F)
#include <cstdio>int f[2000][2000],c[2000],n,i,j;inline int max(int a,int b){ return a>b?a:b;}int main(){ freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;++i){ scanf("%d",c+i); } for(i=1;i<=n;++i){ for(j=0;j<=i;++j){ f[i][j]=max(f[i-1][j]+(c[i]==i-j),f[i-1][j-1]); } } j=0; for(i=0;i<=n;++i){ if(f[n][i]>j) j=f[n][i]; } printf("%d\n",j); return 0;}
真的很 短啊.
第三题:
不会写BST啊神犇滚粗!!!
好吧今天边学习边写,应该SBT比较方便实现吧.
又是一个二模02,不过day2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。