音乐安利 8月28日

魔道祖师就是披着糖的玻璃渣。不敢想汪叽被禁闭三年出来听的第一个消息就是羡羡粉身碎骨魂飞魄散,连一块骨头一缕魂魄都找不到的心情。喝他喝过的酒,受他受过的伤。埋下他爱喝的酒,养他送的兔子,等一个不知道会不会回来的人。还好,十三年过去,听到大梵山那曲笛音,他终于回来了。

转载自《与归》网易云评论

幸有故人同归

音乐安利 8月27日

每一片落叶都知你名姓
(因为它们曾听)
我呢喃过无数个黑夜与天明
也许你已经成为
天上某颗永恒闪烁的星
在深夜里温暖着心隅一方天

即使在黑暗之中,也要勇敢地向前走鸭,因为

———— 每一片落叶都知你名姓

CF245G Suggested Friends 题解

这是蒟蒻的第一篇题解 QwQ,如果有讲得不好的地方敬请谅解,并欢迎大佬在下方评论区提出宝贵的意见。

首先呢,

我们来看看这道题的题意。

这道题要输入用户的名字对,并统计用户的个数。仔细想想,我们会发现如果用朴素做法,会变得很麻烦,所以我们搬出了 stl。去重我们一般使用 map,因为操作图的时候,我们要使用一个序号与名字对应,所以我们在 map 里定义两个类型,string 和 int,其中,又因为我们要进行搜索,所以 string 放在前面用作 key。

map<string,int> name;
map<string,int>::iterator iter; // 操作容器

int ix,it,tot;// tot 是唯一用户的数量,ix,iy 为当前用户唯一 id
for(int i=1;i<=m;++i){  
    cin>>x>>y;// 输入用户名字
    iter=name.find(x);// 查找是否已存在
    if(iter!=name.end())  ix=iter->second; // 操作容器的值不为map的尾巴,说明存在
    else name.insert(pair<string,int>(x,ix=++tot)); //不存在,插入并顺手将当前 id 设为用户数量自增后的结果
    iter=name.find(y);
    if(iter!=name.end())  iy=iter->second;
    else name.insert(pair<string,int>(y,iy=++tot));
}

接下来,我们就要进行图论部分的操作了。
老规矩,因为这道题考查的是图中单点对单点的关系,所以我们就不使用结构体了,转而使用 stl 中的 vector。

先定义一个 vector:vector<int> ship[MAXN<<1];

注意,由于图是无向的,所以要添加两次,故定义时 MAXN 要乘 2(二进制写法为 <<1)。

然后在上面输入中,加入:

for(int i=1;i<=m;++i){ 
    // 此处省略上方代码
    ship[ix].push_back(iy);
    ship[iy].push_back(ix);
}

图输入后之后,就可以进行操作了,使用循环来对每个用户进行分析。

根据题意,推荐好友双方必须互不为好友,故我们先要标记一下当前循环到的用户 $i$ 与其他用户 $j$ 是否为好友(别忘了先 memset 下喔)。

for(int i=1;i<=tot;++i){
    memset(flag,0,sizeof flag);
    for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1;
}

接着,我们来判断用户 $i$ 的推荐好友,如果循环两方 $i$ 和 $j$ 相同或是好友,就跳过。

如果上方条件都不满足,那么就继续判断。

再用一个子循环来判断 $j$ 的好友是不是 $i$ 的好友,如果是,就把 $i$ 和 $j$ 的共同好友数量加 1
找完之后,我们再看看 $i$ 和 $j$ 共同好友的数量是不是当前用户 $i$ 的推荐好友中共同好友数量并列最大的,如果是,把 $i$ 推荐好友数量加 1。如果 $i$ 和 $j$ 的共同好友数量甚至比之前找到的还要大,那么用户 $i$ 的推荐用户就变为了 $j$ 一人。

并且,在这些操作后,我们要把 $i$ 的共同好友数量记下来,故开一个数组 ans(大小也要开到MAXN的两倍喔)。

for(int i=1;i<=tot;++i){
    int suggest_friends=0; // 推荐用户数量
    memset(flag,0,sizeof flag); // 清空一下
    for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1; //  标记 i 和 j 好友
    for(int j=1;j<=tot;++j){
        if(i==j) continue; // 同一个人就跳过吧
        if(!flag[j]){ // 不为好友
            int both_friends=0; // 共同好友数量
            for(int k=0;k<ship[j].size();++k){
                if(flag[ship[j][k]]) both_friends++; // 查找 i 和 j 的共同好友
            }
            if(both_friends>ans[i]){ // i 和 j 的共同好友数量甚至比之前找到的还要大
                suggest_friends=1; // i 的推荐用户就变为了 j 一人。
                ans[i]=both_friends;
            }else if(both_friends==ans[i]) suggest_friends++; // 推荐好友数量加 1
        }
    }
    ans[i]=suggest_friends;// 设成最终的推荐用户数量
}

