Codeforces Round #267 (Div. 2) Really.Record_html/css_WEB-ITnose

I posted DIV2 when I had nothing to do. I originally wanted to register a new small account. As a result, the verification code never appears. So I used a trumpet.

The result is rank 44, but there is no rating.

The meaning of the question will not be explained below.

A:O(n)brainless simulation.

Code:

#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: Notice that the number of digits of 1 in the binary expression of the result obtained after the exclusive OR of two numbers is different. number. Anyway, you can do it any way, O(nlogn) water.

Code:

#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: Obviously it is dp. Let f[i][j] represent the end of paragraph i when j Optimal value, obviously f[i][j]=max{f[i-1][k] sum[j]-sum[j-m]}(0<=k<=j-m)

But this is O(k*n^2) and may time out.

We found that the optimal state that can be used for each stage of transfer is the optimal prefix value of the previous stage, so it is directly recorded during dp for the following transfer, so that there is no need to enumerate. It becomes O(k*n) water.

It seems that the memory is stuck and a rolling array is used.

#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: All kinds of tricks. We actually want to find out what is the smallest answer that a word can get through a series of transformations, but there may be circular transfers and cannot be done directly.

Then the SCC shrinkage point is found, and the initial answer of each node is equal to the optimal value of all internal nodes of the node. Then just dp on the DAG.

It’s just disgusting anyway.

Note that the answer may explode int.

#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: To be filled in.