A 小L的作文

题目：
小 L 写了一篇很烂的作文，烂到老师都不愿意给它扣分，只能给他加分，已知老师比较牛，所以他发现一个字符 x 就会加一分。问你小 L 最后可以得到多少分。

解题思路

遍历表示作文的字符串 s，遇到 x 字符就向答案中加一。

#include<iostream>
using namespace std;

int main(){
    char x;
    string s;
    cin >> x >> s;
    int ans = 0;
    for(char c : s){
        if(c==x) ++ans;
    }
    cout << ans << endl;
    return 0;
}

B 小L的多项式

题目：
一天，小 L 收到了一个多项式 ，现在他想求这个多项式的若干点值。
即，给定 ，需要你求 。由于结果可能很大，你需要输出结果对 998244353 取模的值。

解题思路

使用多项式计算的秦九韶算法，对于每个 ，时间复杂度为 。

#include<iostream>
#include<vector>
using namespace std;

const int MOD = 998244353;

long long f(long long x, vector<int>&a){
    int n = a.size();
    long long ans = a[n-1];
    for(int i=n-2; i>=0; --i){
        ans *= x;
        ans += a[i];
        ans %= MOD;
    }
    return ans;
}

int main(){
    int n, m;
    cin >> n;
    vector<int> a(n+1);
    long long sum = 0;
    for(int i=0; i<=n; ++i){
        cin >> a[i];
        sum += a[i];
    }
    cin >> m;
    vector<int> x(m);
    for(int i=0; i<m; ++i){
        cin >> x[i];
    }
    for(int i=0; i<m; ++i){
        if(x[i]==1){
            cout << sum << " ";
            continue;
        }
        cout << f(x[i],a) << " ";
    }
    return 0;
}

C 小L的编辑器

题目：
小 L 发明了一个文本编辑器。
该文本编辑器的运行方式大概是这样的：一开始文本为空，有一个光标在开头，每一次小 L 会输入一个字符，该字符就会被插入到光标的位置上，然后光标会随机地停留在该字符的左边或右边。
现在小 L 用这个文本编辑器打了一大段文字，但他却忘了保存了，他只记得他依次打了哪些字符和打完每个字符后光标停在了该字符的左边还是右边，请帮助他还原出最终文本的内容。

解题思路

使用链表保存最终文本的内容。
如果光标停留在当前字符的左边，则将下一个字符插入当前字符的左边，反之则插入右边。
最后从头到尾输出链表的字符。
因为链表的插入操作的时间复杂度是 ，所以最终时间复杂度为 ， 表示文本的字符串个数。

#include<iostream>
using namespace std;

struct ListNode{
    char val;
    ListNode* next;
    ListNode():val('0'),next(nullptr){}
    ListNode(char ch):val(ch),next(nullptr){}
};

int main(){
    string s, t;
    cin >> s >> t;
    ListNode* head = new ListNode();
    ListNode* cur = new ListNode(s[0]);
    head->next = cur;
    ListNode* pre = head;
    for(int i=1; i<s.size(); ++i){
        ListNode* q = new ListNode(s[i]);
        if(t[i-1]=='L'){
            pre->next = q;
            q->next = cur;
            cur = q;
        }
        else{
            q->next = cur->next;
            cur->next = q;
            pre = cur;
            cur = q;
        }
    }
    cur = head->next;
    while(cur){
        cout << cur->val;
        cur = cur->next;
    }
    cout << endl;
    return 0;
}

D 小L的数列

题目：
小L喜欢数和数列。小L称这些数为优秀的。小L称一个序列为好的当且仅当：
1.对于任意的 ，满足 。
2.对于任意的 ，满足 。其中， 为 和 的最大公因数。
3.对于任意的 ，这个数是优秀的。
现在，小L想知道最长的能称为好的的序列的长度是多少，容易证明这个长度是有穷的。

解题思路

首先筛选出素数。

先对数列 a 进行排序，这样满足条件 1。

动态规划：
dp[i] 表示加入 a[i] 的 b 数列的最长长度。
状态转移公式：dp[i] = max(dp[i], dp[x]+1)。其中 gcd(a[i],a[x])>1，i>x。

遍历 a，分解出每个值的质因数。
mp 记录排序后的 a 数列中当前最后一个包含某个质因数在 a 中的索引。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N = 100005;
int vis[N];
vector<int> p;

void f(){
    for(long long i=2; i<N; ++i){
        if(!vis[i]){
            p.push_back(i);
            for(long long j=i*i; j<N; j+=i){
                vis[j] = 1;
            }
        }
    }
}

int main(){
    f();
    int T, n;
    scanf("%d", &T);

    while(T--){
        scanf("%d", &n);
        vector<int> a(n);
        for(int i=0; i<n; ++i){
            scanf("%d", &a[i]);
        }

        sort(a.begin(),a.end());

        vector<int> dp(n,1);
        unordered_map<int,int> mp;
        int ans = 1;
        for(int i=0; i<n; ++i){
            int val = a[i];
            for(int fact : p){
                if(val<=1) break;
                if(val%fact==0){
                    if(mp.count(fact)>0){
                        int x = mp[fact];
                        dp[i] = max(dp[i], dp[x]+1);
                    }
                    mp[fact] = i;

                    while(val%fact==0) val/=fact;
                }
            }
            ans = max(ans, dp[i]);
        }

        printf("%d\n", ans);
    }
    return 0;
}