2020年04月12日個人賽

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;
}