2022牛客寒假算法基础集训营5 ADEGIJ

罚坐场

A.疫苗小孩

可以三种做法来写：

Sol.1 二分

1 1 1针和 0 0 0针的贡献都为 0 0 0，那么固定必打 1 1 1针以上，枚举这一针的位置 p o s pos pos(看作第二针)，然后二分找到离 p o s − k pos - k pos−k和 p o s + k pos + k pos+k最近的点，然后讨论计算贡献即可。

注意二分的边界，写丑了就挂了。。。

#include 
#define int long long
using namespace std;

const int N = 1e6 + 10;
int a[N], cnt;

string s;


inline void solve(){
    int n = 0; cin >> n >> s; s = '@' + s;
    for(int i = 1; i > k >> w >> q;
    for(int i = 1; i = 1){
            if(s[lloc] == '0') lans += w;
            else{
                int l = 0, r = i - 1;
                while(l > 1;
                    (a[mid]  k >> w >> q;

    for(int i = 1; i = 1; i--) mr[i] = (s[i] == '0' ? i : mr[i + 1]);
    
    int ans = 0;
    for(int i = 1; i  i) l = w - abs(abs(i - ml[pos]) - k) * q;
        if(mr[pos] && mr[pos] > i) r = w - abs(abs(i - mr[pos]) - k) * q;
        ll = max(ll, max(l, r)), pos = max(1ll, i - k), l = -1, r = -1;
        if(ml[pos] && ml[pos]  k >> w >> q;

    for(int i = 1; i = 1; i--) mr[i] = (s[i] == '0' ? i : mr[i + 1]);

    for (int i = 1; i