798236606 发表于 2020-1-29 12:50:13

PTA A_1093 Count PAT's

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184

解：递推法
#include <stdio.h>
#include <string.h>

typedef long long int LL;

char str;
int P_num;
int T_num;

int main(void)
{
      int i, len;
      LL count = 0;
      
      gets(str);
      
      len = strlen(str);
      
      P_num = (str == 'P') ? 1 : 0;
      T_num = (str == 'T') ? 1 : 0;
      
      for (i = 1; i < len; i++)
                P_num = (str == 'P') ? (P_num + 1) : P_num;

      for (i = len - 2; i >= 0; i--)
                T_num = (str == 'T') ? (T_num + 1) : T_num;

      for (i = 0; i < len; i++)
                if (str == 'A')
                        count += (LL)P_num * (LL)T_num;

      printf("%d", count % 1000000007);
      
      return 0;
}


页: [1]
查看完整版本: PTA A_1093 Count PAT's