题目：金字塔的秘密

时空限制

CPU占用时长: 1秒

内存使用限制: 128MB

题目描述

小C和小T准备金字塔探秘.他们建造了一个N层的金字塔,并把他们喜欢的句子写在上面,一行一行地重复(每行的方向相反,具体看示例).

就像下面的示例:

金字塔示例

小T选了K个问题,每个问题包含一个数字a和字母c,表示询问”在金字塔的第a行有多少个字母c出现”.你是小C的助手,请写一个程序帮助他解决问题!

输入格式

第一行输入一个整数N(1<=N<=10^18),代表金字塔的高度.

第二行一个字符串表示他们喜欢的句子(全部是大写英语字母),句子的长度不超过10^6.

第三行一个整数K(1<=K<=50000),表示小T选择的问题个数.

接下来K行,包含一个数字a,字母c,表示小T的问题.

输出格式

输出K行,每行一个整数,表示出现在a行的字母c的次数.

输入输出样例

样例1

输入样例

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

输出样例

样例2

输入样例

5
A
5
1 A
2 A
3 A
4 A
5 B

输出样例

样例3

输入样例

3
AB
3
2 A
2 B
3 B

输出样例

1
1
2

数据范围与提示

50%的数据N<=1000.

70%的字符串的长度不超过10^5

100%的数据,N<=10^18,字符串的长度不超过10^6,K<=50000.

我的代码

思路之类全部写在了注释里

#include <iostream>
#include <cstring>
using namespace std;

char word[1000100];            // 存储字符串
int word_len;                  // 存储字符串的长度
int count_letter[1000100][27]; // count_letter[i][j]表示在这个字符串下标为0至下标为i的所有字符中，字母j-'A'+1出现了几次

long long toa(long long, char); // toa(a, c)表示从金字塔的第1行到第a行字符c一共出现了几次

int main()
{
std:
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long n, a;
    int k;
    char c;
    cin >> n >> word >> k;
    word_len = strlen(word);

    count_letter[0][word[0] - 'A' + 1]++;
    for (int i = 1; i < word_len; i++)
    {
        memcpy(count_letter[i], count_letter[i - 1], sizeof(count_letter[i])); // 将上一行的内容复制到这一行
        count_letter[i][word[i] - 'A' + 1]++;
    }

    for (int i = 1; i <= k; i++)
    {
        cin >> a >> c;
        cout << toa(a, c) - toa(a - 1, c) << "\n";
    }
    return 0;
}

long long toa(long long a, char c)
{
    /*
    以下是这个函数的原理
    先统计从第一行到第a行一共有几个字符
    然后把得到的这个值除以字符串的长度，得到完整的字符串一共出现了几次
    在此之后，统计剩下来的这一段一共有多少个字符，然后用先前统计过的count_letter直接得到这一段字符中c出现了几次
    在计算过程中，因为要统计第1行到第a行一共有多少个字符，即a*(a+1)/2，而a*(a+1)肯定会超过long long限制，所以在算的时候调整了一下运算顺序，具体看注释
    */

    // ans是要返回的值，count_word表示完整的字符串一共出现了几次，rem表示剩下来的这一段一共有多少个字符
    long long ans = 0, count_word = 0, rem = 0;
    // 不改变顺序的计算应为：
    // count_word = (a * (a + 1) / 2) / len
    // rem = (a * (a + 1) / 2) % len
    // 为防止溢出，分a为偶数和a为奇数两种情况考虑
    if (a % 2 == 0)
    {
        /*
        当a为偶数时

        count_word = (a / 2) * (a + 1) / word_len
        为防止溢出将* (a + 1)和/ word_len调换位置
        为防止a / 2不整除word_len添加了*1.0（很有可能就是这里出了问题，乘上1.0后long long被强制转换为浮点类型可能丢失了数据）
        不过事实上如果word_len是个很小的数仍然会超过long long，是这样的话就还得写高精度了（我并不喜欢写这个东西）

        rem = (a / 2) * (a + 1) % word_len
        用同余的性质该式变形为rem = (((a / 2) % word_len) * ((a + 1) % word_len)) % word_len（这个肯定没有越界）
        */
        count_word = a / 2 * 1.0 / word_len * (a + 1);
        rem = (((a / 2) % word_len) * ((a + 1) % word_len)) % word_len;
    }
    else
    {
        // a为奇数和a为偶数是一样的道理
        count_word = (a + 1) / 2 * 1.0 / word_len * a;
        rem = ((a % word_len) * (((a + 1) / 2) % word_len)) % word_len;
    }
    ans += count_word * count_letter[word_len - 1][c - 'A' + 1]; // 加上完整字符串中c的个数
    ans += count_letter[rem - 1][c - 'A' + 1];                   // 加上最后一段中c的个数
    return ans;
}

2023/5/26 22:25