NOIP2017模拟赛（十三）总结

NOIP2017模拟赛（十三）解题报告

---

T1：炸弹

【题目描述】
在一个N行M列的二维网格里，有些格子是空地（用字符‘.’表示），有些格子是障碍物（用字符‘#’表示）。每个空地格子都有一只虫子，虫子不会移动。FJ打算用最少的炸弹把所有的虫子消灭。FJ每次可以选择在一个空地格子（不妨假设是格子a）放置一个炸弹，这个炸弹爆炸后，格子a的虫子会被消灭，假设有另一个空地格子b，如果空地格子b同时满足如下两个条件，那么空地b格子的虫子也会被该炸弹消灭：
1、格子a和格子b在同一行或者在同一列。
2、格子a和格子b之间没有障碍物格子。
有趣的是，任意两个不同的空地格子都有且只有一条由空地格子构成的路径，即所有空地格子构成一棵树形结构。注意：炸弹并不能毁灭障碍物！
【输入格式】
第一行，两个整数，n和m。1 <= n, m<=50。
接下来是n行m列的二维网格。
【输出格式】
一个整数。

题目分析：考场上这题卡了我1.5h，最后写了个30分的爆搜+大数据随机化，结果随机化一分没拿……。而且由于在这题花了很多时间，导致后面T2没有写对拍。
我一开始看到这题的时候，觉得肯定是贪心。于是我YY了很多种贪心的方法，然而都举出了反例。我看旁边的lhxQAQ也在苦思冥想，觉得这题肯定不简单，但我又不愿放弃：怎么可以第一题就写骗分呢？接下来的题目还怎么拿分呀！（考完试后我才知道T1是最难的）
50min之后，我想出了一种比较靠谱的贪法（至少我没举出反例）：我们称由空地格子组成的一横或一竖为一条路径，记两条路径的交点为关键点，那么放炸弹的时候肯定放关键点更优（如第二个样例中全部炸关键点）。某条路径上可能有多个关键点，但一定会有一条路径只有一个关键点。为什么呢？如果所有路径都有两个或以上的关键点，它们必定形成环，这与题面不符。那么我们假设路径x上只有一个关键点y，我们每次就炸这个关键点y，然后按这个原则继续炸下去，直到炸完所有的空地。注意由于每炸一次将树分成多个连通块，可能会出现许多孤立的单条路径，这时我们随便选路径上的一个点炸即可。
同时我也想了一个看上去很靠谱的随机化算法：每次随机选取一些关键点，直到炸完所有的空地，然后将当前选取的关键点个数更新答案。我们在时间允许的情况下多次执行这个过程，最后输出答案。我感觉如果关键点个数不多的话这个算法能拿很多分，于是写了这个随机化，结果……呵呵。现在想来好像能得到答案的机率确实挺小的。而且我是一开始就将图中的所有关键点列出来，然后随机选取；应该每次炸完一个点再重新列一遍关键点会更优才对，虽然这样每次执行所需的时间会变多，导致执行次数变少，但效率更高。
回家之后我写了写贪心的方法，改了几次就A了……有挺多细节要注意的，其中有一个很重要的地方：我们沿着某条路径炸一个点的时候，要看一下这个点是否还属于其它路径，如果是的话就先不要炸它。举个例子，原图为：
1000
1101
0000
1110
（在这里用0表示空地，用1表示障碍）
假设我们先炸(1,3)，就变成了：
1YBY
11Y1
00X0
1110
图中所有标B或Y的地方表示被炸过，那么X要不要认为被炸过呢？是，则接下来图中就有两条孤立的路径，随便选一个点炸可能要炸2次；否，则图中还存在一个关键点，炸它就只要炸一次。于是我们认为X未被炸过。这样做的话，我写的程序时间复杂度为 O(x2n) ，其中x是原图关键点个数。

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=55;
const int u[4]={0,1,0,-1};
const int v[4]={1,0,-1,0};

int val[maxn][maxn];
int X[maxn*maxn];
int Y[maxn*maxn];
int cnt;

int num[maxn][maxn];
int last[maxn][maxn];

bool map[maxn][maxn];
bool now[maxn][maxn];
int n,m,ans=0;

