NFLS-DAY 15

Posted on By 张, 高畅 NFLS-DAY 15无评论

T0

%CZY,%CQR
想想新初三已经开学了我还在这里打题就有点慌。

T1

给定三位数(abc),将它倒序后变为(cba),再与原数相加求和。 

#include <bits/stdc++.h>
using namespace std;
int n;
int get(int x) {
    int res = 0;
    while (x) {
        res = res * 10 + (x % 10);
        x /= 10;
    }
    return res;
}
int main() {
    scanf("%d", &n);
    printf("%d", n + get(n));
    return 0;
}

T2

给出一个长度为N的字符串，由A，C，G 和T组成。回答以下Q个问题：
问题i: 给出区间[li,ri]。考虑S的子串[li,ri]，中，AC出现了多少次？

前缀和简单统计一下，但是左端点需要向后找到第一个为A的位置再停止。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, s[N];
char str[N];
int main() {
    scanf("%d%d%s", &n, &q, str + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1];
        if (str[i - 1] == &#039;A&#039; && str[i] == &#039;C&#039;)
            s[i]++;
    }
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        while (a <= b && str[a] != &#039;A&#039;) a++;
        if (a <= b)
            printf("%d\n", s[b] - s[a - 1]);
        else
            printf("0\n");
    }
    return 0;
}

T3

黑板上写着N个整数 。
你可以选择其中之一，并用1到1e9（包括1e9）之间的整数替换它，该整数可以与原始写入的整数相同。
移动后，在黑板上找到N个整数的最大可能的最大公约数。

非常厉害のQR采用了ST表（倍增）去做这道题。
然而似乎并不需要这么复杂。
由上一题，很自然我们会想到前缀与后缀，只不过变成前缀/后缀GCD。
值得注意的是，其实没有必要去替换，毕竟再怎么替换，答案并不会提高。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, res, a[N], pre[N], suf[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (i == 1)
            pre[i] = a[i];
        else
            pre[i] = __gcd(a[i], pre[i - 1]);
    }
    for (int i = n; i; i--) {
        if (i == n)
            suf[i] = a[i];
        else
            suf[i] = __gcd(a[i], suf[i + 1]);
    }
    for (int i = 1; i <= n; i++) {
        if (i == 1)
            res = max(res, suf[i + 1]);
        else if (i == n)
            res = max(res, pre[i - 1]);
        else
            res = max(res, __gcd(pre[i - 1], suf[i + 1]));
    }
    printf("%d", res);
    return 0;
}

T4

一共有N个任务和M天，一天只能做一个任务，任务只能做一次，任务当天做完。做完任务后可以在做完后的第Ai天拿到Bi的工资，问N天内最多可以拿到多少工资？

这题做对似乎要全靠蒙
其实说难也不算难，就是将任务按Ai排序后，枚举M表示仅能接受在i(1<=i以二进制形式给出一个整数L，问有多少个非负整数对(a,b)满足：a+b=a^b(^表示异或)<=L。答案对1e9+7取模。

人类进化不带上我。
QR以及某些人使用了统计通过了此题。
不过看起来正解给了一个数位DP的做法。
众所周知，异或其实就相当于不进位加法，所以a+b=a^b，当且仅当a与b的同一位并不同时为1。
剩下的交给数位DP模板

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
typedef long long LL;
int n;
LL f[N];
char s[N];
LL dfs(int u, int limit) {
    if (!u)
        return 1;
    if (!limit && ~f[u])
        return f[u];
    int t = limit ? s[u] - '0' : 1;
    LL res = 0;
    for (int i = 0; i <= t; i++) {
        if (i)
            res = (res + dfs(u - 1, limit) * 2) % mod;
        else
            res = (res + dfs(u - 1, limit && i == t)) % mod;
    }
    return f[u] = res;
}
int main() {
    memset(f, -1, sizeof f);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    reverse(s + 1, s + n + 1);
    printf("%d\n", dfs(n, 1) % mod);
    return 0;
}

T6

LUOGU
第一次见这样的题目，想不到分块还可以用于数论中。
对于朴素的DP，我们有f[i][j]=sum{f[i-1][x]}(1<=x<=n/j)
但是我们发现，d的因数个数最多也仅有2×sqrt(d)个，可以提前预处理出来。

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 9e4 + 5, K = 1e6 + 5, mod = 1e9 + 7;
typedef long long LL;
int n, m, cnt;
LL f[N][M];
int d[K], len[K];
unordered_map<int, int> t;
int main() {
    scanf("%d%d", &n, &m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), n);
        cnt++;
        d[cnt] = r;
        t[r] = cnt;
        len[cnt] = r - l + 1;
    }
    for (int i = 1; i <= cnt; i++) f[0][i] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= cnt; j++)
            f[i][j] = (1LL * f[i][j - 1] + (1LL * len[j] * f[i - 1][t[n / d[j]]] % mod)) % mod;
    }
    printf("%lld\n", f[m][cnt]);
    return 0;
}

T7

LUOGU
这题有很多小结论：
①：对于一个环，我们走一圈获得它的值，不用付出额外代价
（有些路走了两遍就被消掉了）
②：对于多条路径情况下，不用处理，若最大值不在此路径上，则意味着此路径与当前路径构成一个环，此路径走两遍后会被消掉
③：找环，去缩点。大环可以通过若干小环异或得到。所以就意味着不用缩点，只需考虑返祖边（用tarjan）
剩下就变成昨天所讲的线性基求XOR的最大值。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, m, st[N];
int h[N], e[M], ne[M], idx;
LL w[M], d[N], a[N];
void add(int a, int b, LL c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; }
void insert(LL x) {
    for (int i = 63; ~i; i--) {
        if ((x >> i) & 1) {
            if (!a[i]) {
                a[i] = x;
                return;
            }
            x ^= a[i];
        }
    }
}
LL query(LL x) {
    LL res = x;
    for (int i = 63; ~i; i--) res = max(res, res ^ a[i]);
    return res;
}
void dfs(int u, LL ans) {
    d[u] = ans;
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (st[j])
            insert(ans ^ w[i] ^ d[j]);
        else
            dfs(j, ans ^ w[i]);
    }
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        LL c;
        scanf("%d%d%lld", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1, 0);
    printf("%lld\n", query(d[n]));
    return 0;
}
训练日志

发表回复