最后,我们把 ans 的第 $i$ 项设成最终的推荐用户数量。
最后的最后,我们循环输入的用户,输出名字和推荐用户数量(感谢出题人没有要求输出的顺序,否则还要麻烦)。

附上完整 AC 代码

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<cstring>

#define il inline

const int MAXN = 5005;

using namespace std;

map<string,int> name;
map<string,int>::iterator iter;  
vector<int> ship[MAXN<<1];
bool flag[MAXN<<1];
int ans[MAXN];

int m;
int main(){
    std::ios::sync_with_stdio(false);
    cin>>m;
    string x,y;
    int ix,iy,tot=0;
    for(int i=1;i<=m;++i){
        cin>>x>>y;
        iter=name.find(x);
        if(iter!=name.end())  ix=iter->second;
        else name.insert(pair<string,int>(x,ix=++tot));
        iter=name.find(y);
        if(iter!=name.end())  iy=iter->second;
        else name.insert(pair<string,int>(y,iy=++tot));
        ship[ix].push_back(iy);
        ship[iy].push_back(ix);
    }
    cout<<tot<<endl;
    for(int i=1;i<=tot;++i){
        int suggest_friends=0;
        memset(flag,0,sizeof flag);
        for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1;
        for(int j=1;j<=tot;++j){
            if(i==j) continue;
            if(!flag[j]){
                int both_friends=0;
                for(int k=0;k<ship[j].size();++k){
                    if(flag[ship[j][k]]) both_friends++;
                }
                if(both_friends>ans[i]){
                    suggest_friends=1;
                    ans[i]=both_friends;
                }else if(both_friends==ans[i]) suggest_friends++;
            }
        }
        ans[i]=suggest_friends;
    }
    for(iter=name.begin();iter!=name.end();++iter){
        cout<<iter->first<<" "<<ans[iter->second]<<endl;
    }
}

OI中的各种板子(持续更新)

快读

返回值版

inline int read() {
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

重载版

inline int read(int& ret) {
    ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    ret*=f;
}

int128 快读快写

#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

int main(){
    __int128 a=read();
    __int128 b=read();
    print(a+b);
    return 0;
}

快速幂

typedef long long ll;
ll quick_pow(ll x,ll n,ll m){
	ll res = 1;
	while(n > 0){
		if(n & 1)	res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

欧拉筛


void phi_table(int n,int* phi) {
  for(int i=2;i<=n;i++) phi[i]=0;
  phi[1]=1;
  for(int i=2;i<=n;i++)
    if (!phi[i])
      for (int j=i;j<=n;j+=i) {
        if (!phi[j]) phi[j]=j;
        phi[j] = phi[j]/i*(i-1);
      }
}

并查集

#include<iostream>
#include<cstdio>

using namespace std;
int fa[10001];
int n,m,p;
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
        return fa[x];
    }
    return x;
}
void set(int x,int y){
    fa[find(x)]=find(y);
}

int main(){
    scanf("%d%d",&n,&m);
    int t0,t1,t2;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&t0,&t1,&t2);
        if(t0==1) set(t1,t2);
        else printf(find(t1)==find(t2)?"Y\n":"N\n");
    }
}

Dijkstra

#include<iostream>
#include<cstdio>
#include<queue>
#define il inline
#define MAXN 100000
using namespace std;

int n,m,s;

struct edge
{
    int to,dis,next;
}e[MAXN];

struct node{
    int val;
    int pos;
    bool operator<(const node &x)const{
        return x.val<val;
    }
};

priority_queue<node> q;
int head[MAXN],dis[MAXN];
bool vis[MAXN];
int cnt=0;

il void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    int a,b,c;
    for(int i=1;i<m;++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dis[n]=0;
    q.push(node{0,n});
    while(!q.empty()){
        node cur=q.top();
        q.pop();
        int vv=cur.val,pp=cur.pos;
        if(vis[pp]) continue;
        vis[pp]=1;
        for(int i=head[pp];i;i=e[i].next){
            int yy=e[i].to;
            if(dis[yy]>dis[pp]+e[i].dis){
                dis[yy]=dis[pp]+e[i].dis;
                if(!vis[yy]) q.push(node{dis[yy],yy});
            }
        }
    }
    printf("%d",dis[s]);
}

