[TIOJ 1320] 雙子大廈 Twintower

作法：

題目就是要問，給定一個 d ，求「連續 d 個數的最大值」的最小值。而直接作很不好作，如果反過來考慮「最多有連續幾個建築物的高度 <= 某個給定的 h 」，那麼在給定要詢問的 d 之後就可以二分搜答案了。至於這個東西要怎麼算，從高到低依次考慮建築物們，一個一個把他們從 1~n 裡面砍掉，並且維護「還剩下哪些區間」，還有那些區間的長度的最大值，而需要記錄的 h 就是原本的建築物的高度們，因為只有那些高度值才有可能是答案。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=500000+10 ;
 
struct P
{
    int h,id ;
    bool operator < (const P &rhs) const
    {
        return h==rhs.h ? id<rhs.id : h>rhs.h ;
    }
}a[maxn];
 
struct seg
{
    int l,r ;
    bool operator < (const seg &rhs) const
    {
        return l==rhs.l ? r<rhs.r : l<rhs.l ;
    }
};
 
set<seg> st ;
map<int,int,greater<int> > lens ;
vector<pii> v ;
 
void Erase(int x)
{
    auto it=lens.find(x) ;
    if( !(--(it->S)) ) lens.erase(it) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].h) , a[i].id=i ;
    sort(a+1,a+n+1) ;
 
    st.insert((seg){1,n}) ;
    lens[n]++ ;
    for(int i=1;i<=n;i++)
    {
        if(i==1 || a[i].h!=a[i-1].h)
        {
            int maxl= lens.begin()->F , sz=v.size() ;
            if(sz && v[sz-1].S==maxl) v[sz-1].F=a[i].h ;
            else v.push_back(mkp(a[i].h,maxl)) ;
        }
        auto it=st.lower_bound((seg){a[i].id,n+1}) ; it-- ;
        int L=it->l , R=it->r ;
        st.erase(it) ; Erase(R-L+1) ;
        if(L==R) continue ;
        if(L==a[i].id) st.insert((seg){L+1,R}) , lens[R-L]++ ;
        else if(R==a[i].id) st.insert((seg){L,R-1}) , lens[R-L]++ ;
        else
        {
            st.insert((seg){L,a[i].id-1}) ;
            st.insert((seg){a[i].id+1,R}) ;
            lens[a[i].id-L]++ ;
            lens[R-a[i].id]++ ;
        }
    }
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int d ; scanf("%d",&d) ;
        int l=0 , r=v.size() ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(v[mid].S>=d) l=mid ;
            else r=mid ;
        }
        printf("%d\n",v[l].F) ;
    }
}
 

[TIOJ 1316] 晶片設計 Chips

作法：

題目簡單來說就是，有 n 條兩兩端點不重複的線段，要選出最多條使得沒有三條線段同時覆蓋一個點(端點也算)。如果問題的三改成二，也就是任兩條線段不交，那就可以先把有包含別人的線段都砍掉(顯然選他們不會比選裡面的線段好)，然後再從左到右 greedy 就好了。但這裡沒辦法這樣作，有包住別人的線段不一定沒用。

如果把問題反過來，考慮先把全部的線段都取過來，這時候有些點被 > 2 條線段覆蓋了，必須要把一些線段移除掉。而這個問題就可以用貪心解決了，首先看最左邊的不合法的點，那麼可以知道我們只要移除「左端點 <= 他且右端點衝得最遠」的線段，這會是最好的選擇，所以答案就是 n - 移除線段的數量。

這裡實作上應該可以到 O(nlogn)，維護還剩哪些線段之類的，不過因為 n 小小的所以我直接寫了 O(n^2) 的作法。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=8000+10 ;
 
int a[maxn] ;
int l[maxn],r[maxn],num[maxn] ;
bool used[maxn] ;
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=2*n;i++)
    {
        scanf("%d",&a[i]) ;
        if(!l[a[i]]) l[a[i]]=i ;
        else r[a[i]]=i ;
    }
 
    int now=2 ;
    for(int i=1;i<=2*n;i++)
    {
        if(i==l[a[i]]) now-- ;
        num[i]=now ;
        if(i==r[a[i]]) now++ ;
    }
 
    int ans=n ;
    for(int i=1;i<=2*n;i++) while(num[i]<0)
    {
        int M=0 , id ;
        for(int j=1;j<=i;j++)
            if(!used[a[j]] && j==l[a[j]] && r[a[j]]>M)
            M=r[id=a[j]] ;
        used[id]=1 ;
        for(int j=l[id];j<=r[id];j++) num[j]++ ;
        ans-- ;
    }
    printf("%d\n",ans) ;
}
 

