打卡
参考文献
2016-S5 生命圈 - 解决方案
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
int* oldGeneration;
int* newGeneration;
int n;
LL t;
void readInput()
{
cin >> n >> t;
oldGeneration = new int[n];
newGeneration = new int[n];
string input;
cin >> input;
for (int i = 0; i < n; i++)
{
if (input[i] == '0')
oldGeneration[i] = 0;
else
oldGeneration[i] = 1;
}
}
void writeOutput()
{
for (int i = 0; i < n; i++)
cout << oldGeneration[i];
delete oldGeneration;
delete newGeneration;
}
int getCyclicPointer(LL cyclicIndex)
{
LL nonCyclicIndex = cyclicIndex % n;
if (nonCyclicIndex < 0)
return n + nonCyclicIndex;
else
return nonCyclicIndex;
}
void simulateGenerations(LL numberofGenerations)
{
for (int i = 0; i < n; i++)
{
newGeneration[i] = {oldGeneration[getCyclicPointer(i - numberofGenerations)] ^
oldGeneration[getCyclicPointer(i + numberofGenerations)]};
}
}
void swapGenerationPointers()
{
int* intermediate = oldGeneration;
oldGeneration = newGeneration;
newGeneration = intermediate;
}
LL getLargestPowerOfTwo(LL max)
{
LL powerOfTwo = 1;
for (int i = 0; i < 64; i++)
{
powerOfTwo <<= 1;
if (powerOfTwo > max)
{
powerOfTwo >>= 1;
return powerOfTwo;
}
}
return 0;
}
int main()
{
readInput();
LL generationsLeft = t;
while (generationsLeft > 0)
{
LL largestPowerOfTwo = getLargestPowerOfTwo(generationsLeft);
generationsLeft -= largestPowerOfTwo;
simulateGenerations(largestPowerOfTwo);
swapGenerationPointers();
}
writeOutput();
return 0;
}
好长,已经不想写了()
我一般都是先模仿,然后理解,最后熟练,过程很痛苦,成就感也会很强