牛客IOI周赛23-普及组_题解

第一题：
小L的作文
题目大意：给定一个字符串，找到字符串中特定字符的个数。

解题思路：
遍历字符串，将目标字符与字符串中的每个字符，一一匹配，并进行计数即可。

ac代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char c;
    string s;
    cin>>c>>s;
    int i;
    int num=0;
    for(i=0;i<s.length();i++){
        if(s[i]==c){
            num++;
        }
    }
    cout<<num<<endl;
    return 0;
}

第二题：
小L的多项式
题目大意：
已知f(x) =a(n)x^n+a(n-1)x^(n-1)+...+a(1)x^1+a(0)x^0
给定各个位置的系数和指数
给定多个x的值，求出f（x）的值结果对998244353取模

解题思路：
这个题有两种方法
第一种是采用秦九韶算法
图片说明
将原来的方程转化为这样的形式
此时问题的复杂度只有O（n）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int Mod=998244353;
long long f (int n,int a[],int x){
    long long p=a[n];
    for(int i=n;i>0;i--)
        p=(a[i-1]+(x*p)%Mod)%Mod;
    return p;
}
int main()
{
    int m,n;
    int a[maxn];
    int temp;
    scanf("%d",&m);
    for(int i=0;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&temp);
        if(i==0)
        printf("%lld",f(m,a,temp));
        else {
                printf(" %lld",f(m,a,temp));    
        }
    }
    return 0;    
}

本题还有一种解法
通过快速幂来避免因为使用pow函数而导致的超时的问题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int Mod=998244353;
typedef long long ll;
ll quick(ll a,ll b,ll c){
ll A = 1;
ll T = a % c;
while(b!=0){
if(b&1)
A = (A * T ) % c;
b >>= 1;
T = (T * T ) % c;
}
return A;
}
int main()
{
    ll m,n;
    ll a[maxn];
    ll x[maxn];
    ll ans=0;
    scanf("%lld",&m);
    for(int i=0;i<=m;i++)
    {
        scanf("%lld",&a[i]);
    }
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&x[i]);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            ans+=(a[j]*quick(x[i],j,Mod))%Mod;
            ans%=Mod;
        }
        if(i==0)
        printf("%lld",ans);
        else printf(" %lld",ans);
        ans=0; 
    }
    return 0;    
}

第三题：
小L的编辑器
题目大意：
有一个字符串str，和另一个由RL组成的字符串，两两相对应，然后有一个光标，读的是R就插入的光标右边，读入L就插入到光标的左边，问最后形成的新的字符串。

解题思路：
因为向左插入的时候新插入的是放在原来的后面，而向右插入的时候，就是放在原来的前面，因此可以分别用队列和栈储存两边的字符。最后再输出出来就可以了

ac代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1;
    string s2;
    cin>>s1>>s2;
    stack<char>s;
    queue<char>q;

    int i,j;
    for(i=0;i<s1.length();i++){
        if(s2[i]=='L'){
            s.push(s1[i]);
        }
        else{
            q.push(s1[i]);
        }
    }
    char c;
    while(!q.empty()){
        c=q.front();
        cout<<c;
        q.pop();
    }
    while(!s.empty()){
        c=s.top();
        cout<<c;
        s.pop();
    }

    return 0;
}

第四题：
小L的数列
（这个题比赛的时候用的一般的dp，只有80分，参考别的大佬的题解，理解了这个题需要的优化方法）

题目大意：
给定一组整数，求满足a[n]>a[n-1]且gcd（a[n],a[n-1]）>1的最长(不连续)序列

解题思路：
首先将数组排序，然后进行dp，假设当前位置是第i个数，可以枚举前i-1个数，取与i的最大公约数大于1的数j，则f[i]=max(f[i],f[j]+1).（这就是比赛的时候遇到的80分的情况），因此需要考虑怎样优化dp的过程，暴力的方法一大部分时间花在了枚举前i-1个数上，如果我们分解质因数，每次转移只需要枚举这个数的质因子即可。

ac代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int dp[maxn],num[maxn];
int main() {
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int n;
        scanf("%d",&n);
        memset(num,0,sizeof num);
        memset(dp,0,sizeof num);
        for(int i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            num[temp]=1;
        }
        int ans=0;
        for(int i=1;i<=maxn;i++)
        {
            int t=i;
            if(num[i]) dp[i]=max(dp[i],1),ans=max(ans,1);
            else continue;
            for(int j=2;j<=sqrt(t);j++)
            {
                if(t%j==0)
                {
                    for(int k=i+j;k<=maxn;k+=j)
                    {
                        if(num[k])
                        {
                            ans=max(ans,dp[k]=max(dp[k],dp[i]+1));
                            break;
                        }
                    }
                    while(t%j==0)
                    {
                         t/=j;
                     }
                }
            }
            if(t>1)
            {
                int j=t;
                for(int k=i+j;k<=maxn;k+=j)
                {
                    if(num[k])
                    {
                        ans=max(ans,dp[k]=max(dp[k],dp[i]+1));
                        break;
                    }
                }
            }
        }
        printf("%d\n",ans);

    }
    return 0;
}