我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
这个题需要用到我们的神奇海螺分层图大法，像我一样不会分层图的右转去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、正解
你猜
其实这道题方法很多，只是个人倾向的问题。本人更倾向链表队列的方法
- 将所有的点加入链表
- 从链表中随便拿出一个点加入队列，如果链表为空，结束
- 遍历队列
- 对于当前点，把该点的连接的边打标记。
- 遍历链表，取出没有打标记的点从链表中删去并加入队列。
- 取消标记。
- 在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;