130804组队练习赛ZOJ校赛
2024-08-26 18:54:15
A.Ribbon Gymnastics
题目要求四个点作圆，且圆与圆之间不能相交的半径之和的最大值。我当时想法很简单，只要两圆相切，它们的半径之和一定最大，但是要保证不能相交的话就只能取两两个点间距离和最短的作为半径和最大的。到现在也不是非常清楚为什么可以A，我们带错节奏了。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
double x[4],y[4];
double getdis(int i ,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
int i;
double s1,s2,s3;
while(scanf("%lf%lf",&x[0],&y[0])!=EOF)
{
for(i=1; i<4; i++)
{
scanf("%lf%lf",&x[i],&y[i]);
}
s1=getdis(0,1)+getdis(2,3);
s2=getdis(1,2)+getdis(0,3);
s3=getdis(0,2)+getdis(1,3);
printf("%.6f\n",min(s1,min(s2,s3)));
}
return 0 ;
}
E.Magnet Darts
一道计算几何题，计算落在距离要求点一个单位正方形范围内的点都需要得到一个分数，求期望。由于读错题意，想太复杂了。。。
我们可以枚举矩形内的所有整点，判断整点是否在要求的多边形内或边缘，计算整点周围区域面积乘以分数，相加求和，再与平面总面积相除，求期望。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
struct xl
{
double x,y;
}p[22];
int n;
int f2(double x)//判断是否为零
{
if(fabs(x)<exp)
{
return 0;
}
else
{
if(x<0)
{
return -1;
}
else
{
return 1;
}
}
}
double f1(xl p1,xl p2,xl p0)//判断边缘
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double f3(xl p1,xl p2,xl p0)//判断内部
{
return (p1.x-p0.x)*(p2.x-p0.x)+(p2.y-p0.y)*(p1.y-p0.y);
}
bool f(xl z)
{
int i,j=0;
xl p1,p2;
for(i=0;i<n;++i)
{
p1=p[i];
p2=p[(i+1)%n];
if(f2(f1(p1,p2,z))==0&&f2(f3(p1,p2,z))<=0)
{
return true;
}
if(f2(f1(p2,z,p1))>0&&f2(p1.y-z.y)<=0&&f2(p2.y-z.y)>0)
{
j++;
}
if(f2(f1(p2,z,p1))<0&&f2(p1.y-z.y)>0&&f2(p2.y-z.y)<=0)
{
j--;
}
}
if(j!=0)
{
return true;
}
else
{
return false;
}
}
int main()
{
xl a,b,z;
int i,j;
double sum,ans,lx,ly,hx,hy,A,B;
while(scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y)!=EOF)
{
RD(n);
scanf("%lf%lf",&A,&B);
for(i=0;i<n;++i)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
sum=(a.x-b.x)*(a.y-b.y);
ans=0.0;
for(i=a.x;i<=b.x;++i)
{
for(j=a.y;j<=b.y;++j)
{
z.x=i;
z.y=j;
if(f(z)==true)//求区域面积分数
{
lx=max(i-0.5,a.x);
ly=max(j-0.5,a.y);
hx=min(i+0.5,b.x);
hy=min(j+0.5,b.y);
ans+=(hx-lx)*(hy-ly)*(A*i+B*j);
}
}
}
printf("%.3f\n",ans/sum);
}
return 0;
}
F.Final Exam Arrangement
一道水贪心，找到相应区间标记下就行了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
struct xl
{
int x,y,id;
} s[100001];
bool cmp(xl x,xl y)//结构体排序
{
if(x.x==y.x)
{
return x.y<y.y;
}
return x.x<y.x;
}
int main()
{
int i,n,j,r;
bool v[100001];
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; ++i)
{
RD(s[i].x);
RD(s[i].y);
s[i].id=i+1;
}
sort(s,s+n,cmp);
j=0;
r=-1;
for(i=0; i<n; ++i)
{
v[i]=false;//标记
if(s[i].x>=r)
{
r=s[i].y;
j++;
v[i]=true;
}
r=min(r,s[i].y);
}
OT(j);
for(i=0; i<n; ++i)
{
if(v[i])
{
printf("\n");
OT(s[i].id);
}
else
{
printf(" ");
OT(s[i].id);
}
}
printf("\n\n");
}
return 0;
}
J.Painting Storages
一道排列组合的题目，需要找到状态分解：
当dp[i-1]已经满足状况了：dp[i]=dp[i-1]*2；
当dp[i-1]还没满足状况，则[i-m+1,i]区间则用来满足条件，则i-m必为蓝色，所以dp[i-m-1]不能包括在内。所以需要dp[i-1]+pow(2,i-m-1)-dp[i-m-1]；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
long long dp[100001],a[100001];
void f()
{
a[0]=1;
int i;
for(i=1; i<100001; ++i)//构造2次幂表
{
a[i]=a[i-1]*2%N;
}
}
int main()
{
f();
int i,n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[m]=1;
for(i=m+1; i<=n; ++i)
{
dp[i]=((dp[i-1]*2%N+a[i-m-1])%N-dp[i-m-1]+N)%N;//状态递推过程
}
cout<<dp[n]<<endl;
}
return 0 ;
}
最新文章
- 【原创】基于日志增量，统计qps，并基于ip排序
- linux 查找文件与进程常用命令
- 移动app框架inoic功能研究
- SQL--联合查询【Union】
- ASP.NET SignalR 与 LayIM2.0 配合轻松实现Web聊天室（四） 之 用户搜索（Elasticsearch），加好友流程（1）。
- Coder-Strike 2014 - Round 1 C. Pattern
- iOS-Debug
- /proc/sys/vm/ 内存参数
- Python 3学习笔记2
- 大话string
- WinterCamp 2015 总结
- 魅蓝3s adb interface 找不到驱动程序
- Neutron中的Service类
- admin的基础配置
- 关于thinkphp控制器引用model里的方法的一点收获
- JUC中Lock和ReentrantLock介绍及源码解析
- event 和delegate的分别
- SQL Server監控与診斷
- PhoneGap和Cordova应该用哪一个？
- Vue(三)之前端路由