当前位置：首页 > web >正文

第一部分笔试Day_01到Day24_每天两道OJ

web 2025/7/16 4:05:07

Day_01

这题实在不懂

这题脑子抽了，以为死循环，随便选了个C，赋值后是什么就是什么啊，不是恒为真

这题，5左移五位是32，移到第六位了，减1还有五个1，看成移到第五位还有四个1，且异或相乘是逻辑与了，选了B，在学校上傻了。

牛客编程_组队竞赛

组队竞赛__牛客网

代码

（自己想的排序后输出中间1/3，想错了）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() 
{long long n = 0, sum = 0;cin >> n;int v[3 * n];for (int i = 0; i < 3 * n; i++) {cin >> v[i];}sort(v, v + 3 * n); // 排序后依次拿最左边和最右边两个组队int i = 3*n - 2;while(n--) {sum += v[i]; // 中间值是最右边两个的左边元素i -= 2;}cout << sum;return 0;
}
// 64 位输出请用 printf("%lld")

牛客编程_删除公共字符

删除公共字符__牛客网

法一代码（暴力）

#include <iostream>
#include <string>
using namespace std;
int main()
{string s1, s2, ret = "";getline(cin, s1);getline(cin, s2);for (auto& e : s1){if (s2.find(e) == s2.npos){ret += e;}}cout << ret;return 0;
}

法二代码（哈希）

#include <iostream>
#include <string>
using namespace std;
int main()
{string s1, s2, ret = "";getline(cin, s1);getline(cin, s2);int hash[256] = {0};for(auto& e : s2){hash[e]++;}for(auto& e : s1){if(hash[e] == 0){ret += e;}}cout << ret << endl;return 0;
}

Day_02

不太懂位置，选了D，%m.nf，m是对齐数，默认右对齐，加负号是右对齐，n是精度。

以为（1）是野指针错了，选了B，指针和引用区别：指针声明时可以不给值。

选对了但是理解有点错？

应该理解对了啊，点错了？点了D？？？？？？

不太理解位段和字节大小，选了B。

&a变成数组指针，+1偏移一个数组大小，指到4的右边，以为指到2选了B。

牛客编程_排序子序列

排序子序列_牛客笔试题_牛客网

自己的未通过代码：

（什么时候变成大佬了改一改）

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0;cin >> n;vector<int> v(n);for (int i = 0; i < n; ++i){cin >> v[i];}int cnt = 0, new_flag = 0, old_flag = 0; // cnt是极值if (v[1] - v[0] >= 0) // 1是递增，-1是递减，0是不变{new_flag = 1;old_flag = 1;}for (int i = 1; i < n; ++i){if (v[i] - v[i - 1] > 0)new_flag = 1;else if (v[i] - v[i - 1] < 0)new_flag = 0;if (new_flag != old_flag)cnt++;old_flag = new_flag;}cout << cnt + 1;return 0;
}

看了题解通过的代码：

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0, cnt = 0;cin >> n;vector<int> v(n + 1, 0); // 防止数组越界for (int i = 0; i < n; ++i){cin >> v[i];}for (int i = 0; i < n; ++i){if (v[i+1] > v[i]) // 非递减{while(i < n && v[i + 1] >= v[i]){++i; // i走到非递减尽头}++cnt;}else if (v[i + 1] < v[i]) // 非递增{while(i < n && v[i + 1] <= v[i]){++i; // i走到非递增尽头}cnt++;}}cout << cnt;return 0;
}

牛客OR62 倒置字符串

倒置字符串_牛客题霸_牛客网

倒置字符串__牛客网

自己写的通过的代码。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{string str;getline(cin, str, '\n');vector<string> v;string tmp;for (size_t i = 0; i < str.size(); ++i){if (str[i] != ' '){tmp += str[i];}else if (str[i] == ' '){v.push_back(tmp);tmp = "";}}v.push_back(tmp);int left = 0, right = v.size() - 1;while (left < right){string tmp2 = v[left];v[left] = v[right];v[right] = tmp2;++left;--right;}for (auto& e : v){cout << e << " ";}return 0;
}

看了题解敲的代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{string str;getline(cin, str, '\n');auto begin = str.begin(), end = str.end();reverse(begin, end);auto left = begin;auto right = begin;while(right < end){while(right < end && *right != ' '){++right;}reverse(left, right);if(right != end){left = right + 1;}++right;}cout << str;return 0;
}

Day_03

%S打印到\0才停止！！！！！！！

以为全对，for语句初始化只执行一次！！！！！！！！！！！！！！！！！！

不懂，选了A。

long是8字节，%d打印四字节，只有前两个%d有作用。

牛客OR59 字符串中找出连续最长的数字串

字符串中找出连续最长的数字串_牛客题霸_牛客网

解析代码

#include <iostream>
#include <cctype>
using namespace std;
int main()
{string str, tmp = "", ret = "";cin >> str;for (int i = 0; i <= str.size(); ++i){if (isdigit(str[i])){tmp += str[i];}else{if (tmp.size() > ret.size()){ret = tmp;}tmp = "";}}cout << ret;return 0;
}

