社区讨论

萌新WA:为什么我只有80分!为什么没有数据下载!

P3718[AHOI2017初中组] alter参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6z11ja
此快照首次捕获于
2025/11/20 13:08
4 个月前
此快照最后确认于
2025/11/20 13:08
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define ini(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define F(x,y,z) for(register int x=y;x<=z;++x)
#define D(x,y,z) for(register int x=y;x>=z;--x)
#define cint const int&
using namespace std;
const int MAXN=static_cast<int>(1e5)+100;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int oo=0x3f3f3f3f;
const int MOD=2e5+1;
#define int long long
inline int read()
{
  int x = 0, y = 1, c = getchar();
  while (c>'9' || c<'0')
  {
    if (c == '-')y = -1;
    c = getchar();
  }
  while (c >= '0'&&c <= '9')
  {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * y;
};
struct node{
    int data,pos;
    node(int d=0,int p=0):data(d),pos(p){}	
};
class Deque{
    private:
    //#define node int
    node que[MAXN];
    int head,tail,_size;
    
    public:
    Deque():head(0),tail(0),_size(0){};
    void push_back(const node&i){
        que[tail++]=i;
        _size++;
        tail%=MOD;
    }
    void push_front(const node&i){
        que[--head]=i;
        _size++;
        head%=MOD;
    }
    void pop_back(){
        tail--;
        _size--;
        tail%=MOD;
    }
    void pop_front(){
        head++;
        _size--;
        head%=MOD;
    }
    node front(){
        return que[head];
    }
    node back(){
        return que[tail-1];
    }
    int size(){
        return _size;
    }
    bool empty(){
        return !_size;
    }
    //#undef node
};
Deque q; 
int light[MAXN];
inline bool check(cint len,cint n,cint k){
	int cnt=0,pk=0,left=1;
	F(i,1,n){
		if(light[i]==light[left]){
			cnt++;
		}else{
			cnt=1;
			left=i;
		}
		if(cnt>len){
			pk++;
			cnt=0;
			left=i+1;
		}
		if(pk>k){
			return false;
		}
	}
	if(pk>k){
		return false;
	}
	return true;
}
signed main(){
	int n=read(),k=read();
	F(i,1,n){
		int c=getchar();
		while(c>'Z'||c<'A'){
			c=getchar();
		}
		light[i]=(c=='N')?1:0;
	}
	int mid,left=0,right=MAXN;
	while(left<right){
		mid=(left+right)>>1;
		if(check(mid,n,k)){
			right=mid;
		}else{
			left=mid+1;
		}
		//cout<<left<<" "<<right<<endl;
	}
	printf("%lld",right);
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...