【XJTU 2020暑期集训】Day10 - 2019 ACM-ICPC 陕西省赛

C - Grid with Arrows

首先对于连通块个数大于等于2的情况,一定无解。然后我们考虑,对于 n\times m 个点,n\times m 条边构成的这个图,若存在一条哈密顿通路,则至多有一条边没有走。换句话说,如果有解,则原图的结构一定为:在一个环上选一条不走的边,然后将这条边的终点指向图中的任意一个点。所以如果有解,则原图一定有且仅有一个点的入度为0,且该点一定为起点,所以dfs判断一下就好了。

D - Turn It Off

二分答案,然后贪心关灯检验即可。

E - K-hour Clock

x+y\lt z,一定无解;若 x+y=z,则对于任意的 k\gt z 都符合题意;若 x+y\gt z,则 k=x+y-z 为一个可行解,除非 xz 大于等于 k

K - Digit Product

对于 l,r 相差大于等于10的区间,答案一定为0,否则暴力计算即可。

L - 0689

正难则反,假设所有翻转方案都为有效翻转,当原串不全为6或全为9时,能得到的不同的串的个数为 n(n+1)/2+1,否则为 n(n+1)/2(不存在翻转不变的情况)。现在需要计算无效翻转的数量,显然对于一个翻转方案 [l,r] 来说,s_l=0,s_r=0s_l=8,s_r=8s_l=6,s_r=9s_l=9,s_r=6,是「该方案为无效翻转」的充要条件。设 \mathrm{cnt}[i] 表示串中数字 i 出现的次数,则答案为:初始假设得到的总答案减去 (\mathrm{cnt}[0]+1)\cdot \mathrm{cnt}[0]/2+(\mathrm{cnt}[0]+1)\cdot \mathrm{cnt}[0]/2+\mathrm{cnt}[6]\cdot \mathrm{cnt}[9]

Code

C - Grid with Arrows

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 100005
#define id(i, j) ((i)*m + (j))

using namespace std;

int T, n, m, N;
int par[MAX_N];
int deg[MAX_N];
int nxt[MAX_N];
bool vis[MAX_N];
string s[MAX_N];
vector<int> a[MAX_N];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

void merge(int x, int y) {
    par[find(x)] = find(y);
}

bool same(int x, int y) {
    return find(x) == find(y);
}

bool ok(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int getnxt(int i, int j, char c, int d) {
    int x = i, y = j;
    if (c == 'u') {
        x -= d;
    } else if (c == 'd') {
        x += d;
    } else if (c == 'l') {
        y -= d;
    } else {
        y += d;
    }
    if (ok(x, y)) {
        return id(x, y);
    }
    return -1;
}

int getcc() {
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if (i == find(i)) {
            ans++;
        }
    }
    return ans;
}

void dfs(int x) {
    vis[x] = true;
    if (nxt[x] != -1 && !vis[nxt[x]]) {
        dfs(nxt[x]);
    }
}

bool check(int x) {
    for (int i = 0; i <= N; i++) {
        vis[i] = false;
    }
    dfs(x);
    for (int i = 0; i <= N; i++) {
        if (!vis[i]) {
            return false;
        }
    }
    return true;
}

void work() {
    cin >> n >> m;
    N = id(n - 1, m - 1);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        a[i].clear();
    }
    for (int i = 0, t; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            a[i].push_back(t);
        }
    }
    for (int i = 0; i <= N; i++) {
        par[i] = i, deg[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            nxt[id(i, j)] = getnxt(i, j, s[i][j], a[i][j]);
            merge(id(i, j), nxt[id(i, j)]);
            deg[nxt[id(i, j)]]++;
        }
    }
    if (getcc() >= 2) {
        cout << "No" << endl;
        return;
    }
    int t = 0;
    for (int i = 0; i <= N; i++) {
        if (!deg[i]) {
            t = i;
            break;
        }
    }
    if (check(t)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        work();
    }
}

D - Turn It Off

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 200005

using namespace std;

int T, n, K;
char s[MAX_N];

bool nolit() {
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            return false;
        }
    }
    return true;
}

bool check(int x) {
    int pos = 0, cnt = 0;
    while (pos < n) {
        if (s[pos + 1] == '1') {
            pos = min(pos + x, n);
            cnt++;
        } else {
            pos++;
        }
    }
    return cnt <= K;
}

void work() {
    scanf("%d%d%s", &n, &K, s + 1);
    if (nolit()) {
        printf("0\n");
        return;
    }
    if (check(1)) {
        printf("1\n");
        return;
    }
    int l = 1, r = n;
    while (r - l > 1) {
        int m = (l + r) >> 1;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    printf("%d\n", r);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        work();
    }
}

E - K-hour Clock

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int T, x, y, z;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &x, &y, &z);
        if (x + y < z) {
            printf("-1\n");
        } else if (x + y == z) {
            printf("%d\n", z + 1);
        } else {
            int k = x + y - z;
            if (x >= k || z >= k) {
                printf("-1\n");
            } else {
                printf("%d\n", k);
            }
        }
    }
}

K - Digit Product

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MOD 1000000007
#define int long long

using namespace std;

int T, l, r;

int getf(int x) {
    int ans = 1;
    while (x) {
        ans = ans * (x % 10) % MOD;
        x /= 10;
    }
    return ans;
}

int getans(int l, int r) {
    int ans = 1;
    for (int i = l; i <= r; i++) {
        ans = (ans * getf(i)) % MOD;
    }
    return ans;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &l, &r);
        if (r - l >= 10) {
            printf("0\n");
        } else {
            printf("%lld\n", getans(l, r));
        }
    }
}

L - 0689

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define MAX_D 15
#define int long long

using namespace std;

int T, n;
char s[MAX_N];

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        int cnt[MAX_D] = {0};
        for (int i = 1; i <= n; i++) {
            cnt[s[i] - '0']++;
        }
        int ans = (n + 1) * n / 2;
        if (cnt[6] != n && cnt[9] != n) {
            ans++;
        }
        ans -= (cnt[0] + 1) * cnt[0] / 2;
        ans -= (cnt[8] + 1) * cnt[8] / 2;
        ans -= cnt[6] * cnt[9];
        printf("%lld\n", ans);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注