【第021题】题解代码分享：没剪枝，直接挂了5个测试点，USACO 2020 Swapity Swap

小码匠

发布于 2023-12-13 10:56:02

2060

发布于 2023-12-13 10:56:02

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好，我是小码匠。

今天回到家，先看了这道题的题解，

学习代码2应该是推了个公式，没太看懂；
学习代码1加了剪枝，我昨天的没剪枝，就挂了5个测试点。

后来改了昨天的代码，稍微调试了下，还有问题，之后老码农给我安排了另外一道题。

分享的代码是官方代码。

前置知识

搜索

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：22道
待完成：278道

题目地址

https://www.usaco.org/index.php?page=viewproblem2&cpid=1013

Farmer John 的 N 头奶牛（1≤N≤100）站成一排。对于每一个 1≤i≤N，从左往右数第 i 头奶牛的编号为 i。Farmer John 想到了一个新的奶牛晨练方案。他让她们重复以下包含两个步骤的过程 K（1≤K≤

10^9

）次：

当前从左往右数在位置 A1…A2 的奶牛序列反转她们的顺序（1≤A1<A2≤N）。
然后，在当前从左往右数在位置 B1…B2 的奶牛序列反转她们的顺序（1≤B1<B2≤N）。

当奶牛们重复这一过程 K 次后，请对每一个 1≤i≤N 输出从左往右数第 i 头奶牛的编号。

测试点性质：

测试点 2-3 满足 K≤100。
测试点 4-13 没有额外限制。

输入格式（文件名：swap.in）：

输入的第一行包含 N 和 K。第二行包含

A_1

和

A_2

，第三行包含

B_1

和

B_2

。

输出格式（文件名：swap.out）：

在第 i 行输出晨练结束时从左往右数第 i 头奶牛的编号。

输入样例：

7 2
2 5
3 7

输出样例：

初始时，奶牛们的顺序从左往右为 [1,2,3,4,5,6,7]。在这一过程的第一步过后，顺序变为 [1,5,4,3,2,6,7]。在这一过程的第二步过后，顺序变为 [1,5,7,6,2,3,4]。再重复这两个步骤各一次可以得到样例的输出。

题解

暴力代码

直接暴力，13个测试点过了8个，明天继续干正解。

#include <bits/stdc++.h>

using namespace std;

void best_coder() {
    int n, k;
    int a1, a2;
    int b1, b2;
    cin >> n >> k;
    cin >> a1 >> a2;
    cin >> b1 >> b2;
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; ++i) {
        ans[i] = i;
    }
    int a3 = (a1 + a2) / 2 + (a1 + a2) % 2 - a1;
    int b3 = (b1 + b2) / 2 + (b1 + b2) % 2 - b1;
    while(k--) {
        for (int i = 0; i < a3; ++i) {
            swap(ans[i + a1], ans[a2 - i]);
        }

        for (int i = 0; i < b3; ++i) {
            swap(ans[i + b1], ans[b2 - i]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }
}

void happy_coder() {

}

int main() {
   // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

    freopen("swap.in", "r", stdin);
    freopen("swap.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    fclose(stdin);
    fclose(stdout);

    return 0;
}

学习代码

官方提供的代码，进行了剪枝操作，我再原来的代码改了改，没改成功，放弃了就去做另外一道题了。

#include <fstream>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/** Reverses [start, end] in the given vector in-place. */
template <typename T> void reverse_segment(vector<T> &vec, int start, int end) {
	while (start < end) {
		T temp = vec[start];
		vec[start] = vec[end];
		vec[end] = temp;

		start++;
		end--;
	}
}

int main() {
	std::ifstream read("swap.in");
	int n, k;
	read >> n >> k;
	int a1, a2;
	int b1, b2;
	read >> a1 >> a2 >> b1 >> b2;

	vector<int> cows(n);
	// Assign the values 1, 2, 3... to the vector of cows
	iota(cows.begin(), cows.end(), 1);

	// Apply swaps until the cows repeat themselves
	std::set<vector<int>> visited{cows};
	while (true) {
		reverse_segment(cows, a1 - 1, a2 - 1);
		reverse_segment(cows, b1 - 1, b2 - 1);
		if (visited.count(cows)) { break; }
		visited.insert(cows);
	}

	int cycle_len = visited.size();
	int swaps_left = k % cycle_len;
	for (int s = 0; s < swaps_left; s++) {
		reverse_segment(cows, a1 - 1, a2 - 1);
		reverse_segment(cows, b1 - 1, b2 - 1);
	}

	std::ofstream written("swap.out");
	for (int c : cows) { written << c << '\n'; }
}

学习代码2

#include <iostream>

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int N, K, A1, A2, B1, B2, res[101];  // res stores the result

int nex(int x) {
	if (A1 <= x && x <= A2)  // simulate step 1
		x = A1 + A2 - x;
	if (B1 <= x && x <= B2)  // simulate step 2
		x = B1 + B2 - x;
	return x;
}

int main() {
	setIO("swap");

	// read in input
	cin >> N >> K >> A1 >> A2 >> B1 >> B2;

	// solve for each cow
	for (int i = 1; i <= N; ++i) {
		// p = how many turns so far?
		// cur = where are we after p turns?
		int p = 1, cur = nex(i);
		while (cur != i) {  // keep going until we have found a cycle
			p++;
			cur = nex(cur);  // simulating another turn
		}
		int k = K % p;  // reduce k
		for (int j = 0; j < k; ++j) cur = nex(cur);
		res[cur] = i;  // position of cow i after k steps is cur
	}
	// print answer
	for (int i = 1; i <= N; ++i) cout << res[i] << "\n";
}