Codeforces Round #234 (Div. 2)

Problems # Name A Inna and Choose Options standard input/output 1 s, 256 MB x1942 B Inna and New Matrix of Candies standard input/output 1 s, 256 MB x1556 C Inna and Huge Candy Matrix standard input/output 2 s, 256 MB x1114 D Dima and Bacteria standard input/output 2 s, 256 MB x371 E Inna and Binary Logic standard input/output 3 s, 256 MB x169

A題：直接暴力枚舉每種情況即可。水題<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+Qszio7q8x8K8z8JTo6xHtcS+4MDro6zDv9bWvuDA69a70qrSu7TOo6y/qrj2dmlzyv3X6bHqvMejrNfuuvOx6cD60rux6b+009a8uLj2vLS/yTwvcD4KPHA+Q8zio7rEo8Ti0P3Xqry0v8mhozwvcD4KPHA+RMzio7qyorLpvK8mIzQzO2Zsb3lko6yw0Xc9MLXEsd+1xLXjsqKy6byvtKbA7aOsxdC2z82s1tbA4MrHt/G2vNTa0ru49ryvus/E2qOssrvKx77NTm+jrMqjz8K1xL7NwPvTw2Zsb3lkx/Oz9tfutszCt7y0v8mhozwvcD4KPHA+Rczio7rOu9TLy+OjrMO/uPbK/dfWttTTprXEw7+49s67z/LX87rNz/LT0tHTyfqjrNXiuPbH+LzkxNrP8s/CtcTEx7j2yP29x9DOx/i85NK7tqjKx7vh1Pa80ygxPDxpKSq49sr9tcSjrLj2yv21xLzGy+O3vcq9zqpsICogciAmIzQzOyBsICYjNDM7IHKho8i7uvPIpcSjxOK8tL/JoaPXotLis/XKvLuvtcTKsbry0qrTw08obipiKbXEt723qLK7yLtUTEWhozwvcD4KPHA+tPrC66O6PC9wPgo8cD5BzOKjujwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include int t, n; char str[15]; char save[15][15]; bool judge(int a, int b) { int i, j; for (i = 0; i < a; i++) { for (j = 0; j < b; j++) save[i][j] = str[i * b + j]; } for (i = 0; i < b; i++) { for (j = 0; j < a; j++) { if (save[j][i] != 'X') break; } if (j == a) return true; } return false; } int main() { scanf("%d", &t); while (t--) { scanf("%s", str); int ans = 0; if (judge(1, 12)) ans++; if (judge(2, 6)) ans++; if (judge(3, 4)) ans++; if (judge(4, 3)) ans++; if (judge(6, 2)) ans++; if (judge(12, 1)) ans++; printf("%d", ans); if (judge(1, 12)) printf(" 1x12"); if (judge(2, 6)) printf(" 2x6"); if (judge(3, 4)) printf(" 3x4"); if (judge(4, 3)) printf(" 4x3"); if (judge(6, 2)) printf(" 6x2"); if (judge(12, 1)) printf(" 12x1"); printf("\n"); } return 0; }
B題：

#include 
#include 
#include 
using namespace std;
const int N = 1005;
int n, m, i, j, vis[N];
char g[N][N];

int main() {
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
        scanf("%s", g[i]);
    for (i = 0; i < n; i++) {
        int G, S;
        for (j = 0; j < m; j++) {
            if (g[i][j] == 'G') G = j;
            if (g[i][j] == 'S') S = j;
        }
        if (S < G) {
            printf("-1\n");
            return 0;
        }
        int d = S - G;
        vis[d] = 1;
    }
    int ans = 0;
    for (int i = 0; i <= 1000; i++)
        if (vis[i]) ans++;
    printf("%d\n", ans);
    return 0;
}

C題：

#include 
#include 
#include 
using namespace std;
int n, m, x, y, z, p, i, j;
struct Point {
    int x, y;
} po[100005];

void at(Point &a) {
    int x = a.x, y = a.y;
    a.y = n - x + 1;
    a.x = y;
}

void ht(Point &a) {
    int x = a.x, y = a.y;
    a.y = m - y + 1;
    a.x = x;
}

