Infinite Fraction Path UVALive - 8207

Infinite Fraction Path UVALive - 8207

题意：

给你n个数，每个数在0到9之间，每个数的下标一次是0~n-1，然后他所能走到的数为(i^2+1)%n,i为他本身的下标，然后让你求走n步，每一步的数相连，形成的最大的数是多少？

题解：

我想的是用一个队列维护，因为要求数最大，那第一位我们就取最大值，如果有多个一样的最大值，都取。然后一次取出队列中的最大值，然后枚举他们的下一位（即指向的数），然后他所指数的最大值，有多个的话都存到队列，一次进行，进行n轮结束

代码：

#include<bits/stdc++.h> #define mk make_pair using namespace std; typedef long long ll; //bool SUBMIT = 1; const int maxn = 150009; char s[maxn],ans[maxn]; int n; int main() {int t;scanf("%d",&t);queue<int>q[2];for(int i=1;i<=t;i++){scanf("%d%s",&n,s);int g=0,m=0;for(int i=0;i<n;i++){m=max(m,s[i]-'0');}for(int i=0;i<n;i++){if(s[i]-'0'==m)q[g&1].push(i);}ans[0]=m+'0';while(g<n){queue<int>t;m=0;while(!q[g&1].empty()){int k=q[g&1].front();q[g&1].pop();t.push(k);int next=(1ll+1ll*k*k)%n;m=max(m,s[next]-'0');} g++;while(!t.empty()){int k=t.front();t.pop();int next=(1ll+1ll*k*k)%n;if(m==s[next]-'0'){q[g&1].push(next);}}ans[g]=m+'0';}ans[n]='\0';printf("Case #%d: %s\n",i,ans);}return 0; }

总结

以上是生活随笔为你收集整理的Infinite Fraction Path UVALive - 8207的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。