《寒假每日一题》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;
}
推荐这些文章：
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 <...
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}...
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...
题目链接
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...
题目链接：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){
...
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...
题目：[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...
题目：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...
题目[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...
盒子模型
任何元素都有盒子模型
盒子模型由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:...
文章链接：https://www.dianjilingqu.com/4491.html
本文章来源于网络，版权归原作者所有，如果本站文章侵犯了您的权益，请联系我们删除，联系邮箱：saisai#email.cn，感谢支持理解。