Logo __vector__ 的博客

博客

25题题解

...
__vector__
2025-12-01 12:55:42

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-11-11 21:31:34

P3958 [NOIP2017 提高组] 奶酪

难度：$\color{orange}\text{普及/提高-}$

$\color{green}\text{AC算法：dfs}$

题目分析：

数据范围较小，可以dfs所有通向下面的点，看看是否可以到达上面即可

解题流程：

一、预处理所有通向上面的洞，使用一个map容器来记录某个洞是不是通向上面的洞。
二、从所有通向下面的点出发dfs，如果最终到达通向上面的洞，则输出Yes，否则输出No，此部分代码：

bool flag = 0;
for (register auto i = 1;i<=n; i++)
{
\/\/    memset(vis, 0, sizeof(vis));
     if(ball[i].z<=r){
              if(dfs(i)==1){
                printf("Yes\n");
                flag = 1;
                break;
              }
		}
      if (!flag)
      {
         printf("No\n");
      }
}

总体AC代码就是：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1005;
#define int long long
struct Ball
{
    int x, y, z;

} ball[maxn];
inline double dis(Ball a,Ball b)
{
    register int _1 = a.x - b.x;
    register int _2 = a.y - b.y;
    register int _3 = a.z - b.z;
    return sqrt((_1 * _1) + (_2 * _2) + (_3 * _3));
}
inline int read()
{
    int x=0,f=1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int t,n,h,r;
bool vis[maxn];
map<int, bool> im;
bool dfs(int x)
{
    if(im[x]!=0)
    {
        return 1;
    }
    vis[x] = 1;
    for (register int i = 1; i <= n;i++)
    {
        if(i==x)continue;
        if(dis(ball[i],ball[x])>(r<<1))
            continue;
        register int to = i;
        if(!vis[to])
        {
            if(dfs(to)==1)
            {
                return 1;
            }
        }
    }
    return 0;
}
signed main()
{
    t = read();
    map<int, bool> imt;\/\/是不是与上面相交的洞
    while(t--)
    {
        memset(vis, 0, sizeof(vis));
        imt.clear();
        n = read(), h = read(), r = read();
        for (register int i = 1; i <= n;i++)
        {
            ball[i].x = read();
            ball[i].y = read();
            ball[i].z = read();
            if(h-ball[i].z<=r)
            {
                imt[i] = 1;
            }
        }
        im = imt;
        bool flag = 0;
        for (register auto i = 1;i<=n; i++)
        {
        \/\/    memset(vis, 0, sizeof(vis));
            if(ball[i].z<=r){
            if(dfs(i)==1){
                printf("Yes\n");
                flag = 1;
                break;
            }}
        }
        if (!flag)
        {
            printf("No\n");
        }
    }
    return 0;
}

[NOIP2013 提高组] 货车运输 | P1967

难度：$\color{blue}\text{提高+/省选-}$

$\color{green}\text{AC算法：lca,kruscal}$

题目分析：

可以发现，对于图中一个点到另一个点的最大限重，就是两个点之间最小边权最大的路径，其他的路径都不会走。此处例如样例中的一个例子:
1$\rightarrow$3有两条路径，一个是 1$\rightarrow$2$\rightarrow$3；另一个是1$\rightarrow$3。第一条路径限重3,第二条路径限重1。显然，不会走第二条路径。
如何解决这个问题我先想到了网络流的最大流，但是显然在这个数据范围下AC不了。可以构建一个最大生成树来存储要走的路径，使用kruscal算法即可。 接下来使用lca来查询路径即可(可以理解为将根节点作为中点）。

解体流程：

一、使用前向星存图
二、构建最大生成树
三、处理每个节点的深度，父子信息
四、更新每个节点的祖先、关系
五、lca查询

注意：

预处理 $lca$ 时一定要这样写，不然会出现处理当前节点时祖先未处理的情况：

for(int i=0; i<20; i++)
{
    for(int j=1; j<=n; j++)
    {
        fa[j][i+1]=fa[fa[j][i]][i]; 
        w[j][i+1]=min(w[j][i], w[fa[j][i]][i]);
    }
}

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long
const int inf=0xffffffffff; 
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const signed maxn=1e4+5;
const signed maxm=5e4+5;
int tot,tot2,n,m,q,f[maxn]\/*骞舵煡闆?*\/,fa[maxn][21*2]\/*lca*\/,dep[maxn];
int w[maxn][21*2]; 
bool vis[maxn];
int head[maxn];
struct EDGE
{
    int u,to,val;
}edge[maxm];
inline void add_edge(int u,int to,int val)
{
    edge[++tot].to=to;
    edge[tot].val=val;
    edge[tot].u=u;
}
struct EDGE2
{
    int to,nxt,val;
}edge2[maxm];
inline void add_edge2(int u,int to,int val)
{
    edge2[++tot2].to=to;
    edge2[tot2].val=val;
    edge2[tot2].nxt=head[u];
    head[u]=tot2;
}
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
bool cmp(EDGE a,EDGE b)
{
    return a.val>b.val;
}
inline void kruscal()
{
    for(register int i=1;i<=m;i++)
    {
        if(find(edge[i].u)!=find(edge[i].to))
        {
            f[find(edge[i].u)]=find(edge[i].to);
           \/\/ cout<<"u: "<<edge[i].u<<"  to: "<<edge[i].to<<endl;
            add_edge2(edge[i].u,edge[i].to,edge[i].val);
            add_edge2(edge[i].to,edge[i].u,edge[i].val);
        }
    }
}
void dfs(int u,int father)
{
   \/\/ cout<<"node: "<<u<<endl;
    dep[u]=dep[father]+1;
    vis[u]=1;
    for(register int i=head[u];i;i=edge2[i].nxt)
    {
    	int to=edge2[i].to;
    	if(vis[to])continue;
    	fa[to][0]=u;
    	w[to][0]=edge2[i].val;
    	dfs(to,u); 
	}
}
inline int lca(int x,int y)
{
	if(find(x)!=find(y))return -1;
	int ans=inf;
	if(dep[x]<dep[y])swap(x,y);
	for(register int i=20;i>=0;i--)
	{
		if(dep[fa[x][i]]>=dep[y])
		{
			ans=min(ans,w[x][i]);
		    x=fa[x][i];
		}
	}
	if(x==y)return ans;
	for(register int i=20;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
        {
            ans=min(ans,w[x][i]);
		    ans=min(ans,w[y][i]);
		    x=fa[x][i];
		    y=fa[y][i];
        }
	}
	ans=min(ans,min(w[x][0],w[y][0]));
	return ans;
}
signed main()
{
    int x,y,z;
    n=read();
    m=read();
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        z=read();
        add_edge(x,y,z);
    }
    sort(edge+1,edge+m+1,cmp);
    for(register int i=1;i<=n;i++)f[i]=i;
    kruscal();
    for(register int i=1;i<=n;i++)
    {
    	if(vis[i])continue;
    	dfs(i,0);
    	w[i][0]=inf;
    	fa[i][0]=i;
	}
	for(int i=0; i<20; i++)
    {
        for(int j=1; j<=n; j++)
        {
            fa[j][i+1]=fa[fa[j][i]][i]; 
            w[j][i+1]=min(w[j][i], w[fa[j][i]][i]);
        }
    }
        
	q=read();
	for(register int i=1;i<=q;i++)
	{
		x=read();
		y=read();
		printf("%lld\n",lca(x,y));
	}
    return 0;
}

P3959 [NOIP2017 提高组] 宝藏

AC算法：dfs+状压

分析：

可以知道，每个点必然要算一次深度以及路径。所以可以通过已经更新的点u来推导未更新的点to，所以需要dfs。具体更新过程如下：
$Dep[to]=dep[u]+1$
F[to][当前点集][当前深度+1]=中间答案$cur+dis(u,to) * dep[u]$ 那么点集如何表示呢？可以使用状压来解决，定义一个整数$dj$，初始默认为$1<<(i-1)$，这样它的第$i-1$位就是1，表示$i$存在于这个点集里。如果想要向其加入一个数$s$，就表示为： $dj |=(s-1)$，判断是否在点集里可以用if(($1<<(s-1)&dj$))来判断。
那么如何设状态呢？
可以用三维数组f，分别为当前点，当前点集，当前深度。
最后，就是边界条件的处理：
可以发现，每个点都更新完之后，肯定是dj的二进制每一位都是1。这个恰好等于(1<<n)-1，所以如果dj==(1<<n)-1，那么更新答案退出。
调了一个下午的AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int maxn=15;
int imap[maxn][maxn];
int ndep[maxn];\/\/记录从起点到路径开始
int ans=inf;
int f[maxn][8193][maxn];\/\/当前点，点集，深度
inline int min(int a,int b)
{
    return a<b?a:b;
}
void dfs(int dj\/*点集*\/,int dep\/*深度*\/,int cur\/*当前解*\/)
{
    if(cur>=ans)return;
    if(dj==((1<<n)-1))\/\/边界条件
    {
        ans = cur;
        return;
    }
    for(register int u=1;u<=n;u++)
    {
        if(!(1<<(u-1)&dj))continue;\/\/不在点集里，不能通过它更新其他点
        for(register int to=1;to<=n;to++)
        {
            if(!(1<<(to-1)&dj)&&imap[u][to]<inf)
            {
                \/\/如果需要更新，且可以通过u更新
                if(f[to][dj|(1<<(to-1))][dep+1]<=cur+imap[u][to]*ndep[u])
                {\/\/如果下一步不是最优解，剪枝
                    continue;
                }
                f[to][dj|(1<<(to-1))][dep+1]=cur+imap[u][to]*ndep[u];
                ndep[to]=ndep[u]+1;
                dfs(1<<to-1|dj,dep+1,f[to][1<<(to-1)|dj][dep+1]);
            }
        }
    }
}
int main()
{

    memset(imap, 0x3f3f3f3f, sizeof(imap));
    n = read();
    m=read();
    int x,y,v;
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        v=read();
        imap[x][y]=imap[y][x]=min(imap[x][y],v);
    }
    for(register int i=1;i<=n;i++)
    {
        memset(ndep,0,sizeof(ndep));
        memset(f,0x3f3f3f3f,sizeof(f));
        ndep[i] = 1;
        dfs(1<<(i-1),0,0);
    }
    printf("%d",ans);
    return 0;
}

如果是纯dfs呢，可以加两个剪枝就过了。第一个当然就 if(cur>ans)return;。这样就能获得70分的好成绩。第二个可以仿照状压dp的思路，定义一个三维数组f，代表当前点，当前深度，当前点数量（其实就相当于状压做法的点集），加上这句话：

if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
                        continue;

然后将更新点的部分改成这个：

  f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
  sd[to]=sd[u]+1;
  cur+=sd[u]*imap[u][to];
  sd[to]=sd[u]+1;
  tot++;
  dfs(to,step+1,cur);
  tot--;
  cur-=sd[u]*imap[u][to];
  sd[to]=0;

但是真的这样就行了吗？如果你交了这份代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int maxn=13;
int imap[maxn][maxn];
int sd[maxn];\/\/记录从起点到路径开始
int ans=inf;
int tot = 1;
int f[maxn] \/*第几个点*\/[maxn]\/*深度*\/[maxn]\/*tot*\/;
inline void memset()
{
    for(int i=0;i<13;i++)
        for(int j=0;j<13;j++)imap[i][j]=inf;
}
inline void memset2()
{
    for(int j=0;j<13;j++)sd[j]=0;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
void dfs(int x,int step,int cur)
{
    if(cur>ans)return;
 \/\/   cout<<"step: "<<step<<endl;
    if(step==n)
    {
        ans=min(ans,cur);
   \/\/     cout<<"cur: "<<cur<<endl;
        return;
    }
    for(register int to=1;to<=n;to++)
    {
        if(!sd[to])\/\/ mod zgc
        {
            for(register int u=1;u<=n;u++)
            {
                if(imap[u][to]!=inf&&sd[u]!=0)
                {
                    if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
                        continue;
                    if(cur+sd[u]*imap[u][to]>ans)continue;
                    f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
                    sd[to]=sd[u]+1;
                    cur+=sd[u]*imap[u][to];
                    sd[to]=sd[u]+1;
                    tot++;
                    dfs(to,step+1,cur);
                    tot--;
                    cur-=sd[u]*imap[u][to];
                    sd[to]=0;
                }
            }
        }
    }
}
int main()
{
    memset();
    n=read();
    m=read();
    int x,y,v;
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        v=read();
        imap[x][y]=imap[y][x]=min(imap[x][y],v);
    }
    for(register int i=1;i<=n;i++)
    {
        tot = 1;
        memset(f, 0x3f, sizeof(f));
        sd[i]=1;
        dfs(i,1,0);
        sd[i]=0;
    }
    printf("%d",ans);
    return 0;
}

将会收获：95分。
计算一下可以发现原来的不加第二个剪枝的算法可以在n=10的时候挺住。所以可以在n>10时使用剪枝，n<=10时使用原来的搜索。提交这份代码就可以AC。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int maxn=13;
bool vis[maxn][maxn];
int imap[maxn][maxn];
int sd[maxn];\/\/记录从起点到路径开始
int ans=inf;
int tot = 1;
int f[maxn] \/*第几个点*\/[maxn]\/*深度*\/[maxn]\/*tot*\/;
inline void memset()
{
    for(int i=0;i<13;i++)
        for(int j=0;j<13;j++)imap[i][j]=inf;
}
inline void memset2()
{
    for(int j=0;j<13;j++)sd[j]=0;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
void dfs(int x,int step,int cur)
{
    if(cur>ans)return;
 \/\/   cout<<"step: "<<step<<endl;
    if(step==n)
    {
        ans=min(ans,cur);
   \/\/     cout<<"cur: "<<cur<<endl;
        return;
    }
    for(register int to=1;to<=n;to++)
    {
        if(!sd[to])\/\/ mod zgc
        {
            for(register int u=1;u<=n;u++)
            {
                if(imap[u][to]!=inf&&sd[u]!=0)
                {
                    if(f[to][sd[u]+1][tot+1]<cur+sd[u]*imap[u][to])
                        continue;
                    if(cur+sd[u]*imap[u][to]>ans)continue;
                    f[to][sd[u] + 1][tot+1] = cur + sd[u] * imap[u][to];
                    sd[to]=sd[u]+1;
                    cur+=sd[u]*imap[u][to];
                    sd[to]=sd[u]+1;
                    tot++;
                    dfs(to,step+1,cur);
                    tot--;
                    cur-=sd[u]*imap[u][to];
                    sd[to]=0;
                }
            }
        }
    }
}
void dfs_henman(int x,int step,int cur)
{
    if(cur>ans)return;
 
    if(step==n)
    {
        ans=min(ans,cur);
        return;
    }
    for(register int to=1;to<=n;to++)
    {
        if(!sd[to])\/\/ mod zgc
        {
            for(register int u=1;u<=n;u++)
            {
                if(imap[u][to]!=inf&&sd[u]!=0)
                {
                    if(cur+sd[u]*imap[u][to]>ans)continue;
                    sd[to]=sd[u]+1;
                    cur+=sd[u]*imap[u][to];
                    sd[to]=sd[u]+1;
                    dfs_henman(to,step+1,cur);
                    cur-=sd[u]*imap[u][to];
                    sd[to]=0;
                }
            }
        }
    }
}
int main()
{
    memset();
    n=read();
    m=read();
    int x,y,v;
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        v=read();
        imap[x][y]=imap[y][x]=min(imap[x][y],v);
    }
    if(n>10)
    {
        for(register int i=1;i<=n;i++)
        {
            tot = 1;
            memset(f, 0x3f, sizeof(f));
            sd[i]=1;
            dfs(i,1,0);
            sd[i]=0;
        }
    }
    if(n<=10)
    {
        for(register int i=1;i<=n;i++)
        {
            sd[i]=1;
            dfs_henman(i,1,0);
            sd[i]=0;
        }
    }
    printf("%d",ans);
    return 0;
}

此时对比一下：dfs解法提交记录和状态压缩解法提交记录，dfs用了102ms，状压用了405ms，dfs比状压快了5倍！！！！！！

CF1137C Museums Tour

$\color{green}\text{AC算法：}$tarjan缩点+dfn最长路

难度：$\color{purple}\text{省选/NOI-}$

题目内容：

有 $n$ 个城市，$m$ 条边，每周有 $d$ 天，每个城市都会在每周特定的时间开放博物馆，旅行者可以无限走，也可以随时停下来。求参观的不同博物馆数量尽量多。

题目分析

难点就在于每周都有一个轮回，每个城市都在特定时间开放，可以看作题目提供的图 $G1$ 中的点有时候有点权有时没点权。所以可以将每个点拆成 $d$ 个点，每个点 $u$ 连接明天的点 $v$，如果当前 $u$ 已经是第 $d$ 天，那么连接第 $1$ 天的 $v$。这样每条边都有了明确的点权。然后就是如何处理题目中的环，可以用 tarjan 算法将每个环缩成一个强连通分量，每个强连通分量（新的点）的点权就是其中所有原来点权的和。最后将所有强连通分量建边就构成了一张新的图 $G2$，在 $G2$中用 dfs 求最长路即可。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

Server Time: 2025-12-19 19:15:18 | OpenSource Project