题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6223

思路

用优先队列进行BFS,优先队列中记录当前点的层数、点的值、点的编号,按层数从小到大排序,若层数相同则按点值从大到小排序。

最开始把数组中所有权值等于最大值的点放入优先队列 (相当于有多个起点,即多源BFS), 然后开始逐层扩展,考虑两个剪枝:
- 同层只取所有权值等于最大值的点。(小于最大值的直接跳过,不再扩展)
- 同层若出现了多个相同编号的点,只留一个。(因为本题中每个点的后继是唯一的,那么多个相同编号的点只需要一个去扩展就行了)

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=150000+10;
typedef long long int;
int vis[N]; // 记录id上一次出现的层数
int T,n,mx,val[N],nxt[N],ans[N];
struct node
{
    int dep,val,id;
    bool operator < (const node &s) const
    {
        if(dep!=s.dep)return dep>s.dep; // 优先队列关系写相反的!!!
        return val<s.val;
    }
};
void bfs()
{
    priority_queue<node>q;
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<n;i++)
        if(val[i]==mx)q.push({0,val[i],i}); // 第0层,取整个数组中的多个最大值
    int last_dep=-1; // 记录已经扩展到的层号
    while(!q.empty())
    {
        node tmp=q.top();q.pop();
        int id=tmp.id;
        int dep=tmp.dep;
        int v=val[id];
        if(dep>last_dep) // 扩展到了新的一层,第一个就是当前层的最大值
        {
            mx=v; // 当前层的最大值
            ans[dep]=mx;
            if(dep==n-1)return;
            last_dep=dep;
        }
        if(v<mx||vis[id]==dep)continue; // 剪枝:小于当前层最大值 或 当前层已经出现过的id
        vis[id]=dep;
        q.push({dep+1,val[nxt[id]],nxt[id]}); // 当前点的下一个
    }
}
int main()
{
    ios::sync_with_stdio(false);
    string s;
    cin>>T;
    for(int cas=1;cas<=T;cas++)
    {
        cin>>n>>s;
        mx=-1;
        for(int i=0;i<n;i++)
        {
            val[i]=s[i]-'0';
            mx=max(mx,val[i]);
            nxt[i]=int(((ll)i*(ll)i+1)%(ll)n); // i*i爆int
        }
        bfs();
        printf("Case #%d: ",cas);
        for(int i=0;i<n;i++)
            printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}
/*
1
60
986978694864376938576938576935213415791421412900638643325831
ans:
986868816868816868816868816868816868816868816868816868816868
*/

关于本题的时间复杂度

剪枝前可以认为最开始的起点最多有n个,然后它们需要扩展到n层,那么复杂度就是O(n^2^);

剪枝后的时间复杂度比较玄学,首先肯定和这些点组成的有向图有关,但是$i$的后继点$(i*i+1)\%N$可能导致走图中的环很快就能走到相同编号的点,然后被第二个剪枝条件剪掉。

参考
点i可以到达点(ii+1)%n,取模会发生冲突像hash一样,而且由于本题的n很小,即hash表长小,并且如果权值=mx的点越多的话,冲突概率越大(剪枝效果越明显)*,比如x和y权值相同,但是x和y都走到z。于是我们可以增加一个剪枝:每一层要走的权值=mx的点用标记避免重复记录(即z只记录一次)

还有博主说是O(n*L),L为环的大小,不知道咋证明的...这个地方我只能说是玄学剪枝过了。