Codeforces #306 (div2)

11961 ワード
作成
A. Two Substrings
标题:この串に重複しないABとBAがあるかどうか
考え方:ABでBAを列挙して逆さまにもう一度やったり、ABとBAの位置を見つけてマッチングしたり
参考コード:
冗談を言ってfstになったコードを直すと醜いけど
//
//  Created by TaoSama on 2015-06-05
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

string s;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> s) {
        int x = s.find("AB");
        int y = s.find("BA");
        bool ok = false;
        if(~x) {
            while(~y) {
                //cout << x << ' '<<y<<endl;
                if(abs(x - y) >= 2) {
                    ok = true;
                    break;
                }
                //cout<<y<<endl;
                y = s.find("BA", y + 1);
            }
        }
        if(ok) {
            puts("YES");
            continue;
        }

        x = s.find("BA");
        y = s.find("AB");
        ok = false;
        if(~x) {
            while(~y) {
                //cout << x << ' '<<y<<endl;
                if(abs(x - y) >= 2) {
                    ok = true;
                    break;
                }
                //cout<<y<<endl;
                y = s.find("AB", y + 1);
            }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

B. Preparing Olympiad
問題の意味:問題を選んでlとrで直接difがxを上回らないようにします
考え方:直接dfs列挙またはバイナリ列挙
参考コード:
バイナリ列挙
//
//  Created by TaoSama on 2015-06-05
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int n, l, r, x, a[15];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n >> l >> r >> x) {
        for(int i = 0; i < n; ++i) cin >> a[i];
        int ans = 0;
        for(int i = 0; i < 1 << n; ++i) {
            int Min = INF, Max = -INF, sum = 0;
            for(int j = 0; j < n; ++j) {
                if(i >> j & 1) {
                    Min = min(Min, a[j]);
                    Max = max(Max, a[j]);
                    sum += a[j];
                }
            }
            //cout<<endl;
            //cout << Max << ' ' << Min << ' ' << sum << endl;
            if(sum >= l && sum <= r && Max - Min >= x) ++ ans;
        }
        cout << ans << endl;
    }
    return 0;
}

C. Divisibility by Eight
題意:与えられた列の8で割り切れるサブシーケンスを求める
考え方:1000倍数は必ず8で割り切れるから列挙して3位でいいn^3暴力も1000*n暴力ももちろんcf題解は8*nのdpを返した
参考コード:
1000*n暴力
//
//  Created by TaoSama on 2015-06-05
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

string s;
vector<int> G[10];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);
    while(cin >> s) {
        for(int i = 0; i < 10; ++i) G[i].clear();
        for(int i = 0; i < s.size(); ++i)
            G[s[i] - '0'].push_back(i);
        bool ok = false;
        for(int i = 0; i < 1000; ++i) {
            if(i % 8 == 0) {
                int x = i;
                char b[5]; sprintf(b, "%d", x);
                int n = strlen(b), last = -1;
                int can = 0;
                for(int j = 0; j < n; ++j) {
                    for(int k = 0; k < G[b[j] - '0'].size(); ++k) {
                        if(G[b[j] - '0'][k] > last) {
                            ++can;
                            last = G[b[j] - '0'][k];
                            break;
                        }
                    }
                }
                if(can == n) {
                    ok = true, printf("YES
%d
", i);
                    break;
                }
            }
        }
        if(!ok) puts("NO");
    }
    return 0;
}

D. Regular Bridge
題意:すべての点の度がkになり、図の中に少なくとも1つの橋があるように図を構築する.
考え方:
偶数度はきっと削除できませんその橋は1つの連通成分にとって1つの点度が奇数で他はすべて偶数です
これでこの連通成分には奇数の奇度点があり,握手の定理に反する推論である
任意の図(無方向または有方向)では、奇度頂点の個数は偶数である.
奇度に対してまず2つの点を探して1つの橋につながって、それぞれ1つの点で1つの連通成分を整えます
1から2、3、...、k-1ここにk-1度あります(1その橋に加えてk度あります)
2, 3, ... , k-1が互いにつながって1つのk-2度を構成する完全図に上の1度を加えるとk-1度になる
さらに2つの点を探してそれぞれ2,3,...,k-1がつながっているので、この2つの点はk-1度で、2つの辺はk度につながっています.
このとき2,3,...,k-1はk+1度あって更に隣接する辺を2-3,4-5,6-7,k-2-k-1辺を削除してすべてk度です
もう一つの連通成分は同じである
これでポイント数がV=2 k+4握手定理E=V*k/2でkを1とすると良い
参考コード:
//
//  Created by TaoSama on 2015-06-05
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int k, con[300][300];

