又膜了场JSOI2015，壮烈爆蛋
听说lyz大神(S)犇(B)在嘲笑我，这不能忍啊。。我改5个字符就可以轻松碾压他→_→
T1
看到期望吓尿了，先蹭点薯片压压惊。
考完才发现，这™是道水(SB)题。。
先预处理出每个妹子选各个汉子的概率，直接套等比数列求和公式：
然后用树状数组求和就OK辣~
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 510000
#define a(i) a[(i)].a
#define b(i) a[(i)].b
using namespace std;
struct node{
int a,b;
};
bool cmp(node x, node y){
if(x.a!=y.a) return x.a<y.a;
else return x.b<y.b;
}
double ans,s,p;
double tr[N],p1[N],p2[N],f[N];
int d[N];
node a[N];
int n,m,t,l,k;
int main(){
scanf("%d%d",&n,&m);
scanf("%lf",&p);
for (int i=1;i<=n;i++) scanf("%d%d",&a(i),&b(i));
p1[0]=p2[0]=1;
for (int i=1;i<=n;i++){p1[i]=p1[i-1]*p;p2[i]=p2[i-1]*(1-p);}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++) d[a(i)]++;
for (int i=1;i<=n;i++){
if (a(i)!=a(i-1)) l=0;
f[i]=(p2[l++]*p)/(1-p2[d[a(i)]]);
}
for (int i=n;i>0;i--){
k=b(i)-1;
while (k>0){
t=k&(-k);
ans+=f[i]*tr[k];
k-=t;
}
k=b(i);
while (k<=n){
if (!k) break;
tr[k]+=f[i];
k+=k&(-k);
}
}
printf("%.2lf\n",ans);
}
T2
看起来很水的样子，数据明显是让你nlogn嘛，先让我按out排个序。
诶好像是贪心，蛤蛤线段树维护一下。
呀好像in会冲突，离散一下~快排stl不会用。。那就手打吧= =
woc细节好多。。打了两小时终于搞定了耶。
然而……爆蛋了……
日，线段树打错了
#include<cstdio>
#include<cmath>
#define N 210000
using namespace std;
int n,m,s,t,k,l;long long ans;
int num[N*4],tree[N*4],a[N],b[N],d[N],in[N],out[N],p[N],pre[N];
long long c[N];
void qsort(int l,int r)
{
int i,j,x,y;
i=l;
j=r;
x=a[(l+r)/2];
while (i<j){
while (a[i]<x) i++;
while (x<a[j]) j--;
if (i<=j) {
y=a[i];a[i]=a[j];a[j]=y;
y=p[i];p[i]=p[j];p[j]=y;
i++;
j--;
}
}
if (l<j) qsort(l,j);
if (i<r) qsort(i,r);
}
void qsort2(int l,int r)
{
int i,j,x,y;
i=l;
j=r;
x=out[(l+r)/2];
while (i<j){
while (out[i]>x) i++;
while (x>out[j]) j--;
if (i<=j) {
y=out[i];out[i]=out[j];out[j]=y;
y=in[i];in[i]=in[j];in[j]=y;
i++;
j--;
}
}
if (l<j) qsort2(l,j);
if (i<r) qsort2(i,r);
}
void add(int l,int r,int x,int p,int v){
if ((x<1)||(x>n)) return;
if (l==r){
num[p]=v;
tree[p]=d[v];
return;
}
int mid=(l+r)/2;
if (x<=mid) add(l,mid,x,p+p,v);
else add(mid+1,r,x,p+p+1,v);
if (tree[p+p]>tree[p+p+1]){
tree[p]=tree[p+p];
num[p]=num[p+p];
}
else {
tree[p]=tree[p+p+1];
num[p]=num[p+p+1];
}
}
int find(int l,int r,int x,int y,int p){
if (x>y) return 0;
if ((l==x)&&(r==y)){
return(num[p]);
}
int mid=(l+r)/2;
int k,t1,t2;
if (y<=mid) return(find(l,mid,x,y,p+p));
if (x>mid) return(find(mid+1,r,x,y,p+p+1));
if ((x<=mid)&&(y>mid)){
t1=find(l,mid,x,mid,p+p);
t2=find(mid+1,r,mid+1,y,p+p+1);
if (d[t1]>d[t2]) return(t1);
else return(t2);
}
}
int main()
{
// freopen("doll.in","r",stdin);
// freopen("doll.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d%d",&out[i],&a[i],&b[i]);
for (int i=1;i<=n;i++) p[i]=i;
qsort(1,n);
l=1;
for (int i=1;i<=n;i++){
if (a[i]!=a[i-1]) {
pre[a[i]]=i;
for (int j=l;j<a[i];j++) pre[j]=i;
l=a[i]+1;
}
in[p[i]]=i;
d[i]=b[p[i]];
c[i]=a[i];
}
for (int i=l;i<=10000;i++) pre[i]=n+1;
qsort2(1,n);
for (int i=1;i<=n;i++){
// printf("%d\n",out[i]);
if (out[i]==10000) l=0;
else l=find(1,n,pre[out[i]+1],n,1);
c[l]-=out[i];
add(1,n,l,1,0);
add(1,n,in[i],1,in[i]);
}
for (int i=1;i<=n;i++) ans+=c[i]*d[i];
printf("%lld\n",ans);
}
T3
看到计算几何吓傻了，果断放弃。。
听说小天才lyk乱搞A了orz
此题没有正解，尽情乱搞吧
然而我是拒绝做这种码农题的→_→
评论 (0)
