临比赛前最后一篇博文.....T T......鸭梨山大的啊
C 训练赛的时候搞麻烦了，其实根本用不着数据结构。。。。省略代码
D 三点不共线降低了难度，根据基础的数学知识，如果画一条新的线段，与之前m条线段在区间内相交，则新生成m+1个part
O(n*n)超时，第一个反应就是看看排序，按照线段的起点坐标排序，发现之后是逆序数。。。附代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define cl(a) memset(a,0,sizeof(a))
#define ss(a) scanf("%d",&a)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 30005
#define ll long long
using namespace std;
struct lining
{
int k;
int b;
int st;
int id;
int num;
};
struct finalpoint
{
int value;
int id;
}c[N];
lining a[N];
int h[N],tree[N<<2];
bool cmp(lining p,lining q)
{
return p.st<q.st;
}
bool cmp1(finalpoint p,finalpoint q)
{
return p.value<q.value;
}
void pushup(int rt)
{
tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void update(int i,int l,int r,int rt)
{
if (l==r)
{
tree[rt] = 1;
return;
}
int mid = (l+r) >> 1;
if (i<=mid) update(i,lson);
else update(i,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
return tree[rt];
}
int mid = (l+r) >> 1,res = 0;
if (L<=mid) res+=query(L,R,lson);
if (R>mid) res+=query(L,R,rson);
return res;
}
int main()
{
int i,j,x1,x2,n;
while (ss(x1)!=EOF)
{
ss(x2);
ss(n);
for (i=1;i<=n;i++)
{
ss(a[i].k);ss(a[i].b);
a[i].st = a[i].k*x1+a[i].b;
a[i].id = i;
c[i].value = a[i].k*x2 + a[i].b;
c[i].id = i;
}
sort(a+1,a+n+1,cmp);
sort(c+1,c+n+1,cmp1);
cl(h);
for (i=1;i<=n;i++) h[c[i].id] = i;
for (i=1;i<=n;i++)
a[i].num = h[a[i].id];
cl(tree);
ll sum = 1;
for (i=1;i<=n;i++)
{
ll t= a[i].num , qy = 0;
if (t > 1 ) qy = query(1,t-1,1,n,1);
sum += (t-qy);
update(t,1,n,1);
}
cout<<sum<<endl;
}
return 0;
}
E 几何题，刚开始不会
后来才明白，在极坐标的环境下，压缩坐标倍数即可。椭圆变成了圆，半径为1.枚举所有可能为结果的圆，即过任意两个点的圆（不在圆内），看看哪个圆覆盖面积最大
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 220
using namespace std;
struct point
{
double x;
double y;
}u[N];
double dist(point A,point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool creatcircle(point &O, point A,point B)
{
double l = dist(A,B);
if (l>2.0) return 0;
point C;
C.x = (A.x + B.x) / 2.0;
C.y = (A.y + B.y) / 2.0;
double l1 = sqrt (1 - (l/2.0)*(l/2.0));
double k = -1 * (A.x - B.x) / (A.y - B.y);
O.x = C.x + l1 / sqrt(1+k*k);
O.y = C.y + l1 * k / sqrt(1+k*k);
return 1;
}
int check(point O,int n)
{
int i,sum = 0;
for (i=1;i<=n;i++)
{
if (dist(u[i],O)<=1) sum++;
}
return sum;
}
int main()
{
int i,j,n;
double a,b;
while (cin>>a>>b)
{
cin>>n;
for (i=1;i<=n;i++)
{
cin>>u[i].x>>u[i].y;
u[i].x/=a;u[i].y/=b;
}
int res = 1;
for (i=2;i<=n;i++)
for (j=1;j<i;j++)
{
point O;
O.x=O.y=0.0;
if (creatcircle(O,u[i],u[j])) res = max(res , check(O,n));
}
cout<<res<<endl;
}
return 0;
}
H 可以用DP做，DP弱，没有想到。。。。仔细想想，主要原因是两个长方形相交时，一整个矩形全部更新，而不是交叉区域更新。代码显而易见
判断矩形的时候WA了好几次。。。这个题虽然难度不大，但挺不错的~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ss(a) scanf("%d",&a)
#define cl(a) memset(a,0,sizeof(a))
#define N 1005
using namespace std;
struct ractangle
{
int x1;
int y1;
int x2;
int y2;
int h;
}a[N];
int f[N];
bool crossing(ractangle p,ractangle q)
{
if (p.x1>=q.x2||q.x1>=p.x2) return 0;
if (p.y1>=q.y2||q.y1>=p.y2) return 0;
return 1;
}
bool cmp(ractangle p,ractangle q)
{
return p.x1<q.x1;
}
int main()
{
int i,j,n,m,c,height,dx,dy;
while (ss(n)!=EOF)
{
ss(m);ss(c);
cl(f);
for (i=1;i<=c;i++)
{
ss(dx);ss(dy);ss(height);ss(a[i].x1);ss(a[i].y1);
a[i].x2=(a[i].x1+dx)>n?n:a[i].x1+dx;
a[i].y2=(a[i].y1+dy)>m?m:a[i].y1+dy;
a[i].h=height;
}
int res=0;
for (i=1;i<=c;i++)
{
f[i] = 0;
for (j=1;j<i;j++)
{
if (crossing(a[i],a[j])) f[i] = f[j]>f[i]?f[j]:f[i];
}
f[i] += a[i].h;
res = f[i]>res?f[i]:res;
}
cout<<res<<endl;
}
return 0;
}
F , J等待更新.....