经过上一次的vp，发现自己还有很大不足，所以还在板刷div.1。
A
模拟即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,m,k,a[N];
void solve(){
read(n),read(m),read(k);
for(int i=1;i<=m;i++){
read(a[i]);
}
int pos=1,del=0,ans=0;
while(pos<=m){
ans++;
while(pos<=m){
++pos;
if((a[pos]-del-1)/k!=(a[pos-1]-del-1)/k){
break;
}
}
del=pos-1;
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
B
先考虑先手必败的情况。
如果有至少两个 \(0\) 先手或只有一个数且这个数为 \(0\)，先手必败。
如果有两对数一样或者有两个数 \(x\) 且有 \(x-1\)，先手必败。
对于剩下的情况，输的人操作前的局面必然为 \(0,1,2,\dots ,n-1\)，算之前操作了多少步，奇数则先手胜，偶数则后手胜。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,a[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
sort(a+1,a+n+1);
if(a[n]==0){
puts("cslnb");
return;
}
int cnt=0,s=a[n];
for(int i=1;i<n;i++){
if(a[i+1]==a[i]){
cnt++;
if(a[i]==0){
cnt++;
}
}
if((i!=1&&a[i+1]==a[i]&&a[i-1]==a[i]-1)||cnt>=2){
puts("cslnb");
return;
}
s+=a[i];
}
if((s-(n-1)*n/2)%2==1){
puts("sjfnb");
}
else{
puts("cslnb");
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
C
又一道博弈论，我也不知道为什么一场会有两道博弈论。
因为这题两个人的操作可以完全一样，所以当一个人不能获胜时，他会直接复制上一个人的操作，所以最后就变成了判断两个人能否一步获胜。
令 \(l_i\) 为 \(i\) 所在连续块的左端点，\(r_i\) 为 \(i\) 所在连续块的右端点。
若先手想要一步获胜，则他想操作的区间 \(\left[L,R\right]\) 必须满足除了区间 \(\left[L,R\right]\) 外所有棋子颜色相同。
若先手不能一步获胜，则他必然阻止后手获胜，因此后手想一步获胜的条件为无论先手操作哪个区间，后手都能获胜。所以对于所有的合法区间 \(\left[L,R\right]\)，都要满足 \(l_{L-1}=1\and r_{R+1}=n\)。因为先手已经不能获胜了，所以左右两个区间颜色会不同。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,k,l[N],r[N];
string s;
void solve(){
read(n),read(k);
cin>>s;
s=' '+s;
l[0]=l[1]=1;
r[n]=r[n+1]=n;
for(int i=2;i<=n;i++){
if(s[i]==s[i-1]){
l[i]=l[i-1];
}
else{
l[i]=i;
}
}
for(int i=n-1;i;i--){
if(s[i]==s[i+1]){
r[i]=r[i+1];
}
else{
r[i]=i;
}
}
for(int i=1;i<=n-k+1;i++){
int L=i,R=i+k-1;
if(l[L-1]==1&&r[R+1]==n&&(s[L-1]==s[R+1]||L==1||R==n)){
puts("tokitsukaze");
return;
}
}
if(n>2*k){
puts("once again");
return;
}
for(int i=2;i<=n-k;i++){
int L=i,R=i+k-1;
if(l[L-1]!=1||r[R+1]!=n){
puts("once again");
return;
}
}
puts("quailty");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout)
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
D
因为矩形是上面不封顶的，所以我们很自然想到将所有点以 \(y\) 为第一关键字，\(x\) 为第二关键字排序。
假定我们已经确定一个 \(y\) 值，令左右两边分别为无穷远。那么这个矩形内包含的 \(x\) 坐标种类是一定的，我们可以选择将一根线放在一个 \(x\) 坐标左侧，将另一根线放在前一根线右边某一个 \(x\) 坐标右侧。但如果随便放，重复的会有很多。我们可以从左往右选择右边那根线放的范围 \(\left[x,n\right]\)，但为了防止重复，要求出现 \((x,y)\) 这个点。令 \((x_1,y)\) 为距离 \((x,y)\) 最近的纵坐标为 \(y\) 的点，左边那个线只能出现在 \(X=x_1\) 右侧。很明显，左边线 \(x\in (-\infty,x_1]\) 的都被选过，最后用树状数组维护即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
struct node{
int x,y;
}p[N];
int x[N],y[N],n,cnt;
bool have[N];
bool cmp(node x,node y){
if(x.y==y.y){
return x.x<y.x;
}
return x.y>y.y;
}
int c[N];
int lowbit(int x){
return x&(-x);
}
void update(int x){
while(x<=cnt){
c[x]++;
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(p[i].x),read(p[i].y);
x[i]=p[i].x,y[i]=p[i].y;
}
sort(x+1,x+n+1);
cnt=unique(x+1,x+n+1)-x-1;
for(int i=1;i<=n;i++){
p[i].x=lower_bound(x+1,x+cnt+1,p[i].x)-x;
}
sort(p+1,p+n+1,cmp);
int ans=0;
for(int i=1,j;i<=n;i=j){
for(j=i;j<=n;j++){
if(p[j].y!=p[i].y){
break;
}
if(!have[p[j].x]){
update(p[j].x);
have[p[j].x]=1;
}
}
int lst=0;
for(int k=i;k<j;k++){
ans+=(query(cnt)-query(p[k].x-1))*(query(p[k].x)-query(lst));
lst=p[k].x;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}