本次比赛难度：
easy：A，B
medium:D,E,F
medium hard:H
hard:C G
A: 光
本题为签到题，只需输出一行"宏观困难但局部有光!"即可，不再提供题解。
B:天杀的二进制
本题也算是签到题，就是将2的n次方进行相加，简单的循环遍历读取字符即可。
注意要处理换行符。在多组输入输出中，可以构造solve函数，一组测试用例一次调用，降低耦合度，提高函数可读性
#include<stdio.h>
void solve()
{
int sum = 0;
getchar();
for (int i = 0; i <= 31; i++)
{
char ch;
scanf("%c", &ch);
if (ch == '1')
{
sum+=(1 << i);
}
}
printf("%d\n", sum);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C:千年暗室，一灯即明！
方法一：贪心 + 优先队列
思路
我们按照原计划访问所有房间。当访问到第 i 个房间时，如果生命值小于等于 0，那么我们必须要对房间顺序进行调整：
显然选择第 i 个房间之后的房间是没有意义的，它并不会改变当前的生命值；
因此我们只能选择第 i 个房间及之前的房间。对于所有可选的房间，无论将哪个房间调整至末尾，都不会改变最终的生命值（因为数组 nums 的和不会变化）。由于我们希望调整的次数最少，因此应当贪心地选择最小的那个 nums[j] 调整至末尾，使得当前的生命值尽可能高。
算法：
在遍历房间的过程中，如果 nums[i] 为负数，我们将其放入一个小根堆（优先队列）中。当计算完第 i 个房间的生命值影响后，如果生命值小于等于 0，那么我们取出堆顶元素，表示将该房间调整至末尾，并将其补回生命值中。由于一定会从小根堆中取出一个小于等于 nums[i] 的值，因此调整完成后，生命值一定大于 0。
当所有房间遍历完成后，我们还需要将所有从堆中取出元素的和重新加入生命值，如果生命值小于等于 0，说明无解，则输出-1。
本题使用c++解题可以直接使用c++标准库中的stl方法，省去自行实现栈和优先级队列的方法，建议同学们下去可自行学习stl方法，可以省去大量的时间。
栈的本质是一个先进先出的结构，优先级队列是一个大根或者小根堆，插入元素后会自行调整插入位置，使得从优先级队列出来中的数值是最大或者最小的，vector容器就相当于c语言中的数组，但大小可伸缩即变长数组。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int magic(vector<int>& nums) {
priority_queue<int, vector<int>, greater<int>> q;
int ans = 0;
long long hp = 1, delay = 0;
for (int num : nums) {
if (num < 0) {
q.push(num);
}
hp += num;
if (hp <= 0) {
++ans;
delay += q.top();
hp -= q.top();
q.pop();
}
}
hp += delay;
return hp <= 0 ? -1 : ans;
}
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++)
cin >> nums[i];
int ans=magic(nums);
cout << ans << endl;
return 0;
}
D:Set
我们可以从小到大删除数字，因此，之前删除的数字并不会影响未来的选择(如果x<y,那么x不可能是y的倍数)，因此，当且仅当k*x<=r,即x<=[r/k]时，整数x(1<=x<=r)可以被整除，答案是max([r/j]-l+1,0);
cin对应c语言中的scanf，cout对应printf。max是c++标准库中的取最大值函数
#include <bits/stdc++.h>
using namespace std;
int T;
void solve() {
int l, r, k; cin >> l >> r >> k;
cout << max(r / k - l + 1, 0) << endl;
return;
}
int main() {
cin >> T;
while (T--) {
solve();
}
}
E:you love 1203!
本题就是一个暴力遍历，
我们将遍历地毯的所有层，并将每一层中遇到的1203记录数添加到答案中， 为此，我们可以遍历例如每层左上角的单元格，其形式为(i,i),i的范围是[1,min(n,m)/2];然后使用简单算法遍历该层，将遇到的数字写入某个数组，然后遍历数组，计算该层中出现的1203，此外，在遍历数组是，我们应该考虑该层的循环性质，记得检查包含起始单元的1203是否可能出现，以及数组越界的情况。
#include <stdio.h>
char a[1005][1005];
char layer[4005];
void solve() {
int n, m; scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%s", a[i]);
int count = 0;
for (int i = 0; (i + 1) * 2 <= n && (i + 1) * 2 <= m; ++i) {
int pos = 0;
for (int j = i; j < m - i; ++j) layer[pos++] = a[i][j];
for (int j = i + 1; j < n - i - 1; ++j) layer[pos++] = a[j][m - i - 1];
for (int j = m - i - 1; j >= i; --j) layer[pos++] = a[n - i - 1][j];
for (int j = n - i - 2; j >= i + 1; --j) layer[pos++] = a[j][i];
for (int j = 0; j < pos; ++j)
if (layer[j] == '1' && layer[(j + 1) % pos] == '2' && layer[(j + 2) % pos] == '0' && layer[(j + 3) % pos] == '3')
count++;
}
printf("%lld\n", count);
}
int main() {
int t; scanf("%d", &t);
while (t--) solve();
}
F:幂幂幂
本题运用了一点点贪心的策略，尽量使用较大的2的幂次方，但是当n%2==1时，表示必须使用当前这个2，因为如果%2==0，则表示可以别的2的幂次方所表示，%2==1，表示不能再被别的2的幂次方表示了。
的幂次方，比如5%2==1，就必须使用1，5/2=2，此时此时总和为1，2%2==0，所以当前这个2的1次方不选，2/2==1，1%2==1，所以要使用4，总共用了两个2的幂次方数。
#include<stdio.h>
void solve()
{
int n,count=0;
scanf("%d", &n);
while (n)
{
count += n % 2;
n /= 2;
}
printf("%d\n",count);
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
solve();
}
return 0;
}
G:山雨欲来
动态规划
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度
上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。
创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。
显然，leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：
当 1≤i≤n−1 时，leftMax[i]=max(leftMax[i−1],height[i])；
当 0≤i≤n−2 时，rightMax[i]=max(rightMax[i+1],height[i])。
因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。
在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。
本题与c语言版本不一样的仅有vector容器和max函数(取两个数的最大值)，与c语言中的数组起到的作用一样，所以不再提供c语言版本答案，知道vector相当与数组即可。
#include<iostream>
#include<vector>
using namespace std;
int trap(vector<int>& height) {
int n = height.size();
if (n == 0)
return 0;
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; ++i)
{
leftMax[i] = max(leftMax[i - 1], height[i]);
}
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i)
{
rightMax[i] = max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += min(leftMax[i], rightMax[i]) - height[i];
return ans;
}
int main()
{
int n;
cin >> n;
vector<int> height(n);
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
height[i] = a;
}
cout<<trap(height);
return 0;
}
H:Two movies影评
让我们注意一个重要的事实:如果ai!=bi，为评分较高的电影选择评论总是最优的，选择较差的选择不会提高任何电影的评分。
利用这个事实我们来计算几个值：
x-喜欢第一部电影多于第二部电影的人对第一部电影的评分(ai>bi)。
y-喜欢第二部电影多余第一部电影的人对于第二部电影的评分(bi>ai).
neg-两部电影都不喜欢的人数；
pos-两部电影都喜欢的人数。
现在，我们要对ai==bi的观众的评论进行分配，为此，我们可以从-neg到pos重复计算这些观众对第一部电影的评分的贡献，那么第一部电影的评分最终为x+i,第二部电影的最终评分为
y+(pos-neg-i),在所有选项中，选择这两个值中最小值最大的选项。
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;//输入
vector<int> a(n), b(n);//相当于数组
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;//c++标准中遍历数组
int x = 0, y = 0, neg = 0, pos = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
x += a[i];
}
else if (a[i] < b[i]) {
y += b[i];
}
else {
neg += (a[i] < 0)//即a[i]<0，neg++，a[i]>0,pos++;
pos += (a[i] > 0);
}
}
int ans = -1e9;
for (int i = -neg; i <= pos; ++i)
ans = max(ans, min(x + i, y + (pos - neg - i)));
cout << ans << '\n';
}
}
标签：leftMax,周赛,魏方,int,pos,height,2024,++,数组 From： https://www.cnblogs.com/hautacm/p/18577386