Educational Codeforces Round 111 (Rated for Div. 2)

A. Find The Array

列出的一个：
1.1
2.1+1
3.1+2
4.1+3
5.1+3+1
。。。
9.1+3+5
10.1+3+5+1

会发现，其实就是要用公差为2，首项为1的等差数列表示一个数，如果小了就补上一个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int n;
inline void solve() {
    int cnt(0),x(1);
    cin>>n;
    while(x<=n) {
        n-=x; cnt+=1; x+=2;
    }
    if(n) cnt+=1;
    cout<<cnt<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

B. Maximum Cost Deletion

由乘法法则其实知道答案一定要加上，我们通过改变合并的次数来改变的数量。
其次，整个字符串中0相邻的段和1相邻的段数量之差小于等于1。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int n,a,b;
string s;
inline void solve() {
    int cnt(0);
    cin>>n>>a>>b>>s;
    s=" "+s;
    for(int i=1;i<=n;++i) if(s[i]!=s[i-1]) cnt+=1;
    if(b<0) cout<<a*n+(cnt/2+1)*b<<'\n';
    else cout<<(a+b)*n<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

C. Manhattan Subarrays

看完案例，以下标为x轴画图理解后，会发现如果有三个元素在原数组中不递增或者不递减就不符合条件。最直接的价值就是说，符合条件的连续子序列的个数不会超过4个，也就是告诉你可以暴力。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int n,a[maxn];
bool check(int l,int r) {
    for(int i=l;i<r;++i)
    for(int j=i+1;j<r;++j)
    for(int k=j+1;k<=r;++k) if((a[i]<=a[j]&&a[j]<=a[k])||(a[i]>=a[j]&&a[j]>=a[k])) return false;
    return true;
}
inline void solve() {
    int ans=-1;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1,x;i<=n;++i) {
        ans+=2;
        for(x=i+2;x<=n;++x)
            if(check(i,x)) ++ans;
            else break;
    }
    cout<<ans<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. Excellent Arrays

待补