德州市建设工程质量监督站网站,湖北宜昌网,网站建设微商城,wordpress注册链接失效Infinite Fraction Path UVALive - 8207
题意#xff1a;
给你n个数#xff0c;每个数在0到9之间#xff0c;每个数的下标一次是0~n-1#xff0c;然后他所能走到的数为(i^21)%n,i为他本身的下标#xff0c;然后让你求走n步#xff0c;每一步的数相连#xff0c;形成的…Infinite Fraction Path UVALive - 8207
题意
给你n个数每个数在0到9之间每个数的下标一次是0~n-1然后他所能走到的数为(i^21)%n,i为他本身的下标然后让你求走n步每一步的数相连形成的最大的数是多少
题解
我想的是用一个队列维护因为要求数最大那第一位我们就取最大值如果有多个一样的最大值都取。然后一次取出队列中的最大值然后枚举他们的下一位即指向的数然后他所指数的最大值有多个的话都存到队列一次进行进行n轮结束
代码
#includebits/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);queueintq[2];for(int i1;it;i){scanf(%d%s,n,s);int g0,m0;for(int i0;in;i){mmax(m,s[i]-0);}for(int i0;in;i){if(s[i]-0m)q[g1].push(i);}ans[0]m0;while(gn){queueintt;m0;while(!q[g1].empty()){int kq[g1].front();q[g1].pop();t.push(k);int next(1ll1ll*k*k)%n;mmax(m,s[next]-0);} g;while(!t.empty()){int kt.front();t.pop();int next(1ll1ll*k*k)%n;if(ms[next]-0){q[g1].push(next);}}ans[g]m0;}ans[n]\0;printf(Case #%d: %s\n,i,ans);}return 0;
}