SPFA

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define il inline
#define MAXN 100000
#define INF 1e9
using namespace std;

int dis[MAXN],head[MAXN];
bool vis[MAXN];

int n,m,s,cnt=0;

struct edge
{
    int to,dis,next;
}e[MAXN];

il void spfa(){
    memset(dis,INF,sizeof dis);
    memset(vis,1,sizeof vis);
    dis[n]=0;
    vis[n]=false;
    queue <int> q;
    q.push(n);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=true;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[u]+e[i].dis<dis[v]){
                dis[v]=dis[u]+e[i].dis;
                if(vis[v]){
                    q.push(v);
                    vis[v]=false;
                }
            }
        }
    }
}

il void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    int a,b,c;
    for(int i=1;i<m;++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    spfa();
    printf("%d",dis[s]);
}

Kruskal

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

int N,M;
struct edge{
    int u,v,w;
}e[1000001];

int fa[1000001];
int ans,eu,ev,cnt=0;
// cnt=>边数 ans=>边长度之和 eu=>当前起点 ev=>当前终点
using namespace std;

inline bool cmp(edge a, edge b){
    return a.w<b.w;
}

inline int find(int x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

inline void kruskal(){
    sort(e+1,e+1+M,cmp);
    for(int i=1;i<=M;++i){
        eu=find(e[i].u),ev=find(e[i].v);
        if(eu==ev) continue;
        //  两点联通
        ans+=e[i].w;
        fa[ev]=eu;
        ++cnt;
        if(cnt==N-1) break;
    }
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;++i){
        fa[i]=i;
    }
    for(int i=1;i<=M;++i){
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    }
    kruskal();
    printf("%d",ans);
}

LCA

倍增

#include<cstdio>
#include<iostream>
#include<algorithm>
#define il inline
const int MAXN=500005;

using namespace std;

int n,m,s;
struct node{
    int to,next;
}e[MAXN<<1];

int head[MAXN],Log2[MAXN],depth[MAXN],fa[MAXN][22];

int cnt=0;
il void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
il void logc(){
    for(int i=1;i<=n;++i) Log2[i]=Log2[i-1]+(1<<Log2[i-1]==i);
}
il void dfs(int cur,int ff){
    fa[cur][0]=ff;depth[cur]=depth[ff]+1;
    for(int i=1;i<=Log2[depth[cur]];++i){
        fa[cur][i]=fa[fa[cur][i-1]][i-1];
    }
    for(int i=head[cur];i;i=e[i].next){
        if(e[i].to!=ff) dfs(e[i].to,cur);
    }
}
il int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);
    while(depth[x]>depth[y]){
        x=fa[x][Log2[depth[x]-depth[y]-1]];
    }
    if(x==y){
        return y;
    }
    for(int k=Log2[depth[x]]-1;k>=0;--k){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k],y=fa[y][k];
        }
    }
    return fa[x][0];
}
int main(){
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    logc();
    dfs(s,0);
    int x,y;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
}

tarjan

#include<iostream>
#include<cstdio>
#define il inline
using namespace std;

