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 也会爆,然后输出负的,就离谱,这数据点不讲武德!!!)求大神给点建设性的思路?