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

A：小L的作文

解析：简单的字符串问题，只需要查找一下然后记录相同字母就行

#include <bits/stdc++.h>
using namespace std;
int main()
{
  char c;
  char s[101010];
  scanf("%c %s", &c, s);
  int ls = strlen(s);
  int ans = 0;
  for (int i = 0; i < ls; ++i)
  {
    if (s[i] == c)
    ++ans;
  }
  cout << ans << endl;
}

B：小L的多项式

方法一：数学+快速幂

解析：数学+快速幂，只需要模拟一下就可以了，注意开long long

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], b[maxn];
ll fastpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ll n;
    scanf("%lld", &n);
    int cnt = n + 1;
    for (int i = 1; i <= cnt; ++i)
        scanf("%d", &a[i]);
    ll ans;
    ll sum = 0, tot = 0;
    scanf("%lld", &ans);
    for (int i = 1; i <= ans; ++i)
    {
        ll x, k = n;
        sum = 0;
        scanf("%lld", &x);
        for (int i = cnt; i >= 1; --i)
        {
            ll ss = pow(x, k);
            //  cout << x << ' ' << ss << endl;
            sum = sum + (ss * a[i]) % mod;
            k--;
        }
        //  cout << "-----" << sum << endl;
        b[++tot] = sum % mod;
    }
    for (int i = 1; i <= tot; ++i)
        printf("%d ", b[i]);
}

方法二：多点求值

解析：从高到低，每次乘以x再加上a[i]，就可以了，可以手动模拟一遍

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn];
int main()
{
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i <= n; ++i)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
    {
        int x;
        ll ans = 0;
        scanf("%d", &x);
        for (int j = n; j >= 0; --j)
            ans = (ans * x + a[j]) % mod;
        printf("%lld ", ans);
    }
    return 0;
}

C:小L的编辑器

解析：因为每一次的光标移动的时候，字符串的前缀后缀都不会变，所以可以开两个数组模拟一下，也可以发现每次对应出现R的时候这些字符都在一个数组里面，其余的都在另外一个数组里面

方法一：数组模拟

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char a[maxn], b[maxn], L[maxn], R[maxn];
vector<int> v;
int main()
{
  scanf("%s", a);
  scanf("%s", b);
  int la = strlen(a);
  int l = 0, r = 0;
  for (int i = 0; i < la; ++i)
    if (b[i] == 'R')
      L[++l] = a[i];
    else
      R[++r] = a[i];
  for (int i = 1; i <= l; ++i)
    putchar(L[i]);
  for (int i = r; i >= 1; --i)
    putchar(R[i]);
  return 0;
}

方法二：栈和队列模拟

解析：栈是先进后出，队列是先进先出，这和数组模拟差不多，也是放在两个容器里面，逐一输出就行

#include <bits/stdc++.h>
using namespace std;

int main()
{
  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;
}