对本期集训的回顾（一）

          啦啦啦，小火山这个暑假竟然只放了4天的假（包括双休）！！

          不过这个暑假也学到了许多interesting的东西  (￣▽￣＃) = ﹏﹏

以下为清单（7月）：

                                                                哈希，线段树，堆，树状数组，并查集，

                                                           伸展树，Treap，平衡树，AVL树，树链剖分 。 （是不是很眼熟~~） 

                                     

 

以下为清单（8月）：

                                                  Floyd， 树形DP，拓扑排序，网络流，费用流，关键路径，

                                           康托展开，强联通分量，最大二分匹配，最小覆盖问题，快速幂，堆，

                             线段树，同余方程（组），线性筛，欧拉函数，斜率优化，扩展欧几里得算法（还有   对拍  (#￣▽￣#)）

 

小火山厉害吧！

 

有诗曰：

            混沌未分天地乱，渺渺茫茫无人见。

            自从盘古破鸿蒙，开辟从兹清浊辨。

            覆载群生仰至仁，发明万物皆成善。

            欲知造化会元功，须看《西游释厄传》。

 

 

 

来一道水题

       

题目描述

 【问题描述】
         在一个N*N(1<=n<=1000)的网格中，在某些时刻鼹鼠从在某个网格探出来透气。你可以控制一个机器人打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。机器人每一时刻只能够移动一格或原地不动。机器人只能移向上下左右四个网格，不能走出网格。游戏开始时，你可以*选定机器人的初始位置。
         现在你知道在一段时间内有M(1<=M<=10000)个鼹鼠和它出现的时间T和地点(X,Y)，要求你求出机器人最多打死的鼹鼠数量。
 【输入格式】
    第一行，N,M
    接下来的M行T,X,Y
 【输出格式】
    最多打死的鼹鼠数量
 【输入样例】

2 2

1 1 1
2 2 2

 【输出样例】
1

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    int x,y,t;
}y[110000];
 
int tmp(node n1,node n2)
{
    return n1.t<n2.t;
}
 
int f[110000];
 
 
int main()
{
    int n,m;
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&y[i].t,&y[i].x,&y[i].y);
        if(y[i].x<1||y[i].y<1||y[i].y>n||y[i].x>n)
        y[i].t;
    }
     
    sort(y+1,y+1+m,tmp);
    for(int i=1;i<=m;i++) f[i]=1;
 
    for(int i=2;i<=m;i++)
    {
        for(int j=i-1;j>=1;j--)
        if(abs(y[i].x-y[j].x)+abs(y[i].y-y[j].y)<=y[i].t-y[j].t)
        f[i]=max(f[i],f[j]+1);
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    if(f[i]>ans)
    ans=f[i];
    printf("%d",ans);
    return 0;
}