2016年7月27日 星期三

TIOJ 1045 A.細菌培養

TIOJ 1045 A.細菌培養
題目概述:
有一個初始值為1的10000*10000格子,給n個矩形,使每個矩形內的所有元素加倍。
求最後所有元素加總。

思路:
從上而下一排一排的計算。
假設我知道這排被(1,20),(4,8),(6,12),(15,17)覆蓋。
我把每個區間存成兩個點,一個點代表開始,另一個點代表結束。
我只要能知道a和b之間(不包含b)被k個區間覆蓋,那我就讓答案加上(b-a)*2k
可以參考下圖。(紅色的為甚麼要+1可以看看下文)
la代表上一個位置在哪
sum代表被覆蓋了幾次
TIOJ 1045 解題圖.jpg
那我又要怎麼快速地知道每一行有哪些區間呢?
我維護一個該行有的區間multiset<P> s;
我存矩形的方式為存到vector<P> v[],nv[],
v[]代表應該從該行要開始覆蓋的區間
nv[]代表應該從該行要結束覆蓋的區間
假設有個矩形l,u,r,d,注意因為題目給的上下左右是線,不是格子,假設給(0,0)~(2,2)試指涵蓋了(1,1),(1,2),(2,1),(2,2)這四格。
(u+1)~(d)行都需要覆蓋(l+1)~(r)這個區間,
所以從第(u+1)行開始覆蓋,第(d+1)行結束。(注意不是在第d行結束,因為第d行也要覆蓋)
至於為甚麼區間是要在(r+1)結束也是一樣的道理。

接著在每一行都加上v[]裡存的區間,然後扣掉nv[]裡的區間,然後再用上圖的做法求出該行的總和。

對了,記得也要把前後沒有計算到的地方都加上1

AC code:
//By SCJ
//tioj 1045
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define maxn 10000
typedef pair<int,int> P;
vector<P> v[maxn+5],nv[maxn+5];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
   int n;
   while(cin>>n,n!=0)
   {
       int l,u,r,d;
       long long ans=0;
       for(int i=0;i<n;++i)
       {
           cin>>l>>u>>r>>d;
           v[u+1].push_back({l+1,1});
           v[u+1].push_back({r+1,-1});
           nv[d+1].push_back({l+1,1});
           nv[d+1].push_back({r+1,-1});
       }
       multiset<P> s;
       for(int i=1;i<=maxn;++i)
       {
           for(P j:nv[i]) s.erase(s.find(j));
           for(P j:v[i]) s.insert(j);
           int la=1,sum=0;
           for(P j:s)
           {
               ans+=(1LL<<sum)*(j.first-la);
               sum+=j.second;
               la=j.first;
           }
           if(s.size()) ans+=( maxn - ((--s.end())->first) )+1;
           else ans+=maxn;
       }
       cout<<ans<<endl;
       for(int i=0;i<=maxn;++i) v[i].clear(),nv[i].clear();
   }
}



POJ 3250 Bad Hair Day

POJ 3250 Bad Hair Day
題目概述:
給n隻牛的高度,然後n隻牛都站好一排向右看,每一隻牛可以看到在下一個比自己還要高(≧)的牛之前所有的牛的髮型。求所有牛能看到的牛數量的sum,

思路:
維護一個遞減的stack,做法就大概是下圖這樣了。
一開始要丟個INF是為了不讓stack裡是空的,造成呼叫top()時造成RE的困擾,還有一些方便的地方,會讓code簡單多了。
最後丟個INF-1是為了讓剩下在stack裡的東西也加上答案,但又不能算到(INF,0)才會讓INF-1。
POJ 3250 題解圖.jpg

AC code:
//By SCJ
//POJ 3250
#include<iostream>
#include<stack>
using namespace std;
#define endl '\n'
#define INF 2000000000
int main()
{
//ios::sync_with_stdio(0);
//cin.tie(0);
int n;cin>>n;
long long ans=0;
stack<pair<int,int>> s;
s.push(make_pair(INF,0));
for(int i=1;i<=n;++i)
{
int tp;cin>>tp;
while(tp>=s.top().first) ans+=(i-s.top().second-1),s.pop();
s.push(make_pair(tp,i));
}
while(s.size()>1)
{
ans+=(n-s.top().second);s.pop();
}
cout<<ans<<endl;
}
/*
6
5 2 4 2 6 1
*/