A 经典校招题
题目描述：
从第0个台阶跳到第n个台阶，每次可以选择跳跃1步或者2步，求最少的操作次数。
本题思路：
- 每次尽可能跳2步，如果最后只剩下一步就跳跃一步。
- 那么答案就是n / 2向上取整 => (n + 1) / 2;
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
void solve() {
int n;
cin >> n;
cout << (n + 1) / 2;
return ;
}
signed main() {
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
B 小苯购物
题目描述： 给我们3个物品，每个物品存在两个参数a，b。表示只有商品价格大于a元的时候我们才可以优惠b元。每种商品我们可以选或者不选。给出一开始商品的价格x，问最终x的最小值为多少？
本题思路：
- b都是大于0的，如果可以选择优惠我们选就比不选好。
- 但是这样就会存在一些问题，选择优惠之后可能商品的价格会变低，影响后面商品优惠的选择，说明这个又和商品的选择顺序有关。
- 本题只存在3个商品，我们枚举出所有选择的全排列进行依次比较即可，这样以来我们就可以考虑到所有的选择情况了。
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
void solve() {
int n;
cin >> n;
int a[3][2];
for (int i = 0; i < 3; i++) {
cin >> a[i][0] >> a[i][1];
}
vector<int>cnt;
for (int i = 0; i < 3; i++) {
cnt.push_back(i);
}
int res = n;
do {
int t = n;
for (int i = 0; i < 3; i++) {
if (t >= a[cnt[i]][0]) {
t -= a[cnt[i]][1];
}
}
res = min(res,max(0LL,t));
}while (next_permutation(cnt.begin(),cnt.end()));
cout << res << endl;
return ;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
C 小苯的与三角形
题目描述： 给出我们一个数x，要我们找到一个最小的y(1 <= y < x), 使得x，y，x&y这三个值可以可以构成一个三角形。
本题思路：
- 根据&运算符的性质，x & y的值一定不大于min(x,y)，说明x&y是他们当中最小的一个。并且y比x小，所以问题就变为了是否可以满足：
x&y + y > x这个式子。 - 对于x&y + y这个式子，我们可以将他们看出二进制操作。对于x最高位的二进制，如果y这一位二进制位0，那么x&y和y在这一位二进制中都不会做出贡献。这样以来后面的元素也就不可能可以实现了。
- 对于x二进制最高位如果是1，那么x&y + y在这一位二进制当中就会进位，答案也一定大于x.说明此时y的最小值就是x的二进制中最高位为1就可以了。
- 那么答案也就出来了，如果x就是2的幂，并且y是要小于x的，此时就不存在方案，否则就是y就是x的最高位二进制数。
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
void solve() {
int x;
cin >> x;
if ((x & -x) == x) {
cout << -1 << endl;
}else {
for (int i = 30; i >= 0; i--) {
if (x & (1 << i)) {
cout << (1 << i) << endl;
return ;
}
}
}
return ;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
D 小苯的序列染色
题目描述： 一开始我们存在一个长度为n并且全部为0的字符串t，现在可以执行任意次操作，每次操作可以选择t中一个长度为3的子串，将他们赋值为110，如果有重叠就进行覆盖。输入一个字符串s，问最终t是否可以变为s。
本题思路：
- 又是这种贪心构造题目，那么我们必须去观察每次选择110会带来哪些性质。
- 首先末尾如果是1那么就一定不可以构成答案。
- 其次我们就将t变为00··11111···0这种序列。那么对于中间的1来说，我们是可以将任意一位位置的1变为0的（就除了中间第二个位置的1）。对于前面的前导零我们是可以直接舍去的。
- 那么这个问题答案就出来了。将s去除前导零之后，如果第二个位置元素为0.那么就一定是不可以构成的，其他情况都可以按照我上面分析的操作去一步一步实现。
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
void solve() {
int n;
cin >> n;
string s;
cin >> s;
if (s.back() != '0') {
cout << "NO" << endl;
return ;
}
int j = 0;
while (j < n && s[j] == '0') j++;
s = s.substr(j);
if (s.size() >= 2 && s[1] == '0') {
cout << "NO" << endl;
return ;
}
cout << "YES" << endl;
return ;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
E 小苯的数字操作
题目描述：
给我们一个元素n，k。每次我们可以对n进行两次操作，n / 2和n * 2. 最多可以进行k次。问最终一共会产生多少种元素。
本题思路：
- 对于一个元素2和/2我们可以联想到二进制当中的左移或者右移操作。对于2，其实就是再末尾插入一个元素0。/2操作就是删除末尾的一个元素。
- 对于一个二进制串来说，如果左右到右数的个数比/的个数多那么就一定不会产生多余的变化，就有点类似合法括号匹配这种。例如：对n进行**/，其实就是操作一次。所以我们这里就可以先将*运算都计算一边（*进行k次操作），接下来我们就只需要考虑/会带来的影响了。
- 如果先进行一次/操作，如果当前二进制末尾为0，后面进行任意多次*都是不会带来影响了，此时答案就多了一个，就是当前元素。
- 如果当前二进制末尾为1，/之后每次进行操作都会产生一次答案，相当于就是多出了k种方案。注意一下，如果当前元素/操作后变为了0，此时方案也就不会存在了，需要特殊考虑一下。
- 当前二进制考虑完之后，删除当前末尾的答案，对下一个二进制位进行思考与求解。这样以来本题我们也就解决了了。
代码实现：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve() {
int n,k;
cin >> n >> k;
int res = k + 1, cnt = 0;
while (n && k) {
int t = n % 2;
if (t == 1) {
if (n == 1) res++;
else res += k;
}else {
res++;
}
n /= 2;
k--;
}
cout << res << endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
京公网安备 11010502036488号