牛客JZ39 数组中出现次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网

解析代码

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {int cnt = 0 , ret = 0;for(int i = 0; i < numbers.size(); ++i){if(cnt == 0){ret = numbers[i];cnt++;}else {ret == numbers[i] ? ++cnt : --cnt;}}return ret;}
};

Day_04

不知道有进制这回事。。。。。。

脑子抽了选了B？？？？？？？？？

观察选了D，太麻烦看了答案都不想算。

思路知道的，应该算到2就没把自己算上？选了A

牛客WY33 计算糖果

计算糖果_牛客题霸_牛客网

#include <iostream>
using namespace std;
bool isTrue(int a)
{if (a <= 30 && a >= -30){return true;}return false;
}
int main()
{int x1, x2, x3, x4;cin >> x1 >> x2 >> x3 >> x4;int a = (x1 + x3) / 2;int b = (x2 + x4) / 2;int c = x4 - b;if (isTrue(a) && isTrue(b) && isTrue(c) &&a - b == x1 && b - c == x2 && a + b == x3 && b + c == x4){cout << a << " " << b << " " << c;}else{cout << "No";}return 0;
}

牛客DD5 进制转换

进制转换_牛客题霸_牛客网

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;int main()
{int m = 0, n = 0;cin >> m >> n;if (m == 0){cout << 0;return 0;}string ret = "", str = "0123456789ABCDEF";bool flag = false;if (m < 0){m = -m;flag = true;}while (m > 0){ret += str[m % n];m /= n;}if (flag)ret += '-';reverse(ret.begin(), ret.end());cout << ret;return 0;
}

Day_05

应该是懂的吧，选错了还是粗心选了A？第一次对九个。

牛客WY18 统计回文

统计回文_牛客题霸_牛客网

#include <iostream>
#include <string>
using namespace std;
bool isCircal(const string& str)
{int left = 0, right = str.size() - 1;while (left < right){if (str[left++] != str[right--]){return false;}}return true;;
}
int main()
{string s1, s2;getline(cin, s1);getline(cin, s2);int cnt = 0;for (int i = 0; i <= s1.size(); ++i){string tmp = s1;if (isCircal(tmp.insert(i, s2))){++cnt;}}cout << cnt;return 0;
}

牛客DD1 连续最大和

连续最大和_牛客题霸_牛客网

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0;cin >> n;vector<int> arr(n);for (int i = 0; i < n; ++i){cin >> arr[i];}int ret = arr[0];for (int i = 1; i < arr.size(); i++) {arr[i] += max(arr[i - 1], 0);ret = max(ret, arr[i]);}/*int ret = -INT_MAX, sum = 0;for (int i = 0; i < n; ++i){for (int j = i; j < n; ++j){sum += arr[j];ret = max(ret, sum);}sum = 0;}*/cout << ret;return 0;
}

Day_06

脑子抽了？以为是6 / 17 = 2 emmmmm，

牛客WY16 不要二

不要二_牛客题霸_牛客网

用贪心的思想来做，开始将棋盘map全置为1，1代表放入蛋糕。

从左向右从上到下遍历棋盘开始依此放蛋糕，然后将该块蛋糕上下左右欧几里得距离为2的点全部标记为0，意思为该点不能再放入蛋糕，如果下一步扫到的0，则跳过该点，如果扫到1，则计数器cnt++，继续把周围距离为2的点标记为0。扫完棋盘就AC了。

#include <iostream>
#include <vector>
using namespace std;
int main() 
{int w = 0, h = 0, cnt = 0;cin >> w >> h;//cin >> h >> w;vector<vector<int>> arr(w, vector<int>(h, 1));for (int i = 0; i < w; ++i) {for (int j = 0; j < h; ++j) {if (arr[i][j] == 1) {if (i + 2 < w)arr[i + 2][j] = 0;if (j + 2 < h)arr[i][j + 2] = 0;cnt++;}}}cout << cnt;return 0;
}

字符串转整数

把字符串转换成整数__牛客网

class Solution {public:int StrToInt(string str) {long long ret = 0;int n = str.size();int flag = 1, i = 0;if (str[0] == '+')str[0] = '0';if (str[0] == '-') {flag = -1;i = 1;}for (; i < n; ++i) {if (str[i] < '0' || str[i] > '9') {return 0;}ret *= 10;ret += str[i] - '0';}return flag * ret;}
};

Day_07

不应该全错吗？？？？？？？

选了a，a私有能在类内初始化。。。。。。。

牛客WY22 Fibonacci数列

Fibonacci数列_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main() 
{int f1 = 0, f2 = 1, f3 = 1, n = 0;cin >> n;while (true) {f3 = f1 + f2;if (n >= f2 && n <= f3)break;f1 = f2;f2 = f3;}cout << min(f3 - n, n - f2);return 0;
}

牛客_合法括号序列判断

合法括号序列判断__牛客网

