这场怎么说呢……有喜有悲吧。
开场先秒了 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。不管了。