HDU5944——Fxx and string Fxx and string

63 阅读 0 评论 42 点赞

我是靠谱客的博主忧虑小馒头，最近开发中收集的这篇文章主要介绍HDU5944——Fxx and string Fxx and string，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Fxx and string

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 963 Accepted Submission(s): 399

Problem Description

Young theoretical computer scientist Fxx get a string which contains lowercase letters only.

The string

S contains

n lowercase letters

S1S2…Sn .Now Fxx wants to know how many three tuple

(i,j,k) there are which can meet the following conditions:

1、

i,j,k are adjacent into a geometric sequence.

2、

Si= '

y '

,Sj= '

r '

,Sk= '

x '.

3.Either j|i or j|k

Input

In the first line, there is an integer

T(1≤T≤100) indicating the number of test cases.

T lines follow, each line contains a string, which contains only lowercase letters.(The length of string will not exceed

10000 ).

Output

For each case, output the answer.

Sample Input

  
  
   
   2
xyyrxx
yyrrxxxxx

Sample Output

0
2

Source

BestCoder Round #89

题意：

青年理论计算机科学家Fxx得到了一个只包含小写字母的字符串。

字符串的长度为 $n$ ，下标从1开始，第 $i$ 位的字母为 $:s_i$ ，现在Fxx想知道有多少三元组 $(i, j, k)$ 满足下列条件

1、 $i, j, k$ 三个数成等比数列

2、 $s_i=$ ' $y$ ' $,s_j=$ ' $r$ ' $,s_k=$ ' $x$ '

3. $i / j$ 和 $k / j$ 中必须有整数

解：

根据题意直接对于 i,j,k三个变量进行打表操作，然后再字符串中根据已经得到的 i,j,k进行寻找并进行计数。注意反向同样适合规则。

#include <stdio.h>
#include <string.h>
#include <math.h>
char a[10005];
char b[10005];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        getchar();
        while(n--)
        {
            memset(a,0,sizeof(a));
            gets(b);
            int len=strlen(b);
            int i,j,k;
            int count=0;
            for(int m=1;m<=len;m++)
            {
                a[m]=b[m-1];
            }
            for(int z=1;z<=sqrt(len);z++)
            {
                for(i=1;i<=len;i++)
                {
                    j=i*z;
                    k=j*z;
                    if(i<=len && j<=len && k<=len)
                    {
                        if(a[i]=='y' && a[j]=='r' && a[k]=='x')
                        {
                            count++;
                        }
                        if(a[i]=='x' && a[j]=='r' && a[k]=='y')
                        {
                            count++;
                        }
                    }
                }
            }
            printf("%dn",count);
        }
    }
    return 0;
}