prior happiness exactly multi clas multiple without arr 分析
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1262 Accepted Submission(s): 224
bfs + 剪枝
剪枝:
- #include <stdio.h>
- #include <math.h>
- #include <string.h>
- #include <stdlib.h>
- #include <iostream>
- #include <sstream>
- #include <algorithm>
- #include <string>
- #include <queue>
- #include <vector>
- using namespace std;
- const int maxn= 150000+10;
- const int maxm= 1e4+10;
- const int inf = 0x3f3f3f3f;
- typedef long long ll;
- ll ne[maxn]; //ne[i]为以i为起点的边的终点
- int v[maxn],ans[maxn],vis[maxn]; //权值、答案、i上一次在ans数组中出现的位置
- char s[maxn];
- int n,t;
- struct node
- {
- int v,pos,ans; //表示当前节点的权值,下标i,在答案数组中的位置下标
- node(){}
- node(int v,int pos,int ans):v(v),pos(pos),ans(ans){}
- };
- struct compare
- {
- bool operator()(const node &a,const node &b) const //ans最小值优先 权值最大值优先
- {
- if(a.ans!=b.ans) return a.ans>b.ans;
- else if(a.v!=b.v) return a.v<b.v;
- return a.pos>b.pos;
- }
- };
- priority_queue<node,vector<node>,compare> q;
- int main()
- {
- scanf("%d",&t);
- int kase=1;
- while(t--)
- {
- scanf("%d",&n);
- scanf("%s",s);
- memset(vis,-1,sizeof(vis)); //初始化
- memset(ans,-1,sizeof(ans));
- int ma=0;
- for(int i=0;i<n;i++) //权值转化为整数 求出最大值 i的终点(i^2+1)%n
- {
- v[i]=s[i]-‘0‘;
- ma=max(ma,v[i]);
- ne[i]=(((ll)i*(ll)i+1)%(ll)n);
- }
- // for(int i=0;i<n;i++)
- // {
- // printf("%d %d %d\n",i,v[i],next[i]);
- // }
- // printf("%d\n",ma);
- for(int i=0;i<n;i++)
- {
- if(v[i]==ma)
- q.push(node(ma,i,0)); //最大值先压入队列
- }
- while(!q.empty())
- {
- node t=q.top();q.pop();
- if(ans[t.ans]==-1) ans[t.ans]=t.v; //该位置初步确定一个值
- if(ans[t.ans]>t.v) continue; //该节点的权值比以前小 直接跳过
- if(vis[t.pos]<t.ans) vis[t.pos]=t.ans; //更新节点的 访问位置
- else continue;
- if(t.ans==n-1) continue;
- q.push(node(v[ne[t.pos]],ne[t.pos],t.ans+1)); //加入新节点
- }
- printf("Case #%d: ",kase++);
- for(int i=0;i<n;i++)
- printf("%d",ans[i]);
- printf("\n");
- }
- return 0;
- }
2017 ICPC/ACM 沈阳区域赛HDU6223
prior happiness exactly multi clas multiple without arr 分析
原文:http://www.cnblogs.com/stranger-/p/7841085.html
来源: http://www.bubuko.com/infodetail-2396341.html