大家好，我是小码匠。
今天回到家，先看了这道题的题解，
- 学习代码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≤
）次：
- 当前从左往右数在位置 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。第二行包含
和
，第三行包含
和
。
输出格式（文件名：swap.out）：
在第 i 行输出晨练结束时从左往右数第 i 头奶牛的编号。
输入样例：
代码语言：javascript复制7 2
2 5
3 7
输出样例：
代码语言：javascript复制1
2
4
3
5
7
6
初始时，奶牛们的顺序从左往右为 [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
代码语言：javascript复制#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";
}
END
你的每个【点赞 在看】
我都当成了喜欢
让我们同行，一起成长为优秀的oier，去改变世界。
