求助大神,这段代码 60 分出啥问题了?
查看原帖
求助大神,这段代码 60 分出啥问题了?
80298
NetherDevil楼主2020/12/16 22:22

RT ,就是这段代码,最高只能到 60

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned long long QWORD;
typedef void* HANDLE;
int nInputTunnel[100000] = { false };
static bool bAutoUpdate;
typedef class _fraction {
protected:
	QWORD n, m;
	bool bUpToDate;
	QWORD gcd(QWORD x, QWORD y) {
		while (y) {
			QWORD t = x % y;
			x = y;
			y = t;
		}
		return x;
	}
public:
	const static QWORD UPDATE_MANUALLY = false, UPDATE_AUTOMATICLY = true;
	static void SetUpdatePolicy(bool bStat) {
		bAutoUpdate = bStat;
	}
	void UpdateFrac() {
		QWORD nGcd = gcd(n, m);
		n /= nGcd;
		m /= nGcd;
	}
	QWORD GetNume() {
		if (!bUpToDate) {
			UpdateFrac();
		}
		return n;
	}
	QWORD GetDeno() {
		if (!bUpToDate) {
			UpdateFrac();
		}
		return m;
	}
	long double GetValPqf() {
		if (!bUpToDate) {
			UpdateFrac();
		}
		return (long double)n / m;
	}
	void SetValue(QWORD nNume, QWORD nDeno) {
		n = nNume;
		m = nDeno;
		if (bAutoUpdate) {
			UpdateFrac();
			bUpToDate = true;
		}
		else {
			bUpToDate = false;
		}
	}
	void operator =(const QWORD& nParam) {
		n = nParam;
		m = 1;
		bUpToDate = true;
	}
	void operator /=(const QWORD& nParam) {
		m *= nParam;
		if (bAutoUpdate) {
			UpdateFrac();
			bUpToDate = true;
		}
		else {
			bUpToDate = false;
		}
	}
	void operator *=(const QWORD& nParam) {
		n *= nParam;
		if (bAutoUpdate) {
			UpdateFrac();
			bUpToDate = true;
		}
		else {
			bUpToDate = false;
		}
	}
	void operator +=(const _fraction& fParam) {
		n = fParam.m * n + fParam.n * m;
		m *= fParam.m;
		if (bAutoUpdate) {
			UpdateFrac();
			bUpToDate = true;
		}
		else {
			bUpToDate = false;
		}
	}
}fraction;
typedef class _list {
protected:
	struct node{
		int nValue;
		node* next;
	}*head;
	int nElementCnt;
public:
	void Initialize() {
		nElementCnt = 0;
		head = NULL;
	}
	void* QueryFirst() {
		return (HANDLE)head;
	}
	QWORD QueryValue(HANDLE hCurrent) {
		return ((node*)hCurrent)->nValue;
	}
	void* QueryNext(HANDLE hCurrent) {
		if (hCurrent == NULL) {
			return NULL;
		}
		return (HANDLE)(((node*)hCurrent)->next);
	}
	int GetElementQuantity() {
		return nElementCnt;
	}
	void AddToHead(QWORD Value) {
		nElementCnt++;
		node* dTemp = new node;
		dTemp->nValue = Value;
		dTemp->next = head;
		head = dTemp;
	}
	void AddToNode(HANDLE hNode,QWORD Value) {
		node* dTemp = new node;
		dTemp->nValue = Value;
		dTemp->next = head;
		head = dTemp;
	}
	bool DeleteFromHead() {
		if (head == NULL) {
			return false;
		}
		node* dTemp = head;
		head = head->next;
		delete dTemp;
		return true;
	}
	void Cleanup() {
		while (DeleteFromHead());
	}
}list;
list Outputs[100000];
fraction frTotal[100000];
queue<int> qTopo;
int nNodes, nInputs;
int main(void) {
	fraction::SetUpdatePolicy(fraction::UPDATE_AUTOMATICLY);
	cin >> nNodes >> nInputs;
	for (int i = 0;i < nNodes;i++) {
		frTotal[i] = 0;
		int nOutCnt;
		cin >> nOutCnt;
		Outputs[i].Initialize();
		for (int j = 0;j < nOutCnt;j++) {
			int nTo;
			cin >> nTo;
			nTo--;
			nInputTunnel[nTo]++;
			Outputs[i].AddToHead(nTo);
		}
	}
	for (int i = 0;i < nNodes;i++) {
		if (nInputTunnel[i] == 0) {
			qTopo.push(i);
			frTotal[i] = 1;
			nInputTunnel[i] = -1;
		}
	}
	while (!qTopo.empty()) {
		int nTop = qTopo.front();
		HANDLE hCurrent;
		hCurrent = Outputs[nTop].QueryFirst();
		int nElements = Outputs[nTop].GetElementQuantity();
		while (hCurrent != NULL) {
			nInputTunnel[Outputs[nTop].QueryValue(hCurrent)]--;
			fraction frTemp = frTotal[nTop];
			frTemp /= nElements;
			frTotal[Outputs[nTop].QueryValue(hCurrent)] += frTemp;
			hCurrent = Outputs[nTop].QueryNext(hCurrent);
		}
/*		for (int i = 0, e = OutputTo[nTop].size();i < e;i++) {
 *			nInputTunnel[OutputTo[nTop][i]]--;
 *			fraction frTemp = frTotal[nTop];
 *			frTemp /= e;
 *			frTotal[OutputTo[nTop][i]] += frTemp;
 *		}
 */
		for (int i = 0;i < nNodes;i++) {
			if (nInputTunnel[i] == 0) {
				qTopo.push(i);
				nInputTunnel[i] = -1;
			}
		}
		qTopo.pop();
	}
	for (int i = 0;i < nNodes;i++) {
		if (Outputs[i].QueryFirst() == NULL) {
			cout << frTotal[i].GetNume() << ' ' << frTotal[i].GetDeno() << endl;
		}
		Outputs[i].Cleanup();
	}
	return 0;
}

代码没其他问题,就是把 fraction::SetUpdatePolicy(); 设置成为 fraction::UPDATE_AUTOMATICLY 会因为不断约分而拖慢速度,后 4 点 TLE ;但是如果设置为 fraction::UPDATE_MANUALLY 会因为爆 unsigned long long 而使结果不正确,后 7 点 WA 。( __int128 也会爆,然后输出负的,就离谱,这数据点不讲武德!!!)求大神给点建设性的思路?

2020/12/16 22:22
加载中...