[TIOJ 1293] I.送貨倉庫

作法：

這題用到的技巧之前有遇過類似的，例如 HOJ 86 - 接金幣，和 IOI 2007 - pairs ( HOJ 256 )，都是用到類似的座標變換手法。

如果定義的距離是曼哈頓距離的話( | x1-x2 | + | y1-y2 | )，就可以對 x , y 分開做了，並且他會等價於中位數的問題。所以大概會考慮一個座標變換，讓兩個點變換前的距離( 這個指題目定義的 ) 會等於兩個點變換後的曼哈頓距離，那麼就好做了。而這只要考慮 ( x , y ) -> ( x + y , x - y ) ，不難驗證他會滿足上面那件事。

但實際上還要多考慮一些東西，因為這樣會發現變換後的所有點 ( x , y ) 都會滿足 x , y 同為奇數或偶數，所以如果求出的答案坐標相加是奇數的話就會沒辦法對應回原坐標的點，所以在新座標平面上的最好的點不一定可行，答案可能會是次好的點。而我的解決方法是先把在新座標平面上的可能的點們找出來( 至多4個 )，如果他們坐標和是奇數，那就考慮他的上下左右四個點，加入候選人，但這樣沒辦法知道到底哪一個比較好，所以我直接再對每個候選人 O( n ) 算一次他的值，並更新答案。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
struct P
{
    int pos,val ;
    bool operator < (const P &rhs) const
    {
        return pos==rhs.pos ? val<rhs.val : pos<rhs.pos ;
    }
};
 
P x[maxn],y[maxn] ;
bool found ;
int n,ansx,ansy ;
LL ans ;
 
void solve(vector<int> &v,P *p)
{
    LL sum=0LL ;
    for(int i=1;i<=n;i++) sum+=p[i].val ;
    LL now=0LL ;
    for(int i=1;i<=n;i++)
    {
        now+=p[i].val ;
        if(sum%2 && 2*now>sum) { v.push_back(p[i].pos) ; break ; }
        else if(sum%2==0)
        {
            if(2*now==sum)
            {
                v.push_back(p[i].pos) ;
                v.push_back(p[i+1].pos) ;
                break ;
            }
            else if(2*now>sum)
            {
                v.push_back(p[i].pos) ;
                break ;
            }
        }
    }
}
 
LL cal(int x0,int y0)
{
    LL ret=0LL ;
    for(int i=1;i<=n;i++)
        ret+= ((LL)x[i].val)*
            (x0>=x[i].pos ? (LL)x0-x[i].pos : (LL)x[i].pos-x0 ) ,
        ret+= ((LL)y[i].val)*
            (y0>=y[i].pos ? (LL)y0-y[i].pos : (LL)y[i].pos-y0 ) ;
    return ret ;
}
 
bool better(int x0,int y0)
{
    if(!found) return 1 ;
    LL tmp=cal(x0,y0) ;
    if(tmp!=ans) return tmp<ans ;
 
    if(2*ansx!=x0+y0) return x0+y0<2*ansx ;
    if(2*ansy!=x0-y0) return x0-y0<2*ansy ;
    return 0 ;
}
 
void update(int x0,int y0)
{
    if(better(x0,y0))
        ansx=(x0+y0)/2 , ansy=(x0-y0)/2 ,
        ans=cal(x0,y0) , found=1 ;
}
 
main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            int a,b,t ; scanf("%d%d%d",&a,&b,&t) ;
            x[i]=(P){a+b,t} ; y[i]=(P){a-b,t} ;
        }
        sort(x+1,x+n+1) ;
        sort(y+1,y+n+1) ;
 
        found=0 ;
        vector<int> vx,vy ;
        solve(vx,x) ; solve(vy,y) ;
        for(auto i : vx) for(auto j : vy)
        {
            if((i+j)%2==0) update(i,j) ;
            else
            {
                update(i,j-1) , update(i,j+1) ;
                update(i-1,j) , update(i+1,j) ;
            }
        }
        printf("%d %d\n",ansx,ansy) ;
    }
}
 

[TIOJ 1305] 啊嘶起啦集合

作法：

以 merge 和 split 當基礎操作的 Treap ，因為忘記要怎麼用它來做插入和刪除，所以另外想了個作法@@，並且在插入的時候還要先判斷這個元素是不是已經在裡面了。

code :

