poj3276 Face The Right Way(反转问题,好题)

https://vjudge.net/problem/POJ-3276

首先意识到,对一个区间进行两次及以上的反转是没有意义的,而且反转次序不影响最终结果。

有点像二分搜索时用的逐个试的方法,每次翻的个数从1~n,然后进入函数判断。

由于正反性可以很巧妙地利用计数的奇偶来判断,所有这里优化复杂度,用f[i]记录i~i+k-1是否翻转了,不断向右判断,如果是反面就反转接下来的一组,直至最后,最后剩的几个如果全正就说明可以,如果有反面就说明不行。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<map>
 8 #define lson l, m, rt<<1
 9 #define rson m+1, r, rt<<1|1
10 #define INF 0x3f3f3f3f
11 typedef unsigned long long ll;
12 using namespace std;
13 int n, a[5010], f[5010];//f是i~i+k-1的是否翻了
14 char c;
15 int calc(int k)
16 {
17     memset(f, 0, sizeof(f));//每一次都要初始化f
18     int sum=0, res=0;
19     for(int i = 0; i <= n-k; i++){
20         if(!((a[i]+sum)&1)){//判断该点是反,需要翻转
21             f[i] = 1;
22             res++;
23         }
24         sum += f[i];
25         if(i-k+1>=0)
26             sum -= f[i-k+1];
27     }
28     for(int i = n-k+1; i < n; i++){
29         if(!((a[i]+sum)&1)){
30             return -1;
31         }
32         if(i-k+1>=0)
33             sum -= f[i-k+1];
34     }
35     return res;
36 }
37 int main()
38 {
39     cin >> n;
40     for(int i = 0; i < n; i++){
41         cin >> c;
42         if(c == ‘B‘) a[i] = 0;
43         else a[i] = 1;
44     }
45     memset(f, 0, sizeof(f));
46     int mini = INF, ans=-1;
47     for(int i = 1; i <= n; i++){
48         int num = calc(i);
49         //cout << i << " " << num << endl;
50         if(num>0&&num<mini){
51             mini = num;
52             ans = i;
53         }
54     }
55     cout << ans << " " << mini << endl;
56     return 0;
57 }

原文地址:https://www.cnblogs.com/Surprisezang/p/9043597.html

时间: 05-15

poj3276 Face The Right Way(反转问题,好题)的相关文章

反转链表算法题

反转一个单链表. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶:你可以迭代或递归地反转链表.你能否用两种方法解决这道题? 解决方案 方法一:迭代 假设存在链表 1 → 2 → 3 → Ø,我们想要把它改成 Ø ← 1 ← 2 ← 3. 在遍历列表时,将当前节点的 next 指针改为指向前一个元素.由于节点没有引用其上一个节点,因此必须事先存储其前一个元素.在更改引用之前,还需要另一个

看一遍就理解,图解单链表反转

前言 反转链表是程序员必备的基本素养,经常在面试.笔试的过程中出现.一直觉得反转链表实现代码不是很好理解,决定搬leetcode那道经典反转链表题出来,用十多张图去解析它,希望加深大家对链表反转的理解,谢谢阅读. leetcode的反转链表原题&答案 题目描述: 反转一个单链表. 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 分析: 假设存在链表 1 → 2 → 3 → ?,我们想要把它改

Lettcode_344_Reverse String

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/51685726 Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh". Subscribe to see which companies a

Reverse Integer - Palindrome Number - 简单模拟

第一个题目是将整数进行反转,这个题实现反转并不难,主要关键点在于如何进行溢出判断.溢出判断再上一篇字符串转整数中已有介绍,本题采用其中的第三种方法,将数字转为字符串,使用字符串比较大小的方法进行比较. 代码如下: 1 class Solution { 2 public: 3 int reverse(int x) { 4 int stand[10]={2,1,4,7,4,8,3,6,4,8}; 5 int getnum[10]; 6 int a=0,flag=0; 7 if(x>0) 8 flag

剑指Offer(11-20)

关于剑指Offer的一些解题思路 题11:数值的整数次方 实现函数double Power(double base, int exponent),求base的exponent次方. 不得使用库函数,同时不需要考虑大数问题. import java.util.Scanner; public class Main { public static void main(String[] args)throws Exception { Scanner sc=new Scanner(System.in);

【反转】POJ3276

Face The Right Way 题意:N个牛 每个都有一定的方向 B背对 F表示头对着你 给你一个装置 每次可以选择连续的K个牛反转方向 问你如何选择K 使得操作数最少 k也应尽量小. 例子:   N=7   BBFBFBB   (F:前面   B:后面)    (红色的为要反转的)   此出K=3  M=3 B B F B F B B F F B B F B B F F F F B B B F F F F F F F   成功了 如果用暴力的方法的话:   考虑N头牛的话最坏情况下要进行

挑战程序竞赛 反转开关 poj3276

这个我其实也没有看太懂它的证明过程. 1.若某一个位置被翻转了n次,则其实际上被翻转了n%2次. 2.分析易知翻转的顺序并不影响最终结果. 3.现在我们着眼于第1个位置,可知若要将第1个位置进行翻转只有翻转它自己,因为没有其他位置的翻转会引起它的翻转. 由①可知若第1个位置为1则必须且进行翻转(并将其后2个进行连带翻转)且以后不再进行翻转,因为再进行翻转就一共翻转了2次相当于没翻转. 然后着眼于第2个位置,由于第1个位置不再进行翻转,所以要想翻转第2个位置只有翻转它自己,因为没有其他位置的翻转会

反转 开关问题

首先考虑最左端的牛.包含这头牛的区间只有一个,因此如果这头牛面朝前方,这个区间不反转,面朝后方则反转.以此类推,逐渐缩小问题规模. 用数组j[i]=1代表区间[i,i+K-1]进行了反转  j[i]=0代表不反转. 如果一头牛之前被反转的次数为奇数,则朝向和刚开始相反,为偶数则相同. #include<iostream> #include<memory.h> using namespace std; int N,dir[5005]; int j[5005]; //标记区间[i,i-

1.5编程基础之循环控制_29:数字反转

/* 1.5编程基础之循环控制 29:数字反转 总时间限制: 1000ms 内存限制: 65536kB 描述 给定一个整数,请将该数各个位上数字反转得到一个新数. 新数也应满足整数的常见形式,即除非给定的原数为零, 否则反转后得到的新数的最高位数字不应为零(参见样例2). 输入 输入共 1 行,一个整数N. -1,000,000,000 ≤ N≤ 1,000,000,000. 输出 输出共 1 行,一个整数,表示反转后的新数. 样例输入 样例 #1: 123 样例 #2: -380 样例输出 样