首页 > 其他分享 >反转 (开关问题)

反转 (开关问题)

时间:2022-11-29 17:45:19浏览次数:59  
标签:int 反转 sum 问题 开关 瓦片 集合 ufr

[USACO07MAR]Face The Right Way G


$N$ 头牛排成一列 $1 \le N \le 5000$。每头牛或者向前或者向后。为了让所有牛都面向前方,农夫每次可以将 $K$ 头连续的牛转向 $1 \le K \le N$,求使操作次数最小的相应 $K$ 和最小的操作次数 $M$。$F$ 为朝前,$B$ 为朝后。

请在一行输出两个数字 \(K\) 和 \(M\),用空格分开。

  1. 交换区间的反转顺序对结果没有影响。
  2. 对同一个区间的进行反转两次以上是多余的

由此问题就变成的反转区间的集合

将这一列牛存储在一个数组中\(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. 同一个格子反转两次以上是多余的。
  2. 交换反转的区间对结果没有任何的影响

如果用上面的方法对于下面的用例来说,会发现,如果想让\([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

相关文章

  • ios中getTime()的兼容性问题
    时间格式为:2017-12-1212:00:00在苹果上获取时间戳有兼容性问题 需要转换成2017/12/1212:00:00 才可以正确获取到时间戳 vargetTime=function(time){varmyDate......
  • 测试分辨问题
    公司的swagger打开查看发生问题的接口在哪个归属  打开归属  通过其他地方多处对比正确参数,如项目的topoID:    多处对比发现正确的topoID应该是159316......
  • element-ui中el-table设置多选checkbox时,selection-change重复执行,以及选不中问题
    项目中使用了elementUI中el-table的选择框。在另外一个地方展示选中的行的数量。设置显示数量之后,选择框就无法选中,change事件执行两次。解决办法:给el-table设置row-key,并......
  • Echarts 解决饼图文字显示不全问题
    文本越界文本超出容器边界。可以调整center值。series:[{type:'pie',radius:['50%','65%'],lab......
  • gitee推送更新失败问题记录:remote: error: hook declined to update refs/heads/maste
    问题描述:gitee推送更新时,提示:remote:PoweredbyGITEE.COM[GNK-6.4]remote:error:GE007:Yourpushwouldpublishaprivateemailaddress.    remote:......
  • Xcode 14签名问题
    升级Xcode14版本后,打包报错,提示签名相关问题。1、对于cocoapods管理的三方库,设置不签名即可,podfile中,添加下述代码:`post_installdo|installer|installer.pods_projec......
  • ConvTranspose的output_padding问题
    当stride>=2时,反向传播,由dy,w得到dx的时候,dx的形状不唯一。例如input_shape(7,7)或者(8,8)在kernel(3,3)上,以stride=2进行卷积,最终得到的形状都是(3,3)。参考:https:/......
  • 漫途水库大坝安全监测系统,助力解决水库安全问题!
    我国是山川、河流众多的国家,河流湖泊密布,特别是中小河流,错综交互,如此众多的河流,极易造成洪水灾害,为防止洪水灾害,大力兴建水库。水库给人们带来便利的同时也存在巨大的安全......
  • hadoop节点下线的问题
    注意:以下操作都是理论上的,由于我安装的是apachehadoop3.1.3原生版本,所以按照以下操作时,全部不生效,结果只能手工强制停止datanode、nodemanager服务。1.新增文件exclu......
  • viewpager循环滚动和自动轮播的问题
    ViewPager是一个常用的android组件,不过通常我们使用ViewPager的时候不能实现左右无限循环滑动,在滑到边界的时候会看到一个不能翻页的动画,可能影响用户体验。此外,某些区域性......