AcWing第82場(chǎng)周賽題解

• A題
• • 題目鏈接
  • 題解
  • 復(fù)雜度分析
• B題
• • 題目鏈接
  • 題解
  • 復(fù)雜度分析
• C題
• • 題目鏈接
  • 題解
  • 復(fù)雜度分析

本次AcWing周賽主要還是要考察細(xì)節(jié)，難度不大。

成都創(chuàng)新互聯(lián)長(zhǎng)期為上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為田家庵企業(yè)提供專業(yè)的網(wǎng)站制作、成都網(wǎng)站制作，田家庵網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。A題 題目鏈接

第k個(gè)數(shù)

題解

#include#include#include 
using namespace std;
int main() {int n, k;
    cin >>n >>k;
    vectora(n);
    for (int i = 0; i< n; i++) {cin >>a[i];
    }
    sort(a.begin(), a.end());
    cout<< a[n - k]<< endl;
    return 0;
}

復(fù)雜度分析

快排，時(shí)間復(fù)雜度 O ( n l o g n ) O(nlogn) O(nlogn)。

B題 題目鏈接

多米諾骨牌

題解

將各種情況考慮清楚即可。

#includeusing namespace std;
int main() {int n;
    cin >>n;
    int flag = 0;
    int ans = 0;
    int sum = 0;
    for (int i = 0; i< n; i++) {char c;
        cin >>c;
        if (c == '.') sum++;
        else {if (flag == 0 && c == 'L') {sum = 0;
                flag = -1;
            } else if (flag == 0 && c == 'R') {ans += sum;
                sum = 0;
                flag = 1;
            } else if (flag == -1 && c == 'R') {ans += sum;
                sum = 0;
                flag = 1;
            } else if (flag == 1 && c == 'L') {ans += sum % 2;
                sum = 0;
                flag = -1;
            }
        }
    }
    if (flag == 1) sum = 0;
    cout<< ans + sum<< endl;
    return 0;
}

復(fù)雜度分析

讀入同時(shí)進(jìn)行處理即可，時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)。

C題 題目鏈接

構(gòu)造序列

題解

根據(jù)題意，0必須單獨(dú)，1最多可以存在兩個(gè)，共有n個(gè)0和m個(gè)1，因而可以推出只有滿足
n - 1 ≤ \leq ≤ m ≤ \leq ≤ 2 × \times × (n + 1)
才能構(gòu)造出滿足規(guī)則的序列。

#includeusing namespace std;
int main() {int n, m;
    cin >>n >>m;
    if (m< n - 1 || m >2 * (n + 1)) cout<< -1<< endl;
    else {string s = "";
        if (n >m) s += "0";
        while (m >n && n) {s += "110";
            m -= 2;
            n -= 1;
        }
        while (m && n) {s += "10";
            m--;
            n--;
        }
        for (int i = 0; i< m; i++) {s += "1";
        }
        cout<< s<< endl;
    }
    return 0;
}

復(fù)雜度分析

明顯可以 O ( n ) O(n) O(n)的時(shí)間復(fù)雜度完成構(gòu)造。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：AcWing第82場(chǎng)周賽題解-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://weahome.cn/article/dcdgei.html