[USACO07MAR]Face The Right Way G
$N$ 头牛排成一列 $1 \le N \le 5000$。每头牛或者向前或者向后。为了让所有牛都面向前方,农夫每次可以将 $K$ 头连续的牛转向 $1 \le K \le N$,求使操作次数最小的相应 $K$ 和最小的操作次数 $M$。$F$ 为朝前,$B$ 为朝后。
请在一行输出两个数字 \(K\) 和 \(M\),用空格分开。
- 交换区间的反转顺序对结果没有影响。
- 对同一个区间的进行反转两次以上是多余的
由此问题就变成的反转区间的集合
将这一列牛存储在一个数组中\(cows[n]\)对于\([i\rightarrow 1,n]\)正向遍历,如果\(cows[i]\)是正向的,那么就没必要反转,如果\(cows[i]\)是反向的可以反转的区间的长度为\([1,n-i]\),记录每个位置反转的次数,如果这个位置被反转了奇数次那么方向与初始值相反,如果是偶数次方向则不变。
设\(f[i]\)对应的区间为\([i,i+k-1]\),那么\(f[i]=1\)说明该区间被反转了一次,如果为\(0\)说明没变化,考虑第\(j\)头牛的话,其反转的次数\(sums[j]=\sum^{j}_{i=j-k+1}f[i]\),如果\(sums[j]\)是奇数,其状态与\(cows[j]\)相反,如果是偶数则相同。
\[sum_i=\sum^{i}_{j=(i+1)-k+1}f[j]=\sum^{i-1}_{j=i-k+1}f[j]+f[i]-f[j-k+1] \]int N, K, M;
char state[MAX_N];
int dp[MAX_N];
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
#define goto(x, y) x + 1, x + y + 1
#define mm(x, y) memset(x, y, sizeof(x))
inline int solve(int k) {
fill(goto(dp, N), 0);
int sum = 0, num = 0;
// 如果为奇数方向相反,如果为偶数,方向相同
ufr(i, 1, N - k + 1) {
//如果sum是偶数,只有当state[i]=='B'时才翻转
if (!(sum & 1) && state[i] == 'B' || (sum & 1) && state[i] == 'F') {
dp[i] = 1, ++num;
}
sum += dp[i];
if (i - k + 1 >= 1) {
sum -= dp[i - k + 1];
}
}
//最后N-k个剩余的牛牛,如果头是反着的,说明翻转失败
ufr(i, N - k + 2, N) {
if (!(sum & 1) && state[i] == 'B' || (sum & 1) && state[i] == 'F') {
return -1;
}
if (i - k + 1 >= 1) {
sum -= dp[i - k + 1];
}
}
return num;
}
signed main() {
using namespace Solution;
N = f.r();//快读整形
ufr(i, 1, N) state[i] = f.rc();//快速读取字符
K = 1, M = N;//一定会有K=1,M=N
ufr(k, K, N) {
int m = solve(k);
if (m >= 0 && M > m) {
K = k, M = m;
}
}
f.pt(K).ptc(' ').pt(M).ln();//输出
return 0;
}
[USACO07OPEN] Fliptile S
FJ 知道,智商高的奶牛产奶量也大,所以他为奶牛们准备了一个翻动瓦片的益智游戏。
在一个 \(M \times N\) 的方阵上(\(1 \leq M,N \leq 15\)),每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色,另一面是白色。对一个瓦片翻转,可以让它的颜色由黑到白,或是由白到黑。
然而奶牛们很笨拙,它们翻转一个格子的瓦片时,与其有公共边的所有瓦片也会翻转。
现在奶牛们想知道,至少需要多少次翻转,使所有的瓦片都变成白色朝上呢?
- 同一个格子反转两次以上是多余的。
- 交换反转的区间对结果没有任何的影响
如果用上面的方法对于下面的用例来说,会发现,如果想让\([1,1]和[2,2]\)俩瓦片反转,可以选择\([1,2]和[2,1]\),则会出现\(2^{NM}\)中翻转的可能。
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
如果固定住一行的选择那么其他的选的就固定了。比如,不从\([1,2]\)按下,那么就只能按\([2,1]\)了,并且不从\([1,3]\)按下那么就只能按\([2,4]\)了,以此类推。
那么只需要求出其一行选择的可能逐步遍历那么就可以求得最优解,时间复杂度\(O(MN\cdot 2^{N})\)
当集合中数据较少时,可以使用二进制的数码表示(如果某位出现1,就代表选择),比如一个$\{1,2,3,4\}$,$0000$代表空集,$0001$代表集合$\{1\}$,$0011$代表集合$\{1,2\}$,$1111$代表集合$\{1,2,3,4\}$
以下是集合的操作:
- 空集\(\varnothing\):\(0\)
- 只含有元素\(i\)的集合:\(1<<i\)
- 含有全部n个元素的集合 \(\{0,1,2...n-1\}\):\((1<<n)-1\)
- 判断是否属于集合\(S\):\(if((S>>i) \& 1)\)
- 向集合\(S\)加入第\(i\)个元素:\(S | (1 << i)\)
- 删除\(S\)中的第\(i\)个元素:\(S\&~(1<<i)\)
- 求集合T和S并集:\(T|S\)
- 集合S和T的交集:\(T\&S\)
枚举集合中的所有元素:for(int i=0;i<(1<<n);++i)
代码:
主函数
#include <string.h>
#include <algorithm>
#include <iostream>
#define int long long
#define MAX_N 20
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
#define all(x) x.begin(), x.end()
#define goto(x, y) x + 1, x + y + 1
#define mc(x, y) memcpy(x, y, sizeof(y))
#define mm(x, y) memset(x, y, sizeof(x))
using namespace std;
int M, N;
int tile[MAX_N][MAX_N];//瓦片
int opt[MAX_N][MAX_N];//最优操作
int flip[MAX_N][MAX_N];//当前的操作
int dir[5][2]{{0, 0}, {-1, 0}, {0, -1}, {1, 0}, {0, 1}};
signed main() {
cin.tie(0), ios::sync_with_stdio(false);
cin >> M >> N;
ufr(i, 1, M) ufr(j, 1, N) cin >> tile[i][j];
solve();
return 0;
}
\(solve\)函数
\(solve\)函数中每次遍历都清空\(flip\)数组,并且初始化flip数组第一行的操作,即选定一个集合,使得本次操作唯一。当i>>j & 1
是代表本次要按下第一行中哪个列的瓦片,\(flip[i][N-j]\)。然后调用\(calc\)函数进行计算,最后判断结果如果大于\(0\)说明本次操作可行,并且判断本次结果是否为当前最优值。
$calc$函数首先从第二行遍历,因为第一行已经初始化了,对于一直任意的位置$[i,j]$,该位置是否按下与上一行有关,即调用$get(i-1,j)$判断上一行是黑还是白,如果是白则不用按下,如果是黑则需要按下,因为如果本次不按,那么$tile[i-1][j]$这个瓦片以后都按不到了。最后判断第$M$行是否有剩余,如果有本次操作不成立也就是第一行的初始化不正确。如果没有记录本次操作的次数,即$flip$数组中$1$的个数,也就是总和。
$get函数$在主函数上面声明了一个$dir$数组。进行判断,如果$tile[x][y]$为$1$说明这个位置是黑的,那么如果要变白,必须进行奇数次的操作(1+奇数为偶数)。反之,如果为白,必须进行偶数次操作,如果进行了奇数次操作,那么就变黑了,所以在$calc$函数中$if$判断成立,则$flip[i][j]=1$。
int get(int x, int y) {
int c = tile[x][y];
ufr(i, 0, 4) {
int tx = x + dir[i][0], ty = y + dir[i][1];
if (tx >= 1 && tx <= M && ty >= 1 && ty <= N) c += flip[tx][ty];
}
return c % 2;
}
int calc() {
ufr(i, 2, M) ufr(j, 1, N) if (get(i - 1, j)) flip[i][j] = 1;
ufr(i, 1, N) if (get(M, i)) return -1;
int res = 0;
ufr(i, 1, M) ufr(j, 1, N) res += flip[i][j];
return res;
}
inline void solve() {
int res = -1;
for (int i = 0; i < 1 << N; ++i) {
mm(flip, 0);
for (int j = 0; j < N; ++j) flip[1][N - j] = i >> j & 1;
int num = calc();
if (num >= 0 && (res < 0 || res > num)) res = num, mc(opt, flip);
}
if (res < 0) {
cout << "IMPOSSIBLE" << endl;
} else {
ufr(i, 1, M) {
ufr(j, 1, N) cout << opt[i][j] << " ";
cout << endl;
}
}
}
参考书籍《挑战程序设计竞赛 第二版》 标签:int,反转,sum,问题,开关,瓦片,集合,ufr From: https://www.cnblogs.com/GuanStudy/p/16936048.html