Educational Codeforces Round 151 (Rated for Div. 2)

A. Forbidden Integer

贪心的分情况讨论：x没被禁，全1，x被禁，分情况讨论：

如果k<=1，无解。 k=2时奇数，无解。 k>2时，有解。

void solve(){
    int n, k, x; cin >> n >> k >> x;
    if (x != 1){
        vi a(n, 1);print(yes); print(len(a));print(a);return;
    }
    else{
        if (k <= 1) {print(no); return;}
        else if (k == 2 && n & 1){print(no); return;}
        else {  print(yes);
            vi a;
            while (n > 3) {a.pb(2); n-= 2;}
            a.pb(n == 2 ? 2 : 3);
            print(len(a));
            print(a);
        }
    }
}

B. Come Together

二维空间中三个点ABC，求BC到A的最短路径中的最长公共距离。问题等价于：求A到BC的路径中最长公共距离。

当B和C有公共距离时，A一定是满足这个条件：A在BC上或者下方，A在BC左或者右方，直接计算即可。

void solve(){
    ll dis = 0;
    pi a, b, c; cin >> a.first >> a.second >> b.first >>  b.second >>c.first >>c.second;
    if (a.first >= max(b.first, c.first)) {dis += a.first - max(b.first, c.first);}
    else if (a.first <= min(b.first, c.first)) {dis += min(b.first, c.first) - a.first;}
    //print(dis);
    if (a.second >= max(b.second, c.second)) {dis += a.second - max(b.second, c.second); }
    else if (a.second <= min(b.second, c.second)) {dis += min(b.second, c.second) - a.second;}
    print(dis + 1);
}

最后dis+1是考虑了在a点汇合时的一个公共坐标

C. Strong Password

枚举字符串的时间复杂度是O(n * pow(m, 10))，必TLE。

于是问题转换为构造S中不出现的子串。

答案字符串的长度为m，对于0~m-1位置的字符，贪心地枚举每个位置上的字符的最远匹配距离。这个策略可以证明一定是最优解。

void solve(){
    string s; cin >> s;
    int m; cin >> m;
    string t1, t2;cin >>t1 >> t2;
    int rb = 0;
    lfor (i, 0, m - 1){
        int r = 0;
        if(t1[i] > t2[i]) swap(t1[i], t2[i]);
        while (t1[i] <= t2[i]){
            int t = s.find(t1[i], rb);
            if(t==-1){print(yes); return;}
            t ++;
            r = max(r, t);
            t1[i] ++;
        }
        rb = max(rb, r);
    }
    print(no);
}

D. Rating System

在数组求前缀和的过程中找到一个k值，当前缀和在做减法运算时，可以让前缀和不低于k。求前缀和最大的情况下的k值。

贪心策略：可以发现为了让最终前缀和最大，需要消除掉在计算过程中对前缀和影响最大的负数。于是问题转化为，贪心查找数组中连续区间的最小值（值是负数），然后记录这个区间前面的前缀和，就是答案。

void solve(){
    int n; cin >> n;
    vi a(n); liter(x, a) cin >> x;
    ll minn = 2e9;
    ll curmin = 0;
    ll sum = 0;
    ll ans = 0;
    ll presum = 0;
    lfor (i, 0, n - 1){
        curmin += a[i];
        if (cmin(minn, curmin)){        //全局最小值小于当前局部连续区间最小值
            ans = presum;
        }
        sum += a[i];
        if (cmin(curmin, 0ll)){         //当前局部连续区间最小值大于0，舍弃之前的区间，并记录当前的前缀和
            presum = sum;
        }
 
    }
    print(ans);
}