lyzlyz?lyzlyz!

听说这是JSOIDay3

膜了贵省的题目，感到不明觉厉。

Orz NiroBC 210

Orz Chrysanthemum 130

Orz drc神犇(SB) 0

T1

看到期望慌了，先吔点东西压压惊。

好吧让窝萌推一下。

对于一个女性，列表中总共有cnt个对象，选中第i个对象的概率：

[tex]\sum\limits_{j = 0}^{ + \infty } {p*{{(1 - p)}^{i + cnt*j - 1}}}[/tex]

显然这是一个等比数列，列出求和公式：

[tex]\frac{{1 - {{(1 - p)}^j}}}{{1 - {{(1 - p)}^{cnt}}}}*p*{(1 - p)^{i - 1}}[/tex]

当j趋向于正无穷时(1-p)^j趋向于0，那么公式就变成了：

[tex]\frac{{p*{{(1 - p)}^{i - 1}}}}{{1 - {{(1 - p)}^{cnt}}}}[/tex]

接着只要倒着扫一遍，然后将概率一一插入树状数组并询问就可以辣！

什么我居然丢了这送的40分。

T2

看到题目慌了，这不是NiroBC出的Gold_7穿裙子？

让窝萌来YY一个最小割小费用最大流吧。

哦好像是错的。愉快爆蛋。

我去正解是贪心。。。贪心怎会没有反例

考虑将x0放入x，y0放入y，其中b[x]>b[y]，Out[x0]<Out[y0]。

如果把x0放入y，y0放入x（假设x0和y0都是可以放进x和y的）。

ans1=(In[x]-Out[x0])*b[x]+(In[y]-Out[y0])*b[y]

ans2=(In[x]-Out[y0])*b[x]+(In[y]-Out[x0])*b[y]

ans1-ans2=(Out[y0]-Out[x0])*(b[x]-b[y])<0

显然按b排序，取能放下的最大的，一定不存在更优解。

所以贪心好像没有反例。

那么用数据结构维护一下就可以辣！

(窝用二分+线段树O(nlogn²)然而Gold_7用set既快又短。。。)

T3

看到计蒜几何慌了，让我先打个20分压压惊。

诶好像40分也很好拿吖。

诶好像这只是一道码农题+乱搞题。

拒绝做这种恶心题。

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,m,i,j,x,y,edgenum;
double p,ans;
int head[M],vet[M],next[M],a[M];
double tree[M];
double mi[M];
void addedge(int x,int y){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
}
int lowbit(int x){return x&(-x);}
double query(int x){
	double ans=0;
	while (x){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
void update(int x,double t){
	while (x<=n){
		tree[x]+=t;
		x+=lowbit(x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%lf",&p);
	for (i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	mi[0]=1;
	for (i=1;i<=n;i++)mi[i]=mi[i-1]*(1-p);
	for (i=n;i>=1;i--){
		int cnt=0;
		for (int e=head[i];e;e=next[e])a[++cnt]=vet[e];
		sort(a+1,a+cnt+1);
		for (j=cnt;j>=1;j--)ans+=p*mi[j-1]/(1-mi[cnt])*query(a[j]-1),update(a[j],p*mi[j-1]/(1-mi[cnt]));
	}
	printf("%.2lf",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int n,i,flag;
ll ans;
int tree[500010];
struct shit{ll in;ll out;ll imp;}a[500010];
bool cmp(shit i,shit j){return i.imp>j.imp;}
void update(int x,int l,int r,int p,int cmp){
	tree[p]+=cmp;
	if (l==r)return;
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,p<<1,cmp);else update(x,mid+1,r,p<<1|1,cmp);
}
int search(int x,int y,int l,int r,int p){
	if (x==l&&y==r)return tree[p];
	int mid=l+r>>1;
	if (y<=mid)return search(x,y,l,mid,p<<1);
		else if (x>mid) return search(x,y,mid+1,r,p<<1|1);
			else return search(x,mid,l,mid,p<<1)+search(mid+1,y,mid+1,r,p<<1|1);
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++)scanf("%d%d%d",&a[i].out,&a[i].in,&a[i].imp);
	sort(a+1,a+n+1,cmp);
	for (i=1;i<=n;i++)update(a[i].out,1,10000,1,1);
	for (i=1;i<=n;i++){
		if (a[i].in==1){ans+=a[i].in*a[i].imp;continue;}
		int cnt=0;
		int l=1,r=a[i].in-1;
		while (l+1<r){
			int mid=l+r>>1;
			if (search(mid,a[i].in-1,1,10000,1))l=mid;else r=mid;
		}
		if (search(r,a[i].in-1,1,10000,1))cnt=r;else if (search(l,a[i].in-1,1,10000,1))cnt=l;else ans+=a[i].in*a[i].imp;
		if (cnt)update(cnt,1,10000,1,-1),ans+=(a[i].in-cnt)*a[i].imp;
	}
	printf("%lld\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double pi=3.1415926535;
int n,i,ans,ans1,flag[100];
double stx[100],sty[100],edx[100],edy[100];
double X1,Y1,X2,Y2,ang,len,k;
int check(int x){
	if (stx[x]==edx[x]){if (k*stx[x]>=sty[x]&&k*stx[x]<=edy[x]||k*stx[x]>=edy[x]&&k*stx[x]<=sty[x])return 0;else return 1;}
	double k1=(edy[x]-sty[x])/(edx[x]-stx[x]);
	double b=sty[x]-stx[x]*k1;
	if (k==k1)return 1;
	double xx=b/(k-k1);
	if (xx>=stx[x]&&xx<=edx[x])return 0;else return 1;
}
int main(){
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	scanf("%d%lf%lf",&n,&ang,&len);
	for (i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf%d",&stx[i],&sty[i],&edx[i],&edy[i],&flag[i]);
		if (stx[i]>edx[i])swap(stx[i],edx[i]),swap(sty[i],edy[i]);
		if (flag[i]==1){printf("Orz\n");return 0;}
	}
	scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); 
	double shit=X1;
	while (shit<=X2){
		shit=shit+(X2-X1)/1000000;
		if (shit==0)continue;
		ans1++;
		k=Y1/shit;
		for (i=1;i<=n+1;i++)
			if (i==n+1||!check(i))break;
		if (i!=n+1)continue;
		double x=Y1/k;
		if (shit*shit+Y1*Y1<=len*len){
			if (shit<0&&atan(k)+pi/2<=ang/360*pi||shit>0&&pi/2-atan(k)<=ang/360*pi)ans++;
		}
	}
	printf("%.4lf\n",(double)ans/ans1);
}