2014
02-12

# 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

#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是日数。

#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;
}

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

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