2020年04月12日个人赛

0
10

A – Balloons

题意:本题的题意比较简单,简单说就是分数字,使得A得到的数字之和大于B得到的数字之和,然后输出分给A的数字的下标。

题解:要注意特判n==1和n==2的情况,属于签到题。

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    int n;
    cin>>n;
    int num[20]= {0};
    int sum=0;
    for(int i=1; i<=n; i++) {
        cin>>num[i];
        sum=sum+num[i];//总数
    }
    if(n==1) {
        cout<<-1<<endl;
    } else if(n==2) {
        if(num[1]==num[2]) {
            cout<<-1<<endl;
        } else {
            cout<<1<<endl;
            cout<<1<<endl;
        }
    } else { //大于等于 3
        int su=0;
        int i;
        int f=0;
        for(i=1; i<=n; i++) {
            su=su+num[i];
            sum=sum-num[i];
            if(su!=sum&&sum!=0&&su!=0) {
                f=1;
                break;
            }
        }
        if(f==1) {
            cout<<i<<endl;
            for(int j=1; j<=i; j++) {
                cout<<j;
                if(j<i) {
                    cout<<" ";
                }
            }
            cout<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

B – Cutting

题意:这一题也比较简单,题目给你一个长度为n的数组,两个数之间可以“切断”,代价是两个数的差的绝对值。

题解:这一题的解法有几种,这里我是用背包(0-1)写的,关键是判断那两个数之间可以“切”一刀,代价就作为消耗,获的得利益就视为“1”,这样看,就是一道“0-1背包”的裸题。

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int n,B;
    cin>>n>>B/*这相当于一个总的体积*/;
    int num[250]={0};
    int jnum=0,onum=0;
    for(int i=0;i<n;i++){
        cin>>num[i];
        if(num[i]%2==0){
            onum++;
        }else{
            jnum++;
        } 
    }//数据输入完毕,下面开始处理数据
    int t=0;//记录数量
    int V[200]={0},W[200]={0};
    int tj=0,to=0;//分贝表示前面的奇数与偶数的数量 
     for(int i=0;i<n;i++){//栏隙 
        if(i+1<n){
            if(num[i]%2==0){
                to++;
            }else{
                tj++;
            }
            if((tj==to)&&((jnum-tj)==(onum-to))){
                W[t]=1;
                V[t++]=abs(num[i]-num[i+1]);
                tj=0;
                to=0;
            }
        }
    }        
    int dp[500]={0};
    for(int i=0;i<t;i++){
        for(int j=B;j>=V[i];j--){
            dp[j]=max(dp[j],dp[j-V[i]]+1);
        }
    }
    cout<<dp[B]<<endl;
    return 0;
}

D – Sonya and Hotels

题意:这道题大概意思是讲,给你一串数字,在数字之间插入一个数,要求这个数和它相邻的数的差的绝对值=d,问存在几个这样的插入点。

题解:这题比较简单,这里我们求相邻两个数的差,若差>2*d的话,就可以插入2个,差=2*d,可以插入一个,注意最后两个端点处各一个。

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    ll n,d;
    cin>>n>>d;
    int temp,p;
    cin>>temp;
    ll ans=0;
    for(int i=1;i<n;i++){
        cin>>p;
        if(p-temp-2*d>0){
            ans++;
            ans++;
        }else if(p-temp-2*d==0){
            ans++;
        }
        temp=p;
    }
    cout<<ans+2;

    return 0;
}

E – Sonya and Exhibition

题意:这一题就比较有意思了,大概意思是说,有n朵花,可以是百合or玫瑰,有m个人,给出他们的观察区间,求他们的,美丽值(等于玫瑰花的数量*百合花的数量)的总和,求这个美丽值的最大值。

题解:这一题的关键就是要知道要使单个美丽值最大,就得使区间中的两种花的数量相当,还有一个坑就是他这里给出了有m个人,如果说只有一个人的话,这一点就很好发现了。在这里,我们只需要使两种花的交替出现就好了。(就像一个脑筋急转弯似的)

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    ll n,m;
    cin>>n>>m;
    ll li,ri;
    char ptr[10000];
    for(int i=0;i<m;i++){
        cin>>li>>ri;
    }
    for(int i=0;i<n;i++){
        if(i%2==0){
            cout<<1;
        }else{
            cout<<0;
        }
    }

    return 0;
}

F – Sonya and Robots

题意:这一题题意也比较简单,基本要求就是,给你一串有n个元素的int数组,要你从中寻找两个数,将这两个数字分别赋值给两辆小车,并使它们相向运动,在数组中当遇到与本车上相同的数字时,就停止运动,当两辆车的最终的相对位置发生变化时,车子就损坏了,问从这个数组中取出的数的对数,有多少多数可以使车子不损坏。

题解:这道题本质上也是一道简单题,但比赛的时候没看,大概看了也不会写,网上的题解给出的是记录每辆车它的左边有多少种车的数量,再将它们相加即可,可惜我的想法刚好相反,我想到的是记录它的右边的车的种类的数量,最后还没写出来,算是一个思维上的教训吧。

代码:

#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
#define ll long long
const int N=100005;
using namespace std;
int arr[N],vis[N];
set<int> st;
int main(){
    int n,t;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t;
        vis[t]=st.size();
        st.insert(t);
    }
    ll sum=0;
    for(int i=0;i<=100000;i++){
        sum=sum+vis[i];
    }
    cout<<sum<<endl;
    return 0;
}

<

发布回复

请输入评论!
请输入你的名字