挑战程序竞赛 反转开关 poj3276

这个我其实也没有看太懂它的证明过程。

1.若某一个位置被翻转了n次,则其实际上被翻转了n%2次。

2.分析易知翻转的顺序并不影响最终结果。

3.现在我们着眼于第1个位置,可知若要将第1个位置进行翻转只有翻转它自己,因为没有其他位置的翻转会引起它的翻转。

由①可知若第1个位置为1则必须且进行翻转(并将其后2个进行连带翻转)且以后不再进行翻转,因为再进行翻转就一共翻转了2次相当于没翻转。

然后着眼于第2个位置,由于第1个位置不再进行翻转,所以要想翻转第2个位置只有翻转它自己,因为没有其他位置的翻转会引起它的翻转.....................以此类推直至最后剩下的个数<3个,

因为每次都翻转3个,而剩下的少于3个了就不再进行考虑了,此时只需判断剩下的是否全为0的即可,若不全为0,则不存在全部翻转为0的方案。

以上内容转自 反转(开关问题) Poj3276、3279、3185、1244

不过差不多就这样吧,书上还有一个公式,这个直接看还是很难看懂的,结合一下代码就很简单了。

#include <cstring>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5 + 10;
int dir[maxn], f[maxn], n;
char s[10];

int cul(int x)
{
    int sum = 0, res = 0;
    memset(f, 0, sizeof(f));
    for (int i = 1; i + x <= n + 1; i++) {
        if ((dir[i] + sum) % 2 == 0) {
            f[i] = 1;
            sum++;
            res++;
        }
        if (i - x + 1 >= 0) sum -= f[i - x + 1];
    }
    sum = 0;;
    for(int i=1;i<=n;i++)
    {
        sum += f[i];
        if ((dir[i] + sum) % 2 != 1) return -1;
        if (i - x + 1 >= 0) sum -= f[i - x + 1];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s", s);
        if (s[0] == ‘F‘) dir[i] = 1;
        else dir[i] = 0;
    }
    int ans = inf, mark = 0;
    for(int i=1;i<=n;i++)
    {
        int k = cul(i);
        if(k>=0&&ans>k)
        {
            ans = k;
            mark = i;
        }
    }
    printf("%d %d\n", mark, ans);
    return 0;
}

反转poj3276

原文地址:https://www.cnblogs.com/EchoZQN/p/11296222.html

时间: 08-01

挑战程序竞赛 反转开关 poj3276的相关文章

《挑战程序竞赛》1.6.2 Ants poj1852

题意:n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行.当蚂蚁爬到竿子的端点时就会掉落.由于竿子太细,两只蚂蚁相遇时,它们不能交错通过,只能各自反向爬回去.对于每只蚂蚁,我们知道它距离竿子左端的距离xi,但不知道它当前的朝向.请计算所有蚂蚁落下竿子所需的最短时间和最长时间. 解法:(1)对于最短时间,所有蚂蚁都朝向较近的端点走时时间最短,因为这种情况下不会发生两只蚂蚁相遇的情况,所以只要求出这种情况下最后一只到端点的蚂蚁的时间即可,时间亦最短. (2)对于最长时间,如果不考虑蚂蚁的实际体长等外

《挑战程序竞赛》 2.1.4 部分和问题

题意:给定整数a1,a2,a3,...,an,判断是否可以从中选出若干数,使它们的和恰好为k. 解法:利用dfs深度优先遍历,从a1开始按顺序决定每个数是加还是不加. code: 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 #define maxn 100000 6 7 int k, n; 8 9 int a[maxn]; 10 11 bool dfs(int i, int sum)

《挑战程序竞赛》1.6.1 三角形

题意:有n根棍子,棍子i的长度为ai,想要从中选出3根棍子组成周长尽可能长的三角形,请输出最大的周长,若无法组成三角形则输出0. 解法:将输入的棍子长度进行排序,由最长开始,一次取出三根最长的棍子,判断:最长的棍子 < 其余两根棍子的长度之和 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 #define maxn 1000 6 int n; 7 int func(int a[])

POJ 3420 Quad Tiling 题解 《挑战程序设计竞赛》

POJ 3420 Quad Tiling贴瓷砖:4*N的地板上用2*1的瓷砖铺满,求所有方案数对M求余.3.4熟练掌握动态规划矩阵的幂久违地上了节课,太无聊,只好刷一题.假设S[n]表示填满n时的方案数,有S[0]=1.定义矩阵M[p][q] := 边缘p和边缘q可以拼合时取1,否则取0所谓的可以拼合表示,两个边缘拼起来后长度为1(为2就拼接不起来了),且内部缝隙可以用2*1的瓷砖填满.那么M就有一些简单的性质了,比如M的第一行应该是:0 0 0 0 0 0... 继续阅读:码农场 » POJ

POJ 3411 Paid Roads 题解 《挑战程序设计竞赛》

POJ 3411 Paid Roads开路:N个城市间有m条单向路,分别从a到b,可以在c处交P路费,也可以直接交R路费.那么问题来了,你的挖掘机怎么开最省钱?3.4熟练掌握动态规划状态压缩DP乍一看可以Dijkstra,实际上的确可以Dijkstra.不过多了一个预交费的c,所以在遍历的时候多了一维状态,这个维度储存当前走过的城市集合.在Dijkstra的时候,如果走过了c那么就有两个选择,选其中最省的即可:否则没得选.#include <iostream> #include&nb.

字符串HASH模板 取自挑战程序设计竞赛(第2版)

/*===================================================* 从b串中寻找和a串长度相同的子串,返回开始位置 不保证绝对正确,发生冲突概率为O(sqrt(n)), n为哈希函数的最大值 \*===================================================*/ #define ull unsigned long long const ull B = 1e8+7; /*according to the book*/

[转] AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

来自 码农场 ? AOJ 0525 Osenbei<挑战程序设计竞赛(第2版)>练习题答案 只把代码复制过来,原博的其他分析请看链接. 1 #include <iostream> 2 #include <bitset> 3 #include <algorithm> 4 5 using namespace std; 6 7 bitset<10000> cookie[10]; 8 9 ///////////////////////////SubMai

POJ 2836 Rectangular Covering 题解 《挑战程序设计竞赛》

POJ 2836 Rectangular Covering铺地板:坐标平面上有n各点,用任意大小(非零)的地板砖覆盖它们,求最省的地板砖总面积.3.4熟练掌握动态规划状态压缩DP先预处理数据,将n个点两两组合形成n * (n-1) / 2个矩形,计算每个矩形的面积和内部点个数.接着利用预处理数据来枚举,定义dp[S] := 矩形集为S时的最省面积先假设平面上没有矩形,那么dp[0]=0,接着一个一个地往平面上加矩形,递推关系是:dp[新矩形集合] = min(dp[新矩形集合], dp[旧矩形集

poj2431 Expedition (优先队列) 挑战程序设计竞赛

题目链接:http://poj.org/problem?id=2431 Expedition Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9148   Accepted: 2673 Description A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor driver