大庆做网站的,柯城网站建设,上海自助建站系统,大连网站的优化正题
题目链接:http://noi.ac/contest/266/problem/794 题目大意
无限多个1∗21*21∗2的砖块交替着 一个砖块会掉落仅当下方两个砖块都掉落#xff0c;现在抽出nnn个砖块#xff0c;求掉落多少个砖块。 解题思路
开一个优先队列#xff0c;若两个连在一起的就把上面那个…正题
题目链接:http://noi.ac/contest/266/problem/794 题目大意
无限多个1∗21*21∗2的砖块交替着 一个砖块会掉落仅当下方两个砖块都掉落现在抽出nnn个砖块求掉落多少个砖块。 解题思路
开一个优先队列若两个连在一起的就把上面那个加进去就好了然后我们发现这样会TLETLETLE。
我们可以将连着的存在一块里就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N3e510;
struct node{ll x,l,r;
}v[N];
bool operator(const node x,const node y)
{return x.xy.x?x.ly.l:x.xy.x;}
ll n,ans,cnt;
priority_queuenode q;
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);q.push((node){x,y,y1});}while(!q.empty()){ll xq.top().x;cnt0;while(!q.empty()q.top().xx)v[cnt]q.top(),q.pop();ll lv[1].l,rv[1].r;for(ll i1;icnt;i){if(r1v[i].l)rmax(v[i].r,r);else{if(l1!r)q.push((node){x1,l1,r-1});ans(r-l1)/2;lv[i].l;rv[i].r;}}if(l1!r)q.push((node){x1,l1,r-1});ans(r-l1)/2;}printf(%lld,ans);
}
