有几个PAT（25）

#include<cstdio>
#include<cstring>
const int MAXN = 100010;
const int MOD = 1000000007;
char str[MAXN];
int numLeftP[MAXN] = { 0 };
int main(){
	gets(str);
	int len = strlen(str);
	for (int i = 0; i < len; i++){
		if (i>0)
			numLeftP[i] = numLeftP[i - 1];
		if (str[i] == 'P')
			numLeftP[i] += 1;
	}
	int ans = 0, numRightT=0;
	for (int i = len - 1; i >= 0; i--){
		if (str[i] == 'T')
			numRightT++;
		else if (str[i] == 'A')
			ans = (ans + numLeftP[i] * numRightT) % MOD;
	}
	printf("%d\n", ans);
	return 0;
}

#include <cstdio>
int main() {
    for(int c, p = 0, pa = 0, pat = 0; ((c = getchar()) != '\n' ? (c == 'P'? ++p : (c == 'A' ? (1 + (pa = (pa + p) % 1000000007)) : (1 + (pat = (pat + pa) % 1000000007)))) : (~printf("%d\n", pat))) > 0;);
    return 0;
}

分析

• 暴力破解是不可能暴力的，这辈子都不会暴力的。还是分析下他的数学规律吧。

• 首先，应该看到它的有序性，PAT字符串是按顺序的，有点动态规划的意思，也就是，没遇到A前，P个数是被统计的，A以后的P是遇到下一个A才会被统计。考虑APAPAT返回应该是3。所以有每次遇到A前，统计P个数；遇到A时，应统计PA个数，也就是之前的PA和当前组成PA的个数；遇到T时，应统计PAT个数，也就是之前的PAT和当前PAT个数。

/*
 * app=PAT-Basic lang=c++
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616
 */
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 100010;
char ch[maxn];
int main()
{
    scanf("%s",ch);
    int len = strlen(ch);
    int res = 0, P = 0, PA = 0;
    for (int i = 0; i < len; i++){
        if (ch[i] == 'P') P++;
        if (ch[i] == 'A') PA = (PA + P) % 1000000007;//这里很巧妙地解决了PA的顺序出现。要慢慢理解
        if (ch[i] == 'T') res = (res + PA) % 1000000007;//这里很巧妙地解决了PAT的顺序出现。
    }
    printf("%d",res);
    return 0;
}

小觑天下英雄了！
灵光一现想到这种方法，正自鸣得意，评论区一看，大家都是用的这类似的方法。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PatNum
{
    class Pat
    {
        static void Main(String[] argu)
        {
            String s = Console.ReadLine();
            int p = 0, pa = 0, pat = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == 'P')
                {
                    p++;
                }
                if (s[i] == 'A')
                {
                    pa += p;
                }
                if (s[i] == 'T')
                {
                    pat += pa;
                }
                pat = pat % 1000000007;
            }
            Console.WriteLine(pat);
            Console.ReadKey();
        }
    }
}

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function(line) {
    var res = 0;
    var p = 0;
    var t = line.length - line.replace(/T/g, '').length;
    for (var i = 0; i < line.length; i++) {
        switch (line[i]) {
            case "P":
                p++;
                break;
            case "A":
                res = (res + p * t) % 1000000007;
                break;
            case "T":
                t--;
                break;
        }
    }
    console.log(res);
});

//答案参考的那个“啥”的代码，真大神，膜拜了。
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    long pCount = 0, paCount = 0, patCount = 0;
    char letter;
    scanf("%c", &letter);
    while(letter != '\n' && letter != ' ')
    {
        if(letter == 'P')
            pCount++;
        else if(letter == 'A')
            paCount += pCount;
        else
            patCount += paCount;
        scanf("%c", &letter);
    }
    cout << patCount % 1000000007;
    return 0;
} 

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    // 初始化变量
    char c; int p=0, pa=0, pat=0;

    // 统计
    while(scanf("%c", &c) && c!=' ' && c!='\n') {
        if(c == 'P') {
            p++;
        } else if(c == 'A') {
            pa += p;
            pa = pa%1000000007;
        } else {
            pat += pa;
            pat = pat%1000000007;
        }
    }
    printf("%d\n", pat);
    return 0;
} 

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String text = in.next();
		int pCount = 0;
		int paCount = 0;
        int total = 0;
		for(int i = 0;i<text.length();i++){
			char c = text.charAt(i);
			if(c=='P'){
				pCount++;
			}else if(c=='A'){
				paCount += pCount;
			}else{
				total += paCount;
				total %= 1000000007;
			}
		}
		System.out.println(total);
	}
}

#include <iostream>
using namespace std;
char s[100010];
int main(){
    cin>>s;
    long long p=0,pa=0,pat=0;
    for(int i=0;s[i];i++){
        if(s[i]=='P') p++;         //i及左边共几个p
        else if(s[i]=='A') pa+=p;  //i及左边共几个pa
        else pat+=pa;              //i及左边共几个pat
    }
    cout<<pat%1000000007;
    return 0;
}

import java.util.Scanner;

/**
 * 有几个PAT
 * 题目描述
 * 字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；
 * 第二个PAT是第3位(P),第4位(A),第6位(T)。现给定字符串，问一共可以形成多少个PAT？
 * 输入描述:
 * 输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。
 * 输出描述:
 * 在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。
 * 输入例子:
 * APPAPT
 * 输出例子:
 * 2
 *
 * @author shijiacheng
 * @date 2018/2/1
 */
public class B1030HowManyPAT {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        char[] chars = str.toCharArray();

        int countT = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'T') {
                countT++;
            }
        }
        int countP = 0;
        int result = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'P') {
                countP++;
            }
            if (chars[i] == 'T') {
                countT--;
            }
            if (chars[i] == 'A') {
                result = (result + (countP * countT) % 1000000007) % 1000000007;
            }
        }

        System.out.println(result);
    }
}