class Parenthesis {public:bool chkParenthesis(string A, int n){if (n & 1) // 如果n是奇数return false;stack<char> st;for (int i = 0; i < n; ++i) {if (A[i] == '(') {st.push('(');} else if (A[i] == ')' && !st.empty()) {if (st.top() == '(')st.pop();elsereturn false;} elsereturn false;}return true;}
};

Day_08

选了B。。。。。。。。。？？？？？？？

选了3,。。。。。怎么选的这么少。。

选了A。。。。友元函数重载运算符。。。。。

牛客WY20 两种排序方法

两种排序方法_牛客题霸_牛客网

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0;cin >> n;vector<string> v(n);for (int i = 0; i < n; ++i) {cin >> v[i];}bool flag_lex = true, flag_len = true;for (int i = 0; i < n - 1; ++i) {if (v[i] > v[i + 1])flag_lex = false;if (v[i].size() > v[i + 1].size())flag_len = false;}if (flag_lex && flag_len)cout << "both";else if (flag_lex)cout << "lexicographically";else if (flag_len)cout << "lengths";elsecout << "none";return 0;
}

牛客_求最小公倍数

求最小公倍数__牛客网

#include <iostream>
using namespace std;
int main()
{long long a = 0, b = 0, c = 0;cin >> a >> b;if(a < b)swap(a,b);long long x = a * b;while (c = a % b){a = b;b = c;}cout << x / b;return 0;
}

Day_09

选了D.........

纠结地选了A，const 静态数据成员可以在类内初始化。。。

选了D。。。只能在栈上创建的才没很好的办法做到。

力扣+牛客另类加法

面试题 17.01. 不用加号的加法

