Educational Codeforces Round 93 (Rated for Div. 2)A~D题解

发布于 2020-08-15  0 次阅读


A. Bad Triangle

题目大意:

给你一个长度为n的数组,让你从中选出i , j , k ,满足1 ≤ i < j < k ≤ n ,其中ai , aj , ak 不能构成一个三角形

思路:

将序列排序后直接判断第一个,第二个和最后一个能不能构成三角形即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=5e4 +10;
int n, a[N];
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    if(a[1]+a[2]<=a[n]) cout<<"1 2 "<<n<<endl;
    else                cout<<"-1"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Substring Removal Game

题目大意:

给你一个长度为n的0,1字符串,两个人轮流选择其中不少于一位的连续子序列,得分为所选子序列中1个数的总和,你先选

思路:

求出其中每个连续的1的区间的1的个数,排序后隔一个取一个即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=109;
string s;
int a[N];

bool cmp(int a, int b){ return a>b;}

void solve(){
    cin>>s;
    int ans=0, cnt=0;
    for(int i=0; i<s.length(); i++){
        if(s[i]=='1') ans++;
        else if(s[i]=='0'){
            a[cnt++]=ans;
            ans=0;
        }
    }
    
    if(ans!=0)  a[cnt++]=ans;
    sort(a,a+cnt, cmp);
    int sum=0;
    for(int i=0; i<cnt; i+=2){
        if(a[i]==0) break;
        sum+=a[i];
    }
    cout<<sum<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Good Subarrays

题目大意:

image 17

思路:

在求前缀和的时候将每个元素都-1,题目就变成了子区间长度=和——> 有多少个子区间的和为0
就能想到根据前缀和的性质,两个前缀和相等的话,区间中的和肯定是为0,也就是说任意两个相等的前缀和之间都有一个区间的和为0,求出相同的前缀和的个数,贡献即为t e p ∗ ( t e p − 1 ) / 2(其中tep为个数)
注:提前记录一下0的个数为1(因为-1后前缀和为0的区间直接满足)

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, pre[N];
string s;
map<int,int> mp;
void solve(){
    cin>>n;
    cin>>s;
    mp.clear();
    mp[0]++;
    for(int i=1; i<=s.length(); i++){
        pre[i]=pre[i-1]+(s[i-1]-'0')-1;
        mp[pre[i]]++;
    }
    int ans=0;
    for(auto t:mp){
        int tep=t.second;
        ans+=tep*(tep-1)/2;
    }
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

D. Colored Rectangles

题目大意:

有R,G,B三种颜色的棍子
现在告诉你每种棍子长度的对数和每对的长度,让你用两种不同颜色的棍子对围成矩形
求每个矩形加起来的最大值

思路:

排序后直接dp就行了,三维dp,每位分别表示当前用的棍子的位置

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=209;
int R, G, B;
int r[N], g[N], b[N];
int dp[N][N][N];
void solve(){
    cin>>R>>G>>B;
    for(int i=0; i<R; i++)  cin>>r[i];
    for(int i=0; i<G; i++)  cin>>g[i];
    for(int i=0; i<B; i++)  cin>>b[i];
    sort(r, r+R); sort(g, g+G); sort(b, b+B);
    for(int i=0; i<=R; i++){
        for(int j=0; j<=G; j++){
            for(int k=0; k<=B; k++){
                if(i&&j)    dp[i][j][k]=max(dp[i][j][k], dp[i-1][j-1][k]+r[i-1]*g[j-1]);
                if(j&&k)    dp[i][j][k]=max(dp[i][j][k], dp[i][j-1][k-1]+g[j-1]*b[k-1]);
                if(i&&k)    dp[i][j][k]=max(dp[i][j][k], dp[i-1][j][k-1]+r[i-1]*b[k-1]);
            }
        }
    }
    cout<<dp[R][G][B]<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}


平平无奇的在校大学生