省选测试32

首页 > 省选测试32 > 列表

省选测试32

A 跑步

题目大意 :

Code

Show Code
#include cstdio
#include algorithm

using namespace std;
const int N = 2005;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c  '0' || c  '9'; c = getchar()) if (c == '-') f = -1;
    for (; c ='0'  c ='9'; c = getchar()) x = x * 10 + c - '0';
    return x * f;
}

int n, a[N][N], f[N][N], t[N][N];
long long ans;

void Add(int op, int x, int w) {
    for (; x = n; x += x  -x) t[op][x] += w;
}

int Ask(int op, int x, int w = 0) {
    for (; x; x -= x  -x) w += t[op][x];
    return w;
}

bool Judge(int x, int y) {
    return Ask(x, y) == max(Ask(x-1, y), Ask(x, y-1)) + a[x][y];
}

int main() {
    n = read();
    for (int i = 1; i = n; ++i) {
        for (int j = 1; j = n; ++j) {
            a[i][j] = read();
            f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            ans += f[i][j];
            Add(i, j, f[i][j] - f[i][j-1]);
        }
    }
    for (int i = 1; i = n; ++i) t[i][n+1] = 1e9;
    printf("%lld\n", ans);
    for (int k = 1; k = n; ++k) {
        char c; scanf(" %c", c);
        int x = read(), y = read(), w = c == 'U'  1 : -1;
        int l = y, r = y; a[x][y] += w;
        for (int i = x; i = n; ++i) {
            while (l = n  Judge(i, l)) l++;
            Add(i, l, w); Add(i, r+1, -w); ans += w * (r - l + 1);
            while (r  n  !Judge(i, r+1)) r++, Add(i, r, w), Add(i, r+1, -w), ans += w;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

B 算术

题目大意 :

Code

Show Code
#include cstdio
#include cstring
#include algorithm

using namespace std;

char c[1000005];
int len, k, M;

bool Prime(int x) {
    for (int i = 2; i * i = x; ++i)
        if (x % i == 0) return 0;
    return 1;
}

int Pow(int a, int k, int ans = 1) {
    for (; k; k = 1, a = 1ll * a * a % M)
        if (k  1) ans = 1ll * ans * a % M;
    return ans;
}

bool Judge() {
    for (int i = 1; i = 20; ++i) {
        if (!Prime(M = i * k + 1)) continue;
        int s = 0;
        for (int j = 1; j = len; ++j)
            s = (s * 10ll + c[j] - '0') % M;
        if (Pow(s, i)  1) return 0;
    }
    return 1;
}

int main() {
    int T; scanf("%d", T);
    while (T--) {
        scanf("%s%d", c + 1, k);
        len = strlen(c + 1);
        puts(Judge()  "Y" : "N");
    }
    return 0;
}

C 求和 (Unaccepted)

题目大意 :

Code

Show Code