牛客周赛 Round 94

emm...这次周赛挺难评，CD都是偏向于思维题

A

思路：

n / 2向上取整

代码：

import mathn = int(input())
print(math.ceil(n / 2))

B

思路：

使用优惠卷肯定比不使用更优惠，但是使用当前优惠卷后会影响后续优惠卷使用的结果进而影响到最终的结果
比如商品价格为100 第一张优惠卷a = 70 b = 50， 第二张优惠卷a = 60 b = 30
如果先使用第一张优惠卷，那么最终的价格为100 - 50 = 50（此时的价格已经不满足使用第二张优惠卷的条件）
如果先使用第二张优惠卷则最终的价格为100 - 30 - 50 = 20。
        所以若想求解本题需要考虑如上的情况，但是本题只有三张优惠卷可用，则仅有6种情况分别为123，132，213，231，312，321（全排列）那么遍历六种情况即可，对于每种情况求其结果并与每种结果取min即可。时间复杂度O(1)。全排列可以用next_permutation函数

代码：

#include<bits/stdc++.h>using namespace std;
typedef pair<int, int> pii;
#define x first
#define y secondint T, n;void solve()
{cin >> n;vector<int> p(3);vector<pii> a(3);for(int i = 0; i < 3; i ++){cin >> a[i].x >> a[i].y;p[i] = i;}int ans = 1e9;do {int aa = n;for(auto & i : p)//再遍历每种情况即可{if(aa >= a[i].x) aa -= a[i].y;}ans = min(ans, max(0, aa));}while(next_permutation(p.begin(), p.end()));//全排列：next_permutation(p.begin(), p.end())对应6种情况 012，021， 120，102，210，201cout << ans << endl;return;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> T;while(T -- )solve();return 0;
}

C

思路：

对于x&y, x, y我们不难发现若想满足非退化三角形则一定是y + x&y > x（因为y < x 而x&y < min(x, y）

对于二进制中x若为：1101001，那么如果y = 1000000则x&y = 1000000 = y。如果y = 0111111（二进制下1000000 - 1）则x&y = 101001则此时不符合非退化三角形；
那么我们就有二进制下y = 1000000可以，y - 1不可以，那么y的最小值即为二进制下x最高位后全补1（继续模拟即可发现此规律）

代码：

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--) {int y;int x; cin >> x;for(int i = 31; i >= 0; i --){if(x >> i & 1){y = 1 << i;break;}}if(y < 1 || y >= x) y = -1;cout << y << endl;}return 0;
}

D

思路：

可以模拟几个样例可以得到以下结果，以下结果为false：1、末尾不为0，2、一开始出现的两个1不连续

代码：

#include<bits/stdc++.h>using namespace std;int t;void solve()
{int n;string a;vector<int> v;cin >> n;cin >> a;for(int i = 0; i < n; i ++ )if(a[i] == '1')v.push_back(i);if(v.empty()){puts("YES");return;}if(n < 3)//长度小于3不可以{puts("NO");}else{if(v.size() == 1 || a.back() == '1') puts("NO");else if(v[1] == v[0] + 1) puts("YES");else puts("NO");}return;}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> t;while(t -- )solve();return 0;
}