[Codeforces] #418 (Div. 2)

題目連結：http://codeforces.com/contest/814

#A
k >= 2時一定是輸出Yes，至於k = 1時就只要比第 i 項有沒有小於 i-1 項。

#include <iostream>
#include <algorithm>
#define endl '\n'
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
int a[7122],b[7122];
int main(){
    int n,k;cin >> n >> k;
    for(int i = 0 ; i < n ; i++)cin >> a[i];
    for(int j = 0 ; j < k ; j++)cin >> b[j];
    if(k >= 2){cout << "Yes" << endl;return 0;}
    for(int i = 0 ; i < n ; i++){
        if(!a[i])a[i] = b[0];
        if(a[i] < a[i-1] && i){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

#B
有些人會用很多條件去判斷哪一格該放哪一個數字，但其實因為 a 序列和 b 序列皆和 p 序列差一個數字，而a != b，因此可以直接嘗試看看把a序列數字重複的那兩格擇一替換成缺少的那個數字，並檢查是否與 b 序列差一，差一的即為p序列。

#include <iostream>
#include <bitset>
#define endl '\n'
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
int a[1005],b[1005];
int n,ans,s,p1,p2;
int aa[1005];
bool check(int x){
    int tmp = 0;
    if(x){
        a[p1] = ans;a[p2] = s;
        for(int i = 1 ; i <= n ; i++)if(a[i] != b[i])tmp++;
    }else{
        a[p1] = s;a[p2] = ans;
        for(int i = 1 ; i <= n ; i++)if(a[i] != b[i])tmp++;
    }
    if(tmp > 1)return 0;
    for(int i = 1; i <= n ; i++)cout << a[i] << ' ';
    return 1;
}
int main(){jizz
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        if(aa[a[i]]){
            p1 = aa[a[i]];
            ans = a[i];
            p2 = i;
        }
        else aa[a[i]] = i;
    }
    for(int i = 1 ; i <= n ; i++)if(!aa[i])s = i;
    for(int i = 1 ; i <= n ; i++)cin >> b[i];
    for(int i = 0 ; i < 2; i++)if(check(i))return 0;
    return 0;
}

#C
酷，他的詢問次數比所有可能問的組合數還要高。
對於每一組詢問，我們可以枚舉其最長子序列的右界，其左界隨右界往右移有單調性，因此取最大值即可。
我們可以將答案存起來這樣之後問同樣組合時可以直接回答或是直接枚舉所有可能問的組合。

#include <iostream>
#include <bitset>
#include <string>
#define endl '\n'
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
int dp[26][1505];
int main(){jizz
    int n;cin >> n;
    string s;cin >> s;
    int q;cin >> q;
    for(char a = 'a'; a <= 'z'; a++){
        for(int k = 1; k <= n ; k++){
            int tmp = 0,l = 0;
            for(int j = 0 ; j < n ; j++){
                if(s[j] != a)tmp++;
                while(tmp > k){
                    if(s[l] != a)tmp--;
                    l++;
                }
                dp[a - 'a'][k] = max(dp[a - 'a'][k] ,(j-l+1));
            }
        }
    }
    while(q--){
        int x;char c;cin >> x >> c;
        cout << dp[c-'a'][x] << endl;       
    }
}

#D
既然要求面積最大，那半徑越大的就應該要加他的面積會比較好。
因此我們可以計算這個圓圈被幾個比他大的覆蓋著。
其值 = 0的就直接加上他的面積。
再來因為可以分成兩邊，所以值 = 1的也是加上他的面積，但值 = 2的就需要減掉她的面積，值 = 3的因為可以放在值 = 2的那片上面所以又可以加，因此可以歸納出若此圓圈被奇數或零個比他大的圓圈覆蓋就將答案加上他的面積，
反之則減。
至於怎麼判斷圓圈是否覆蓋，可以利用圓心距和兩圓半徑和去判斷。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const long double PI = acos(-1);
struct Ken{
    long long x,y,r;
}s[1005];
bool compare(Ken a,Ken b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < (a.r+b.r)*(a.r+b.r);
}
int main(){
    int n;cin >> n;
    for(int i = 0 ; i < n ; i++)cin >> s[i].x >> s[i].y >> s[i].r;
    sort(s,s+n,[](Ken a,Ken b){return a.r > b.r;});
    long double ans = 0;
    for(int i = 0 ; i < n ; i++){
        int tmp = 0;
        for(int j = i-1 ; j >= 0 ; j--)if(compare(s[i],s[j]))tmp++;
        if(!tmp)ans += s[i].r*s[i].r;
        else if(tmp & 1)ans += s[i].r*s[i].r;
        else ans -= s[i].r*s[i].r;
    }
    cout << fixed << setprecision(8) << ans*PI << endl;
}

#E
待編輯