bool Work()
{
memset(val,0,sizeof(val));
    cnt=0;
bool flag=false;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
        {
if (now[i][j]) flag=true;
if ( now[i-1][j] || now[i+1][j] ) val[i][j]++;
if ( now[i][j-1] || now[i][j+1] ) val[i][j]++;
if ( now[i][j] && val[i][j]>=2 ) cnt++,X[cnt]=i,Y[cnt]=j;
        }

if (!flag) return false;
if (!cnt)
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (now[i][j])
                {
for (int w=0; w<4; w++)
for (int k=0; true; k++)
                        {
int x=i+u[w]*k,y=j+v[w]*k;
if (!map[x][y]) break;
                            now[x][y]=false;
                        }
                    ans++;
return true;
                }

memset(num,0,sizeof(num));
memset(last,0,sizeof(last));
for (int i=1; i<=cnt; i++)
for (int j=0; j<4; j++)
for (int k=0; true; k++)
            {
int x=X[i]+u[j]*k,y=Y[i]+v[j]*k;
if (!map[x][y]) break;
                last[x][y]=i;
                num[x][y]++;
            }

    num[0][0]=10000;
int x=0,y=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if ( now[i][j] && last[i][j] && num[i][j]<num[x][y] )
                x=i,y=j;

int id=last[x][y];
    now[ X[id] ][ Y[id] ]=false;
for (int j=0; j<4; j++)
for (int k=1; true; k++)
        {
            x=X[id]+u[j]*k,y=Y[id]+v[j]*k;
if (!map[x][y]) break;
            now[x][y]=false;
if ( now[x-1][y] && now[x+1][y] ) now[x][y]=true;
if ( now[x][y-1] && now[x][y+1] ) now[x][y]=true;
        }
    ans++;
return true;
}

int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
        {
char c=getchar();
while ( c!='.' && c!='#' ) c=getchar();
if (c=='.') map[i][j]=true;
else map[i][j]=false;
            now[i][j]=map[i][j];
        }

while ( Work() );
printf("%d\n",ans);

return 0;
}

---

T2：贸易

【题目描述】
我们大天朝共有m个城市，一开始某些城市间有双向道路，使得m个城市中的n个城市是连通的，并且这n个城市中的每两个城市间有且仅有一条路径。每个城市中的商品都有一个价格。HYC可以从某一个城市中买入商品，经过一些道路后到达另一个城市卖出商品，赚取其间的差价。HYC是一只很奇葩的生物，他会选择两个城市x和y，然后询问从x城市走到y城市经过的这条路径上能赚取的最大差价是多少。当然，如果最大差价小于0，TA就不会做任何贸易，收益为0。在HYC询问的过程中，天朝会有新的道路建造，具体过程是一个原本与外界阻隔的城市与已经在连通块中的城市间建造一条双向道路。LZT作为HYC的好友，义不容辞地承担起回答HYC询问的任务。
【输入格式】
输入文件第一行包含三个整数m、n和c，分别表示城市总数、一开始连通的城市数，操作数。
接下来的一行共m个整数，第i个整数vi表示i号城市中商品的价格为vi。
接下来的n-1行，每行有两个整数x和y，表示城市x和y之间有一条双向道路。
接下来的c行，每行有三个数k、x和y，当k=0时表示询问从城市x走到城市y最多能够赚取多少银子，k=1时表示在城市x和y间建造了一条双向道路。
【输出格式】
对于输入文件中的每个询问(x,y)，输出一行一个整数，表示从x城市走到y城市最多能赚到多少银子。
【输入样例】
5 3 4
5 1 3 2 4
1 3
3 4
0 1 4
1 2 1
1 4 5
0 2 5
【输出样例】
0
4
【样例解释】
一开始1、3、4三个城市连通。第一个询问：1城市到4城市路径上的商品价格依次为5、3、2，依次减小，所以无法取得收益，输出0。第二、三个操作分别把2城市连到1城市、5城市连到4城市，第四个操作：2城市到5城市路径上的商品价格依次为1、5、3、2、4，所以从2城市买入商品，从1城市卖出，得到收益最大为4。
【数据范围】
对于10%的数据，1≤n≤m≤10，0≤c≤10。
对于30%的数据，1≤n≤m≤500，0≤c≤500。
对于100%的数据，1≤n≤m≤100000，0≤c≤100000，0≤vi≤100000。

