Educational Codeforces Round 93 (Rated for Div. 2)

Educational Codeforces Round 93 (Rated for Div. 2)

A. Bad Triangle

input

3
7
4 6 11 11 15 18 20
4
10 10 10 11
3
1 1 1000000000

output

2 3 6
-1
1 2 3

Note

In the first test case it is impossible with sides . Note, that this is not the only correct answer.

In the second test case you always can construct a non-degenerate triangle.

题意：

在非递减序列中找坏三角形。

思路：

由于是非递减的序列，直接特判

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
ll a[maxn];
bool check(ll x, ll y, ll z) {
    if (x + y <= z || x + z <= y || y + z <= x)
        return false;
    return true;
}
void solve() {
    int n; cin >> n;
    bool flag = false;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    if (!check(a[1], a[2], a[n])) {
        cout << 1 << " " << 2 << " " << n << endl;
    }
    else if (!check(a[1], a[n - 1], a[n]))
        cout << 1 << " " << n - 1 << " " << n << endl;
    else cout << "-1" << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while (t--)solve();
}

B. Substring Removal Game

题意：

Alice 和 Bob 又在玩游戏了，给出一个0，1构成的字符串，问在每个人都想得到最多分的情况下，Alice能得多少分（删去1的个数 = 所得分数）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
ll a[maxn];
bool check(ll x, ll y, ll z) {
    if (x + y <= z || x + z <= y || y + z <= x)
        return false;
    return true;
}
void solve() {
    string s;cin >> s;
    vector<int>q;
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '1')cnt++;
        else {
            if (cnt == 0)continue;
            q.push_back(cnt);
            cnt = 0;
        }
    }
    q.push_back(cnt);
    cnt = 0;
    sort(q.begin(), q.end());
    for (int i = q.size() - 1; i >= 0; i -= 2)
        cnt += q[i];
    cout << cnt << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while (t--)solve();
}

C. Good Subarrays

题意：

给定一个个元素的序列a,求满足的区间个数.

#include<bits/stdc++.h>
using namespace std;int T,n;
string s;map<int,int>mp;
int main(){
    cin>>T;
    while(T--){mp.clear(); 
        cin>>n>>s;mp[0]++;
        long long ans=0,sum=0;
        for(int i=0;i<n;i++){
            sum+=s[i]-'1'; 
            ans+=mp[sum];mp[sum]++;
        }
        cout<<ans<<endl;
    }
}

D. Colored Rectangles

Examples

input

1 1 1
3
5
4

output

20

input

2 1 3
9 5
1
2 8 5

output

99

input

10 1 1
11 7 20 15 19 14 2 4 13 14
8
11

output

372

题目大意:给定若干个红色,绿色,蓝色的一对长度一样的棍子.问用这些棍子组成的颜色不同的矩形的面积的最大总和是多少.注意不能把两个相同颜色的一对棍子拆成两个分别去用.其次颜色不同指的是在两个集合里选的两对棍子.

数据范围:

思路

首先比较容易想到的是贪心,但是这个题会跟棍子的数目有关,贪心会有很多问题,而且打补丁的方式是解决不了的.

考虑O(n3)O(n3)的DP,由于一共就三种元素,不妨就直接按定义直接设计状态:

状态:表示红色用了i个,绿色用了j个,蓝色用了k个的前提下得到的矩形面积总和的最大值.

入口:全为0即可,不需要额外处理.

转移:三种匹配方式直接枚举即可.

出口:所有值的最大值.

注意点的话，防止int爆掉吧

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 205;
int r[N],g[N],b[N];
int f[N][N][N];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int R,G,B;cin >> R >> G >> B;
    for(int i = 1;i <= R;++i)    cin >> r[i];sort(r + 1,r + R + 1,greater<int>());
    for(int i = 1;i <= G;++i)    cin >> g[i];sort(g + 1,g + G + 1,greater<int>());
    for(int i = 1;i <= B;++i)    cin >> b[i];sort(b + 1,b + B + 1,greater<int>());
    int res = 0;
    for(int i = 0;i <= R;++i)
    {
        for(int j = 0;j <= G;++j)
        {
            for(int k = 0;k <= B;++k)
            {
                auto& v = f[i][j][k];
                if(i >= 1 && j >= 1)    v = max(v,f[i - 1][j - 1][k] + r[i] * g[j]);
                if(j >= 1 && k >= 1)    v = max(v,f[i][j - 1][k - 1] + g[j] * b[k]);
                if(i >= 1 && k >= 1)    v = max(v,f[i - 1][j][k - 1] + r[i] * b[k]);
                res = max(res,v);
            }
        }
    }
    cout << res << endl;
    return 0;
}

E. Two Types of Spells

Example

input

6
1 5
0 10
1 -5
0 5
1 11
0 -10

output

5
25
10
15
36
21