首页 > 其他分享 >Acwing 4440 照相

Acwing 4440 照相

时间:2023-06-14 13:22:10浏览次数:54  
标签:偶数 01 int 反转 照相 4440 变为 include Acwing

Acwing 4440 照相

原题指路

因为序列长为偶数,考虑将牛进行两两分组


为什么要将其进行两两分组:因为题目按偶数前缀进行反转,每一组中的牛总是相邻的,不会被拆散。

两两分组后会有四种情况: GG HH GH HG

我们再观察可得:每次反转,就是将每组内的两头牛进行互换

如:

GG HH 反转并无影响

我们不妨将GH 定义为0(H在偶数位) HG 定义为1(G在偶数位) ,另外两种情况无影响直接舍去。

则对上述字符串可转化为一个01串:110 ,其反转规则如下:

题目要求求当G在偶数为的最大值时,需要反转的最小次数。因为要求G在偶数的最大值,即求变换多少次可将01串变为尽可能多的1的变换次数的最小。

我们不难发现任意一个01串都可以变为全0或全1,现给予如下举例证明:

任意一个01串按上述方法变换都能变为全为1的串

我们就找到了G在偶数的最大值的可行解,现继续寻找最优解.

贪心找最优解

若对任意01串.....01... 在1的后面进行反转我们无法将01全变为11,只能将串变为..10...... ,所以由此,我们可以得到启发,在每个0和1中间做一次反转

可以得到最小值(从前往后做这样的反转)

边界判断:当01串最后一位为0时,我们需要额外添加一步让其变为1。

具体代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=2e5+10;

int n,m;
char s[N];
int w[N];

int main(void)
{
    int res=0;
    cin>>n>>s;
    for(int i=0;i<n;i+=2)
        if(s[i]!=s[i+1])
            w[m++]=s[i]=='H';
    
    if(!w[m-1]) res++;
    for(int i=0;i<m-1;i++)
        if(w[i]!=w[i+1])
            res++;
            
    cout<<res<<endl;
    
    return 0;
}

标签:偶数,01,int,反转,照相,4440,变为,include,Acwing
From: https://www.cnblogs.com/laniser/p/17479927.html

相关文章

  • AcWing——凑数(二进制中1的个数)
    1、题目初始时,n=0。每一轮操作都要依次完成两个步骤:第一步,任选一个非负整数a,将n增加a,这一步所需付出的代价为a。第二步,将n乘以2,这一步无需付出任何代价。你可以不断重复上述操作。给定一个整数x,你的任务是使n在某一步操作后(不一定是某一轮结束后)恰好等于x且付出的总代......
  • 【蓝桥杯集训·周赛】AcWing 第96场周赛
    第一题AcWing4876.完美数一、题目1、原题链接4876.完美数2、题目描述如果一个正整数能够被2520整除,则称该数为完美数。给定一个正整数n,请你计算[1,n]范围内有多少个完美数。输入格式一个整数n。输出格式一个整数,表示[1,n]范围内完美数的个数。数据范围前3个测试点满......
  • 【蓝桥杯集训·周赛】AcWing 第 95 场周赛
    第一题AcWing4873.简单计算一、题目1、原题链接4873.简单计算2、题目描述给定四个整数x1,y1,x2,y2,请你计算max(|x1−x2|,|y1−y2|)。输入格式第一行包含两个整数x1,y1。第二行包含两个整数x2,y2。输出格式一个整数,表示max(|x1−x2|,|y1−y2|)的值。数据范围前4个测试点......
  • AcWing——砝码称重
    4942.砝码称重-AcWing题库1、题目给定一个天平和101个砝码。101个砝码的重量依次为n⁰,n¹,n²,…,n¹⁰⁰克,其中n是一个不小于2的整数。请你判断,我们能否利用给定天平和砝码对重量为m克的物品进行称重。注意,天平的两端都可以放入砝码。具体来说,你的任务是判断是否可......
  • 【acwing】Trie字符串统计
    Trie树学习感受相比于之前学习的kmp匹配算法,Trie树的实现还是非常好理解的。(kmp算法太难了orz)从直观的模拟过程来看,trie树就像一颗树一样,从上(根节点)到下(叶节点)有序串联起来组成一个字符串。每一个额外标记结束的位置表示字符串的结束,通过计算标记数即可指导一共有多少该字符串......
  • 【每日一题】AcWing 1904. 奶牛慢跑
    题目奶牛们又出去锻炼蹄子去了!有N头奶牛在无限长的单行道上慢跑。每头奶牛在跑道上开始奔跑的位置互不相同,一些奶牛的奔跑速度可能相同,也可能不同。由于跑道是单行道,十分狭窄,奶牛们无法相互超越。当一头速度很快的牛追上另一头牛时,她必须减速至与另一头牛速度相同以免发生碰撞,并成......
  • 【蓝桥杯集训·每日一题】AcWing 3805. 环形数组
    写在前面本人CSDN博客主页:这里一、题目1、原题链接3805.环形数组2、题目描述给定一个长度为n的环形数组a0,a1,…,an−1。现在要对该数组进行m次操作。操作分为以下两种:增值操作lrd,将区间[l,r]上的每个元素都增加d。求最小值操作lr,输出区间[l,r]内的所有元素的最小......
  • 【蓝桥杯集训·每日一题】AcWing 1079. 叶子的颜色
    写在前面本人CSDN博客主页:这里一、题目1、原题链接1079.叶子的颜色2、题目描述给一棵有m个节点的无根树,你可以选择一个度数大于1的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都至少包含一个有色节点,哪......
  • 【蓝桥杯集训·每日一题】AcWing 4496. 吃水果
    写在前面本人CSDN博客主页:这里一、题目1、原题链接4496.吃水果2、题目描述n个小朋友站成一排,等着吃水果。一共有m种水果,每种水果的数量都足够多。现在,要给每个小朋友都发一个水果,要求:在所有小朋友都拿到水果后,恰好有k个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同(最左......
  • 前缀和 (Acwing_796 子矩阵的和)
    题目1.S[i,j]即为图1红框中所有数的的和为:S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]2.(x1,y1),(x2,y2)这一子矩阵中的所有数之和为:S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]#include<iostream>usingnamespacestd;constintN=1e3+10;int......