题解 P6273 【[eJOI2017]魔法】

· · 题解

放个题面

P6273 [eJOI2017]魔法

非常妙的一道题

一定要认真审题！！！

我一开始就没看见这句话:

“ 设 S 中不同的字符数为 k ”

步骤：

  1. 求得每一个位置上每个字母的前缀和

  2. 标记出现过的字母并找到一枚幸运的j 这一步很巧妙，任意j都可以，我们称其为幸运的j (doge）

  3. 将每个i的前缀和减掉此i中幸运j的前缀和 可能有点拗口，仔细想想很少女口阿

  4. 对上一次操作得到的数组进行排序（使得每个包含式的魔法串相邻）

  5. 利用求和公式 (n-1)*n/2 求得答案

主要是步骤2、3很难想，思维难度有点打

code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;
const int N = 100010;

struct node
{
  int a[53];
  bool operator <(const node x)const
  {
    for(int i = 0; i < 52; ++i)
      if(a[i] != x.a[i])
        return a[i] < x.a[i];
    return 0;
  }
//细节排序，处理相等情况
  bool operator ==(const node x)const
  {
    for(int i = 0; i < 52; ++i)
      if(a[i] != x.a[i])
        return 0;
    return 1;
  }
}sum[N];

int n, t;
char s[100010];
bool vis[53];

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL),cout.tie(NULL);
  cin>>n>>s + 1;
//步骤1：
  for(int i = 1; i <= n; ++i)
    for(int j = 0; j < 52; ++j)
      if(j < 26 && s[i] - 'a' == j || j >= 26 && s[i] - 'A' == j - 26)
        sum[i].a[j] = sum[i - 1].a[j] + 1;
      else
        sum[i].a[j] = sum[i - 1].a[j];
//步骤2：
  for(int i = 0; i < 52; ++i)
    if(sum[n].a[i]) vis[i] = true, t = i;
//步骤3：
  for(int i = 1; i <= n; ++i)
    for(int j = 0; j < 52; ++j)
      if(vis[j])
        sum[i].a[j] -= sum[i].a[t];
//步骤4：
  sort(sum,sum + n + 1);
//步骤5：
  int ans = 0;
  for(int l = 0, r; l <= n; l = r + 1)
  {
    r = l;
    while(r < n && sum[r + 1] == sum[r])++r;
    int len = r - l + 1;
    ans = (ans + 1ll * len * (len - 1) / 2 % mod) % mod;//n*(n-1)/2
  }
//
  cout<<ans;
  return 0;
}

另外eJOI这几道题都很好，这道题算比较简单的

eJOI

谢谢阅读