我TM但凡有点水平也不至于一点水平没有吧。——每日感想

T1

距离/P4162 [SCOI2009] 最长距离
这道题本质上是一道十分弱智的搜索题，无论是开DFS还是开BFS还是开BDFS都能做。本人在这里不建议使用使用deque进行BFS，理由是运行速度比较慢，稍有不慎就见祖宗了。
我在这里使用DFS,但是纯净的DFS直接用估计不大行（自己算算，你就知道为啥不大行了）。所以我们加上大记忆恢复术记忆化和剪枝。就可以过掉该题目了。

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int n,m,t,t;
int ans;
int dis[40][40],a[40][40];
void dfs(int x,int y,int sum){
    if(sum>T){
    	return ;
	}
    if(sum>=dis[x][y]){
    	return ;
	}
    dis[x][y]=sum;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1||yy<1||xx>n||yy>m){
        	continue;
		}       
        dfs(xx,yy,sum+a[xx][yy]);
    }
}
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            memset(dis,INF,sizeof(dis));
            if(a[i][j]==1)
            dfs(i,j,1);
            else dfs(i,j,0);
            for(int x=1;x<=n;x++){
                for(int y=1;y<=m;y++){
                    if(dis[x][y]<=t){
                        ans=max(ans,((i-x)*(i-x)+(j-y)*(j-y)));
                    }
                }
            }
        }
    }
    printf("%.6lf",sqrt(ans));
    return 0;
}

T2

交通/P1346 电车

这个题需要用到我们的神奇海螺分层图大法，像我一样不会分层图的右转去bdfs一下

题目中给出的只有两种状态：横边和纵边。我们建立两层图，第一层只存储横边，第二层只存储纵边。

显然，只需要在相邻两个换乘站（即可以转向的交汇站）之间建立双向边。否则走到其他站点就再也回不了家了。

于是，在每一层内，我们分别以换乘站的横坐标或纵坐标为第一关键字排序，那样就省去了一个换乘站和其他所有都建边的操作，只需在相邻两个之间建边即可，并且不影响图的连通性。

之后考虑层与层之间建边。如果要从一层转到另一层（相当于转向操作），需要1单位时间。那么就将每层中的相同节点之间建立一条边权为一的边。特别地，起点和终点要建立边权为0的边。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+10;
const int inf=1e+8;
int g[maxn][maxn];
int n,m,k,f,t;
int main()
{
    scanf("%d%d%d",&n,&f,&t);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {g[i][j]=inf;g[i][i]=0;} 
    for(int i=1;i<=n;i++){
    scanf("%d",&k);
    for(int j=1;j<=k;j++){
    int a;
    scanf("%d",&a);
    if(j==1)g[i][a]=0;
    else g[i][a]=1;
    }
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    if(g[f][t]==inf)puts("-1");
    else printf("%d",g[f][t]);
}

T3

鸽了

T4

微信/P3452 [POI2007] BIU-Offices

想要做对这道题，学好语文很重要（？）。本题目的特殊限制是不在同一个牛圈里的牛必须是微信好友，但是他说在同一个牛圈里的牛一定不是了吗？没说！所以那些语文不好读不懂题的人就寄了。
然后考虑一下一些方法：
1、暴力
这个题吧，一次性存入所有的边然后暴力地去走，我没说不可以，只是你看看这个: $ 2≤N≤10^5 $,如果暴力能过那么有且仅有两种可能：数据太水，或者你这测评机是太湖一号（或者别的什么）。
这一条知道了，下一个。
2、 跑SPFA
我就只能说：spfa……额……但愿他和pause玩得开心。
3、正解

你猜

其实这道题方法很多，只是个人倾向的问题。本人更倾向链表队列的方法

1. 将所有的点加入链表
2. 从链表中随便拿出一个点加入队列，如果链表为空，结束
3. 遍历队列
   • 对于当前点，把该点的连接的边打标记。
   • 遍历链表，取出没有打标记的点从链表中删去并加入队列。
   • 取消标记。
4. 在3中进入队列的点统计为一个连通块

/、不是本人代码，凑合着看吧
#include <cstdio>
#include <algorithm>
const int N=1e5+10;
const int M=2e6+10;
int head[N],to[M<<1],Next[M<<1],cnt;
void add(int u,int v)
{
    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int n,m,pre[N],suc[N],q[N],l,r,ans[N],col[N],tot;
int main()
{
    scanf("%d%d",&n,&m);
    for(int u,v,i=1;i<=m;i++)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n;i++)
        pre[i]=i-1,suc[i]=i+1;
    suc[0]=1,suc[n]=0;
    while(suc[0])
    {
        l=1,r=0;
        q[++r]=suc[0];
        suc[0]=suc[suc[0]];
        pre[suc[q[r]]]=0;
        while(l<=r)
        {
            int now=q[l++];
            for(int i=head[now];i;i=Next[i])
                col[to[i]]=1;
            int cur=suc[0];
            while(cur)
            {
                if(!col[cur])
                {
                    q[++r]=cur;
                    pre[suc[cur]]=pre[cur];
                    suc[pre[cur]]=suc[cur];
                }
                cur=suc[cur];
            }
            for(int i=head[now];i;i=Next[i])
                col[to[i]]=0;
        }
        ans[++tot]=l-1;
    }
    std::sort(ans+1,ans+1+tot);
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
    return 0;