int n,m,s,x,y,tot=0,vtot=0;
const int N=500005,M=1000005;
int head[N],to[M],nxt[M];
int vhead[N],vto[M],vnxt[M];
int fa[N],lca[2*M];
bool visit[N];
il void add(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
il void vadd(int x,int y){
    vto[++vtot]=y;
    vnxt[vtot]=vhead[x];
    vhead[x]=vtot;
}
il int find(int u){
    return fa[u]==u?u:fa[u]=find(fa[u]);
}
il void Tarjan(int u){
    visit[u]=true;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(visit[v]) continue;
        Tarjan(v);
        fa[v]=u;
    }
    for(int i=vhead[u];i;i=vnxt[i]){
        int v=vto[i];
        if(visit[v]){
            lca[i]=find(v);
            if(i%2) lca[i+1]=lca[i];
            else lca[i-1]=lca[i];
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vadd(x,y);vadd(y,x);
    }
    Tarjan(s);
    for(int i=1;i<=m;i++) printf("%d",lca[i*2]);
}

线段树

#include<iostream>
#include<cstdio>
#define il inline
#define ll long long
using namespace std;

ll n,m;

ll a[1000005];
ll ans[1000005];
ll tag[1000005];
il ll leftson(ll x){
    return x<<1;
}
il ll rightson(ll x){
    return x<<1|1;
}
il void dd(ll p,ll l,ll r,ll k){
    ans[p]+=(r-l+1)*k;
    tag[p]+=k;
}
il void pushdown(ll l,ll r,ll p){
    ll mid=(l+r)>>1;
    dd(leftson(p),l,mid,tag[p]);
    dd(rightson(p),mid+1,r,tag[p]);
    tag[p]=0;
}
il void pushup(ll p){
    ans[p]=ans[leftson(p)]+ans[rightson(p)];
}
il void update(ll rl,ll rr,ll l,ll r,ll p,ll k){
    if(rl<=l&&r<=rr){
        ans[p]+=(r-l+1)*k;
        tag[p]+=k;
        return;
    }
    pushdown(l,r,p);
    ll mid=(l+r)>>1;
    if(rl<=mid) update(rl,rr,l,mid,leftson(p),k);
    if(rr>mid) update(rl,rr,mid+1,r,rightson(p),k);
    pushup(p);
}
il void build(ll p,ll l,ll r){
    tag[p]=0;
    if(l==r){ ans[p]=a[l];return; } // 子叶
    ll mid=(l+r)>>1;
    build(leftson(p),l,mid);
    build(rightson(p),mid+1,r);
    pushup(p);
}
il ll query(ll rl,ll rr,ll l,ll r,ll p){
    ll result=0;
    if(rl<=l&&r<=rr){
        return ans[p];
    }
    ll mid=(l+r)>>1;
    pushdown(l,r,p);
    if(rl<=mid) result+=query(rl,rr,l,mid,leftson(p));
    if(rr>mid) result+=query(rl,rr,mid+1,r,rightson(p));
    return result;
}
int main(){
    scanf("%lld%lld",&n,&m);
    ll action,b,c,d;
    for(ll i=1;i<=n;++i) scanf("%lld",a+i);
    build(1,1,n);
    for(ll i=1;i<=m;++i){
        scanf("%lld",&action);
        if(action==1){
            scanf("%lld%lld%lld",&b,&c,&d);
            update(b,c,1,n,1,d);
        }else{
            scanf("%lld%lld",&b,&c);
            printf("%lld\n",query(b,c,1,n,1));
        }
    }
}

拓扑排序

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
 
using namespace std;
 
int n,m;
 
int step=1;
 
void work(vector<vector<int>> &G, vector<int> &indrgee){
    queue<int> q;
    for(int i=1;i<=n;++i)
    if(indrgee[i]==0) q.push(i);
    while(!q.empty()){
        int cur=q.front().first,le=q.front().second;
        q.pop();
        for(int i=0;i<G[cur].size();++i){
            int v=G[cur][i];
	    indrgee[v]--;
	    if (indrgee[v]==0) q.push(v);
        }
        G[cur].clear();
    }
}
 
int main(){
    scanf("%d",&m);
    vector<vector<int>> G(n+1);
    vector<int> indrgee(n);
    int s,t;
    for(int i=1;i<=m;++i){
        scanf("%d",&s,&t);
        G[s].push_back(t);
    }
    for (auto x : G) {
        for (auto y : x) indrgee[y]++;
    }
    work(G, indrgee);
    return 0;
}

拓扑排序

介绍

有向无环图

如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。

拓扑排序


拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得对图G中的任意两个顶点u、v,如果存在边u->v,那么在序列中u一定在v前面,这个序列又被称为拓扑序列。
如下图:结点0和1没有前驱节点,可以任意访问,但是结点2必须在结点0和1访问完之后才能访问,同理结点3和4必须在结点2访问完以后才能访问,但是结点3和4 之间没有依赖关系,结点5必须在结点3和结点6访问之后才能访问,等等…..因此,对于下图的一个拓扑序列可以是:0,1,2,3,4,6,5,7 也可以是:0,1,2,4,6,3,5,7

拓扑排序步骤如下:

  1. 定义一个队列Q,并把所有入度为0的结点加入队列
  2. 取队首结点,访问输出,然后删除所有从它出发的边,并令这些边到达的顶点的入度减1,如果某个顶点的入度减为0,则将其加入队列
  3. 重复进行 2 操作,直到队列为空。如果队列为空时入过队的结点数恰好为N,说明拓扑排序成功,图G为有向无环图;否则,拓扑排序失败,图G有环

例题

【洛谷】P1083 车站分级

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>

#define MAXN 1005

using namespace std;

// bool vis[MAXN];
int station[MAXN];
bool stop[MAXN];
bool pd[MAXN][MAXN];

int n,m;

int step=1;

void work(vector<vector<int>> &G, vector<int> &indrgee){
    queue<pair<int,int>> q;
    for(int i=1;i<=n;++i)
    if(indrgee[i]==0) q.push(make_pair(i,1));
    while(!q.empty()){
        int cur=q.front().first,le=q.front().second;
        q.pop();
        for(int i=0;i<G[cur].size();++i){
            int v=G[cur][i];
			indrgee[v]--;
			if (indrgee[v]==0){ 
                q.push(make_pair(v,le+1));
                step=max(step,le+1);
            }
        }
        G[cur].clear();
    }
}

int main(){
    scanf("%d%d",&n,&m);
    vector<vector<int>> G(n+1);
    vector<int> indrgee(n);
    int s;
    for(int i=1;i<=m;++i){
        scanf("%d",&s);
        memset(stop,0,sizeof(stop));
        for(int j=1;j<=s;++j){
            scanf("%d",&station[j]);
            stop[station[j]]=1;
        }
        for(int j=station[1];j<=station[s];++j){
            if(stop[j]) continue;
            for(int k=1;k<=s;++k){
                 if(!pd[j][station[k]]){
                     indrgee[station[k]]++;
                     G[j].push_back(station[k]);
                     pd[j][station[k]]=1;
                 }
            }
        }
    }
    // for (auto x:G) {
	// 	for (auto y:x){
    //         if(vis[y]==1) continue;
    //         indrgee[y]++;
    //         vis[y]=1;
    //     }
	// }
    work(G, indrgee);
    printf("%d\n",step);
    return 0;
}

双端队列BFS

问题模型1-1: 如果在一张图上(有向图和无向图),边权只可能是1或0,现在我们想从某个节点(假设为s)到另一个节点(假设为t),>怎样才能使得路径上的权值和最大?

这是最短路径问题中的特例,因为其边权只可能是0或1;同时这也是许多问题的抽象形式,很多问题可以抽象为上述模型1-1。我们的目标就是找到一个尽可能高效的算法解决上述问题模型。

最短路径算法

这是很容易想到的图论算法,解决此题的效率为O(NM)或O(M log N),取决于不同的算法。

双端队列BFS

算法描述:

由于这是一张边权要么为0、要么为1的图。在这样的图上,我们可以通过双端队列广搜来计算。算法的整体框架与一般的广搜类似,只是在每个节点沿分支拓展时稍作改变。如果这条分支边权为0,则从队首入队,否则从队尾入队。这样我们能保证,任意时刻广搜队列中节点对应的距离值都有“两端性”和“单调性”,每个节点第一次被访问时,就能得到从左上角到该节点的最短距离。

效率分析:

我们可以知道该算法中每个节点仅被访问一次,因为这是BFS的特性,所以该算法的效率为O(N)。

正确性证明:

由于我们最终目标是求路径权值和,而权值为0的边无论走多少条权值和依旧是+0,因此我们可以优先走权值为0的边,更新与这些边相连的点x的d[x](d[i] 为从s到i最小权值和),此时d[x]一定是最小的,因为它是由尽可能多的权值为0的边更新而来。所以在队列中取出的节点同时满足“连通性”和“权值最小”,因此每个节点仅需被更新一次。

解题思路:

首先将其转化为一张边权仅由0、1构成的无向图,由于最多可能有500* 500 = 250000个点,1000,000条边,所以用此种方法时需要注意数据范围是否合适。然后就采用双端队列BFS求解,效率为O(N),在此题中是O(R* C)。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 400000;
const int M = 300000*4;
int head[MAXN],ver[M],Next[M],edge[M],d[MAXN];
bool vis[MAXN];
int tot,r,c,n,m;
void addEdge(int x,int y,int z){
    ver[++tot] = y,edge[tot] = z;
    Next[tot] = head[x],head[x] = tot;
}
void solve(){
    memset(d,0x3f,sizeof d);
    memset(vis,false,sizeof vis);
    d[1] = 0;
    deque<int> q;
    q.push_back(1);
    while(q.size()){
        int x = q.front();q.pop_front();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i;i = Next[i]){
            int y = ver[i],z = edge[i];
            d[y] = min(d[x] + z,d[y]);
            if(z) q.push_back(y);
            else q.push_front(y);
            //printf("%d %d\n",y,d[y]);
        }
    }
}
void init(){
    memset(head,0,sizeof head);
    memset(Next,0,sizeof Next);
    memset(ver,0,sizeof ver);
    tot = 0;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d",&n,&m);
        r = m+1,c = n+1;
        char str[MAXN];
        for(int i = 0;i < n;i++){
            scanf("%s",str);
            for(int j = 1;j <= m;j++){
                if(str[j-1] == '\\'){
                    addEdge(i*r+j,(i+1)*r+j+1,0),addEdge((i+1)*r+j+1,i*r+j,0);
                    addEdge((i+1)*r+j,i*r+j+1,1),addEdge(i*r+j+1,(i+1)*r+j,1);
                }else{
                    addEdge(i*r+j,(i+1)*r+j+1,1),addEdge((i+1)*r+j+1,i*r+j,1);
                    addEdge((i+1)*r+j,i*r+j+1,0),addEdge(i*r+j+1,(i+1)*r+j,0);
                }
            }
        }
        if((n+m)%2) puts("NO SOLUTION");
        else{
            solve();
            printf("%d\n",d[r*c]);
        }
    }
    return 0;
}