#include<bits/stdc++.h>
using namespace std;
 
struct node
{
    node *l,*r ;
    int val,pri,size ;
    node(int v)
    {
        l=r=NULL ;
        val=v ; size=1 ;
        pri=rand() ;
    }
};
 
inline int lsize(node *u) { return u->l ? u->l->size : 0 ; }
inline int rsize(node *u) { return u->r ? u->r->size : 0 ; }
inline int size(node *u) { return u ? u->size : 0 ; }
inline void pull(node *u){ if(u) u->size = lsize(u)+rsize(u)+1 ; }
 
node *merge(node *a,node *b)
{
    if(!a || !b) return a ? a : b ;
    if(a->pri < b->pri)
    {
        a->r=merge(a->r,b) ;
        pull(a) ;
        return a ;
    }
    else
    {
        b->l=merge(a,b->l) ;
        pull(b) ;
        return b ;
    }
}
 
void split(node *u,node *&a,node *&b,int value)
{
    if(!u) { a=b=NULL ; return ; }
    if(u->val <= value)
    {
        a=u ;
        split(u->r,a->r,b,value) ;
        pull(a) ;
    }
    else
    {
        b=u ;
        split(u->l,a,b->l,value) ;
        pull(b) ;
    }
}
 
int getmax(node *u)
{
    return u->r ? getmax(u->r) : u->val ;
}
 
node *root ;
void insert(int x)
{
    node *a,*b ;
    split(root,a,b,x) ;
    if(a && getmax(a)==x) root=merge(a,b) ;
    else root= merge( merge(a,new node(x)) , b ) ;
}
 
void erase(node *&u,int value)
{
    if(!u) return ;
    if(u->val==value) u=merge(u->l,u->r) ;
    else if(u->val>value) erase(u->l,value) ;
    else erase(u->r,value) ;
    pull(u) ;
}
 
int kth(node *u,int k)
{
    if(lsize(u)+1==k) return u->val ;
    else if(lsize(u)+1>k) return kth(u->l,k) ;
    else return kth(u->r,k-lsize(u)-1) ;
}
 
main()
{
    srand(time(NULL)) ;
    root=NULL ;
    char s[100] ;
    int x ;
    while(scanf("%s%d",s,&x)!=EOF)
    {
        if(s[0]=='e') break ;
        if(s[0]=='i') insert(x) ;
        if(s[0]=='a')
        {
            if(x<1 || x>size(root)) printf("error\n") ;
            else printf("%d\n",kth(root,x)) ;
        }
        if(s[0]=='r') erase(root,x) ;
    }
}
 

[CF 521C] Pluses everywhere

這題是數學，但我一開始就想到很麻煩的作法，然後就爛掉了QQ

作法：

考慮 a_i 被實際當成的數值等於 a_i * 10^j 的時候，會被算到幾次，第一種可能是 i 的後面隔了 j 個之後緊接著一個加號，另一種可能是後面就是數列的尾了。如果是第一種可能，那麼剩下的 k-1 個加號就會被放在從 i 和 i+j 中間的以外的地方，因為 a_i 要乘的是 10^j ，所以他們中間不能有加號，所以這樣的選擇有 C( n - j - 2 , k - 1 ) 種，也就是這個部份的總和為

sigma( i = 1 ~ n ) sigma( j = 0 ~ n - i - 1 ) ( a_i * 10^j ) * C( n - j - 2 , k - 1 )

再注意到其實 j 頂多只到 n - k - 1 ，並且把兩個 sigma 交換後可以得到他等於

sigma( j = 0 ~ n - k - 1 ) sigma( i = 1 ~ n - 1 - j ) ( a_i * 10^j ) * C( n - j - 2 , k - 1 )

把兩個 sigma 交換的動作就像是如果現在要算一個方格表裡的元素總和，那麼可以先橫著加，再直著把那些加好的數加起來，或是先直著加再橫著加。另外至於為什麼內層的 i 是從 1 跑到 n - 1 - j ，可以把所有要求和的 ( i , j ) 都畫在坐標平面上，觀察他的規律就可以得到當 j 固定的時候 i 是從 1 跑到 n - 1 - j 了。

而內層的 sigma 可以直接加起來，這樣就變成等於

sigma( j = 0 ~ n - k - 1 ) ( S_i * 10^j ) * C( n - j - 2 , k - 1 )

