茶顏悅色

題意

固定$k$的矩形，能最多框住多少個點。

題解

假如我們固定一個矩形，以左下角為坐標。
這樣子對于$(a,b)$，那么能夠包括到這個點的矩形左下角的范圍：
$x\in (a?k,a),y\in (b?k,b)$
利用掃描線的思想，從$x$軸掃過去，每次對$y$上的區間加$1$，表示正方形左下角為此點的時候有多少個點能獲得，求全局最大即可。

#include<bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;i++) #define inf 0x3f3f3f3f typedef long long ll; using namespace std; const int maxn= 4e5+500; //êy?Y·??§struct node{int x,yl,yr,io;node(){}node(int _x,int _yd,int _yu,int _io):x(_x),yl(_yd),yr(_yu),io(_io){}friend bool operator < (node a,node b){return a.x<b.x;} }line[maxn];struct tree2{tree2 *lson,*rson;int x,lazy; }dizhi[maxn<<2],*root=&dizhi[0];int n,m,t=1,yy[maxn];void push_up(tree2 *tree,int l,int r){tree->x=max(tree->lson->x,tree->rson->x); }void build(tree2 *tree,int l,int r){if(l==r){tree->x=tree->lazy=0;return ;}tree->lson=&dizhi[t++];tree->rson=&dizhi[t++];int mid=(l+r)>>1;build(tree->lson,l,mid);build(tree->rson,mid+1,r);push_up(tree,l,r); }void push_down(tree2 *tree,int l,int r){if(!tree->lazy)return ;tree->lson->x+=tree->lazy;tree->rson->x+=tree->lazy;tree->lson->lazy+=tree->lazy;tree->rson->lazy+=tree->lazy;tree->lazy=0; }void update(tree2 *tree,int l,int r,int x,int y,int d){if(x<=l&&r<=y){tree->x+=d;tree->lazy+=d;return ;}push_down(tree,l,r);int mid=(l+r)>>1;if(x<=mid)update(tree->lson,l,mid,x,y,d);if(y>mid)update(tree->rson,mid+1,r,x,y,d);push_up(tree,l,r); }int main(){cin>>n>>m;int cnt=0,len;FOR(i,1,n){int x,y;scanf("%d%d",&x,&y);line[++cnt]=node(x-m,y-m,y,1);yy[cnt]=y-m;line[++cnt]=node(x+1,y-m,y,-1);yy[cnt]=y;}sort(line+1,line+1+cnt);sort(yy+1,yy+1+cnt);len=unique(yy+1,yy+1+cnt)-yy-1;build(root,1,len);int ans=-1;for(int i=1;i<=cnt;i++){int x=lower_bound(yy+1,yy+1+len,line[i].yl)-yy;int y=lower_bound(yy+1,yy+1+len,line[i].yr)-yy;//cout<<line[i].x<<" "<< x<<" "<<y<<endl;update(root,1,len,x,y,line[i].io);ans=max(ans,root->x);}cout<<ans<<endl; }

飛行棋

題意

有個骰子有$k$面，類似于飛行棋，如果到達距離超過和終點的距離就會往前幾步。
求到達終點扔的次數的期望。

題解

本質很簡單。
如果你到達的距離比$k$小了，那么你有$\frac{1}{k}$的概率到達終點。
否則到達一個新點，新點一定還是滿足比$k$小，依然還是有$\frac{1}{k}$概率。
期望就是$k$次。
所以$E_n=1+{\sum }_{x=n?k}^{n?1}\frac{1}{k}{E}_x$
每個可以直接到達終點的點有$\frac{1}{k}$的概率直接到達終點，所以期望加一。

總結

以上是生活随笔為你收集整理的CCPC－Wannafly Comet OJ 夏季欢乐赛（2019）部分题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。