牛客IOI周赛23-普及组

A、小L的作文

模拟

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans(0);
    string s;
    char x;
    cin>>x>>s;
    for(auto y:s) {
        if(y==x) ans+=1;
    }
    cout<<ans<<'\n';
    return 0;
}

B、小L的多项式

思路：
n、m比较小可以直接暴力
下标从大到小扫一遍，通过每次，同时求出所有项

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,mod=998244353;
typedef long long ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
int a[10005];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<=n;++i) scanf("%d",&a[i]);
    int q,x;
    scanf("%d",&q);
    ll ans;
    while(q--) {
        scanf("%d",&x);
        ans=0;
        for(int i=n;~i;--i) ans=(ans*x+a[i])%mod;
        printf("%lld ",ans);
    }
    return 0;
}

C、小L的编辑器

思路：
当光标在输入完的字符右边时，这个字符的位置已经确定了，可以直接输出
当光标在输入完的字符左边时，位置还不确定，由于每次输入的字符都会在它前面，有点类似栈，可以放在栈里面。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=1e6+7;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
int pos[maxn],n,tot=-1;
char s[maxn],t[maxn],ans[maxn];
stack<char>q;
int main() {
    scanf("%s%s",s,t);
    n=strlen(s);
    for(int i=0;s[i];++i) {
        if(t[i]=='L') q.push(s[i]);
        else ans[++tot]=s[i];
    }
    while(q.size()) {
        ans[++tot]=q.top();
        q.pop();
    }
    ans[++tot]='\0';
    puts(ans);
    return 0;
}

D、小L的数列

思路：
引理：对于质数 ，若存在 且 都是 的倍数，那么选出的序列一定不会让 相邻。

先筛出1e5以内的所有素数，然后对序列排序
根据定理，对每个数，分解质因数(直接枚举质数来加速)，然后，与有相同的质因数且最靠近它()

MyCode:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
bool vis[maxn];
vector<int>prime;
inline void initial() {
    for (int i = 2; i < maxn ; ++i) {
        if (!vis[i])
            prime.emplace_back(i);
        for (int j = 0,size=prime.size(); j < size; ++j) {
            if (i * prime[j] >= maxn) break;
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
int  dp[maxn] , last[maxn];
bool a[maxn];
inline int max(int a,int b) {
    return a>b?a:b;
}
inline int read() {
    char c=getchar();
    int x=0;
    bool f=0;
    for(; !isdigit(c); c=getchar())f^=!(c^45);
    for(; isdigit(c); c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;
    return x;
}
int main() {
    initial();
    int T = read() , n , k;
    while(T--) {
        n = read();
        memset(last , 0 , sizeof(last));
        memset(a , 0 , sizeof(a));
        for(int i = 1 ; i <= n ; ++i) {
            k = read();
            a[k] = 1;
        }
        int m (0),res=1;
        dp[1] = 1;
        for(int i = 2 ,y; i <= 100000 ; ++i) {
            if(a[i] == 0)   continue;
            dp[y=i]=1;
            for(auto x : prime) {
                if(x > y)   break;
                if(!vis[y]) {
                    if(last[y])
                        dp[i] = max(dp[i] , dp[last[y]] + 1);
                    last[y] = i;
                    break;
                }
                if(y % x == 0) {
                    if(last[x])
                        dp[i] = max(dp[i] , dp[last[x]] + 1);
                    last[x] = i;
                    while(y % x == 0)   y /= x;
                }
            }
            res = max(res , dp[i]);
        }
        printf("%d\n" , res);
    }
    return 0;
}