其中 S_i = a_1 + ... + a_i。所以這個式子的值就能O( n ) 得到了。
( 註： C 的部分會用到 C( n+1,m ) = C( n , m ) * (n+1) / ( n-m+1 ) 這件事，而在模一個質數下的除法等於乘他的反元素，所以還要另外寫的求反元素的函數 )

另外，對於第二種情形( a_i 當作 a_i * 10^j 的時候後面就是數列的尾了 )，可以得到總和等於

sigma ( i = k+1 ~ n ) a_i * 10^( n - i ) * C( i - 1 , k )

所以也可以直接O(n)作了。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=100000+10 ;
 
LL power(LL x,int n)
{
    if(n==0) return 1LL ;
    if(n==1) return x ;
    LL tmp=power(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
LL inv(LL x)
{
    return power(x,MOD-2) ;
}
 
LL pw[maxn] ;
int a[maxn] ;
LL sum[maxn] ;
char s[maxn] ;
 
main()
{
    int n,k ; scanf("%d%d%s",&n,&k,s+1) ;
    for(int i=1;i<=n;i++)
        a[i]=s[i]-'0' ,
        sum[i]=sum[i-1]+a[i] ;
    pw[0]=1LL ;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*10%MOD ;
 
    LL ans=0LL , comb=1LL ;
    for(int i=k-1;i<=n-2;i++)
    {
        ans+=(sum[i+1]*pw[n-i-2]%MOD)*comb ;
        ans%=MOD ;
        comb=(comb*(i+1)%MOD)*inv(i-k+2)%MOD ;
    }
    comb=1LL ;
    for(int i=k+1;i<=n;i++)
    {
        ans+=(a[i]*pw[n-i]%MOD)*comb ;
        ans%=MOD ;
        comb=(comb*i%MOD)*inv(i-k)%MOD ;
    }
    printf("%I64d\n",ans) ;
}
 

[CF 521B] Cubes

這題寫的好卡阿@@......一個小時多才過=ㄦ=

作法：

可以想到就是維護「現在還有哪些方塊可以取」，所以上面沒有任何方塊的方塊可以被取，但我一開始想的時候漏了「這個方塊上面有方塊，但別人有幫他支撐所以可以拿掉」的情形，害我慌了一陣子(?)，所以對每個方塊要記錄上面和下面根他相鄰的有誰，還有每次拿掉一個方塊的時候，第一個是如果它底下有方塊沒有支撐東西了，就可以把它加進去，另外一個可能是被拿掉的方塊上面的方塊剩下一個支撐物了，所以他的左右鄰居可能會變成不能拿，必須要砍掉。

另外我一開始又看錯題目，以為是越大越好，原來是要一次取最大一次取最小OAO

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
#define LL long long
#define MOD 1000000009
using namespace std;
const int maxn=100000+10 ;
 
map<pii,int> mp ;
vector<int> v[maxn],v2[maxn] ;
int x[maxn],y[maxn],deg[maxn] ;
int dx[]={-1,0,1} , dy[]={1,1,1} , dx2[]={-2,-1,1,2} ;
set<int> s1 ;
set<int,greater<int> > s2 ;
bool done[maxn] ;
 
int cal(int id)
{
    int ret=0 ;
    for(auto i : v[id]) if(!done[i]) ret++ ;
    return ret ;
}
 
bool check(int x)
{
    if(!deg[x]) return 1 ;
    for(auto i : v2[x]) if(!done[i] && cal(i)==1) return 0 ;
    return 1 ;
}
 
void erase(int u)
{
    done[u]=1 ;
    for(auto i : v[u]) deg[i]-- ;
    s1.erase(u) ; s2.erase(u) ;
    mp.erase(mkp(x[u],y[u])) ;
 
    for(int i=0;i<4;i++)
    {
        auto it1=mp.find(mkp(x[u]+dx2[i],y[u])) ;
        if(it1!=mp.end())
        {
            if(check(it1->S)) continue ;
            auto it2=s1.find(it1->S) ;
            if(it2!=s1.end())
                s1.erase(it1->S) ,
                s2.erase(it1->S) ;
        }
    }
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]) ;
        mp[mkp(x[i],y[i])]=i ;
    }
 
    for(int i=0;i<n;i++) for(int j=0;j<3;j++)
    {
        int nx=x[i]+dx[j] , ny=y[i]+dy[j] ;
        auto it=mp.find(mkp(nx,ny)) ;
        if(it!=mp.end())
            v[it->S].push_back(i) ,
            v2[i].push_back(it->S) ,
            deg[i]++ ;
    }
 
    LL ans=0LL ;
    for(int i=0;i<n;i++) if(check(i))
        s1.insert(i) , s2.insert(i) ;
    for(int type=0;!s1.empty();type^=1)
    {
        int u= type==0 ? *s2.begin() : *s1.begin() ;
        erase(u) ;
        ans=(ans*((LL)n)+u)%MOD ;
        for(auto i : v[u]) if(!done[i] && check(i))
            s1.insert(i) , s2.insert(i) ;
    }
    printf("%I64d\n",ans) ;
}
 

