2020年04月19日個人賽

A - Buggy Sorting

題意：這個題意就是給你一個錯誤的排序方式，要求你在它的這個排序方式下判斷是否存在正確的運行結果。若存在正確的結果，則輸出-1，否則輸出一個例子說明是錯誤的。題目的輸入是元素的個數n。

題解：這一題比較有意思，很容易判斷出只有當n=1 or n=2時運行結果是正確的，其餘的情況都是錯誤的。這樣我們就構造出一個序列出來就可以了。

代碼：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<=2){
        cout<<-1;
    }else{
        for(int i=n;i>=1;i--){
            cout<<i;
            if(i!=1){
                cout<<" "; 
            }
        }
    }
    return 0;
} 

B - Increase and Decrease

題意：這一題的大概意思是給你一個長度為n的int序列。你可以選擇其中任意兩個數對其分別進行+1和-1操作，問在進行若幹次後，最多可存在多少個相同的數。

題解：對同一個數組裡面的兩個元素進行+1和-1操作，很容易想到的一點是它的元素和總是一定的，這是一個突破點。這裡我們判斷元素的和是否能被n整除，如果能，則最多的個數就是n(說明一定存在某種方式將所有的元素變為一樣的)，如果不能，就肯定存在一個餘數，這時，我們就可以捨去這個元素，對其他的元素進行操作。則此時的元素個數就是n-1。

代碼：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    int num[100005]={0};
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>num[i];
        sum=sum+num[i];
    }
    if(sum%n==0){
        cout<<n<<endl;
    }else{
        cout<<n-1<<endl;
    }
    return 0;
} 

E - Dividing Orange

題意：這一題的大概意思是k個人平均分n*k個橘子，特別的是每個人都有它們各自必須必須需要的一個橘子，其他的沒有要求。

題解：這一題也是比較簡單的(悔不當初)，

代碼：這裡我們只需要用一個vis數組記錄一下哪一個橘子被分了就可以，然後依次輸出應有數量的橘子即可(同時特別關註該人特別需要橘子的編號這個需要特別判斷一下)。

代碼：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    ll n,k;
    cin>>n>>k;
    int num[1000]={0};
    int vis[1000]={0}; 
    int t;
    for(int i=0;i<k;i++){ 
        cin>>vis[i];
        num[vis[i]]=1;
    }
    int len=0;
    for(int i=0;i<k;i++){
        len=0;
        cout<<vis[i]<<" ";
        len++;
        for(int j=1;j<=n*k;j++){
            if(len<n&&num[j]==0){
                cout<<j;
                num[j]=1;
                len++;
                if(len<=n-1){
                    cout<<" ";
                }
            }
        } 
        cout<<endl;
    } 
    return 0;
} 

F - Undoubtedly Lucky Numbers

題意：這一題的大概意思它定義了一種特別的數，其中這個數字包含的單個數字的種類的數量不超過2種，現在給你n需要你求出在[1,n]之中存在多少個這樣的數字。

題解：比賽想了半天就是沒看出這是一個dfs，這裡我們可以這樣想，我們遍歷[0,9]中全部的2種數字的組合，然後將它們去排列組合，小於n就放入set(可以去重)中，最後輸出就可以了。

知識點：dfs 排列組合

代碼：

#include<iostream>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
set<ll> st;
ll n;
void dfs(int a,int b,ll num){
    st.insert(num);
    ll ta=num*10+a;
    ll tb=num*10+b;
    if(ta&&ta<=n){
        dfs(a,b,ta);
    }
    if(tb&&tb<=n){
        dfs(a,b,tb);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            dfs(i,j,0);/*每個數字都是從0開始的*/
        }
    }
    cout<<st.size()-1;
    return 0;
}