首页 > ACM题库 > HDU-杭电 > hdu 2652 Warching TV-模拟-[解题报告]C++
2014
02-12

hdu 2652 Warching TV-模拟-[解题报告]C++

Warching TV

问题描述 :

Lemon likes warching TV very much. When winter holiday comes, it is a good time, isn’t it. There are lots of TV program listed on the paper. Every TV program has its start time ,end time, and the happiness value that will add Lemon’s happiness and it depends on Lemon’s taste.

输入:

There are many test cases. Please process to end of file. Each test case starts with one integer N (1 <= N <= 100000) which indicates the size of the list of the TV program. Then N lines follow, each line contains three integers s, e and v. s, e indicate that the TV program is during [s, e](1 <= s <= e <= 1000000). v indicates that after warching the TV program will add Lemon v happyiness(1 <= v <= 1000). Once Lemon choose a TV program, he must finish warching the TV program.

输出:

There are many test cases. Please process to end of file. Each test case starts with one integer N (1 <= N <= 100000) which indicates the size of the list of the TV program. Then N lines follow, each line contains three integers s, e and v. s, e indicate that the TV program is during [s, e](1 <= s <= e <= 1000000). v indicates that after warching the TV program will add Lemon v happyiness(1 <= v <= 1000). Once Lemon choose a TV program, he must finish warching the TV program.

样例输入:

2
1 2 1
3 4 2
2
1 2 1
2 4 2

样例输出:

3
2

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=2562

题意:求任意年的11月份的第四个星期日的具体日期(感恩节)的日期。

方法一:直接模拟,999年11月1日是星期五(可以试出来)。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int a[10005];
    int t = 5;
    for(int i=1000; i<=9999; i++)
    {
        if(i%400 == 0 || (i%4 == 0 && i%100!=0))
        {
            t+=2;
        }
        else
        {
            t++;
        }
        t%=7;
        a[i] = t;
    }
    int n;
    while(scanf(" %d",&n)!=EOF)
    {
        int x=a[n]-4;
        printf("%d-11-",n);
        if(x<=0)
        {
            printf("%d\n",3*7-x+1);
        }
        else
        {
            printf("%d\n",4*7-x+1);
        }
    }
    return 0;
}

方法二:蔡勒公式

公式:

蔡勒公式: 

W =( [C/4] – 2C + y + [y/4] + [13×(M+1) / 5] + d – 1) % 7; 

W是星期几,C是世纪数减一,y是年份后两位,M是月份(从3月开始,1月和2月要按上一年的13月和 14月来算,这时C和y均按上一年取值),d是日数。

出W的值,再除以7,余几就是星期几,余数为0,则是星期天。

注意:[...]表示只取整数部分

注意:公式中如计算得出负数,不能按习惯的余数的概念求余数,只能按数论中的余数的定义求余。为了方便计算,我们可以给它加上一个7的整数倍,使

变为一个正数,比如加上7、14、21、28等,得到一个整数后, 再除以7,余几,说明这一天是星期几。

#include <cstdio>

int w,c,y,m,d;

int main()
{
  int x;
  m=11;
  while (scanf("%d",&y)==1)
  {
    d=1;
    printf("%d-11-",y);
    c=y/100;
    y%=100;
    w=(c>>2)-(c<<1)+y+(y>>2)+13*(m+1)/5+d-1;
    while (w<0) w+=7;
    w%=7;
    x=4-w;
    if (x<0) x+=7;
    d+=x+21;
    printf("%d\n",d);
  }
  return 0;
}


解题转自:http://blog.csdn.net/niuox/article/details/8832389


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。