题目分析：这题本应是我得分的主要来源，结果变成了失分的主要来源……一开始我花了20min想树上倍增，想了一会儿感觉要维护很多东西……。既然这是树上路径问题，就可以用LCT解决。如果要查询u->v的答案，我Evert(u)，Access(v)之后，只要在Splay上记录一下左右儿子答案的最大值，再用右儿子的最大值减左儿子的最小值更新当前答案就可以了。至于翻转标记……我们直接记原答案为ans1，翻转后的答案为ans2，ans2用左儿子的最大值减右儿子的最小值维护，翻转的时候交换ans1，ans2即可（数据结构常用套路）。
哇，动态树裸题呀！我兴奋不已，25min敲完了，然后检查代码，造了几组小数据，完全没问题。（我还担心会不会有些卡常数。）结果一测：第2个点RE，3~8个点WA。看到评测结果的那一刻，我整个人懵逼了：我居然会写错数据结构？直到回到宿舍，我都在回想自己LCT的代码，为什么会出问题。我感觉自己LCT白学了，七八道练习题白做了。明明会做却拿不到分，学来有什么用？看看人家n平方的暴力都60了，我一写炸就只有样例分……
第二天我回到机房，仔细查看我LCT部分的代码，然而一点问题都没有。我忽然想起我为了降低常数，手写了max，min，swap三个函数，然后我检查了一下：
我没有写取址符！我没有写取址符！我没有写取址符！
由于这个手写的Swap是在Splay翻转的时候调用的，所以小数据根本看不出问题（小数据只能检查我的LCT部分是否写错）……一改，立马90（还有一个点是因为数据有问题，点的编号不是1~m）。
算了我已经不想说什么了，这次是我第一次手写Swap，就当积累经验吧……另外，有时间一定要写对拍。

CODE（LCT）：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int maxn=100100;

int Min(int x,int y)
{
return ((x<y)? x:y);
}

int Max(int x,int y)
{
return ((x>y)? x:y);
}

void Swap(int &x,int &y)
{
int z=x;
    x=y;
    y=z;
}

struct Tnode
{
int val,Lmin,Lmax,Rmin,Rmax,ans1,ans2,path_parent;
bool flip;
    Tnode *fa,*son[2];
int Get_d() { return fa->son[1]==this; }
void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
void Push_down()
    {
if (flip)
        {
            swap(son[0],son[1]);
if (son[0])
            {
                Swap(son[0]->Lmin,son[0]->Rmin);
                Swap(son[0]->Lmax,son[0]->Rmax);
                Swap(son[0]->ans1,son[0]->ans2);
                son[0]->flip^=1;
            }
if (son[1])
            {
                Swap(son[1]->Lmin,son[1]->Rmin);
                Swap(son[1]->Lmax,son[1]->Rmax);
                Swap(son[1]->ans1,son[1]->ans2);
                son[1]->flip^=1;
            }
            flip=false;
        }
    }
void Up()
    {
        Lmin=Lmax=Rmin=Rmax=val;
        ans1=ans2=0;
if (son[0])
        {
            Lmin=Min(Lmin, Min(son[0]->Lmin,son[0]->Rmin) );
            Lmax=Max(Lmax, Max(son[0]->Lmax,son[0]->Rmax) );
            ans1=Max(ans1,son[0]->ans1);
            ans2=Max(ans2,son[0]->ans2);
        }
if (son[1])
        {
            Rmin=Min(Rmin, Min(son[1]->Lmin,son[1]->Rmin) );
            Rmax=Max(Rmax, Max(son[1]->Lmax,son[1]->Rmax) );
            ans1=Max(ans1,son[1]->ans1);
            ans2=Max(ans2,son[1]->ans2);
        }
        ans1=Max(ans1,Rmax-Lmin);
        ans2=Max(ans2,Lmax-Rmin);
    }
} tree[maxn];
Tnode *Node[maxn];
int cur=-1;

int V[maxn];
int m,n,c;

Tnode *New_node(int v)
{
    cur++;
    tree[cur].val=tree[cur].Lmin=tree[cur].Lmax=tree[cur].Rmin=tree[cur].Rmax=v;
    tree[cur].ans1=tree[cur].ans2=tree[cur].path_parent=0;
    tree[cur].flip=false;
    tree[cur].fa=tree[cur].son[0]=tree[cur].son[1]=NULL;
return tree+cur;
}

void Push(Tnode *P)
{
if (!P) return;
    Push(P->fa);
    P->Push_down();
}

void Zig(Tnode *P)
{
int d=P->Get_d();
    Tnode *F=P->fa;
if (P->son[!d]) F->Connect(P->son[!d],d);
else F->son[d]=NULL;
if (F->fa) F->fa->Connect(P, F->Get_d() );
else P->fa=NULL;
    P->Connect(F,!d);
    F->Up();
    P->path_parent=F->path_parent;
    F->path_parent=0;
}

