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

首先声明一下,这里的规律指的是循环,即找到最小循环周期。这么一说大家心里肯定有数了吧,“不就是next数组性质的应用嘛”。

先来看一道题

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.

Sample Input

2
1
2

Sample Output

Sunday
Thursday

Hint

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

题目的大意是知道今天是周六,让你求 f = 11 + 22 + 33 + ... + NN 这么多天之后是星期几。

也就是求f % 7对于每个输入的N的值。这题在网上一搜题解,都说是打表找规律,当然这题有两种找法,一是对于每个ii  % 7 的值都找规律。

这里我们打表可知 前100个值如下所示

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

有一种找规律的方法是当有数字等于第一个数的时候做个标记,再人工判断是否能够构成一个循环。

不可否认的,对于周期较短的一组数字这样找周期并不难,可是如果周期大到数百数千甚至数万时,靠这种方法找周期恐怕是杯水车薪。

当时我就迷茫在了这一长串的数字中不知所措,猛然想起前不久看过的KMP中next数组的性质,当即想到了用KMP求最小重复子串长度的方法,于是脑洞大开……

该性质为:令j=leni-next[i],如果i%j==0且i/j>1,j就是Pi的最小循环节( Pi表示文本串的前i个字符,leni表示该字符串的长度,一般表示为leni = i + 1)

关键代码如下:

/*注: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;
    }
}

可以求出最小周期为42。

还有一种找规律的方法是直接对 f % 7 的值进行打表找规律,按照上述方法找到的周期为294,下面要做的就很简单了~

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 }

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

自从上次大开脑洞之后,今天又遇到了一道题,POJ 3070。

题目的大意是让你求第n个斐波那契数的后四位是多少,题目的本意考察的是矩阵快速幂,可是暴力打表又有何不可呢?遂打表用KMP查询,找到周期为15000,顺利水过了这题~

嗯,这篇文章只是跟大家分享一下自己偶然发现的KMP在竞赛中一种用法,在有些题目中使用不免有投机取巧之嫌(就像POJ 3070 ╮(╯▽╰)╭),不过不管投机不投机,只要能AC,就是好方法。O(∩_∩)O哈哈~ 开个玩笑,若有不足之处,还请各位指正。

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

时间: 08-02

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

浅谈DevExpress&lt;三&gt;:在GridView中加载动态图片

今天的演示效果如下:在GridView中的下拉框中选中一种颜色,则后面的加载相应的图片,如下图: 1. 2. 3. 下面说下实现方法:首先在项目中拉一个GirdControl,在里面创建4列:ID,Name,Color,Image,并将Color和Image分别创建repositoryItemComboBox和repositoryItemPictureEdit控件,如下图: 将一个图片文件夹放到程序的启动目录中: 文件夹中包含如下图片: 接下来进行创建数据模板,先创建一个Datetable,添加

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

浅谈利用同步机制解决Java中的线程安全问题

我们知道大多数程序都不会是单线程程序,单线程程序的功能非常有限,我们假设一下所有的程序都是单线程程序,那么会带来怎样的结果呢?假如淘宝是单线程程序,一直都只能一个一个用户去访问,你要在网上买东西还得等着前面千百万人挑选购买,最后心仪的商品下架或者售空......假如饿了吗是单线程程序,那么一个用户得等前面全国千万个用户点完之后才能进行点餐,那饿了吗就该倒闭了不是吗?以上两个简单的例子,就说明一个程序能进行多线程并发访问的重要性,今天就让我们去了解一下Java中多线程并发访问这个方向吧. **第一

浅谈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个字符的后缀

浅谈今天所学的Jquery 中的filter()方法

一直以来对JQuery很喜欢,它封装了JavaScript,用起来更方便,不过无论什么方法,必须要理解这个方法本来的含义,此外就是要在自己的逻辑上整理清楚,这样才能做到更多的效果.“遇到问题了,多看手册”这句话是当初学脚本语言的时候老师经常说的一句话,当初很郁闷他这句话,不过现在发现,封住的方法的确多得很,只有不断地学习,不断地用到,才会发现这些方法的区别,也才能更加合理地利用这些前辈们为我们打造好的各种包. 先来说说今天认识到的filter()方法吧. 这个方法主要用来遍历列表中的元素,或者有

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 个线

【ASP.NET 系列】浅谈缓存技术在ASP.NET中的运用

本篇文章虽不谈架构,但是Cache又是架构中不可或缺的部分,因此,在讲解Cache的同时,将会提及到部分架构知识,关于架构部分,读者可以不用理解,或者直接跳过涉及架构部分的内容, 你只需关心Cache即可,具体的架构,会在后续文章中与大家分享,如果你感兴趣,只需关注即可. 一   为什么要在ASP.NET 项目中引入缓存 1. 我们先来考虑一个问题,通常,面临高并发问题时,我们应该怎么处理? 下图为常规的处理思路和方法 2.为什么引入Cache呢? 我们知道,造成高并发的根本原因是大量读写的问题

浅谈文档协作在工程设计中的应用——共享excel计算书

我们设计过程中大量采用excel计算书,因为很多经典的计算都可以用excel解决,最最基本的就是工程量计算啦.稍微复杂的比如钢管计算,埋地钢管结构计算,顶管计算,水力学计算,波浪爬高计算,堤防高程计算,挡土墙稳定计算,溢洪道计算,水闸消能计算等,统统可以用excel编写公式解决. 而且随着工作的积累,这些计算书越来越多了,有同事们一起编写的,经过校核和审查的,有的根据需要不断去扩展,去完善的,达到参数化要求的. 比如一些参数化的工程量计算书,一些钢筋图甚至都可以用excel来做,比如输入结构尺寸