《寒假每日一题》2022/1/2 AcWing 2058.笨拙的手指

原题链接:https://www.acwing.com/problem/content/2060/

Problem Description:

奶牛贝茜正在学习如何在不同进制之间转换数字。

但是她总是犯错误,因为她无法轻易的用两个前蹄握住笔。

每当贝茜将数字转换为一个新的进制并写下结果时,她总是将其中的某一位数字写错。

例如,如果她将数字 14 转换为二进制数,那么正确的结果应为 1110,但她可能会写下 0110 或 1111。

贝茜不会额外添加或删除数字,但是可能会由于写错数字的原因,写下包含前导 0 的数字。

给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果,请确定 N 的正确初始值(十进制表示)。

Input:

第一行包含 N 的二进制表示,其中一位是错误的。

第二行包含 N 的三进制表示,其中一位是错误的。

Output:

输出正确的 N 的值。

Sample Input:

1010
212

Sample Output:

14

解题思路:

  • 暴力枚举,将输入的二进制数和三进制数每一位进行改变,然后转为十进制,最后求交集,交集必只有一个数就是结果
  • 跟着y总的思路进行康复训练,企图删除脑子里的大物、概率论、计网

代码讲解:

  • for (auto element : mylist) 冒号的作用为,让容器 mylist 中的数据逐个读取到element中
  • unordered_set<int> S 哈希表
  • ^:异或运算(同为0异为1),二进制每一位上只有0和1 ASCII码分别为48和49,通过异或可以相互转化

AC代码:

#include<bits/stdc++.h>
#include<unordered_set> //哈希表
using namespace std;

int get(string s,int b) //将b进制的数s转为十进制数
{
        //秦九韶算法
	int res=0;
	for(char c:s)
	    res= res * b + c- '0';
	return res; 
}

int main( )
{
	string a,b;
	cin>>a>>b;
	
	unordered_set<int>S;
	
	for(char &c:a)  //引用,通过c的改变改变a的值
	{
		c^=1;
		S.insert(get(a,2));
		c^=1; 
	}
	
	for(char &c:b)
	{
		char t=c;
		for(int i=0;i<3;i++) //三进制数每一位有0、1、2三种可能要进行循环判断
		{
			if(i-'0'!=t) //若与原来该位上的数不同则进行求值、求交集
			{
				c=i-'0';
				int x=get(b,3);
				if(S.count(x))
				{
					cout<<x<<endl;
					return 0; 	
				}	
			}
			c=t;	
		}
	}
	
	return 0;
} 

推荐这些文章:

《寒假每日一题 2022》

1960. 闪烁
重点分析

状态压缩:将二进制转化为十进制
状态转移:在十进制状态下进行转移 int last = num & 1;
int temp = (num >> 1) + (last << n - 1);
num = num ^ temp;

计算答案(容易出错,算明白了再写,尤其注意T=1的情况)

Ac代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <...

AcWing cup 2022春季

A:水题。
链接:https://www.acwing.com/problem/content/4379/

1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <map>
5 using namespace std;
6 map<int,int> mp={
7 {0,1},
8 {1,0},
9 {2,0},
10 {3,0},
11 {4,1},
12 {5,0}...

2022寒假训练week2

Day 1 - Day5
AcWing 2014. 岛
首先要对每个点进行离散化,然后对于相邻的相同高度的点进行去重,然后按照高度排序,并枚举每一个点
对于每个点有三种情况

两侧都比中间高,淹没该点后小岛数+1
两侧都比中间低,淹没该点后小岛数-1
两侧一高一低,淹没该点后小岛数不变

虽然去重后相邻的点不会一般高,但是会出现不相邻的点被同时淹没的情况
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int h[N] , n;
pair<int,int> q[N];

int m...

AcWing 898. 数字三角形

题目链接

https://www.acwing.com/problem/content/900/

题目思路
这道题我们可以从最底层考虑,若要使当前路径之和最大,选择当前的所选值加左上/右上之和最大即可
因为有负数情况,所以要把边界设置好

题目代码
#include <iostream>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
int a[N][N], f[N][N];
int n;

int main()
{
cin...

2022-5-4 每日一题-leetcode

题目链接:https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
个人题解:

队列模拟(会比较慢)
数学递归,迭代节省空间(对比约瑟夫环)

点击查看代码
class Solution {
public:
int findTheWinner(int n, int k) {
queue<int> q;
for(int i=1;i<=n;i++) q.push(i);

while(q.size()>1){
...

《春季每日一题2022》

AcWing 3346. 你知道你的ABC吗
题目链接
https://www.acwing.com/problem/content/3349/
解析*
大小比较,推理。排序后首先得A和A+B+C,然后得B + C,剩余数中最小的为B,作差求得C.
Ac代码

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int a[N];
bool st...

2022春每日一题:Day 37

题目:[USACO14FEB]Auto-complete S
字典树套路题,字典树优化剪枝,加个cnt标记即可
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
const int M=1e6+5;
using namespace std;
int tot,m,n,q;
char s[1005];
namespace trietree
{
struct trie
{
in...

2022春每日一题:Day 41

题目:I Hate It
一个基础的线段树模板,单点修改+区间查询
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ls(x) x<<1
#define rs(x) x<<1|1
const int N=2e5+5;
using namespace std;
int n,m,a[N];
namespace segment
{
struct smt
{
int l,r,v;
smt...

2022春每日一题:Day 38

题目[USACO17JAN]Promotion Counting P
从根节点dfs一遍,树状数组维护进入和出去时这个节点的贡献,一减就是答案
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#define lowbit(x) x&-x
const int N=1e5+5;
using namespace std;
struct pos
{
int v,id;
pos...

<2022年4月14号>

盒子模型
任何元素都有盒子模型
盒子模型由4部分组成:content内容,
padding内边距,border边框,margin外边距
从内到外:content-padding-border-margin
Padding:10px ;上下左右10px
Padiding:5px 10px;上下5px 左右10px
Padding:5px 10px 4px;上5 左右10 下4
Padding:5px 10px 2px 1px
按顺时针上5 右10 下2 左1
外边距margin
margin:10px ;上下左右10px
margin:5px 10px;上下5px 左右10px
margin:...

文章标题:《寒假每日一题》2022/1/2 AcWing 2058.笨拙的手指
文章链接:https://www.dianjilingqu.com/4491.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>