2020 Jiangsu Collegiate Programming Contest（C,D,H,J）

oj: CodeForces

D. Delete Prime

oj: CodeForces

题意

定义一个生成序列的流程：

1. 根据 \(n\) 生成一个 \(1,2,...,n\) 数组。
2. 取出序列里第 \(1\) 和第素数位置的元素，保持其相对位置不变加入到 \(D\) 数组的末尾。
3. 重复 \(2\) 过程直到原数组为空。

例如 \(n=6\) 时，数组 \(D\) 为 \([1,2,3,5,4,6]\) 。

有若干次提问，每次提问会给出 \(3\) 个整数： \(t,n,k\) 。其中 \(t\) 表示提问类型：

1. 给定 \(n\) 和 \(k\) ，求出 \(x\) 满足 \(D[x]=k\) 。
2. 给定 \(n\) 和 \(k\) ，求出 \(x\) 满足 \(D[k]=x\) 。

题解

测试了一下， \(n\) 为 \(1000,000\) 时，需要 \(80\) 轮迭代求出 \(D\) 。把每次迭代取出的数单独存为一个数组，那么这些数组都是有序的。

然后根据给定的 \(n\) 和 \(k\) 从第一个数组到最后一个数组依次二分查找即可。

1. 给定了值，求索引。按照迭代顺序依次枚举数组，直接在此数组里二分查找 \(k\) ，如果找不到就维护一个 和，和 保存的是此数组中小于等于 \(n\) 的数的个数。如果找到了，就把 \(k\) 在此数组中的位置加上维护的 和 就是 \(k\) 在 \(D\) 数组中的位置。
2. 给定了位置，求值。仿照情况 \(1\) 的思路，维护一个 和 保存小于等于 \(n\) 的元素的个数，一旦个数之和大于等于 \(k\) ，就说明 \(D\) 中第 \(k\) 个元素在当前我们枚举的数组里。直接输出即可。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 1000000;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
    while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
    return x * f;
}

int a[maxn + 1];
int used[maxn + 1];
vector<int> b[81];
int cnt;

vector<int> arr;
int vis[1000006];
void doit(int maxnum) {
    for(int i = 2; i <= maxnum; ++i) {
        if(!vis[i]) arr.push_back(i);
        for(int j = 0; j < arr.size() && arr[j] * i <= maxnum; ++j) {
            vis[arr[j] * i] = 1;
            if(i % arr[j] == 0) break;
        }
    }
}

int findl(int de, int val) {
    return lower_bound(b[de].begin(), b[de].end(), val) - b[de].begin();
}

int findu(int de, int val) {
    return upper_bound(b[de].begin(), b[de].end(), val) - b[de].begin();
}

void sol() {
    int t = read(), n = read(), k = read();
    if(t == 1) {
        int num = 0;
        _for(i, cnt) {
            int p = findl(i, k);
            if(p < b[i].size() && b[i][p] == k) {
                printf("%d\n", num + p + 1);
                return;
            }
            else num += findu(i, n);
        }
    }
    else {
        _for(i, cnt) {
            int p = findu(i, n);
            if(p >= k) {
                printf("%d\n", b[i][k - 1]);
                return;
            }
            else k -= p;
        }
    }
}

int main() {
    doit(1000000);
    _rep(i, 1, maxn) a[i] = i;
    cnt = 0;
    int n = 1000000;
    while(n) {
        _rep(i, 1, n) used[i] = 0;
        used[1] = 1;
        b[cnt].push_back(a[1]);
        for(int i = 0; i < arr.size() && arr[i] <= n; ++i) {
            used[arr[i]] = 1;
            b[cnt].push_back(a[arr[i]]);
        }
        int tn = 0;
        _rep(i, 1, n) if(!used[i]) a[++tn] = a[i];
        n = tn;
        ++cnt;
    }
    int T = read();
    _for(i, T) {
        sol();
    }
    return 0;
}

H. Happy Morse Code

oj: CodeForces

题意

给定一组密钥 \(s\) 和一串密码 \(t\) ，求出是否可以根据这组密钥唯一求解密码，如果不能求解就输出nonono，如果能唯一求解就输出happymorsecode，如果有多种求解方式就输出puppymousecat和求解方法数，答案对 \(128\) 取余。

题解

动态规划。

定义 \(dp[i]\) 为密码的字串 \(t[i:n]\) 的求解方法数。
\(ln[j]\) 为第 \(j\) 个密钥的长度。

边界值： \(dp[n]=1\)

状态转移：\(dp[i] = \sum\limits_{j=0}^{m-1}{dp[i + ln[j]]}\) \((t[i:i+len(s[j])]=s[j])\)。

注意，我们需要根据 \(dp[0]\) 的值来判断答案有多少种求解方式，所以 \(i\) 中间的计算过程不能直接对 \(128\) 取余，否则我们不知道最后的答案 \(0\) 是因为没有解还是取余后变成了 \(0\) 。所以稳妥的做法是如果大于 \(128\) 就先减去 \(128\) ，再对 \(128\) 取余，再加上 \(128\) 。之后答案的值就能维持在大于 \(128\) 但不超过 \(256\) 的水平。最后输出的时候再对 \(128\) 取余。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
    while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
    return x * f;
}

LL dp[maxn];
int n, m;
char s[26][11];
char t[maxn];
int ln[maxn];
int fl;

void init() {
    fl = 0;
    _for(i, n + 1) dp[i] = 0;
}

int che(int i, int p) {
    _for(j, ln[i]) {
        if(t[p + j] != s[i][j]) return 0;
    }
    return 1;
}

void sol() {
    init();
    _for(i, m) {
        scanf("%s", s[i]);
        scanf("%s", s[i]);
        ln[i] = strlen(s[i]);
    }
    scanf("%s", t);
    dp[n] = 1;
    for(int i = n - 1; i >= 0; --i) {
        _for(j, m) {
            if(i + ln[j] > n) continue;
            if(che(j, i)) {
                dp[i] += dp[i + ln[j]];
                if(dp[i] > 128) {
                    dp[i] = (dp[i] - 128) % 128 + 128;
                }
            }
        }
    }
    if(dp[0] == 0) printf("nonono\n");
    else if(dp[0] == 1) printf("happymorsecode\n");
    else printf("puppymousecat %lld\n", dp[0] % 128);
}

int main() {
    int T = read();
    _for(i, T) {
        n = read(), m = read();
        sol();
    }
    return 0;
}

J. Just Multiplicative Inverse

oj: CodeForces

题意

给定一个函数，每回合给出一个 \(p\) ，求出此函数的调用次数。

题解

观察后发现函数再调用过程中 \(p\) 不变， \(x\) 持续变小。所以可以按 \(x\) 从小到大计算，较大的 \(x\) 可以利用到较小的 \(x\) 的结果，从而避免多余计算，进行记忆化搜索。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 1000005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
    while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
    return x * f;
}
LL p, ans;
LL dp[maxn];
inline LL dfs(LL x, LL p, int dep) {
    if(dp[x] != -1) return dp[x];
    if(x <= 1) return 1;
    return dp[x] = dfs(p % x, p, dep + 1) + 1;
}
void init() {
    ans = 0;
    _rep(i, 1, p) dp[i] = -1;
}
void sol() {
    init();
    _rep(i, 1, p - 1) ans += dfs(i, p, 1);
}
int main() {
    int T = read();
    _for(i, T) {
        p = read();
        sol();
        printf("%.10f\n", 1.0 * ans / (p - 1));
    }
    return 0;
}

2020 Jiangsu Collegiate Programming Contest（C,D,H,J）

原文：https://www.cnblogs.com/zjtdddg/p/14458383.html