swift's blog

swift's blog

题解 CF1111C 【Creative Snap】

posted on 2019-08-05 12:34:45 | under 题解 |

看了那么多大佬的线段树题解,本萌新瑟瑟发抖,那么就写一篇卡常能过的$dfs$题解吧

首先,对于每一段区间,我们可以用树状数组来维护其中的复仇者数量,然后讨论如何炸毁这段区间:

如果其中没有复仇者,直接炸毁即可

要不然把区间分成两段,枚举每一段是直接炸毁还是继续$dfs$下去,最后取答案的最小值即可

但是注意一下数据范围

$1≤n≤30$

这样树状数组一定会$MLE$的

那用$map$代替数组?

复杂度多了一个$log$,又$TLE$了

那么我们就要用一种神奇的数据结构了:tr1::unordered_map,它和map的用法一模一样,而且复杂度是$O(1)$的

我们这样就愉快的通过这道题了

code:

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#pragma GCC optimize(3)
using namespace std;

#define int long long
int n,k,A,B,ans,a[100002],l;
tr1::unordered_map<int,int>tt;
void add2(int s,int v){
    for(int i=s;i<=l+5;i+=(i&-i)){
        tt[i]+=v;
    }
}
int ask2(int s){
    int sum=0;
    for(int i=s;i;i-=(i&-i))sum+=tt[i];
    return sum; 
}
int work2(int l,int r){
    int xr=ask2(r),xl=ask2(l-1);
    if(xr-xl==0){
        return A;
    }
    if(l==r){
        return B*(xr-xl);
    }
    int mid=(l+r)/2;
    int a1=work2(l,mid),a2=work2(mid+1,r);
    int b1=B*(mid-l+1)*(ask2(mid)-xl),b2=B*(r-mid)*(xr-ask2(mid));
    if(b1==0)b1=1e8;
    if(b2==0)b2=1e8;
    return min(B*(r-l+1)*(xr-xl),min(a1+b2,min(b1+a2,a1+a2)));
} 
main(){
    scanf("%lld%lld%lld%lld",&n,&k,&A,&B);
    l=pow(2,n);
    for(int i=1;i<=k;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=k;i++){
        add2(a[i],1);
    }
    printf("%lld\n",work2(1,l));
    return 0;
}