[日本银行 9519，中国人民银行]昏昏欲睡

问题链接

boj 9519

分类

实现, 字符串, 模拟

描述

这个问题最初是通过全面探索解决的。

• 首先测量字符串的长度

• 分配一个与字符串长度相等的数字向量

• 根据问题条件重复并翻转

• 如果翻转了一定次数，则使用相应的哈希值将它们按相反顺序排列

• 你将看到原始图像！

这里最重要的一点是，你可以根据问题的条件反复翻转，而循环返回的结果将始终与初始数组相同。

找到上述规则后，你可以使用

• 先测量字符串的长度

• 0 ~ 指定一个与字符串长度相等的数字向量

  • 检查从 1 到（字符串长度 - 1）的循环次数

  • 重复翻转总次数除以循环次数，得出哈希值

• 如果翻转了一定次数，则使用该散列值按相反顺序排列

• 你可以看到原始图像！

看起来像这样

    for (int i = 1; i <= target_length - 1; i++)
    {
        for (int j = 0; j < target_length / 2; j++)
        {
            temp = result.back();
            result.pop_back();
            result.insert(result.begin() + 2 * j + 1, temp);
        }

		if (start_vector == result)
		{
			cycle = i;
			break ;
		}
    }

起初，我们如上图所示直接移动数组，但这造成了一些开销，因为插入后的数组也要移动，所以花费的时间稍长。

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

因此，我们使用上述方法提前创建数组，然后逐个插入数值，这样时间只用在数组的最大长度上。

求解代码

// 졸려

#include <iostream>
#include <vector>

using namespace std;

vector<int> flicker_action(int target_length, int count);

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int flicker_number;
    string result_string, init_string;
    vector<char> string_vector;
    vector<int> idx_vector;

    cin >> flicker_number;
    cin.ignore();
    getline(cin, result_string);

    for (int i = 0; i < (int) result_string.length(); i++)
        string_vector.push_back(result_string[i]);
    

    idx_vector = flicker_action(result_string.length(), flicker_number);
    init_string.resize(result_string.length());

    for (int i = 0; i < (int) result_string.length(); i++)
        init_string[idx_vector[i]] = result_string[i];

    cout << init_string << endl;
    return (0);
}

vector<int> flicker_action(int target_length, int count)
{
    vector<int> result, temp_vector, start_vector;
	int cycle;

    for (int i = 0; i < target_length; i++)
        result.push_back(i);

	start_vector = result;
	cycle = 1;

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

	result = start_vector;

    for (int i = 0; i < (count % cycle); i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		result = temp_vector;
    }

    return (result);
}