# Infinite Fraction Path

**Infinite Fraction Path** Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 6221 Accepted Submission(s): 1209

# Problem Description

The ant Welly now dedicates himself to urban infrastructure. He came to the kingdom of numbers and solicited an audience with the king. He recounted how he had built a happy path in the kingdom of happiness. The king affirmed Welly’s talent and hoped that this talent can help him find the best infinite fraction path before the anniversary. The kingdom has N cities numbered from 0 to N - 1 and you are given an array D[0 … N - 1] of decimal digits (0 ≤ D[i] ≤ 9, D[i] is an integer). The destination of the only one-way road start from the i-th city is the city labelled (i2 + 1)%N. A path beginning from the i-th city would pass through the cities u1,u2,u3, and so on consecutively. The path constructs a real number A[i], called the relevant fraction such that the integer part of it is equal to zero and its fractional part is an infinite decimal fraction with digits D[i], D[u1], D[u2], and so on. The best infinite fraction path is the one with the largest relevant fraction

Input The input contains multiple test cases and the first line provides an integer up to 100 indicating to the total numberof test cases. For each test case, the first line contains the integer N (1 ≤ N ≤ 150000). The second line contains an array ofdigits D, given without spaces. The summation of N is smaller than 2000000.

Output For each test case, you should output the label of the case first. Then you are to output exactly N characters which are the first N digits of the fractional part of the largest relevant fraction.

# Sample Input

```4
3
149
5
12345
7
3214567
9
261025520```

Sample Output

```Case #1: 999
Case #2: 53123
Case #3: 7166666
Case #4: 615015015```

# 代码

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
char s[200000];//初始化字符串数组
int vis[200000];//是否被标记过
char mm[200000];//结果答案字符数组
int f[200000];//记录位置
int ma=0;//当前记录位置的数组里面中有几个元素
ll n,t;
struct Node{
ll id;//这个节点对应的字符串的位置
int st;//层数
Node(ll x=0,int y=0)// 这个是为了在队列放元素的时候直接有  Node (x,y)；这样用
{
id=x;
st=y;
}
friend bool operator <(Node a,Node b)//定义 优先队列里面的排列顺序
{
if(a.st==b.st) return s[a.id]<s[b.id];
return a.st>b.st;
}
};

priority_queue<Node>que;

void bfs()
{
int flag=-1;//表示当前是第几层
while(!que.empty())
{
Node now=que.top();
que.pop();
if(now.st!=flag)//如果层数变化了，那么就要初始化标记数组了
{
flag=now.st;//更新当前的位置
while(ma)
{
vis[f[--ma]]=0;//初始化为零
}
}
if(now.st<n&&mm[now.st]<=s[now.id]&&!vis[now.id ])//当前位置没被标记果
{                                                //且当前的位置和结果数组的当前层数相同时放入队列中
vis[now.id]=1;            // 防止重复处理，将该位置标记
f[ma++]=now.id;        //当前这一层的数别标记的个数加一，并且记录该位置，为了方便下次初始化
mm[now.st]=s[now.id];//该位置的字符满足了题目要求防如结果里面这样其实也是每次都会更新结果数组的值只是等新的值都是大于等于以前的值得
que.push(Node((now.id*now.id+1)%n,now.st+1));//将该位置放入队列中
}
}
}

int main()
{

scanf("%d",&t);
int K=1;
while(t--)
{
scanf("%d%s",&n,s);
char maxn=0;
for(int i=0;i<n;i++)
{
if(s[i]>maxn) maxn=s[i];//找出最大的元素
}
for(int i=0;i<n;i++) que.push(Node(i,0));//把最大的元素全部作为第一层放入优先队列里
bfs();//开始搜索
printf("Case #%d: ",K++);
for(ll i=0;i<n;i++)
putchar(mm[i]);
puts("");
for(ll i=0;i<n;i++)//每次操作完以后都要把结果数组给初始化因为是多组输入，这样避免这次结果对下次的结果造成影响
mm[i]=0;
}
return 0;
}```

0 条评论

• ### C. NEKO's Maze Game

time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

• ### F2. Animal Observation (hard version)

time limit per test：3 seconds memory limit per test：512 megabytes inputstandard ...

• ### 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

• ### poj 3126 Prime Path

Description ? The ministers of the cabinet were quite upset by the message from ...

• ### CF---（452）A. Eevee

A. Eevee time limit per test 1 second memory limit per test 256 megabytes in...

• ### Codeforces Beta Round #1 A,B,C

A. Theatre Square time limit per test:1 second memory limit per test:256 megabyt...

• ### 多语种机器翻译: 缩小共享和特定语言编码解码器之间的差距（CS CL)

最先进的多语种机器翻译依赖于通用的编码解码器，这需要重新训练整个系统来添加新的语言。 在本文中，我们提出了一种基于特定语言编码解码器的替代方法，从而可以更容易地...

• ### leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

Given a string, find the length of the longest substring without repeating chara...

• ### Codeforces Beta Round #2 A,B,C

A. Winner time limit per test:1 second memory limit per test:64 megabytes input:...