牛客IOI周赛23-普及组

A - 小L的作文

题意

给一个字符x和一个字符串b 然后去找b中x出现了几次

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    char a , b;
    cin>>a;
    getchar();
    ll ans = 0;
    while(scanf("%c" , &b) && b != '\n'){
        if(b == a)  ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B - 小L的多项式

题意

简单来说就是给出一个多项式然后给一个数字让你把这个数字带到这个多项式里求值多项式是规律的即 $a_1 * x_{3} + a_2 * x_{2} + a_3 * x{1} + a_4$ 这样

有多少个 $a_i$ 就有多少项（加一项，还有0次方）

并且数据范围较小直接暴力即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
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 N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;


int a[N];

int main(void){
    int n , m;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n + 1 ; ++i){
        scanf("%d" , &a[i]);
    } 
    scanf("%d" , &m);
    ll k = 0;
    for(int i = 1 ; i <= m ; ++i){
        ll ans = 0;
        scanf("%lld" , &k);
        for(int j = 1 ; j <= n + 1 ; ++j){
            ans += a[j] * qpow(k , j - 1 , mod) % mod;
            ans %= mod;
        }
        printf("%lld%c" , ans , i == m ? '\n' :' ');
    }

    return 0;
}

这是我比赛的时候的代码然后还有更快的做法

即因为 $x$ 是不断地从一次方二次方三次方这样乘上来因此我们可以保存上一次的结果然后用到下一次这样就不用每次都 $qpow$ 一下了速度会快很多

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
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 N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;


int a[N];

int main(void){
    int n , m;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n + 1 ; ++i){
        scanf("%d" , &a[i]);
    } 
    scanf("%d" , &m);
    ll k = 0;
    for(int i = 1 ; i <= m ; ++i){
        ll ans = 0;
        scanf("%lld" , &k);
        ll t = 1;
        for(int j = 1 ; j <= n + 1 ; ++j){
            ans += a[j] * t % mod;
            t = (t * k) % mod;
            ans %= mod;
        }
        printf("%lld%c" , ans , i == m ? '\n' :' ');
    }

    return 0;
}

C - 小L的编辑器

题意

给出两个字符串a ，b，然后a中的字符按照b的规律输出，即有一个光标，每一次输出之后，光标停的位置按照b的顺序

即 a中为 ab

b为LR

那么第一次输出之后就是 |a

然后再输出b就是在a的左边

即输出之后就是 b|a

如果这个时候还是有一个c 然后对应b中是L

那么就是b|ca

到现在为止如果直接去模拟不仅时间复杂度裂开而且挺难模拟的

我们直接观察以光标为分界线其实不难看出在右边的就是谁先进来就排在后面左边的就是谁先进来就谁排在前面所以很明显了

当输入L的时候就把字符插到一个栈中输入R的时候就插到队列中然后把栈和队列按顺序输出就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    string a , b;
    cin>>a>>b;
    stack<char>st1;
    queue<char>st2;
    for(int i = 0 ; i < a.size() ; ++i){
        if(b[i] == 'L'){
            st1.push(a[i]);
        }
        else{
            st2.push(a[i]);
        }
    }
    while(st2.size()){
        cout<<st2.front();
        st2.pop();
    }
    while(st1.size()){
       cout<<st1.top();
       st1.pop();
    }
    return 0;
}

D - 小L的数列

题意

给出 $n$ 个数要求从中挑出一些数来组成一个数列要求排在前面的小于后面的并且相邻的两个数字不互质

要不互质那么我们就要求取出来的数字两个之间有相同的因子，因此我们可以先把所有的素数筛出来，然后我们去找那些数字有这个素数作为因子的，再找数字的时候我们可以记录这个数字的下一个用相同因子的素数

我们只需要找到下一个有着相同的因子的数即可然后进行dp

然后这个代码应该是目前最快的了

几个加速的地方桶排因为数据卡的很那个所以用桶排是比直接sort要快的

然后dp的优化因为上面也说了我们只要把上一个和他有相同因子的转移过来就可以了

然后筛素数的时候只需要筛到 $2 * i < maxn$ 就可以了因为后面不会再出现这个素数的倍数了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
bool vis[maxn];
vector<int>prime;
int i ;
inline int max(int a,int b) {
    return a>b?a:b;
}
inline void initial() {
    for (i = 2; 2 * i < maxn ; ++i) {
        if (!vis[i])
            prime.push_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;
        }
    }
}
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 a[N] , dp[N] , last[N];
int main(void){
    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;
        int res = 1;
        for(i = 2 ; i <= 100000 ; ++i){
            if(a[i] == 0)   continue;
            dp[i] = 1;
            int y = i;
            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;
}