您的位置: 首页 > IT文章 > Educational Codeforces Round 93 (Rated for Div. 2)

Educational Codeforces Round 93 (Rated for Div. 2)

分类: IT文章 • 2022-05-10 13:23:04

题意，给你一个非递减的数组，问你里面有没有不能构成三角形的边，如果存在则输出，否则输出-1；

思路：非递减，说明刚开始两个加一块是最小的，如果后面存在比他们的和大的就肯定有三条边构不成三角形了，如果后面的比他们的和都要小，说明这个数组里面任意三条边都能构成三角形。

#include<bits/stdc++.h>
#include<map>
const int N=5e4+10;
using namespace  std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long a[N];
        for(int i=0; i<n; i++)
            cin>>a[i];
        long long ans=a[0]+a[1];
        int fla=0;
        int lo=0;
        for(int i=2; i<n; i++)
        {
            if(ans<=a[i])
            {
                fla=1;
                lo=i;
                break;
            }
        }
        if(fla==1)
            cout<<"1"<<" "<<"2"<<" "<<lo+1<<endl;
        else
            cout<<"-1"<<endl;
    }

    return 0;
}

View Code

Educational Codeforces Round 93 (Rated for Div. 2)

题意：两个人玩游戏，每次去掉一串1，每次得分是每次去掉的串中1的个数，问先手最多能获得的多少分。

思路：统计一下每个都是1的串里面含有1的个数，然后压入优先队列，（刚开始用的sort排序T掉了...）然后在从队列中取出来，在隔一次加一次就行了。

#include<bits/stdc++.h>
#include<map>
#include<queue>
const int N=100000+10;
using namespace  std;
int main()
{
    int t;
    cin>>t;
    priority_queue<int> q;
    while(t--){
        string s;
        cin>>s;
        int ans=0;
        int j;
        for( j=0; j<s.size(); j++){
            if(s[j]=='0')
                continue;
            else
                break;
        }
        for(int i=j; i<s.size(); i++)
        {
            if(s[i]=='0'){
                q.push(ans);
                ans=0;
            }
            else if(s[i]=='1'){
                ans++;
            }

        }
        if(ans!=0)
            q.push(ans);
        int sum=0;
        int flage=1;
        while(!q.empty()){
            int s=q.top();
            q.pop();
            if(flage%2==1)
            sum+=s;
            flage++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

View Code

Educational Codeforces Round 93 (Rated for Div. 2)

题意：有一个数组，数组中每个元素只包含0-9这10中数字。问有多少个子数组满足子数组和等于该子数组长度。

思路：把公式变形一下：假设 i = 4 , j = 6.那么就是要找a[4]+a[5]+a[6]=6 - 4 +1 = 3;

然后我让 a[4]-1+a[5]-1+a[6]-1=3-3=0；

所以我让每个数减1，就是问那些区间的和是0.也就是 Educational Codeforces Round 93 (Rated for Div. 2)

区间和为0有两种情况

1.如果sum [ i ]==0,就说明存在一个ans++；

2.如果sum[ i ]= =sum[ j ],这时候就要统计一下sum[ i ]出现的次数，就得出规律。如果一个数出现的次数是t，那么区间为0的个数是

t=t-1;
ans+=t*(1+t)/2;

0的时候单独计算一下就行了

ans+=t*(1+t)/2;  //t不用减1了

#include<bits/stdc++.h>
#include<map>
#include<queue>
using namespace  std;
typedef long long ll;
const int N=1e5+10;
int main()
{
    int t;
    cin>>t;
    map<ll,ll>q;
    queue<ll>p;
    while(t--){
        int sum[N],n,a[N];
        string s;
        q.clear();
        cin>>n;
        cin>>s;
        for(int i=0; i<n; i++){
            a[i]=s[i]-'0'-1;
        }
        sum[0]=a[0];
        p.push(sum[0]);
        q[sum[0]]++;
        for(int i=1; i<n; i++){
            sum[i]=sum[i-1]+a[i];
            if(q[sum[i]]==0){
                p.push(sum[i]);
            }
            q[sum[i]]++;
        }
        ll k=q[0];
        ll ans=k*(1+k)/2;
        while(!p.empty()){

            ll s=p.front();
            if(s==0){
                p.pop();
                continue;
            }
            s=q[s];
            s=s-1;
            ans+=s*(1+s)/2;
            p.pop();
        }
        cout<<ans<<endl;
    }
    return 0;
}

View Code

Educational Codeforces Round 93 (Rated for Div. 2)

相关推荐