牛客IOI周赛23-普及组

小L的作文

https://ac.nowcoder.com/acm/contest/11164/A

A、小L的作文

给出字符串 $S, |S|\le5000$ ，求解字符 $ch$ 的出现次数。签到题，遍历计数即可。

const int N = 1e5 + 7;
ll n, m;
char s[5005];

void solve() {
    char ch = getchar();
    getchar();
    scanf("%s", s);
    int ans = 0;
    for (int i = 0; s[i]; ++i)
        if (s[i] == ch) ++ans;
    printf("%d\n", ans);
}

B、小L的多项式

因为 $1\le n,m\le1000$ ，所以支持 $O(n^2log_n)$ 的解法，那么每次输入 $x$ ，直接带入求解即可，对于 $x^i$ 使用快速模幂即可 $log_n$ 求解。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1000 + 7;
ll n, m;
ll p[N];

int calc(int x) {
    ll ans = 0;
    rep(i, 0, n) {
        if (p[i] == 0)    continue;
        ans = (ans + p[i] * qpow(x, i, MOD)) % MOD;
    }
    return ans;
}

void solve() {
    n = read();
    rep(i, 0, n)    p[i] = read();
    m = read();
    while (m--) {
        int  x = read();
        int ans = calc(x);
        print(ans, 32);
    }
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

C、小L的编辑器

对于给出的字符串第一行叫做 $S$ ，第二行叫做 $P$ 的话。
很显然，我们每次输入完一个指令后，当前字符的相对位置已经确定了。
举个例子

如果当前输入的是a，并且指令是L
那么显然留下的字符串是    |a
不管你后续如何操作a后面的序列都是固定的。
那么同理，输入b，指令为R
留下字符串就是     b|
b前面的字符串也是固定的

那么就可以看出来，对于每次 $R$ 的指令，直接把 $s_i$ 输出出去即可，对于 $L$ 的指令我们要保存在栈里面倒序的输出出来。
这里有一个比赛交了一发 $T$ 掉才知道的点，在 $cpp$ 中 $string$ 类里面， $ans = ans + s_i$ 复杂度是 $O(1)$ 添加。
但是如果写法是 $ans = s_i + ans$ ，复杂度就是 $O(n)$ 添加，导致 $T$ 了一发，所以才使用栈输出答案。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
int n, m;
string s, p;
char v[N];

void solve() {
    js;
    cin >> s >> p;
    bool op = 0;
    n = s.size();
    int cnt = 0;
    rep(i, 0, n - 1) {
        if (p[i] == 'L') {
            v[++cnt] = s[i];
        }
        else {
            cout << s[i];
        }
    }
    repp(i, cnt, 1)    cout << v[i];
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

D、小L的数列

给出 $n\le 10^5$ 个数的序列 $a_i\le10^5$ ，你可以从中挑选一些数，并且把这些数随意排序。只需要保证最后你得到的数列，满足下面的要求。 $b_i < b_{i+1}\\\gcd(b_i,b_{i+1})!=1$
特别的如果序列长度为 $1$ 的话，它本身就是满足要求的。
那么我们抓住关键点，每两个数之间前面的要严格小于后面的数，并且相邻的数之间一定要存在公因子。
我们可以首先写个朴素的算法，时间复杂度 $O(n^2)$ ，可以写到 $80$ 分。
我们首先知道，对于 $1$ 来说，这个肯定是不存在解的，也就是我们最终求解的序列里面如果可以没有 $1$ 的话，那就一定不会选 $1$ 。
而且还要满足条件 $b_i<b_{i+1}$ ，那么相同的数也是无解的。
我们预处理输入的数组，可以得到离散之后的新数组。对于新数组，我们每次枚举一个 $i$ ，再去遍历前面全部的 $j$ ，很容易发现状态转移就是 $\\f[i]=max(f[i],f[j]+1)\ \ \ \ if\ \ \ \gcd(a_i,a_j)!=1$

const int N = 1e5 + 7;
int n, m, x, a[N], f[N];

void solve() {
    n = read();
    m = 0;
    rep(i, 1, n) {
        x = read();
        if (x != 1) a[++m] = x;
    }
    sort(a + 1, a + 1 + m);
    m = unique(a + 1, a + 1 + m) - a - 1;
    f[1] = 1;
    int ans = 0;
    rep(i, 2, m) {
        f[i] = 1;
        for (ll j = 1; j < i; ++j) {
            if (gcd(a[i],a[j]) != 1)    f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    print(ans);
}

接下来考虑 $100$ 分的解法，我的做法是建图再去跑动态规划。
我们知道我们上面的 $dp$ 方程最花费时间的就是枚举前面出现过的全部 $j$ ，非常的耗费时间，我们又知道。
对于每个 $a_i$ 来说，它出现过的全部素因子我们是可以分解出来的。我就想到使用素因子做为有向边，把不同的 $i$ 进行连接。再去跑记忆化的一张图，求解出现过的最深节点即可。
首先使用线性筛法筛选 $\sqrt{10^5}$ 中全部的素数。再去分解离散之后的新数组中每个 $a_i$ ，使用 $vector[prime_i]$ 保存存在素因子 $prime_i$ 的下标。
接下来把相邻下标进行有向图的连边，去跑图的遍历，注意这里需要加上记忆化，并且使用 $dp$ 去转移求解，如果不上记忆化，这种图直接就会 $T$ 掉。

const int N = 1e5 + 7;
int n, m, x, a[N], ans;
bool vis[321];
int cnt, prime[321];
vector<int> v[N];

int head[N], tot = 0;//前向星变量
struct Node {
    //int u; //起点
    //int w; //权值
    int v, next;
} edge[N << 2];

void add(int u, int v) {
    tot++;
    //edge[tot].u = u;
    edge[tot].v = v;
    //edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
int f[N];
int dfs(int u) {
    if (f[u])   return f[u];
    f[u] = 1;
    for (int i = head[u]; i; i = edge[i].next)
        f[u] = max(f[u], dfs(edge[i].v) + 1);
    ans = max(ans, f[u]);
    return f[u];
}

void solve() {
    ms(f, 0);
    ms(head, 0);
    tot = 0;
    rep(i, 1, N - 1)    v[i].clear();
    n = read();
    ans = m = 0;
    rep(i, 1, n) {
        x = read();
        if (x != 1) a[++m] = x;
    }
    if (!m) { puts("1"); return; }
    sort(a + 1, a + 1 + m);
    m = unique(a + 1, a + 1 + m) - a - 1;
    rep(i, 1, m) {
        x = a[i];
        rep(j, 1, cnt) {
            if (prime[j] > x)    break;
            if (x % prime[j] == 0) {
                v[prime[j]].push_back(i);
                while (x % prime[j] == 0)   x /= prime[j];
            }
        }
        if(x != 1)    v[x].push_back(i);
    }
    rep(i, 1, a[m]) {
        n = v[i].size();
        rep(j, 1, n - 1)    add(v[i][j - 1], v[i][j]);
    }
    ans = 1;
    rep(i, 1, m)
        if (!f[i])  dfs(i);
    print(ans);
}

int main() {
    rep(i, 2, 320) {
        if (!vis[i])    prime[++cnt] = i;
        rep(j, 1, cnt) {
            if (i * prime[j] >= 320) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)  break;
        }
    }
    int T = read(); while (T--)
        solve();
    return 0;
}