[CF 521A] DNA Alignment

作法：

對於原題定義的式子，最外層的 sigma 可以先拿掉，因為不管 i 是多少，當 j 跑一圈後算出來的值都會一樣。再來則是注意到一個字母會被算到幾次，會發現每個在 s 裡的字母都會被算到「在 t 裡面且和他一樣的字母個數」那麼多個。所以如果 s 裡的 A,C,G,T 分別有 a,b,c,d 個，並設我們要找的 t 的四個字母分別有 x,y,z,w 個，所以我們要讓當 x+y+z+w = 定值(字串長度) 的時候， ax + by + cz + dw 的值最大。這邊就可以用調整法，如果 a,b,c,d 裡面有一個數嚴格小於另一個數，那小的那個乘的數可以直接把他往下調成 0 ，大的那個乘的數往上調，會讓整體的解更佳。所以重點只剩下那些出現次數最多的字母們了，而可以發現怎麼取都可以達到最大值，也就是在要求的 t 的每一位都可以任意放那些字母，也就是如果出現次數最多的字母有 k 個，那麼答案就是 k^n ，其中 n 是字串長度。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
 
LL power(LL x,int n)
{
    if(n==0) return 1LL ;
    if(n==1) return x ;
    LL tmp=power(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
char s[100000+10] ;
int a[4] ;
main()
{
    int n ; scanf("%d%s",&n,s) ;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='A') a[0]++ ;
        if(s[i]=='C') a[1]++ ;
        if(s[i]=='G') a[2]++ ;
        if(s[i]=='T') a[3]++ ;
    }
    int M=max(max(a[0],a[1]),max(a[2],a[3])) ;
    int num=0 ;
    for(int i=0;i<4;i++) if(a[i]==M) num++ ;
    printf("%I64d\n",power(num,n)) ;
}
 

[TIOJ 1254] 砲打皮皮2

作法：

題目就是要求最小包含圓的半徑，向上取整，之前有聽說有O(n)的隨機算法，但還沒看QQ 只想到O(n^3)的作法，感覺過不了，所以只好用爬山法唬爛(?)

簡單來說要找的東西是一個點(圓心)到所有點的距離的最大值最小，考慮隨機取一個點，往他的 8 方位跑 len 長度，如果答案變小了就更新，如果沒有更小的答案就把 len 除掉 2 ，一直做下去就可以了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=1000+10 ;
struct pt{DB x,y;};
 
pt operator - (const pt &a,const pt &b) { return (pt){a.x-b.x,a.y-b.y}; }
DB length(const pt &a) { return sqrt(a.x*a.x+a.y*a.y) ; }
 
int n,m ;
int dx[]={1,1,0,-1,-1,-1,0,1} ;
int dy[]={0,1,1,1,0,-1,-1,-1} ;
pt a[maxn*maxn] ;
 
DB cal(const pt &p)
{
    DB ret=0.0 ;
    for(int i=1;i<=m;i++) ret=max(ret,length(p-a[i])) ;
    return ret ;
}
 
main()
{
    while(scanf("%d%d",&n,&m)==2 && n+m)
    {
        DB x0=0.0,y0=0.0 ;
        for(int i=1;i<=m;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y) ,
            x0+=a[i].x , y0+=a[i].y ;
        x0/=m , y0/=m ;
        DB val=cal((pt){x0,y0}) ;
        for(DB len=1.0;len>1e-1;len*=0.5)
        {
            DB x1,y1 ;
            while(1)
            {
                bool found=0 ;
                DB nx,ny ;
                for(int i=0;i<8;i++)
                {
                    nx=x0+len*dx[i] , ny=y0+len*dy[i] ;
                    DB tmp=cal((pt){nx,ny}) ;
                    if(tmp>=val) continue ;
                    found=1 ; x1=nx ; y1=ny ;
                    val=tmp ;
                }
                if(!found) break ;
                else x0=x1 , y0=y1 ;
            }
        }
        val+=1e-5 ;
        printf("%d\n",int(ceil(val)+1e-5)) ;
    }
}