void Splay(Tnode *P)
{
    Push(P);
while (P->fa)
    {
        Tnode *F=P->fa;
if (F->fa) ( P->Get_d()^F->Get_d() )? Zig(P):Zig(F);
        Zig(P);
    }
    P->Up();
}

void Down(int x)
{
    Splay(Node[x]);
    Tnode *&tag=Node[x]->son[1];
if (tag)
    {
        tag->fa=NULL;
        tag->path_parent=x;
        tag=NULL;
        Node[x]->Up();
    }
}

void Access(int x)
{
    Down(x);
int y=Node[x]->path_parent;
while (y)
    {
        Down(y);
        Node[y]->Connect(Node[x],1);
        Node[y]->Up();
        Node[x]->path_parent=0;
        x=y;
        y=Node[x]->path_parent;
    }
}

void Evert(int x)
{
    Access(x);
    Splay(Node[x]);
    Node[x]->flip^=1;
    Swap(Node[x]->Lmin,Node[x]->Rmin);
    Swap(Node[x]->Lmax,Node[x]->Rmax);
    Swap(Node[x]->ans1,Node[x]->ans2);
}

void Link(int x,int y)
{
    Evert(x);
    Node[x]->path_parent=y;
}

int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);

scanf("%d%d%d",&m,&n,&c);
for (int i=1; i<=m; i++) scanf("%d",&V[i]);
for (int i=0; i<maxn; i++) Node[i]=New_node(V[i]);
for (int i=1; i<n; i++)
    {
int x,y;
scanf("%d%d",&x,&y);
        Link(x,y);
    }

for (int i=1; i<=c; i++)
    {
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if (k) Link(x,y);
else
        {
            Evert(x);
            Access(y);
            Splay(Node[x]);
int ans=Node[x]->ans1;
printf("%d\n",ans);
        }
    }

return 0;
}

回到家之后，我又仔细想了想树上倍增的做法。其实知道了怎么用LCT做之后，树上倍增要维护的东西很快就能想出来。设mid为i向上跳 2j 步所到达的点，我们记big[i][j]为i~mid的最大val值，small为最小值，up[i][j]为i走到mid的最大收益，down[i][j]为mid走到i的最大收益。询问u->v的时候我们模仿LCA的倍增过程，用不超过 3log(n) 的时间将u，v跳至LCA处，如下图：

这样我们就将u->v的路径分成了不超过 3log(n) 块，对于块内的答案，我们直接调用up和down的信息，对于跨越块间的答案，我们可以用和块的个数成正比的时间暴力求得。时间复杂度 O(nlog(n)) 。

CODE（LCA）：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=100100;
const int maxl=20;

struct edge
{
int obj;
    edge *Next;
} e[maxn<<1];
edge *head[maxn];
int cur=-1;

int big[maxn][maxl];
int small[maxn][maxl];

int up[maxn][maxl];
int down[maxn][maxl];

int X[maxn];
int Y[maxn];
int num=0;

int fa[maxn][maxl];
int dep[maxn];

int max1[maxl*3];
int min1[maxl*3];
int len1;

int max2[maxl];
int min2[maxl];
int len2;

int val[maxn];
int n,m,c,ans;

void Add(int x,int y)
{
    cur++;
    e[cur].obj=y;
    e[cur].Next=head[x];
    head[x]=e+cur;
}

void Dfs(int node)
{
for (edge *p=head[node]; p; p=p->Next)
    {
int son=p->obj;
if (son!=fa[node][0])
        {
            fa[son][0]=node;
            dep[son]=dep[node]+1;
            Dfs(son);
        }
    }
}