void addEdge(int s, int t) {
    for(int i = s; i <= t; ++i) {
        con[s - 1][i] = con[i][t + 1] = con[i][t + 2] = true;
        for(int j = i + 1; j <= t; ++j)
            con[i][j] = true;
    }

    for(int i = s; i < t; i += 2)  //decrease 1 degree
        con[i][i + 1] = false;

    con[t + 1][t + 2] = true;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> k) {
        if(k % 2 == 0) {
            cout << "NO
";
            continue;
        }
        cout << "YES
";
        if(k == 1) {
            cout << "2 1
2 1
";
            continue;
        }

        memset(con, false, sizeof con);
        int V = 2 * k + 4, E = V * k >> 1;

        addEdge(2, k);
        con[1][k + 3] = true;
        addEdge(k + 4, V - 2);

        cout << V << ' ' << E << '
';
        int cnt = 0;
        for(int i = 1; i <= V; ++i)
            for(int j = i + 1; j <= V; ++j)
                if(con[i][j]) cout << i << ' ' << j << '
';
    }
    return 0;
}

E. Brackets in Implications
題意:カッコ構造の合法的な式を追加して値を0にする
考え方:この人の言うことはとてもはっきりしていて、私は翻訳しません@RedNextyears
You must be clear fist on the fact that (x->1 = 1)
This means that the last number in the input must be zero.
So now our sequence takes the form "xxxxxx...0"
Now we want to make the second to last number equal to 1 in order to have (1->0 = 0)
Now we have two cases:
Case 1 "xxxxxx..10"
You can just leave the sequence as it is ... all the numbers to the left of the 1 will just have no effect .. and then the final value will be (1->0 = 0)
Case 2 "xxxxxx..00"
We need to turn this new 0 into a 1 somehow in order to be like case 1.
In order to get rid of this zero we have to match it with some other number.
From the rules, we have (1->0 = 0) and (0->0 = 1), so obviously we will try to match this 0 with another 0.
So we will search for the first 0 to the left of this 0.
So our sequence now takes the form "xxxx...0111..1100"
We can get rid of this group of 1s by grouping (1->1->1->1->....->0 = 0)
So now our sequence takes the form "xxxx...0(111..110)0"= "xxxx...000"
Now you will just have to group these two 0s together to change them into 1
"xxxx...(0(111..110))0"= "xxxx...(00)0"= "xxxx...10"= "0"
参考コード:
//
//  Created by TaoSama on 2015-06-06
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int n, a[N];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n) {
        for(int i = 1; i <= n; ++i) cin >> a[i];
        if(a[n] == 1) {
            cout << "NO
";
            continue;
        }
        bool ok = false;
        if(n == 1 && a[1] == 0) {
            cout << "YES
0
";
            continue;
        }
        if(n >= 2 && a[n - 1] == 1 && a[n] == 0)  {
            cout << "YES
";
            for(int i = 1; i <= n; ++i)
                cout << a[i] << (i == n ? "" : "->");
            cout << "
";
            continue;
        }
        string cur;  //"xxxx...(0(111..110))0" = "xxxx...(00)0" = "xxxx...10" = "0"
        for(int i = 1; i <= n - 2; ++i) {
            if(a[i]) cur += (a[i] + '0'), cur += "->";
            else {
                ok = true;
                cout << "YES
";
                cout << cur << "(0->";  //          
                bool have = ++i <= n - 2;  //    
                if(have) cout << "(";  //     
                while(i <= n - 2) cout << a[i++] << "->";
                cout << "0)";  //       0
                if(have) cout << ")";
                cout << "->0
";  //    0
            }
        }
        if(!ok) cout << "NO
";
    }
    return 0;
}
SQL serverデータベースの「インデックス」の詳細
SQL Serverの6つの制約