【arc101】比赛记录

　　这场还好切出了D，rt应该能涨，然而这场的题有点毒瘤，700分的D没多少人切，更别说EF了。（暴打出题人）既然这样，干脆就水一篇博客，做个简单的比赛记录。

C - Candles

　　这题是一道一眼题，花了大约30s看懂题意，然后就想到做法开始敲。

　　首先先把蜡烛的坐标从小到大排序，我们要点亮的蜡烛一定在一个区间里，因此若我们要点亮区间$ [i,i+k) $的蜡烛我们可以这么走：先走到蜡烛$ i $和$ i-k+1 $中较近的一根，然后再走向另一根，并把途径的蜡烛全部点亮。这样的花费是$ \min(|x_i|,|x_{i+k-1}|)+x_{i+k-1}-x_i $。于是扫一遍顺便维护最小值答案即可。

　　然而我因为括号有点多，敲错了一个傻逼错误，调了快10min才调出来。。QAQ

代码：（时间复杂度$ O(n \log(n)) $）

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define ull unsigned long long

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define lowbit(x) (x& -x)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define eps 1e-18

#define maxn 1000010

inline ll read(){ll tmp=; char c=getchar(),f=; for(;c<''||''<c;c=getchar())if(c=='-')f=-; for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-''; return tmp*f;}

inline ll power(ll a,ll b){ll ans=; for(;b;b>>=){if(b&)ans=ans*a%mod; a=a*a%mod;} return ans;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;}

using namespace std;

int a[maxn];

int n,k;

int main()

{

    n=read(); k=read();

    for(int i=;i<=n;i++)a[i]=read();

    sort(a+,a+n+);

//    for(int i=1;i<=n;i++)printf("%d %d\n",i,a[i]);

    int ans=inf;

    for(int i=k;i<=n;i++)

        ans=min(ans,min(abs(a[i]),abs(a[i-k+]))+a[i]-a[i-k+]);

    printf("%d\n",ans);

    return ;

}

arc101C

D - Median of Medians

　　感觉我思想江化了，总是在想怎么快速求出以某个数为中位数的区间个数，推了一堆式子也没搞出来。最后看到hjw巨佬一句“二分答案”，方如醍醐灌顶地想出了解法。（orzhjw!!!）

　　首先我们先二分最后序列的中位数。设$ tot $为中位数$>= mid $的区间个数，若中位数序列的中位数$>= mid $，则有$ tot>=\lfloor \frac{n(n+1)}{4} \rfloor $。

　　那么如何求$ tot $？

　　我们另外构造一个序列$ b $，当$ a_i>=mid $时$ b_i=1 $，否则 $ b_i=-1 $。那么若区间$ [l,r] $的中位数$ >= mid $，则有$ \sum_{i=l}^{r} b_i>mid $，于是我们求出序列$ b $的前缀和序列$ sum $，那么问题就变成了求满足$ l<r $且$ sum[r]-sum[l]>=0 $的数对$ (l,r) $数量$ (0<=l,r<=n) $，这个问题可以用与求逆序对数量相似的方法解决。蒟蒻我就直接上树状数组了。

代码：（时间复杂度$ O(n \log^2(n) $）

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define ull unsigned long long

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define lowbit(x) (x& -x)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define eps 1e-18

#define maxn 100010

inline ll read(){ll tmp=; char c=getchar(),f=; for(;c<''||''<c;c=getchar())if(c=='-')f=-; for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-''; return tmp*f;}

inline ll power(ll a,ll b){ll ans=; for(;b;b>>=){if(b&)ans=ans*a%mod; a=a*a%mod;} return ans;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;}

using namespace std;

int bit[*maxn];

int a[maxn];

int n;

void add(int x,int k){for(;x<=*n;x+=lowbit(x))bit[x]+=k;}

int getsum(int x){int sum=; for(;x;x-=lowbit(x))sum+=bit[x]; return sum;}

int check(int mid)

{

    for(int i=;i<=*n;i++)bit[i]=;

    ll tot=,sum=;

    add(n,);

    for(int i=;i<=n;i++){

        sum+=(a[i]>=mid?:-);

        tot+=getsum(sum+n);

        add(sum+n,);

    }

//    printf("%d %lld\n",mid,tot);

    return tot>=1ll*n*(n+)/;

}

int main()

{

    n=read();

    int mx=-inf,mn=inf;

    for(int i=;i<=n;i++){

        a[i]=read();

        mx=max(mx,a[i]); mn=min(mn,a[i]);

    }

    int l=mn,r=mx;

    while(l<r){

        int mid=(l+r+)>>;

        if(check(mid))l=mid;

        else r=mid-;

    }

    printf("%d\n",l);

}

arc101D

E - Ribbons on Tree

　　以后填吧。。。

F - Robots and Exits

　　同上。。。

巴特西

【arc101】比赛记录

最新文章

热门文章