int main()
{
    freopen("b.in","r",stdin);
    freopen("b(LCA).out","w",stdout);

scanf("%d%d%d",&m,&n,&c);
for (int i=1; i<=m; i++) scanf("%d",&val[i]);
for (int i=1; i<maxn; i++) head[i]=NULL;

int s;
for (int i=1; i<n; i++)
    {
int x,y;
scanf("%d%d",&x,&y);
        Add(x,y);
        Add(y,x);
        s=x;
    }

for (int i=1; i<=c; i++)
    {
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if (k) Add(x,y),Add(y,x);
else num++,X[num]=x,Y[num]=y;
    }

    fa[s][0]=s;
    dep[s]=1;
    Dfs(s);

for (int i=1; i<maxn; i++)
    {
        big[i][0]=max(val[i],val[ fa[i][0] ]);
        small[i][0]=min(val[i],val[ fa[i][0] ]);

        up[i][0]=max(0,val[ fa[i][0] ]-val[i]);
        down[i][0]=max(0,val[i]-val[ fa[i][0] ]);
    }

for (int j=1; j<maxl; j++)
for (int i=1; i<maxn; i++)
        {
int mid=fa[i][j-1];
            fa[i][j]=fa[mid][j-1];

            big[i][j]=max(big[i][j-1],big[mid][j-1]);
            small[i][j]=min(small[i][j-1],small[mid][j-1]);

            up[i][j]=max( max(up[i][j-1],up[mid][j-1]) , big[mid][j-1]-small[i][j-1] );
            down[i][j]=max( max(down[i][j-1],down[mid][j-1]) , big[i][j-1]-small[mid][j-1] );
        }

for (int i=1; i<=num; i++)
    {
int u=X[i],v=Y[i];
if (u==v)
        {
printf("0\n");
continue;
        }

bool flip=false;
if (dep[u]<dep[v]) swap(u,v),flip=true;
        len1=len2=ans=0;

for (int j=maxl-1; j>=0; j--)
if (dep[ fa[u][j] ]>=dep[v])
            {
if (!flip) ans=max(ans,up[u][j]);
else ans=max(ans,down[u][j]);

                len1++;
                max1[len1]=big[u][j];
                min1[len1]=small[u][j];

                u=fa[u][j];
            }

if (u!=v)
        {
for (int j=maxl-1; j>=0; j--)
if (fa[u][j]!=fa[v][j])
                {
if (!flip) ans=max(ans, max(up[u][j],down[v][j]) );
else ans=max(ans, max(up[v][j],down[u][j]) );

                    len1++;
                    max1[len1]=big[u][j];
                    min1[len1]=small[u][j];

                    len2++;
                    max2[len2]=big[v][j];
                    min2[len2]=small[v][j];

                    u=fa[u][j];
                    v=fa[v][j];
                }

if (!flip) ans=max(ans, max(up[u][0],down[v][0]) );
else ans=max(ans, max(up[v][0],down[u][0]) );

            len1++;
            max1[len1]=big[u][0];
            min1[len1]=small[u][0];

            len2++;
            max2[len2]=big[v][0];
            min2[len2]=small[v][0];
        }

for (int j=len2; j>=1; j--)
        {
            len1++;
            max1[len1]=max2[j];
            min1[len1]=min2[j];
        }

if (flip) for (int j=1; j<=(len1>>1); j++)
            swap(max1[j],max1[len1-j+1]),swap(min1[j],min1[len1-j+1]);

for (int j=2; j<=len1; j++) min1[j]=min(min1[j],min1[j-1]);
for (int j=len1-1; j>=1; j--) max1[j]=max(max1[j],max1[j+1]);

for (int j=1; j<len1; j++) ans=max(ans,max1[j+1]-min1[j]);
printf("%d\n",ans);
    }

return 0;
}

---

T3：青蛙

【题目描述】
FJ的庄稼最近受到青蛙的严重损坏。青蛙会从跳过FJ的农田，青蛙每次跳跃的距离是相等的。不同的青蛙每次的跳跃能力可能不一样，跳跃的方向可能也不同，如下图所示：这些都是青蛙的跳跃路线。

FJ的农田被分成R行C列,在行列的交界处有庄稼。 青蛙从农田的某一侧外面，跳过农田，跳到农田的另一侧。如下面的Figure-1所示。

农田里可能有很多条青蛙路线.。 如Figure-3所所示. 注意：同一个庄稼可能被多个青蛙跳过. 当然，在农田外面的，你可以不管。

