HDU 5944 Fxx and string【题意】【枚举】

发表于 | 更新于 | 分类于

题目大意：

给出一个字符串$S$($|S| < 10000$)，问你能找出多少个下标三元组$(i, j, k)$，使得他们同时满足下列条件：

  1. $i,j,k$ are adjacent into a geometric sequence.($i, j, k$成等比数列)
  2. $Si=’y’,Sj=’r’,Sk=’x’. $
  3. Either $j|i$ or $j|k$ .(i % j == 0 || k % j == 0)

解题思路：

知道i,j,k是等比数列后就可以直接做了。

固定住j的位置，枚举i和k的取值情况。

MyCode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 11111;

int t;
char s[N];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", s);
        int len = strlen(s), res = 0;
        for(int i = 1; i <= len; ++i)
        {
            if(s[i - 1] == 'r')
            {
                for(int j = 2; i * j <= len; ++j)
                {
                    if(i % j == 0)
                    {
                        int pre = i / j, nex = i * j;
//                        printf("%d %d %d %d\n", i, j, pre, nex);
                        if(s[pre - 1] == 'x' && s[nex - 1] == 'y')  ++res;
                        if(s[nex - 1] == 'x' && s[pre - 1] == 'y')  ++res;
                    }
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}
Donate comment here
0%