# 【ZOJ】3785 What day is that day? ——浅谈KMP应用之ACM竞赛中的暴力打表找规律

ZOJ 3785

What day is that day?

Time Limit: 2 Seconds      Memory Limit: 65536 KB

It‘s Saturday today, what day is it after 11 + 22 + 33 + ... + NN days?

#### Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is only one line containing one integer N (1 <= N <= 1000000000).

#### Output

For each test case, output one string indicating the day of week.

```2
1
2
```

#### Sample Output

```Sunday
Thursday
```

#### Hint

A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2 5 1 5 1 0 1 4 1 4 4 6 0 1 1 3 2 6 1 0 1 2 2 1 2 6 0 1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2 5 1 5 1 0 1 4 1 4 4 6 0 1 1 3 2 6 1 0 1 2 2 1 2 6 0 1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2

```/*注：int next[]为next数组，int arr[]为要找规律的数组，len为数组长度*/
next[0] = 0;
for(int i = 1, q = 0; i < len; i++){
while(q > 0 && arr[i] != arr[q])
q = next[q-1];
if (arr[i] == arr[q])
q++;
next[i] = q;
if (q != 0 && (i + 1) % (i + 1 - q) == 0){
printf("%d\n", i+1-q);
break;
}
}```

AC代码如下：

``` 1 #include <cstdio>
2
3 const char day[10][10] = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
4 int s[300];
5
6 int work(int n)
7 {
8     int sum = 1;
9     for(int i = 1; i <= n; i++){
10         sum = sum * n;
11         sum %= 7;
12     }
13     return sum;
14 }
15
16 void init()
17 {
18     s[0] = 0;
19     for(int i = 1; i <= 294; i++){
20         s[i] = s[i-1] + work(i);
21         s[i] %= 7;
22     }
23 }
24
25 int main()
26 {
27     int T;
28     int n;
29     init();
30     scanf("%d", &T);
31     while(T--){
32         scanf("%d", &n);
33         n %= 294;
34         printf("%s\n", day[ s[n]]);
35     }
36     return 0;
37 }```

---------------------------------------------------------我是分割线--------------------------------------------------------------

【ZOJ】3785 What day is that day? ——浅谈KMP应用之ACM竞赛中的暴力打表找规律,布布扣,bubuko.com

## ZOJ 3622 Magic Number 打表找规律

A - Magic Number Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu Submit Status Practice ZOJ 3622 Appoint description: Description A positive number y is called magic number if for every positive integer x it satisfies that

## 浅谈KMP算法及其next[]数组

KMP算法是众多优秀的模式串匹配算法中较早诞生的一个,也是相对最为人所知的一个. 算法实现简单,运行效率高,时间复杂度为O(n+m)(n和m分别为目标串和模式串的长度),比蛮力算法的O(nm)快了许多. 理解KMP算法,关键是理解其中的精髓——next[]数组. (统一起见,下文将目标字符串记作obj,将模式字符串记作pattern,这与后面的程序代码是一致的) 我们给一个字符串S定义一个next值,记作next(S),next(S)=n表示: (1)S的前n个字符构成的前缀,和后n个字符的后缀

## zoj 3629 Treasure Hunt IV 打表找规律

H - Treasure Hunt IV Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Description Alice is exploring the wonderland, suddenly she fell into a hole, when she woke up, she found there are b - a + 1 treasures labled a from b in

## 浅谈六类布线施工过程中要考虑的因素-深圳苏山伟达

1.电缆拉伸张力 不要超越电缆制造商规则的电缆拉伸张力.张力过大会使电缆中的线对绞距变形,严重影响电缆按捺噪音(NEXT.FEXT 及衍生物) 的才能,及严重影响电缆的结构化回波损耗,这会改动电缆的阻抗,危害整体回波损耗功能.这些要素是高速局域网体系传输中的重要要素,如千兆位以太网.此外,这可能会导致线对散开,可能会损坏导线. 2.电缆曲折半径 防止电缆过度曲折,由于这会改动电缆中线对的绞距.如果曲折过度,线对可能会散开,导致阻抗不匹配及不行接受的回波损耗功能.别的,这可能会改动电缆内部4 个线