你想知道到底有多少条青蛙路线，这里说的青蛙路线指的是在农田里至少有三个点的。
在 Figure-3里画出了3条青蛙路线 (当然还有其他的青蛙路线没画出来). 当然，像第2行第1列的点和第6行第1列的点距离是4，但只有两个点，因此不是青蛙路线。
（2，3）、（3，4）、（6，7）有三个点，但是他们的距离不相等，所以也不是青蛙路线。
另外要注意的是：在某一条合法的青蛙路线中间，可能会有一些点，但你可以忽视它 (例如在Figure-4里，请看第2行，有5个点，其中点(2, 6)你可以忽视它，剩下的4个点构成一条青蛙路线).你的任务是：计算最长的青蛙路线经过的点数。
【输入格式】
第1行: 两个整数：R, C. 1 <= R <= 5000; 1 <= C <= 5000.
第 2行: 一个整数N,农田里点的个数 , 3 <= N <= 5000.
第 3..N+2行: 两个整数ri,ci. (1<= ri<= R) 、(1<= ci <= C).表示一个点所在的行和列，给出点不会有重复
【输出格式】
一行:一个整数，最长的青蛙路线经过的点数。如果没有，输出0.
【输入样例】
6 7
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7
【输出样例】
7
时限2s

题目分析：这题我20min写完了代码，以为 O(n3) 一分都拿不到，结果AC了……该怎么说呢？事后想想，只能用一句话来表达：意料之外，情理之中。我的做法是先将所有点存进哈希表里面，然后暴力枚举两个点为相邻点向两边扩展，判断是否存在某个点时 O(1) 查询Hash表即可。由于枚举是 n2 的，扩展的过程是可能达到 O(n) ，所以我理所当然地认为这是立方级别的。
但考完试后我重新思考了一下，发现这样做是 O(n2ln(n)) 的。我们先来考虑一下什么样的数据会让我这个算法运行次数最多。由于不存在某个点时我会break掉扩展的过程，所以肯定是5000个点全在一条直线上时我的程序运行时间最久。这种情况下我们枚举了间隔为1的点对 n−1 次，每次共向两边扩展 n−1 步，时间可以近似看成 n2 ；枚举间隔为2的点对 n−2 次，每次共向两边扩展 n−22 步，时间可以看成 n22 ……
于是：
T=n2+n22+……+n2n=n2(1+12+……+1n)=n2ln(n)
由于常数较小且时限2s，AC也就不奇怪了。（我听说Ab.Ever也想到了这个方法，但以为立方算法一分得不到就没有写代码，呵呵。这告诉我们时间复杂度的证明很重要，敢于写暴力也很重要。）

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const long long M1=998585857LL;
const long long M2=233333333LL;
const int M=3005007;
const int maxn=5010;
typedef long long LL;

struct data
{
int x,y;
} Hash[M];

int r[maxn];
int c[maxn];
int R,C,N;
int ans=0;

void Push(int nx,int ny)
{
    LL id=(nx*M1+ny*M2)%M;
while (Hash[id].x) id=(id+1)%M;
    Hash[id].x=nx;
    Hash[id].y=ny;
}

bool Judge(int nx,int ny)
{
return 1<=nx && nx<=R && 1<=ny && ny<=C;
}

bool Check(int nx,int ny)
{
    LL id=(nx*M1+ny*M2)%M;
while ( Hash[id].x && ( Hash[id].x!=nx || Hash[id].y!=ny ) ) id=(id+1)%M;
return Hash[id].x;
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

scanf("%d%d%d",&R,&C,&N);
for (int i=1; i<=N; i++)
    {
scanf("%d%d",&r[i],&c[i]);
        Push(r[i],c[i]);
    }

for (int i=1; i<N; i++)
for (int j=i+1; j<=N; j++)
        {
int num=2;
int dx=r[i]-r[j];
int dy=c[i]-c[j];

bool flag=true;
for (int k=1; Judge(r[j]-dx*k,c[j]-dy*k); k++)
            {
if ( !Check(r[j]-dx*k,c[j]-dy*k) )
                {
                    flag=false;
break;
                }
                num++;
            }
if (!flag) continue;

for (int k=1; Judge(r[i]+dx*k,c[i]+dy*k); k++)
            {
if ( !Check(r[i]+dx*k,c[i]+dy*k) )
                {
                    flag=false;
break;
                }
                num++;
            }
if ( flag && num>=3 ) ans=max(ans,num);
        }

printf("%d\n",ans);
return 0;
}

---

总结：这次比赛问题主要出在T1。我不仅用时过长影响T2对拍，还高估了随机化算法的得分效率，放弃了看上去很靠谱的贪心。也许我处理贪心方面的能力还要加强。T2的话……就当积累教训吧。对于我而言写LCT和写LCA差不多一样熟练，而在这题中用前者去想思维难度应该更低些。T3虽然我错误估计了时间复杂度，但还是印证了那句话：写暴力总比不交代码强。