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

Re:共享一下本人AC的代码

Posted by wskiwwwx at 2010-06-24 22:27:55 on Problem 1030
In Reply To:共享一下本人AC的代码 Posted by:walker01 at 2010-04-05 11:27:03
> 这道题易出错的细节很多, 一定要先将题意吃透,理清思路,合理规划采用的数据结构。这种模拟题适合用面向对象的思想。第一次因为忘记更新头结点而WA,第二次就AC了。与大家分享一下本人AC的代码(176k, 0ms),希望能对大家有所帮助。
> 
> Source Code 
> #include <iostream>
> using namespace std;
> 
> enum Status
> {
> 	UNCERTAIN = 0,
> 	INSINGLE,
> 	INBOTH
> };
> 
> enum JoinType
> {
> 	NONE = 0,
> 	FIRST,
> 	SECOND,
> 	BOTH
> };
> 
> struct TeamRecord
> {
> 	int rank1;
> 	int rank2;
> 	int sumRanks;
> 	JoinType joinType;
> };
> 
> struct LinkTeamRecord
> {
> 	int teamId;
> 	LinkTeamRecord *right;
> 	LinkTeamRecord *next;
> 	LinkTeamRecord(int _teamId): right(NULL),next(NULL)
> 	{
> 		teamId = _teamId;
> 	}
> 	~LinkTeamRecord()
> 	{
> 		if(right) delete right;
> 		if(next) delete next;
> 	}
> };
> 
> //globals///
> const int TEAMSCOUNT = 100;
> const char *DELIMITERS = " \n";
> char LINEDATA[3*TEAMSCOUNT];
> TeamRecord g_teamRecords[TEAMSCOUNT+1];
> int g_contestRanks[4*TEAMSCOUNT+2];
> ////////////
> 
> class ContestInfoReader
> {
> public:
> 	ContestInfoReader()
> 	{
> 		memset(g_teamRecords, 0, sizeof(g_teamRecords));
> 		memset(g_contestRanks, 0, sizeof(g_contestRanks));
> 	}
> 	void InitData()
> 	{
> 		m_currentRankIndex = 0;
> 		m_currentContestNumber = 1;
> 		ReadContestData();
> 
> 		gets(LINEDATA);
> 
> 		FillContestRank(0);
> 		m_currentContestNumber = 2;
> 		ReadContestData();
> 		FillContestRank(0);
> 	}
> 	bool NextTeamOfBothType()
> 	{
> 		++m_currentTeamId;
> 		for(int i=m_currentTeamId; i<=TEAMSCOUNT; ++i)
> 			if(g_teamRecords[i].joinType == BOTH)
> 			{
> 				m_currentTeamId = i;
> 				return true;
> 			};
> 		return false;
> 	}
> 	bool NextTeamOfSingleType()
> 	{	
> 		int teamIndex = g_contestRanks[++m_currentRankIndex];
> 		while(teamIndex != 0)
> 		{
> 			JoinType type = (m_currentContestNumber==1)?FIRST:SECOND;
> 			if(g_teamRecords[teamIndex].joinType != type)
> 				teamIndex = g_contestRanks[++m_currentRankIndex];
> 			else
> 			{
> 				m_currentTeamId = teamIndex;
> 				return true;
> 			}				
> 		}
> 	
> 		if(PrepareForNextGroup())
> 			return NextTeamOfSingleType();
> 		else
> 			return false;	
> 	}
> 	void ResetCurrentTeamId()
> 	{
> 		m_currentTeamId = 0;
> 	}
> 	void ResetCurrentRank()
> 	{
> 		m_currentRankIndex = -1;
> 		m_currentContestNumber = 1;
> 		PrepareForNextGroup();
> 	}
> 
> 	int CurrentTeamId()
> 	{
> 		return m_currentTeamId;
> 	}
> 	Status& CurrentStatus()
> 	{
> 		return m_status;
> 	}
> 	int CurrentGroupId()
> 	{
> 		return m_groupIndex;
> 	}
> protected:
> 	void ReadContestData()
> 	{
> 		int rankSum, rankCur; 
> 		int teamId, teamCount;
> 		char *pCur;
> 
> 		gets(LINEDATA);
> 		sscanf(LINEDATA, "%d", &teamCount);
> 
> 		rankSum = 0;
> 		for(int i=0; i<teamCount; ++i)
> 		{
> 			gets(LINEDATA);
> 			rankCur = rankSum+1;
> 			pCur = strtok(LINEDATA, DELIMITERS);
> 			while(pCur)
> 			{
> 				++rankSum;
> 				teamId = atoi(pCur);
> 				FillTeamRecord(teamId, rankCur);
> 				FillContestRank(teamId);
> 				pCur = strtok(NULL, DELIMITERS);
> 			}
> 			FillContestRank(0);
> 		}
> 	}
> 	void FillTeamRecord(int teamId, int rank)
> 	{
> 		if(m_currentContestNumber == 1)
> 		{
> 			g_teamRecords[teamId].joinType = FIRST;
> 			g_teamRecords[teamId].rank1 = rank;
> 		}
> 		else if(m_currentContestNumber == 2)
> 		{
> 			if(g_teamRecords[teamId].joinType == NONE)
> 			{
> 				g_teamRecords[teamId].joinType = SECOND;
> 				g_teamRecords[teamId].rank2 = rank;
> 			}
> 			else if(g_teamRecords[teamId].joinType == FIRST)
> 			{
> 				int rank1 = g_teamRecords[teamId].rank1;
> 				g_teamRecords[teamId].joinType = BOTH;
> 				g_teamRecords[teamId].rank2 = rank;
> 				g_teamRecords[teamId].sumRanks = rank1+rank;
> 			}
> 		}
> 	}
> 	void FillContestRank(int teamId)
> 	{
> 		g_contestRanks[m_currentRankIndex++] = teamId;
> 	}
> 	bool PrepareForNextGroup()
> 	{
> 		int rankIndex = m_currentRankIndex+1;
> 		if(g_contestRanks[rankIndex] > 0)
> 		{
> 			SetGroupStatus();
> 			if(m_status == UNCERTAIN)
> 			{
> 				JumpCurrentGroup();
> 				return PrepareForNextGroup();
> 			}
> 			return true;
> 		}
> 		else if(m_currentContestNumber == 1)
> 		{
> 			++m_currentRankIndex;
> 			m_currentContestNumber = 2;
> 			return PrepareForNextGroup();
> 		}
> 		return false;
> 	}
> 	void SetGroupStatus()
> 	{
> 		m_groupIndex = 0;
> 		bool bUncertain = false;
> 		for(int i=m_currentRankIndex+1; ;++i)
> 		{
> 			int teamIndex = g_contestRanks[i];
> 			if(teamIndex == 0)
> 				break;
> 
> 			if(g_teamRecords[teamIndex].joinType == BOTH)
> 			{
> 				if(m_groupIndex == 0)
> 					m_groupIndex = teamIndex;
> 				else if(g_teamRecords[m_groupIndex].sumRanks != g_teamRecords[teamIndex].sumRanks)
> 				{
> 					bUncertain = true;
> 					break;
> 				}
> 			}
> 		}
> 
> 		if(bUncertain)
> 			m_status = UNCERTAIN;
> 		else if(m_groupIndex == 0)
> 			m_status = INSINGLE;
> 		else
> 		    m_status = INBOTH;
> 	}
> 	void JumpCurrentGroup()
> 	{
> 		int teamIndex = g_contestRanks[++m_currentRankIndex];
> 		while(teamIndex != 0)
> 			teamIndex = g_contestRanks[++m_currentRankIndex];
> 	}
> private:
> 	//for iteration
> 	int m_currentTeamId;
> 	int m_currentRankIndex;
> 	int m_currentContestNumber;
> 
> 	//group status
>         Status m_status;
> 	int m_groupIndex;
> };
> 
> class ContestRatingSorter
> {
> public:
> 	ContestRatingSorter() : m_pHead(NULL)
> 	{}
> 	~ContestRatingSorter()
> 	{
> 		if(m_pHead)
> 			delete m_pHead;
> 	}
> 
> 	bool PrepareForInsert(int id)
> 	{
> 		m_pInsert = new LinkTeamRecord(id);
> 		if(m_pHead)
> 		{
> 			ResetFromHead();
> 			return true;
> 		}
> 		m_pHead = m_pInsert;
> 		return false;		
> 	}
> 	void InsertBothType()
> 	{
> 		int sumInsert = g_teamRecords[m_pInsert->teamId].sumRanks;
> 		int sumCurrent = g_teamRecords[m_pHead->teamId].sumRanks;
> 
> 		if(sumInsert > sumCurrent)
> 		{
> 			while(NextGroup())
> 			{
> 				sumCurrent = g_teamRecords[m_pCurrentGroup->teamId].sumRanks;
> 				if(sumInsert <= sumCurrent)
> 					break;
> 			}
> 		}
> 	
> 		if(sumInsert == sumCurrent)
> 			InsertInGroup();
> 		else 
> 			NewGroup();
> 	}
> 	void InsertSingleInBothType(int groupId)
> 	{
> 		Find(groupId);
> 		InsertInGroup();
> 	}
> 	bool InsertSingleType()
> 	{
> 		bool bUncertain = false;
> 		bool bFindGroup = false;
> 		LinkTeamRecord *pFront = NULL;
> 		LinkTeamRecord *pBack = NULL; 
> 		
> 		JoinType typeInsert = g_teamRecords[m_pInsert->teamId].joinType;
> 		int rankInsert = GetSingleRank(typeInsert, m_pInsert->teamId);
> 		
> 		do
> 		{
> 			int rankCurrent = GetSingleRank(typeInsert, m_pCurrentNode->teamId);
> 			if(rankCurrent != 0)
> 			{
> 				if(rankInsert > rankCurrent)
> 				{
> 					if(pBack)
> 					{
> 						bUncertain = true;
> 						break;
> 					}
> 					pFront = m_pCurrentGroup;
> 				}			
> 				else if(rankInsert < rankCurrent)
> 				{
> 					if(m_pCurrentGroup == pFront)
> 					{
> 						bUncertain = true;
> 						break;
> 					}
> 					if(!pBack)
> 						pBack = m_pCurrentGroup;
> 				}		
> 				else
> 				{
> 					bFindGroup = true;
> 					break;
> 				}
> 			}
> 		}
> 		while(Next());
> 
> 		if(!bUncertain)
> 		{
> 			if(bFindGroup)
> 				InsertInGroup();
> 			else
> 				InsertBetweenGroups(pFront, pBack);
> 			return true;
> 		}
> 		
> 		if(m_pInsert)
> 			delete m_pInsert;  //free memory
> 		return false;
> 	}
> 	void PrintRatingList()
> 	{
> 		LinkTeamRecord *pGroup = m_pHead;
> 		LinkTeamRecord *pNode = m_pHead;
> 		while(pGroup)
> 		{
> 			printf("%d", pGroup->teamId);
> 			pNode = pGroup->right;
> 			while(pNode)
> 			{
> 				printf("%s%d"," ",pNode->teamId);
> 				pNode = pNode->right;
> 			}
> 			printf("\n");
> 			pGroup = pGroup->next;
> 		}
> 	}
> protected:
> 	void ResetFromHead()
> 	{
> 		ResetFromGroup(NULL);
> 	}
> 	void ResetFromGroup(LinkTeamRecord *pPre)
> 	{
> 		LinkTeamRecord *pCur = NULL;
> 		if(!pPre)
> 			pCur = m_pHead;
> 		else
> 			pCur = pPre->next;
> 
> 		m_pPreviousNode = NULL;
> 		m_pCurrentNode = pCur;
> 		m_pPreviousGroup = pPre;
> 		m_pCurrentGroup = pCur;
> 	}
> 	bool Next()
> 	{
> 		if(!NextNodeInGroup())
> 			return NextGroup();
> 		return true;
> 	}
> 	bool NextGroup()
> 	{
> 		m_pPreviousGroup = m_pCurrentGroup;
> 		m_pCurrentGroup = m_pCurrentGroup->next;
> 		m_pPreviousNode = NULL;
> 		m_pCurrentNode = m_pCurrentGroup;
> 		return m_pCurrentGroup!=NULL;
> 	}
> 	bool NextNodeInGroup()
> 	{
> 		m_pPreviousNode = m_pCurrentNode;
> 		m_pCurrentNode = m_pCurrentNode->right;
> 		return m_pCurrentNode!=NULL;
> 	}
> 	void InsertInGroup()
> 	{
> 		//restart from current group
> 		m_pPreviousNode = NULL;
> 		m_pCurrentNode = m_pCurrentGroup;
> 
> 		int idInsert = m_pInsert->teamId;
> 		if(idInsert > m_pCurrentGroup->teamId)
> 		{
> 			while(NextNodeInGroup())
> 			{
> 				if(idInsert < m_pCurrentNode->teamId)
> 					break;
> 			}
> 		}	
> 		NewNode();
> 	}
> 	void InsertBetweenGroups(LinkTeamRecord *front, LinkTeamRecord *back)
> 	{
> 		ResetFromGroup(front);
> 
> 		int rankCurrent = 0;
> 		int rankInsert = GetSingleRank(m_pInsert->teamId);
> 		
> 		while(m_pCurrentGroup != back)
> 		{
> 			rankCurrent = GetSingleRank(m_pCurrentGroup->teamId);
> 			if(rankInsert <= rankCurrent)
> 				break;
> 			NextGroup();
> 		}
> 
> 		if(rankInsert == rankCurrent)
> 			InsertInGroup();
> 		else
> 			NewGroup();
> 	}
> 	void NewGroup()
> 	{
> 		if(m_pCurrentGroup == m_pHead)
> 		{
> 			//new head
> 			m_pInsert->next = m_pHead;
> 			m_pHead = m_pInsert;
> 		}
> 		else
> 		{
> 			//new group
> 			m_pPreviousGroup->next = m_pInsert;
> 			m_pInsert->next = m_pCurrentGroup;
> 		}
> 	}
> 	void NewNode()
> 	{
> 		if(m_pCurrentNode == m_pCurrentGroup)
> 		{
> 			if(m_pPreviousGroup)
> 				m_pPreviousGroup->next = m_pInsert;
> 
> 			m_pInsert->right = m_pCurrentGroup;
> 			m_pInsert->next = m_pCurrentGroup->next;
> 			m_pCurrentGroup->next = NULL;
> 
> 			//new head
> 			if(!m_pPreviousGroup)
> 				m_pHead = m_pInsert;
> 		}
> 		else
> 		{
> 			m_pPreviousNode->right = m_pInsert;
> 			m_pInsert->right = m_pCurrentNode;
> 		}
> 	}
> 	LinkTeamRecord *Find(int id)
> 	{
> 		if(id != m_pHead->teamId)
> 			while(Next())
> 			{
> 				if(id == m_pCurrentNode->teamId)
> 					break;
> 			};
> 		return m_pCurrentNode;
> 	}
> 	int GetSingleRank(int teamId)
> 	{
> 		int rank = 0;
> 		TeamRecord team = g_teamRecords[teamId];
> 		if(team.joinType == FIRST)
> 			rank = team.rank1;
> 		else if(team.joinType == SECOND)
> 			rank = team.rank2;
> 		return rank;
> 	}
> 	int GetSingleRank(JoinType type, int teamId)
> 	{
> 		int rank = 0;
> 		TeamRecord team = g_teamRecords[teamId];
> 		if(type == FIRST)
> 			rank = team.rank1;
> 		else if(type == SECOND)
> 			rank = team.rank2;
> 		return rank;
> 	}
> private:
> 	LinkTeamRecord *m_pHead;
> 	LinkTeamRecord *m_pInsert;
> 
> 	//for iteration
> 	LinkTeamRecord *m_pPreviousGroup;
> 	LinkTeamRecord *m_pCurrentGroup;
> 	LinkTeamRecord *m_pPreviousNode;
> 	LinkTeamRecord *m_pCurrentNode;
> };
> int main()
> {
> 	ContestInfoReader reader;
> 	ContestRatingSorter sorter;
> 	
> 	reader.InitData();
> 	reader.ResetCurrentTeamId();
> 	while(reader.NextTeamOfBothType())
> 	{
> 		int id = reader.CurrentTeamId();
> 		if(sorter.PrepareForInsert(id))
> 			sorter.InsertBothType();
> 	}
> 
> 	reader.ResetCurrentRank();
> 	while(reader.NextTeamOfSingleType())
> 	{
> 		int id = reader.CurrentTeamId();
> 		if(sorter.PrepareForInsert(id))
> 		{
> 			Status status = reader.CurrentStatus();
> 			if(status == INBOTH)
> 			{
> 				int groupId = reader.CurrentGroupId();
> 				sorter.InsertSingleInBothType(groupId);
> 			}
> 			else if(status == INSINGLE)
> 				sorter.InsertSingleType();
> 		}		
> 	}
> 
> 	sorter.PrintRatingList();
> 	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