2017icpc沈阳 G Infinite Fraction Path BFS+剪枝

题意：给一个长度为n的字符串数组，你可以选定起点跳n次，从i点只能跳到(i*i+1)%n的位置，最后求一个最大字典序。

思路：要求最大的，即每一步都是最大，所以将最大的数都入队进行bfs跳下一步。

剪枝：1.如果该点跳到下一步比其他点跳到下一步要小就剔除

           2.如果存在某两个点经过相同步数到达同一个点，那么他们之后的状态也是一样的这样也剔除。

           ok，it is all。

首先我们用一个结构体包装步数step与所在的位置pos   node{step,pos}

用nex数组表示从该pos点调到下一步的位置的数的值

然后我们在优先队列自定义一个排序函数（最主要的剪枝其实是排序方式）

如果step与下一步的值nex[pos]都相等，我们按照pos从小到大排序

如果step相等,nex[pos]不相等 按照nex[pos]从大到小

如果step不相等，按照step从小到大

坑！！！  注意i*i爆int ，恶心心

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<time.h>
#include<unordered_map>

#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
typedef long long ll;
const ll inFF = 9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=2e5+5;
int d[maxn],ans[maxn],nex[maxn];
char s[maxn];
struct node
{
    int pos,step;
    bool friend operator<(node s,node e)
    {
        if(s.step==e.step&&nex[s.pos]==nex[e.pos]) return s.pos<e.pos;
        if(s.step==e.step) return nex[s.pos]<nex[e.pos];
        return s.step>e.step;
    }
};
int main()
{
    int t;
//    freopen("E://1.in","r",stdin);
//    freopen("E://1.out","w",stdout);
    cin>>t;
    for(int p=1;p<=t;p++)
    {
        int n;
        ll h;
        cin>>n;
        scanf("%s",s);
        int maxs=0;
        for(int i=0;i<n;i++) d[i]=s[i]-'0',maxs=max(d[i],maxs),ans[i]=-1;
        for(int i=0;i<n;i++) h=((ll)i*i+1)%n,nex[i]=d[h];
        ans[n]=-1;
        priority_queue<node> q;
        for(int i=0;i<n;i++) if(d[i]==maxs) q.push(node{i,1});
        ans[1]=maxs;
        int pre=-1;
        while(!q.empty())
        {
            node now=q.top();
            q.pop();
            ll c=now.pos;
            c=(c*c+1)%n;
            int step=now.step+1,pos=c;
            if(ans[step]==-1) q.push(node{pos,step}),ans[step]=d[pos],pre=pos;
            else if(d[pos]==ans[step])
            {
                if(pos!=pre)
                {
                    q.push(node{pos,step});
                    pre=pos;
                }
            }
            if(ans[n]!=-1) break;
        }
        printf("Case #%d: ",p);
        for(int i=1;i<=n;i++) printf("%d",ans[i]);
        printf("\n");
    }
}