音乐安利 4月16日

望断门前隔岸的杨柳 寂寞仍不休

我无言让眼泪长流

我独酌山外小阁楼 听一夜相思愁

醉后让人烦忧 心事难收

山外小阁楼 我乘一叶小舟

放思念随风漂流

这是我最早开始喜欢的古风歌之一呢,偏向疗伤治愈系的风格。

生活中总是有那么多的不如意之事,但此亦是生活中不可或缺的一部分,就像苏轼的《水调歌头》中写的一样:“人有悲欢离合,月有阴晴圆缺,此事古难全”。但与其为之而悲伤,还不如鼓起勇气来,“世界以痛吻我,我仍报之以歌”。

锦鲤抄(OI版)(转载)

转载自 https://www.cnblogs.com/nirundong/p/11618568.html

01背包装下了忧伤 笑颜洋溢脸庞
深夜电脑,富丽堂皇,题目 W A ,不免彷徨.
D P 背包,迷迷茫茫,R P R P ,全部用光.
屏幕微亮,代码千行,灰名蓝名,淡淡忧伤……
屏幕在深夜微微发亮
思想在那虚树路径上彷徨
平面的向量交错生长
织成 忧伤的网
剪枝剪去我们的疯狂
SPFA 告诉我前途在何方
01 背包装下了忧伤
笑颜 洋溢脸庞
键盘微凉 鼠标微凉
指尖流淌 代码千行
凸包周长 直径多长
一进考场 全都忘光
你在 OJ 上提交了千百遍
却依然不能卡进那时限
双手敲尽代码也敲尽岁月
只有我一人
写的题解
凋零在 OJ 里面
Tarjan 陪伴强连通分量
生成树完成后思路才闪光
欧拉跑过的七桥古塘
让你 心驰神往
队列进出图上的方向
线段树区间修改求出总量
可持久化留下的迹象
我们 伏身欣赏
数论算法 图论算法
高斯费马 树上开花
线性规划 动态规划
时间爆炸 如何优化
我在 OI 中辗转了千百天
却不让我看 AK 最后一眼
我用空间换回超限的时间
随重新编译
测完样例
才发现漏洞满篇
原来 CE 是因选错语言
其实爆零 …

童话镇(OI版)(转载)

转载自 https://www.cnblogs.com/nirundong/p/11618568.html

听说津津为课程烦恼 金明一家住进了新房
听说丁丁玩数字游戏 火柴棒能搭出新天地
听说校门外正在砍树 大家一起做靶形数独
听说旅行者在赚差价 潜伏者正在破译着密码
只有无尽的代码知道 津津摆脱了学习的烦恼
金明开心地走进商店 挑选着书桌和电脑
总有一种算法能够让你成功拿到分
无论是贪心还是动规 或者将答案二分
思如泉涌掀起波涛 又汇成一个新的算法
让所有TLE 所有MLE 激励着我们前行写代码
听说同学们在玩推理 小Z的袜子总配不齐
听说两人在挑选客栈 火星上有条能量项链
听说陶陶在采摘苹果 一只青蛙要从河边过
听说推销员走入胡同 杰瑞爬进了奶酪的小洞
只有无尽的代码知道 同学们男女配对练起了舞蹈
小Z把他的袜子找到 AK了无数机房
屏幕微微发亮 思想在虚树路径彷徨
平面的向量交错生长 织成忧伤的网
剪枝剪去我们的疯狂 SPFA告诉我前途在何方