Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么这样还超时啊 是不是因为stl的原因啊?

Posted by kakassi at 2009-09-10 22:15:45 on Problem 1026
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void cacCycle(vector<vector<int> >& key,vector <int> &cip){
	int i;
	for(i=1;i<key.size();i++){
		int now;
		int next;
//		key[i].push_back(cip[i]);
		now = i;
		while(1){
			key[i].push_back(now);
			next=cip[now];
			if(next==i)
				break;
			else 
				now = next;
//			cout <<" iiiiiii: " <<next << " ";
		}
//		cout << endl;
	}
	return;
}

void solve(vector<char> &str,vector<vector<int> >& key,int k){
	int i;
	vector<char> ans(str.size());
	for(i=1;i<str.size();i++){
		int km = k%key[i].size();
//		cout << key[i][km] << endl;
//		cout << str[i] << endl;
		ans[key[i][km]] = str[i];
	}
	for(i=1;i<ans.size();i++){
	//	cout << ans[i];
		printf("%c",ans[i]);
	}
//	cout << endl;
	printf("\n");
}

int main(int argc, char* argv[])
{
	int i;
	int n;
	int k;
//	while(cin >> n){
	while(1){
		scanf("%d",&n);
		if(n==0)
			return 0;
		vector <int> cip(n+1);
		for(i=1;i<=n;i++){
		//	cin >> cip[i];
			scanf("%d",&cip[i]);
		}//获得密码表 从1到N
		vector<vector<int> > key(n+1);
		cacCycle(key,cip);
//		while(cin >> k){
		while(1){
			scanf("%d",&k);
			if(k==0)
				break;
			//cin.get();
			//scanf("%c");
			getchar();
			//cout << c << endl;
			vector <char> str(n+1,' ');
			for(i=1;i<=n;i++){
				char c;
				//c = cin.get();
				scanf("%c",&c);
				if(c == '\n')
					break;
				str[i] = c;
			}
			solve(str,key,k);
		}
		//cout << endl;
		printf("\n");
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator