Codeforces Round 573 (Div.1) 题解

这场怎么说呢……有喜有悲吧。

开场先秒了 A。看到 B，感觉有点意思，WA 了 2 发后也过了。

此时还在 rk 前 200。

开 C，一看就不可做。跟榜，切 D 人数是 C 的两倍。

开 D。一眼感觉很 SB，然后就想了个假做法，WA 了 3 发。

1:10 时开始重构。再 WA1 发。结果 WA 了 4 发，才过掉。

怎么全世界的 D 都比我高分……

system test 前 predictor 说我的 rating 变化是……0。顿时很慌。

幸好 B 题 FST 了一片（DQ 和 deco 也 FST 了），rk 从 350+ 翻到了 320+。

最后 rating+=8。我还是太菜了……

A

直接模拟即可。每次找到最小的还没被删的东西，看看能删到哪里。可以 $O(m)$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int m,ans;

ll n,k,p[maxn];

int main(){

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

    FOR(i,,m) p[i]=read();

    FOR(i,,m){

        ll at=(p[i]-i+k)/k;

        int j=i;

        while(j<=m && p[j]-i+<=at*k) j++;

        j--;

        i=j;ans++;

    }

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

}

B

先判先手能不能走第一步：

$0$ 出现了至少两次，不行。
有数出现了至少三次，不行。
有数（$x$）出现了至少两次，且满足条件的 $x$ 不止一个，不行。
有数（$x$）出现了至少两次，且 $x-1$ 也出现了，不行。（这个情况 pretest 没有，所以 FST 了一片）、
否则就可以。

如果先手能走第一步，那么可以证明最后状态肯定是 $0$ 到 $n-1$ 的一个排列。判下奇偶性就可以了。

时间复杂度 $O(n\log n)$，因为要排序/map。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,a[maxn];

bool hhh;

ll s;

int main(){

    n=read();

    FOR(i,,n) s+=a[i]=read();

    sort(a+,a+n+);

    if(!a[] && a[]==a[]) return puts("cslnb"),;

    FOR(i,,n-) if(a[i]==a[i-] && a[i]==a[i+]) return puts("cslnb"),;

    FOR(i,,n-) if(a[i]==a[i+] && a[i]==a[i-]+) return puts("cslnb"),;

    FOR(i,,n-) if(a[i]==a[i+]){

        if(hhh) return puts("cslnb"),;

        hhh=true;

    }

    puts((s-1ll*n*(n-)/)&?"sjfnb":"cslnb");

}

C

太神仙了吧……先咕着。

D

全部离散化。

枚举最小的 $y=y'$。那么只用考虑所有在 $y=y'$ 上及其上方的点。

假设 $y=y'$ 的点有 $(x_1,y'),(x_2,y')\dots(x_k,y')$，那么这些答案的和就是 $f(cnt(1,szx,y'))-f(cnt(1,x_1-1,y'))-f(cnt(x_k+1,szx,y'))-\sum\limits_{i=1}^{k-1}f(cnt(x_i+1,x_{i+1}-1,y'))$。

注意，离散化过了，离散化后所有点的最大 $x$ 坐标是 $szx$。$f(x)=\frac{x(x+1)}{2}$，也就是长度为 $x$ 的区间有多少个子区间。$cnt(l,r,a)$ 表示 $x$ 坐标在 $[l,r]$ 的点中有几个的 $y$ 坐标 $\ge a$。

（建议画图理解）

可以上扫描线+树状数组。从上往下扫。树状数组维护哪些列上有点。$cnt(l,r,y')$ 就是个区间求和。每次对于每个点，如果它所在的列还没被加入树状数组中，加入。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,x[maxn],y[maxn],tmpx[maxn],tmpy[maxn],szx,szy,b[maxn],cnt[maxn];

vector<int> xs[maxn];

ll ans;

void update(int p,int v){

    for(int i=p;i<=szx;i+=i&-i) b[i]+=v;

}

int query(int p){

    int s=;

    for(int i=p;i;i-=i&-i) s+=b[i];

    return s;

}

int query(int l,int r){

    if(l>r) return ;

    return query(r)-query(l-);

}

int main(){

    n=read();

    FOR(i,,n) tmpx[i]=x[i]=read(),tmpy[i]=y[i]=read();

    sort(tmpx+,tmpx+n+);szx=unique(tmpx+,tmpx+n+)-tmpx-;

    sort(tmpy+,tmpy+n+);szy=unique(tmpy+,tmpy+n+)-tmpy-;

    FOR(i,,n) x[i]=lower_bound(tmpx+,tmpx+szx+,x[i])-tmpx,y[i]=lower_bound(tmpy+,tmpy+szy+,y[i])-tmpy;

    FOR(i,,n) xs[y[i]].push_back(x[i]);

    FOR(i,,szy) sort(xs[i].begin(),xs[i].end());

    ROF(i,szy,){

        FOR(j,,(int)xs[i].size()-) if(++cnt[xs[i][j]]==) update(xs[i][j],);

        int len=query(,szx);

        ans+=1ll*len*(len+)/;

        len=query(,xs[i][]-);

        ans-=1ll*len*(len+)/;

        len=query(xs[i][(int)xs[i].size()-]+,szx);

        ans-=1ll*len*(len+)/;

        FOR(j,,(int)xs[i].size()-){

            len=query(xs[i][j]+,xs[i][j+]-);

            ans-=1ll*len*(len+)/;

        }

    }

    cout<<ans<<endl;

}

E

PB 说这是个 SB 题，没有思维难度，比 C 还简单……我说我不会还被喷了 QwQ

回来再说吧。

F

其实说句实话，这辈子都没想过改出 Div.1 的 F。不管了。

巴特西

Codeforces Round 573 (Div.1) 题解

A

B

C

D

E

F

最新文章

热门文章