Codeforces ラウンド #267 (ディビジョン 2) Really.Record_html/css_WEB-ITnose

もともと新しい小さなアカウントを登録したかったので、何もすることがなかったときにDIV2を投稿しました。その結果、確認コードは表示されません。なので小さいサイズで作りました。

結果はランク44ですが評価はありません

質問の意味は以下では説明しません。

A:O(n) 頭脳を使わないシミュレーション。

コード:

#include <cstdio>int main() {    int n, a, b;    scanf("%d", &n);    int res = 0;    while(n--) {        scanf("%d%d", &a, &b);        if (a + 2 <= b)            ++res;    }    printf("%d", res);    return 0;}

B: 2 つの数値の後に得られる結果の 2 進表現の 1 の桁数が異なる、または相違の数であることに注意してください。とにかく、どうやっても大丈夫です、O(nlogn)水。

コード:

#include <cstdio>#include <cstring>#include <cctype>#include <iostream>#include <algorithm>using namespace std;#define M 1010int a[M];int count(int x) {    int res = 0;    for(; x; x -= x & -x)        ++res;    return res;}int main() {    int n, m, k;    scanf("%d%d%d", &n, &m, &k);    register int i, j;    int S = (1 << n) - 1;    for(i = 1; i <= m + 1; ++i) {        scanf("%d", &a[i]);        a[i] &= S;    }        int ans = 0;    for(i = 1; i <= m; ++i)        if (count(a[i] ^ a[m + 1]) <= k)            ++ans;        printf("%d", ans);        return 0;}

C: 明らかに dp、i 番目の段落の終わりが j であるときの最適値を f[i][j] で表します、明らかに f[i][j]=max{ f [i-1][k]+sum[j]-sum[j-m]}(0

ただし、これは O(k*n^2) なので、タイムアウトになる可能性があります。

転送の各ステージで使用できる最適な状態は、前のステージの最適なプレフィックス値であることが判明したため、次の転送の dp 中に直接記録されるため、列挙する必要がなく、 O(k*n)水が通過します。

メモリが詰まっていてローリング配列が使用されているようです。

#include <cstdio>#include <cstring>#include <cctype>#include <iostream>#include <algorithm>using namespace std;#define N 5010long long a[N];long long dp[2][N], sav[2][N];int main() {    int n, m, num;    scanf("%d%d%d", &n, &m, &num);    register int i, j, k;    for(i = 1; i <= n; ++i) {        scanf("%I64d", &a[i]);        a[i] += a[i - 1];    }        int now = 0, last = 1;    for(i = 1; i <= num; ++i) {        now ^= 1;        last ^= 1;        memset(dp[now], 0, sizeof(dp[now]));        memset(sav[now], 0, sizeof(sav[now]));        for(j = i * m; j <= n; ++j) {            dp[now][j] = sav[last][j - m] + a[j] - a[j - m];            sav[now][j] = max(sav[now][j - 1], dp[now][j]);        }    }        long long res = 0;    for(i = num * m; i <= n; ++i)        res = max(res, dp[now][i]);        printf("%I64d", res);        return 0;}

D: あらゆる種類のトリック。実際には、単語が一連の変換を通じて得られる最小の答えは何かを知りたいのですが、循環転送が発生する可能性があるため、直接行うことはできません。

その後、SCC 収縮点が見つかり、各ノードの初期応答はノードのすべての内部ノードの最適値に等しくなります。次に、DAG を dp するだけです。

とにかく気持ち悪いです。

答えは爆発する可能性があることに注意してください。

#include <cstdio>#include <cstring>#include <cctype>#include <iostream>#include <string>#include <algorithm>#include <map>using namespace std;#define N 100010#define E 100010int sav[N];    map<string, int> M;inline void low(string &s) {    int len = s.length();    for(int i = 0; i < len; ++i)        if (s[i] >= 'A' && s[i] <= 'Z')            s[i] = s[i] - 'A' + 'a';}struct Ans {    int num, len;    Ans(int _num = 0, int _len = 0):num(_num),len(_len){}    bool operator < (const Ans &B) const {        return (num < B.num) || (num == B.num && len < B.len);    }    void get(string &s) {        int res = 0, l = s.length();        for(int i = 0; i < l; ++i)            if (s[i] == 'r')                ++res;        num = res;        len = s.length();    }}S[N * 3], dp[N * 3];int head[N * 3], next[E], end[E];void addedge(int a, int b) {    static int q = 1;    end[q] = b;    next[q] = head[a];    head[a] = q++;}int dfn[N * 3], lowd[N * 3], tclock, stack[N * 3], belong[N * 3], top, num;bool instack[N * 3];void dfs(int x) {    dfn[x] = lowd[x] = ++tclock;    stack[++top] = x;    instack[x] = 1;    for(int j = head[x]; j; j = next[j]) {        if (!dfn[end[j]]) {            dfs(end[j]);            lowd[x] = min(lowd[x], lowd[end[j]]);        }        else if (instack[end[j]])            lowd[x] = min(lowd[x], dfn[end[j]]);    }    if (dfn[x] == lowd[x]) {        dp[++num] = Ans(0x3f3f3f3f, 0);        int i;        while(1) {            i = stack[top--];            belong[i] = num;            instack[i] = 0;            if (S[i] < dp[num])                dp[num] = S[i];            if (dfn[i] == lowd[i])                break;        }    }}    struct Graph {    int head[N * 3], next[E], end[E], ind;    void reset() {        ind = 0;        memset(head, -1, sizeof(head));    }    void addedge(int a, int b) {        int q = ind++;        end[q] = b;        next[q] = head[a];        head[a] = q;    }}NewG;bool Calc[N * 3];void work(int x) {    Calc[x] = 1;    for(int j = NewG.head[x]; j != -1; j = NewG.next[j]) {        if (!Calc[NewG.end[j]])            work(NewG.end[j]);        if (dp[NewG.end[j]] < dp[x])            dp[x] = dp[NewG.end[j]];    }}int main() {    int n;    scanf("%d", &n);        string s, a, b;    register int i, j;    int id = 0;    for(i = 1; i <= n; ++i) {        cin >> s;        low(s);        if (!M[s]) {            M[s] = ++id;            S[id].get(s);        }        sav[i] = M[s];    }        int m;    scanf("%d", &m);    int x, y;    for(i = 1; i <= m; ++i) {        cin >> a >> b;        low(a), low(b);        if (!M[a]) {            M[a] = ++id;            S[id].get(a);        }        x = M[a];        if (!M[b]) {            M[b] = ++id;            S[id].get(b);        }        y = M[b];        if (x != y)            addedge(x, y);    }        for(i = 1; i <= id; ++i)        if (!dfn[i])            dfs(i);        NewG.reset();    for(i = 1; i <= id; ++i)        for(j = head[i]; j; j = next[j])            if (belong[i] != belong[end[j]])                NewG.addedge(belong[i], belong[end[j]]);        for(i = 1; i <= num; ++i)        if (!Calc[i])            work(i);        long long ansnum = 0, anslen = 0;    for(i = 1; i <= n; ++i)        ansnum += dp[belong[sav[i]]].num, anslen += dp[belong[sav[i]]].len;        printf("%I64d %I64d", ansnum, anslen);        return 0;}

E: 記入する必要があります。