牛客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;
}
海康威视工作强度 84人发布