void ct(Point &a) {
    int x = a.x, y = a.y;
    a.y = x;
    a.x = m - y + 1;
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &x, &y, &z, &p);
    x %= 4;
    y %= 2;
    z %= 4;
    for (i = 0; i < p; i++)
        scanf("%d%d", &po[i].x, &po[i].y);
    for (j = 0; j < x; j++) {
        for (i = 0; i < p; i++) {
            at(po[i]);
        }
        int t = n; n = m; m = t;
    }
    for (j = 0; j < y; j++) {
        for (i = 0; i < p; i++) {
            ht(po[i]);
        }
    }
    for (j = 0; j < z; j++) {
        for (i = 0; i < p; i++) {
            ct(po[i]);
        }
        int t = n; n = m; m = t;
    }
    for (i = 0; i < p; i++)
        printf("%d %d\n", po[i].x, po[i].y);
    return 0;
}

D題：

#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 100005;
int n, m, K, type[N], i, j, k;
int f[505][505], fa[N], c[505];

int find(int x) {
    if (x == fa[x])
        return x;
    x = find(fa[x]);
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    int tn = 0;
    memset(f, INF, sizeof(f));
    for (i = 1; i <= n; i++)
        fa[i] = i;
    for (i = 1; i <= K; i++) {
        f[i][i] = 0;
        scanf("%d", &c[i]);
        for (j = 0; j < c[i]; j++) {
            type[++tn] = i;
        }
    }
    int u, v, w;
    while (m--) {
        scanf("%d%d%d", &u, &v, &w);
        if (type[u] != type[v] && f[type[u]][type[v]] > w) {
            f[type[u]][type[v]] = w;
            f[type[v]][type[u]] = w;
        }
        if (w == 0) {
            int pu = find(u);
            int pv = find(v);
            if (pu != pv)
                fa[pv] = pu;
        }
    }
    for (i = 2; i <= n; i++) {
        int u = i - 1, v = i;
        if (type[u] == type[v]) {
            if (find(u) != find(v)) {
                printf("No\n");
                return 0;
            }
        }
    }
    printf("Yes\n");
    for (k = 1; k <= K; k++) {
        for (i = 1; i <= K; i++) {
            for (j = 1; j <= K; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    for (i = 1; i <= K; i++) {
        for (j = 1; j < K; j++) {
            if (f[i][j] == INF) f[i][j] = -1;
            printf("%d ", f[i][j]);
        }
        if (f[i][K] == INF) f[i][K] = -1;
        printf("%d\n", f[i][K]);
    }
    return 0;
}

E題：

#include 
#include 

const int N = 100005;
const int M = 20;
int n, m, i, j, b;
int a[N][M];
__int64 sum, mi[32];

int main() {
    mi[0] = 1;
    for (i = 1; i < 32; i++)
        mi[i] = mi[i - 1] * 2;
    sum = 0;
    scanf("%d%d", &n, &m);
    int num;
    for (i = 1; i <= n; i++) {
        scanf("%d", &num);
        for (b = 0; b <= 18; b++) {
            if (num&mi[b]) {
                a[i][b] = 1;
            }
        }
    }
    __int64 k = 0;
    for (b = 0; b <= 18; b++) {
        for (i = 1; i <= n; i++) {
            if (a[i][b]) k++;
            else {
                sum += mi[b] * k * (k + 1) / 2;
                k = 0;
            }
        }
        if (k != 0) {
            sum += mi[b] * k * (k + 1) / 2;
                k = 0;
        }
    }
    int p;
    __int64 v;
    while (m--) {
        scanf("%d%I64d", &p, &v);
        __int64 ans1 = 0, ans2 = 0;
        for (b = 0; b <= 18; b++) {
            if (a[p][b]) sum -= mi[b];
            if (a[p][b] && (v&mi[b]) == 0) {
                __int64 l = p, r = p;
                while (a[l - 1][b]) {
                    l--;
                }
                while (a[r + 1][b]) {
                    r++;
                }
                ans1 += mi[b] * ((p - l) * (r - p) + (p - l) + (r - p));
                a[p][b] = 0;
            }
            else if ((v&mi[b]) && a[p][b] == 0) {
                int l = p, r = p;
                while (a[l - 1][b]) {
                    l--;
                }
                while (a[r + 1][b]) {
                    r++;
                }
                ans2 += mi[b] * ((p - l) * (r - p) + (p - l) + (r - p));
                a[p][b] = 1;
            }
        }
        sum = sum - ans1 + ans2 + v;
        printf("%I64d\n", sum);
    }
    return 0;
}