class Solution {
public:int add(int a, int b) {while(b != 0){int c = ((b & a) << 1); // 进位a ^= b; // 无进位相加b = c; }return a;}
};

另类加法__牛客网

class UnusualAdd {public:int addAB(int A, int B) {while (B != 0) {int C = ((B & A) << 1); // 进位A ^= B; // 无进位相加B = C; // 直到进位不为0就跳出循环}return A;}
};

牛客HJ91 走方格的方案数

走方格的方案数_牛客题霸_牛客网

#include <iostream>
#include <vector>
using namespace std;
int pash(int n, int m)
{if (n == 1 || m == 1)return 1;elsereturn pash(n - 1, m) + pash(n, m - 1);
}
int main() 
{int n = 0, m = 0;cin >> n >> m;n += 1;m += 1;vector<vector<int>> arr(n, vector<int>(m, 1));for (int i = 1; i < n; ++i){for (int j = 1; j < m; ++j){arr[i][j] = arr[i - 1][j] + arr[i][j - 1];}}cout << arr[n - 1][m - 1];// cout << pash(n + 1, m + 1); // 法二...这题目描述 +1？return 0;
}

Day_10

以为报错，选了A，强转了所以没报错。。。。。。

牛客_井字棋

井字棋__牛客网

class Board {public:bool checkWon(vector<vector<int> > board) {// 当前玩家是否胜出！！！不是有玩家胜出int row = board.size(), col = board[0].size();for (int i = 0, cnt = 0; i < row; ++i) { // 每行for (int j = 0; j < col; ++j)cnt += board[i][j];// if (cnt == col || cnt == -col)// 当前玩家是否胜出！！！不是有玩家胜出if (cnt == col)return true;}for (int i = 0, cnt = 0; i < col; ++i) { // 每列for (int j = 0; j < row; ++j)cnt += board[i][j];// if (cnt == row || cnt == -row)// 当前玩家是否胜出！！！不是有玩家胜出if (cnt == row)return true;}int cnt = 0;for (int i = 0; i < row; ++i) {cnt += board[i][i];}// if (cnt == row || cnt == -row)// 当前玩家是否胜出！！！不是有玩家胜出if (cnt == row)return true;cnt = 0;for (int i = 0; i < row; ++i) {cnt += board[i][row - 1 - i];}// if (cnt == row || cnt == -row)// 当前玩家是否胜出！！！不是有玩家胜出if (cnt == row)return true;return false;}
};

牛客HJ87 密码强度等级

密码强度等级_牛客题霸_牛客网

题目描述

密码按如下规则进行计分，并根据不同的得分为密码进行安全等级划分。

一、密码长度:
5 分: 小于等于4 个字符
10 分: 5 到7 字符
25 分: 大于等于8 个字符

二、字母:
0 分: 没有字母
10 分: 密码里的字母全都是小（大）写字母
20 分: 密码里的字母符合”大小写混合“

三、数字:
0 分: 没有数字
10 分: 1 个数字
20 分: 大于1 个数字

四、符号:
0 分: 没有符号
10 分: 1 个符号
25 分: 大于1 个符号

五、奖励（只能选符合最多的那一种奖励）:
2 分: 字母和数字
3 分: 字母、数字和符号

5 分: 大小写字母、数字和符号

最后的评分标准:
>= 90: 非常安全
>= 80: 安全（Secure）
>= 70: 非常强
>= 60: 强（Strong）
>= 50: 一般（Average）
>= 25: 弱（Weak）
>= 0: 非常弱（Very_Weak）

对应输出为：

VERY_SECURE
SECURE
VERY_STRONG
STRONG
AVERAGE
WEAK
VERY_WEAK

请根据输入的密码字符串，进行安全评定。

注：
字母：a-z, A-Z
数字：0-9
符号包含如下： (ASCII码表可以在UltraEdit的菜单view->ASCII Table查看)
!"#$%&'()*+,-./ (ASCII码：0x21~0x2F)
:;<=>?@ (ASCII码：0x3A~0x40)
[\]^_` (ASCII码：0x5B~0x60)
{|}~ (ASCII码：0x7B~0x7E)

提示:
1 <= 字符串的长度<= 300

输入描述：

输入一个string的密码

输出描述：

输出密码等级

#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int level(string str)
{int ret = 0;int n = str.size(); // 长度if (n <= 4)ret += 5;else if (n >= 5 && n <= 7)ret += 10;elseret += 25;//cout << "长度" << n << "分数" << ret << endl;int low = 0, gre = 0, cnt0 = 0; // 0字母for (auto& e : str) {if (islower(e))++low;else if (isupper(e))++gre;cnt0 = low + gre;}if (low && gre == 0)ret += 10;else if (gre && low == 0)ret += 10;else if (gre && low)ret += 20;int cnt1 = 0; // 1数字for (auto& e : str) {if (isdigit(e))++cnt1;}if (cnt1 == 1)ret += 10;else if (cnt1 > 1)ret += 20;int cnt2 = 0; // 2符号for (auto& e : str){if (e >= 0x21 && e <= 0x2F|| e >= 0x3A && e <= 0x40|| e >= 0x5B && e <= 0x60|| e >= 0x7B && e <= 0x7E)++cnt2;}if (cnt2 == 1)ret += 10;else if (cnt2 > 1)ret += 25;if (low && gre && cnt1 && cnt2) // 加分ret += 5;else if (cnt0 && cnt1 && cnt2)ret += 3;else if (cnt0 && cnt1)ret += 2;return ret;
}int main()
{string str;cin >> str;int res = level(str);//cout << res;if (res >= 90)cout << "VERY_SECURE";else if (res >= 80)cout << "SECURE";else if (res >= 70)cout << "VERY_STRONG";else if (res >= 60)cout << "STRONG";else if (res >= 50)cout << "AVERAGE";else if (res >= 25)cout << "WEAK";elsecout << "VERY_WEAK";return 0;
}

Day_11

选了B，数组指针，且还没指向。

选了C，语法没问题，但不推荐

牛客CM24 最近公共祖先

最近公共祖先_牛客题霸_牛客网

class LCA {
public:int getLCA(int a, int b) {// 左孩 = 父 * 2 + 1，右孩 = 父 * 2 + 2；// 父 = （孩 - 1） / 2；// 1 2 3// int a_f = a , b_f = b;int a_f = a - 1, b_f = b - 1; // 让其对应平时的下标while (a_f != b_f){if (a_f > b_f) // 让大的找自己的父结点{a_f = (a_f - 1) / 2;}else{b_f = (b_f - 1) / 2;}}// return a_f;return a_f + 1;}
};

牛客HJ86 求最大连续bit数

求最大连续bit数_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{int n = 0, cnt = 0, ret = 0;cin >> n;for (int i = 0; i < 32; ++i){if (n & (1 << i)) // 如果是1就计数{++cnt;}else // 如果是0就更新结果，且重新计数{ret = max(ret, cnt);cnt = 0;}}cout << ret;return 0;
}

Day_12

选了A?，B可以通过类域

引用！！以为是拷贝构造，选了C

选了A！！！！！！！！脑子瓦特了

选了B，可以私有+只声明或者用delete，那天脑子真瓦特了

选了D。。。。。。。。。寄！！！！！！！

牛客CM26 二进制插入

二进制插入_牛客题霸_牛客网

class BinInsert {
public:int binInsert(int n, int m, int j, int i) {// 1 2 4 8 16 32 64 128 256 512 1014// 1024 + 2 + 4 + 32 =// 1024 + 4 + 8 + 64 = 1024 + 76// 10000000000// 10011// 10001001100return n |= (m << j); // 法1//for (int k = j; k <= i; ++k) // 法2//{//	if (m & 1)//	{//		n |= (1 << k);//	}//	m >>= 1;//}// return n;}
};

牛客HJ60 查找组成一个偶数最接近的两个素数

查找组成一个偶数最接近的两个素数_牛客题霸_牛客网

#include <cmath>
#include <iostream>
using namespace std;
bool isPrime(int n)
{for (int i = 2; i <= sqrt(n); ++i){if (n % i == 0){return false;}}return true;
}
int main()
{int n = 0;cin >> n;for (int i = n / 2; i < n; ++i){if (isPrime(i) && isPrime(n - i)){cout << n - i << endl << i;return 0;}}return 0;
}

Day_13

...最后两个函数调用是B调用的。

声明纯虚函数的类是抽象类。

只有4对，2是8

编译器有优化，注意有两次析构。

牛客HJ74 参数解析

参数解析_牛客题霸_牛客网

解析代码1

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{string str = "";getline(cin, str);vector<string> res;if (str.size() == 0 || str[0] == ' ')return 0;string tmp;for (int i = 0; i < str.size(); ++i){if(str[i] == '"'){while(str[++i] != '"'){tmp += str[i];}res.push_back(tmp);tmp = "";i++; // 跳过一个双引号后的空格}else if (str[i] != ' '){tmp += str[i];}else{res.push_back(tmp);tmp = "";}}if(!tmp.empty())res.push_back(tmp);cout << res.size() << endl;;for (auto& e : res){cout << e << endl;}return 0;
}

解析代码2

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{string str = "";getline(cin, str);vector<string> res;if (str.size() == 0 || str[0] == ' ')return 0;string tmp;bool flag = false;for (int i = 0; i < str.size(); ++i){if(str[i] == '"') // 如果是双引号，让标志换值{flag = !flag;}else if (str[i] != ' ' || flag) {tmp += str[i];}else{res.push_back(tmp);tmp = "";}}if(!tmp.empty())res.push_back(tmp);cout << res.size() << endl;;for (auto& e : res){cout << e << endl;}return 0;
}

牛客WY28 跳石板

跳石板_牛客题霸_牛客网

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;void get_div_num(int n, vector<int>& arr)
{for (int i = 2; i <= sqrt(n); ++i){if (n % i == 0) // i是约数{arr.push_back(i);if (n / i != i) // 另一个大的约数arr.push_back(n / i);}}
}
int Jump(int n, int m)
{vector<int> step(m + 1, INT_MAX);// 存放到达这个位置的最少步数，int_max表示不可达到step[n] = 0; // 当前位置初始化for (int i = n; i < m; ++i){if (step[i] == INT_MAX)continue;// 获取i的约数，并保存到arrvector<int> arr;get_div_num(i, arr);for (int j = 0; j < arr.size(); ++j){if (arr[j] + i <= m && step[arr[j] + i] != INT_MAX){	// 挑选一个最小值step[arr[j] + i] = min(step[arr[j] + i], step[i] + 1);}else if (arr[j] + i <= m && step[arr[j] + i] == INT_MAX){	// 更新不可到达的地方step[arr[j] + i] = step[i] + 1;}}}return step[m] == INT_MAX ? -1 : step[m];
}int main()
{int n = 0, m = 0, min_step = 0;while (cin >> n >> m){min_step = Jump(n, m);cout << min_step;}return 0;
}

Day_14

B：普通对象能调用const成员函数，const对象不能调用普通函数。

C：析构函数可以是虚函数，构造函数不可以是虚函数。

A：不严谨，是取地址符，不是引用操作符。

D：在类里弄一个函数返回new的对象，单例模式。。。。。。。

父类的I = 10 ，子类的func2 加等2 -> 12

静态。。

多态虚函数考得多，没复习。。。。。。。。。。

构造子类先调用父类构造函数。

牛客HJ73 计算日期到天数转换

计算日期到天数转换_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{int year = 0, month = 0, day = 0, sum = 0;cin >> year >> month >> day;static int arr[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};for (int i = 1; i < month; ++i){sum += arr[i];}// if (month > 2 && (year % 4 == 0 && year % 400 != 0))if (month > 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)){++sum;}cout << sum + day;return 0;
}

WY15 幸运的袋子

幸运的袋子_牛客题霸_牛客网

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int getLuckyBag(const vector<int>& v, int pos, int sum, int mul)
{int count = 0;for (int i = pos; i < v.size(); i++){sum += v[i];mul *= v[i];if (sum > mul) //只有数据有1的时候才可能sum>mulcount += 1 + getLuckyBag(v, i + 1, sum, mul);else if (v[i] == 1) // 如果不幸运，并且当前值为1(数据只有1才会这样)count += getLuckyBag(v, i + 1, sum, mul);elsebreak;sum -= v[i];mul /= v[i];while (i < v.size() - 1 && v[i] == v[i + 1]){	// 处理重复问题i++;}}return count;
}int main()
{int n = 0;cin >> n;vector<int> v;v.reserve(n);for (int i = 0;i < n;i++){int j = 0;cin >> j;v.push_back(j);}sort(v.begin(), v.end());cout << getLuckyBag(v, 0, 0, 1);
}

Day_15

构造子类，先调用父类构造函数。

A foo不是虚函数

牛客HJ62 查找输入整数二进制中1的个数

查找输入整数二进制中1的个数_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{int n = 0;while (cin >> n){int cnt = 0;while (n != 0){n &= (n - 1);++cnt;}cout << cnt << endl;}return 0;
}

牛客OR57 手套

手套_牛客题霸_牛客网

class Gloves {
public:int findMinimum(int n, vector<int> left, vector<int> right) {int ret = 0;int left_cnt = 0, right_cnt = 0;int left_min = INT_MAX, right_min = INT_MAX;for (int i = 0; i < n; ++i){if (left[i] == 0){ret += right[i];}else if (right[i] == 0){ret += left[i];}else{left_cnt += left[i];right_cnt += right[i];left_min = min(left[i], left_min);right_min = min(right[i], right_min);}}ret += min(left_cnt - left_min, right_cnt - right_min);return ret + 2; // 全部情况拿完，再左右各拿一个}
};

Day_16

C：多态？

B私有继承C。。。。。。

FuncA不是虚函数。

父类指针调用父。

牛客HJ56 完全数计算

完全数计算_牛客题霸_牛客网

#include <cmath>
#include <iostream>
using namespace std;
bool isPerfect(int n)
{int sum = 1; // 先把1加上for (int i = 2; i <= sqrt(n); ++i){if (n % i == 0){sum += i;if (n / i != i)sum += n / i;}}return sum == n;
}
int main()
{int n = 0, cnt = 0;cin >> n;for (int i = 2; i <= n; ++i){if (isPerfect(i))++cnt;}cout << cnt;return 0;
}

牛客OR44 扑克牌大小

扑克牌大小_牛客题霸_牛客网

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;string FindMax(const string& line)
{if (line.find("joker JOKER") != string::npos)return "joker JOKER";int dash = line.find('-');// 分开两手牌string car1 = line.substr(0, dash);string car2 = line.substr(dash + 1);// 获取两手牌的张数int car1_cnt = count(car1.begin(), car1.end(), ' ') + 1;int car2_cnt = count(car2.begin(), car2.end(), ' ') + 1;// 获取两手牌的各自第一张牌string car1_first = car1.substr(0, car1.find(' '));string car2_first = car2.substr(0, car2.find(' '));if (car1_cnt == car2_cnt) // 两手牌的类型相同{string str = "345678910JQKA2jokerJOKER";if (str.find(car1_first) > str.find(car2_first))return car1;return car2;}if (car1_cnt == 4) // 说明是炸弹return car1;else if (car2_cnt == 4)return car2;return "ERROR";
}int main()
{string line = "";getline(cin, line);cout << FindMax(line) << endl;return 0;
}

Day_17

内联函数不能成为虚函数。

继承主要用来实现多态，多态靠的是虚函数。

先析构子类，后析构父类

牛客_计算某字符出现次数

计算某字符出现次数_牛客题霸_牛客网

#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int main()
{string str;getline(cin, str);char c;cin >> c;if (islower(c)) // 全部小写字母转大写{c -= 32;}int cnt = 0;for (auto& e : str){if (islower(e))e -= 32;if (e == c)++cnt;}cout << cnt;return 0;
}

杨辉三角的变形

杨辉三角的变形_牛客题霸_牛客网

解法1（超出内存限制）

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0;cin >> n;vector<vector<int>> vv(n);for (int i = 0; i < n; ++i){vector<int> tmp(i + 1, 1);vv[i] = tmp;}for (int i = 2; i < n; ++i){for (int j = 1; j < i + 1; ++j) // 只需填到中间{if (j == 1) // 第二列vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];else if (j == i) // 最后中间列（最后一列）vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j - 2] * 2;elsevv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1] + vv[i - 1][j - 2];}}// for(int i = 0; i < n; ++i)// {// for(int j = 0; j < vv[i].size(); ++j)// {// cout << vv[i][j] << ' ';// }// cout << endl;// }int len = vv[n - 1].size();for (int i = n - 1, j = 1; j < len; ++j){if (vv[i][j] % 2 == 0){cout << j + 1;return 0;}}cout << -1;return 0;
}

解法2（找规律）

#include <iostream>
using namespace std;
int main()
{int n = 0;cin >> n;if (n <= 2)cout << -1;else if (n % 4 == 1 || n % 4 == 3)cout << 2;else if (n % 4 == 2)cout << 4;elsecout << 3;return 0;
}

Day_18

插入和删除都有可能导致迭代器失效

程序崩溃

牛客HJ37 统计每个月兔子的总数

统计每个月兔子的总数_牛客题霸_牛客网

#include <iostream>
#include <vector>using namespace std;
int main()
{int n = 0;cin >> n;vector<int> arr(n + 1, 0);arr[1] = 1, arr[2] = 1, arr[3] = 2; // 3 5int cnt = 1; // 下一月会生的for (int i = 4; i <= n; ++i){arr[i] = arr[i - 1] + cnt;cnt = arr[i - 1];}// for(auto& e : arr)// {// cout << e << ' ';// }// cout << endl;cout << arr[n];return 0;
}

HJ71 字符串通配符

描述

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。

要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。

输入：
通配符表达式；
一组字符串。

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

数据范围：字符串长度：1≤s≤100 1≤s≤100

进阶：时间复杂度：O(n2)，空间复杂度：O(n)

输入描述：

先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

输出描述：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

抄的代码（写题时直接在ture和false返回一个了）

#include <iostream>
#include <string>
using namespace std;bool match(const char* pattern, const char* str)
{if (*pattern == '\0' && *str == '\0')return true; // 当前字符结束，返回trueif (*pattern == '\0' || *str == '\0')return false; // 两个字符串有一个先结束，则返回falseif (*pattern == '?') // 新增用例，题目强调?只能够匹配数字和字母，所以增加新的判断{if (!isdigit(*str) && !isalpha(*str))return false;return match(pattern + 1, str + 1); // 遇到?号，匹配一个字符，跳过一个位置}else if (*pattern == '*'){while (*pattern == '*'){pattern++; // 遇到*号，(str不挪动)，1个（两者都向前挪动一个字符）或多个(str向前挪动一个字符)}pattern--;if (!isdigit(*str) && !isalpha(*str))return match(pattern + 1, str);return match(pattern + 1, str) || match(pattern + 1, str + 1) || match(pattern, str + 1);}else if (tolower(*pattern) == tolower(*str)) // 忽略大小写{return match(pattern + 1, str + 1); // 如果当前字符相等，匹配下一个字符}return false;
}int main()
{string pattern, str;while (cin >> pattern >> str){bool ret = match(pattern.c_str(), str.c_str());if (ret)cout << "true" << endl;elsecout << "false" << endl;}return 0;
}

Day_19

汽水瓶_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{int empty = 0;while (cin >> empty){if (empty == 0)break;int sum = 0;while (empty > 1){int res = empty / 3; //所能兑换的个数int left = empty % 3; //遗下的个数sum += res;empty = left + res;if (empty == 2){sum++;break;}}cout << sum << endl;}return 0;
}

#include <iostream>
using namespace std;
int main()
{int empty = 0;while (cin >> empty){if (empty > 2) // 取巧cout << empty / 2 << endl;}return 0;
}

HJ65 查找两个字符串a,b中的最长公共子串

查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网

#include <iostream>
#include <string>
#include <vector>
using namespace std;string getComSubstr(string& str1, string& str2) // 寻求最短字符串
{if (str1.size() > str2.size())swap(str1, str2);int len1 = str1.size();int len2 = str2.size();vector<vector<int>> MSC(len1 + 1, vector<int>(len2 + 1, 0));int start = 0, max_size = 0;for (int i = 1; i <= len1; ++i){for (int j = 1; j <= len2; ++j){if (str2[j - 1] == str1[i - 1])MSC[i][j] = MSC[i - 1][j - 1] + 1;if (MSC[i][j] > max_size){max_size = MSC[i][j];start = i - max_size;}}}return str1.substr(start, max_size);
}int main()
{string str1, str2;while (cin >> str1 >> str2){string substr = getComSubstr(str1, str2);cout << substr << endl;}return 0;
}

Day_20

以为中序遍历是有序的，乱选的。。。。。。。。。

看那两个是拍排好的，是关键字。

牛客HJ12 字符串反转

字符串反转_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{string str = "";cin >> str;int left = 0, right = str.size() - 1;while (left < right){char tmp = str[left];str[left] = str[right];str[right] = tmp;++left;--right;}cout << str;return 0;
}

HJ75 公共子串计算

公共子串计算_牛客题霸_牛客网

#include <iostream>
using namespace std;
int main()
{string str1 = "", str2 = "";cin >> str1 >> str2;int n1 = str1.size(), n2 = str2.size();int res = -1;for (int i = 0; i < n1; ++i){for (int j = 0; j < n2; ++j){int cnt = 0;int tmpi = i, tmpj = j;while (tmpi < n1 && tmpj < n2 && str1[tmpi++] == str2[tmpj++]){++cnt;}res = max(res, cnt);}}cout << res << endl;return 0;
}

Day_21

牛客WY24 洗牌

洗牌_牛客题霸_牛客网

#include <iostream>
#include <vector>
using namespace std;int main()
{int T = 0;cin >> T;while (T--){int n = 0, k = 0;cin >> n >> k;vector<int> arr(2 * n, 0);for (int i = 0; i < 2 * n; ++i){cin >> arr[i];}while (k--){vector<int> tmp1(arr.begin(), arr.begin() + n);vector<int> tmp2(arr.begin() + n, arr.end());for (int i = 0, j = 0; i < n; ++i){arr[j++] = tmp1[i];arr[j++] = tmp2[i];}}for (auto& e : arr){cout << e << " ";}cout << endl;}return 0;
}

MP3光标位置

MP3光标位置_牛客题霸_牛客网

#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0;string cmd;while (cin >> n >> cmd){// 将n首歌进行编号1：n,其中num代表当前光标所在的歌曲编号// first代表当前页的第一首歌曲的编号int num = 1, first = 1;if (n <= 4) // 歌曲总数 <= 4{for (int i = 0; i < cmd.size(); ++i) // 解析命令{if (num == 1 && cmd[i] == 'U')num = n;else if (num == n && cmd[i] == 'D')num = 1;else if (cmd[i] == 'U')num--;elsenum++;}for (int i = 1; i <= n; ++i){cout << i << " ";}cout << endl;cout << num << endl;}else // 歌曲总数 > 4{for (int i = 0; i < cmd.size(); ++i) // 解析命令{if (first == 1 && num == 1 && cmd[i] == 'U'){first = n - 3; // 将first跳入最后一页num = n;}else if (first == n - 3 && num == n && cmd[i] == 'D'){first = num = 1;}else if (first != 1 && num == first && cmd[i] == 'U'){first--;num--;}else if (first != n - 3 && num == first + 3 && cmd[i] == 'D'){first++;num++;}else if (cmd[i] == 'U'){num--;}else{num++;}}for (int i = first; i <= first + 3; ++i){cout << i << " ";}cout << endl;cout << num << endl;}}return 0;
}

Day_22

是判断p指针是不是尾结点。。。。。。。不是插入p。

选的B，没看懂吧

选了1.5，有点蒙

编程题少写了个等号，25分没了，还被认定抄袭，鼓掌鼓掌鼓掌鼓掌鼓掌

小易的升级之路_牛客题霸_牛客网

#include <iostream>
#include <vector>
using namespace std;int getVal(int a, int b)
{if (a > b)swap(a, b);for (int i = a; i >= 1; --i){if (a % i == 0 && b % i == 0)return i;}return -1;
}int main()
{int n = 0, c = 0;while (cin >> n >> c){vector<int> arr(n);for (int i = 0; i < n; ++i){cin >> arr[i];}for (int i = 0; i < n; ++i){if (arr[i] <= c)c += arr[i];elsec += getVal(c, arr[i]);}cout << c << endl;}return 0;
}

找出字符串中第一个只出现一次的字符_牛客题霸_牛客网

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {string str = "";getline(cin, str);unordered_map<char, int> hash; // 字符和出现的次数for (auto& e : str) {hash[e]++;}string strOne = "";for (auto& e : hash) {if (e.second == 1) {strOne += e.first;}}
// cout << strOne << endl;for (auto& e : str) {for (auto& One : strOne) {if (One == e) {cout << e << endl;return 0;}}}cout << -1 << endl;return 0;
}

Day_23

QQ2微信红包（排序或摩尔投票法）

微信红包_牛客题霸_牛客网

class Gift {
public:int getValue(vector<int> gifts, int n) {int cnt = 0, ret = 0;//for (int i = 0; i < n; ++i) // 摩尔投票法//{//	if (cnt == 0)//	{//		ret = gifts[i];//	}//	else//	{//		ret == gifts[i] ? ++cnt : --cnt;//	}//}//cnt = 0;sort(gifts.begin(), gifts.end());ret = gifts[n / 2];for (auto& e : gifts){if (e == ret)++cnt;}if (cnt > n / 2)return ret;return 0;}
};

HJ52计算字符串的编辑距离（dp）

计算字符串的编辑距离_牛客题霸_牛客网

原代码：（可以在前面添加，此代码思路就错了）

#include <iostream>
#include <string>
using namespace std;
int main()
{string str1 = "", str2 = "";getline(cin, str1);getline(cin, str2);if (str1.size() > str2.size())swap(str1, str2);int n1 = str1.size(), n2 = str2.size();// cout << n1 << " " << n2 << endl;if (str1.empty()){cout << n2;return 0;}int cnt = 0;for (int i = 0; i < n2; ++i){if (i > n1 - 1){cnt += n2 - n1;break;}else{if (str1[i] != str2[i])++cnt;}}cout << cnt;return 0;
}

正解dp代码：

#include <iostream>
#include <string>
#include <vector>
using namespace std;int main()
{string str1 = "", str2 = "";cin >> str1 >> str2;int n1 = str1.size(), n2 = str2.size();// if(n1 == 0 || n2 == 0)// {//     cout << max(n1, n2);//     return 0;// }vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));for(int i = 1; i <= n1; ++i){dp[i][0] = i;}for(int j = 1; j <= n2; ++j){dp[0][j] = j;}for(int i = 1; i <= n1; ++i){for(int j = 1; j <= n2; ++j){if(str1[i - 1] == str2[j - 1])dp[i][j] = dp[i - 1][j - 1];elsedp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));}}cout << dp[n1][n2] << endl;return 0;
}

Day_24

七层满的话就是2^7 - 1 = 127，减去9个叶节点的孩子就是127 - 2*9 = 109

JD1 年终奖（dp）

年终奖_牛客题霸_牛客网

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。

class Bonus {
public:
int getMost(vector<vector<int> > board) {int m = board.size(), n = board[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + board[i - 1][j - 1];}}return dp[m][n];}
};

HJ43 迷宫问题（dfs+回溯）

迷宫问题_牛客题霸_牛客网

#include <iostream>
#include <vector>
#include <queue>
using namespace std;vector<pair<int,int>> path, res;
bool vis[13][13];
int m, n;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};void dfs(vector<vector<int>>& vv, int sr, int sc)
{path.push_back({sr, sc});vis[sr][sc] = true;if(sr == m - 1 && sc == n - 1){res = path; // 一定要保存一下结果return;}queue<pair<int, int>> q;for(int j = 0; j < 4; ++j){int x = sr + dx[j], y = sc + dy[j];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && vv[x][y] == 0){dfs(vv, x, y);}}path.pop_back(); // 回溯vis[sr][sc] = false;
}int main()
{cin >> m >> n;vector<vector<int>> vv(m, vector<int>(n, 0));for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){cin >> vv[i][j];}}dfs(vv, 0, 0);for(auto [a, b] : res){cout << '(' << a << ',' << b << ')' << endl;}return 0;
}

查看全文

http://www.xdnf.cn/news/596.html