关键词:
1. 题目来源
链接:1208. 翻硬币
相同题,不同场景:[递推] aw3777. 砖块(思维+递推+CF1271B)
2. 题目解析
经典递推题目,思路和 [递推] aw3777. 砖块(思维+递推+CF1271B) 一样,数据保证一定有解,无解情况需要判断操作最后尾元素和目标尾元素是否相同。
从头到 n-1
都是字符相同的,第 n
个字符如果不相同那也不能再操作了,也就是无解情况了。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
#include <bits/stdc++.h>
using namespace std;
void update(char &c)
if (c == '*') c = 'o';
else c = '*';
int main()
string a, b;
cin >> a >> b;
int res = 0;
for (int i = 0; i + 1 < a.size(); i ++ )
if (a[i] == b[i]) continue;
else res ++ , update(a[i]), update(a[i + 1]);
cout << res << endl;
return 0;
第四届蓝桥杯第八题翻硬币(代码片段)
题解:简单贪心,比赛之前写写水题#include<iostream>#include<cstring>#include<string>usingnamespacestd;constintmaxn=1000+20;voidsolve()intinit[maxn],over[maxn];stringin,ov;intans=0;cin>>in;cin& 查看详情
蓝桥杯矩阵翻硬币
思路:参考了http://blog.csdn.net/snailset/article/details/26752435,思路很清晰。用java实现了高效的牛顿迭代法。我tm都要爱上java了。实现:1importjava.math.*;2importjava.util.*;34publicclassMain{56publicstaticBigIntegersqrt(BigIntegerx){7i 查看详情
蓝桥杯--矩阵翻硬币
...et/article/details/26752435 题目: 小明先把硬币摆成了一个n行m列的矩阵。 随后,小明对每一个硬币分别进行一次Q操作。 对第x行第y列的硬币进行Q操作的定义:将所有第i*x行,第j*y列的硬币进行翻转。 ... 查看详情
蓝桥杯[翻硬币]贪心
...id=T29题目大意:给两个串,初始串和目标串,每一位表示硬币的正反状态。一次操作的定义是让两个相邻的硬币反面。问从初始状态到目标状态所需要的最少操作次数是多少。关键思想:贪心。要知道如果两个串的某一位不同,... 查看详情
蓝桥杯备赛--教你用矩阵优化递推
先导知识矩阵乘法[abcd]∗[efgh]=[ae+bgaf+bhce+dgcf+dh]\\beginbmatrixa&b\\\\c&d\\endbmatrix*\\beginbmatrixe&f\\\\g&h\\endbmatrix=\\beginbmatrixae+bg&af+bh\\\\c 查看详情
蓝桥杯历届试题prev-34矩阵翻硬币
历届试题矩阵翻硬币 时间限制:1.0s 内存限制:256.0MB问题描述 小明先把硬币摆成了一个n行m列的矩阵。 随后,小明对每一个硬币分别进行一次Q操作。 对第x行第y列的硬币进行Q操作的定义:将所有第i*x行,第j... 查看详情
[递推]aw3777.砖块(思维+递推+cf1271b)(代码片段)
....题目解析1.题目来源链接:3777.砖块2.题目解析经典的递推问题,也有类似问题,翻硬币问题。这种开关问题也可以拓展到二维平面上,枚举第一行的所有状态,递推即可,时间复杂度是O(2n)O(2^n)O(2n)。当数... 查看详情
蓝桥杯练习系统题解
BEGIN-4(Fibonacci数列)有递推公式,大家都知道用递推公式求,仅仅要记得在递推的时候同一时候取模求好这里给一份另类代码,用矩阵高速幂求,事实上还有循环节/*(11)*(Fn-1)=(Fn)//矩阵相乘,将就着看吧(10)(Fn-2)(Fn-1)(11)*(11)*(Fn-2)=(Fn)... 查看详情
acwing蓝桥杯c++ab组辅导课第一讲递归与递推(代码片段)
蓝桥杯C++AB组辅导课例题92.递归实现指数型枚举AC代码:#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=16;intst[N];intn;voiddfs(int 查看详情
acwing蓝桥杯c++ab组辅导课第一讲递归与递推(代码片段)
蓝桥杯C++AB组辅导课例题92.递归实现指数型枚举AC代码:#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=16;intst[N];intn;voiddfs(int 查看详情
蓝桥杯dfs正确入门方式|dfs+递归与递推习题课(上)|一节课教你爆搜!——学习笔记(代码片段)
...1;1001.2014.3001.5501【蓝桥杯】DFS正确入门方式|DFS+递归与递推习题课(下)|一节课教你爆搜!——学习笔记_小卢先冲的博客-CSDN博客第一题:入门迷宫问题、第二题:[USACO10OCT]LakeCountingS洪水灌溉问题、第三题:棋盘问题、第... 查看详情
蓝桥杯备赛--教你用矩阵优化递推
先导知识矩阵乘法[abcd]∗[efgh]=[ae+bgaf+bhce+dgcf+dh]\\beginbmatrixa&b\\\\c&d\\endbmatrix*\\beginbmatrixe&f\\\\g&h\\endbmatrix=\\beginbmatrixae+bg&af+bh\\\\ce+dg&cf+dh\\endbmatrix[acbd]∗[egfh]=[ae+bgce+... 查看详情
蓝桥杯历届试题-翻硬币:看似bfs,实则找规律贪心(代码片段)
文章目录题目题目解析题解题解一:优化的双向bfs(可惜还是过不了,当作bfs复习了)题解二:真正的此题题解(能0ms过所有题目oj平台题目解析很快能有bfs思路,但是提交后会发现,无论怎么优化bfs都只能过一个,... 查看详情
蓝桥杯十四届单片机省赛
...有凌云志,平凡一生也英雄!【失败的博主】<蓝桥杯最后一文>感想:练完省赛题就去练国赛题!!!十五届蓝桥杯选手参赛准备:1.B站小蜜蜂老师(基础模块)(容易听懂)2.做一... 查看详情
蓝桥杯准备
packagelanQiao;importjava.util.Scanner;/***@author国真*Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1,*当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少*/publicclassdemo1{publicstaticvoidmain(String[]args){Scannerscanner 查看详情
bzoj1042硬币购物——递推+容斥(代码片段)
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1042递推,再用容斥原理减掉多余的,加上多减的……(dfs)即可。代码如下:#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongll;llc[5 查看详情
蓝桥杯备赛刷题(代码片段)
第十三届蓝桥杯第二场模拟赛题解马上到蓝桥杯了,虽然省赛简单化,但是刷题是不可或缺的,下面我会更新蓝桥杯刷题题解,一起冲进国赛文章目录第十三届蓝桥杯第二场模拟赛题解前言填空题第一题第二题第三题第四题第五题第... 查看详情
[bzoj1042][haoi2008][硬币购物](容斥原理+递推)
Description 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。Input 第一行c1,c2,c3,c4,tot下面tot行d1,d2,d3,d4,s,其中di,s<=100000,tot&l... 查看详情