A. 本场比赛灵感来源于树状数组出题组
本题主要内容 ：在数组中，对于第 𝑥 个数字 𝑎𝑥，如果其他数字中有至少 80% 的数字小于等于 𝑎𝑥 ，则将第 𝑥 个数字分在 A 组，否则分在 B 组。求A组中数字的和。
本题主要思路：由于本题的 n 的取值范围是 2 - 1e3 ，所以可以直接暴力枚举。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 100;
int n;
int a[N];
int main()
{
int res = 0;
scanf("%d", &n);
for(int i = 1; i <= n ; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= n ; i++)
{
int cnt = 0;
for(int j = 1;j <= n; j++)
{
if(i == j) continue;
if(a[i] >= a[j])
cnt ++;
}
if( (double)cnt - (double)0.8 * (n-1) >= 0)
res+ = a[i];
}
printf("%d\n",res);
return 0;
}
B. 构造部落
本题主要内容：已知部落有 n 位连续在位的首领，第 1 位首领的第 1 年是公元 s 年，每位首领在位年数已知；
现在有 q 件文物，每件记录了某首领在位第 y 年发生的事件，需要你算出每件文物事件对应的公元年份。
本题主要思路：由于第 i 位首领的年份与前 i-1 个首领在位时间加和有关，所以本题我们可以用前缀和来实现。
首先可以设定sum[ 0 ] = s-1 , 这样以后每个首领在位时间的加和就是现在所对应的时间了。
因此：第 i 位首领在位第 y 年发生的事件对应的时间就是：sum [ i - 1] + y
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int n, q, s;
int a[N], sum[N];
int main()
{
scanf("%d %d %d", &n, &q, &s);
sum[0] = s - 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
while (q--)
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", sum[x - 1] + y);
}
return 0;
}
C. 墨提斯的排列
本题主要内容：构造一个长度为 2n 的排列，使之相邻两项异或值之和最小。求该排列。
本题主要思路：要想相邻两项异或值之和最小，那就要尽量让相邻两项的二进制表示尽可能的相似，并且不一致的地方位置越低越好。这就想到了用格雷码。
格雷码：是一种二进制编码系统，其中两个连续数字的二进制表示只有一位不同。
格雷码的构造方式：格雷码可以通过 G = B ⊕ (B >> 1) 的方式构造。
因此：直接在0 - 2n 上构造格雷码 即是所求的最小排列。
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int n;
int main()
{
scanf("%d", &n);
n = 1 << n;
for (int i = 0 ; i < n ; i++)
printf("%d ", i ^ (i >> 1) );
return 0;
}
F. 爱音的01串构造
本题主要内容：构造一个由 𝑎 个 0 和 𝑏 个 1 组成的 01 字符串，且使得这个 01 字符串所有非空连续子串的 最小未出现的非负整数 之和最大。
本题主要思路：要想 所有非空连续子串的 最小未出现的非负整数 之和最大 ，那就要尽可能的出现 01或者10 这样的子串
所以 当 a = b 的时候，0101010101这样的字符串就是满足要求的字符串。
当 a > b 的时候，我们可以将字符串看作由 b+1 段 0 和 b 段 1 交替组成 。
由于 0 比较多，所以我们可以让 b+1 段 0 中 0 的长度不为1， 为 a/(b+1) 或者 a/(b+1) + 1 。
由于 1 比较少，所以每段 1 的长度都是 1 。
当 a < b 的时候同理。
例如： a=5, b=2
分成3段0和2段1：0 - 1 - 0 - 1 - 0
每段0的长度：5/3=1 余 2，所以三段0的长度分别为2,2,1
构造：00 - 1 - 00 - 1 - 0 = 0010010
每段0的长度：5/3=1 余 2，所以三段0的长度分别为2,2,1
构造：00 - 1 - 00 - 1 - 0 = 0010010
代码实现：
#include <iostream>
#include <string>
using namespace std;
int t;
int main()
{
scanf("%d", &t);
while(t--)
{
int a, b;
scanf("%d %d", &a, &b);
string s = "";
// 情况1：没有0，只能输出全1
if(a == 0)
{
for(int i = 0; i < b; i++)
printf("1");
puts("");
continue;
}
// 情况2：没有1，只能输出全0
else if(b == 0)
{
for(int i = 0; i < a; i++)
printf("0");
puts("");
continue;
}
// 情况3：0的数量大于等于1的数量
if(a >= b)
{
// 将0分成(b+1)段
int l = a / (b + 1); // 每段0的基本长度
int ex_l = a % (b + 1); // 需要额外加1的段数
// 构建第一段0
int d = l + (ex_l > 0 ? 1 : 0); // 第一段0的长度
if(ex_l > 0) ex_l--; // 如果第一段用了额外长度，余数减1
for(int i = 0; i < d; i++)
s += "0"; // 添加第一段0
// 交替添加1和后续的0段
for(int j = 0; j < b; j++)
{
s += '1'; // 添加1
d = l + (ex_l > 0 ? 1 : 0); // 计算下一段0的长度
if(ex_l > 0) ex_l--; // 如果这段用了额外长度，余数减1
for(int i = 0; i < d; i++)
s += "0"; // 添加下一段0
}
}
// 情况4：1的数量大于0的数量
else
{
// 将1分成(a+1)段
int l = b / (a + 1); // 每段1的基本长度
int ex_l = b % (a + 1); // 需要额外加1的段数
// 构建第一段1
int d = l + (ex_l > 0 ? 1 : 0); // 第一段1的长度
if(ex_l > 0) ex_l--; // 如果第一段用了额外长度，余数减1
for(int i = 0; i < d; i++)
s += "1"; // 添加第一段1
// 交替添加0和后续的1段
for(int j = 0; j < a; j++)
{
s += '0'; // 添加0
d = l + (ex_l > 0 ? 1 : 0); // 计算下一段1的长度
if(ex_l > 0) ex_l--; // 如果这段用了额外长度，余数减1
for(int i = 0; i < d; i++)
s += "1"; // 添加下一段1
}
}
cout << s << endl;
}
return 0;
}
H. 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学
本题主要内容： 在一张 n 行 m 列的网格地图上，每个格子有若干敌人，敌方会进行 q 次增援（每次给指定格子增加 z 个敌人）。
你需要在每次增援后，找到一个格子作为 “玉米加农炮” 的发射位置，
使得该位置曼哈顿距离不超过 2 的所有格子内的敌人总数最多，并输出这个最优位置（若有多个，任选其一即可）。
本题主要思路：本题其实应该通过线段树求解，但这里给出一个暴力的方法。
通过题意可知，当（x,y）作为 “玉米加农炮” 的发射位置，有如图所示的13个格子受到攻击，因此可以先初始化出以每个点为中心，覆盖的敌人的总数 计入数组中。
|
|
|
@ |
|
|
|
|
@ | @ | @ |
|
| @ | @ | （x,y） | @ | @ |
|
|
@ | @ | @ |
|
|
|
|
@ |
|
|
每次增员后， 可以对该区域进行类似于如上格子的遍历，将每个点都增加 y 值，增员后的最大值就是 max ( 原最大值 ，相关点增加y之后的最大值）
重复以上步骤，即可实现问题求解。
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL a[510][510], b[510][510]; // a: 原始敌人数量，b: 每个位置作为炮台的总伤害值
int n, m, q;
int main()
{
scanf("%d %d %d", &n, &m, &q);
// 为了便于边界处理，从下标2开始存储数据
for(int i = 2; i <= n + 1; i++)
for(int j = 2; j <= m + 1; j++)
scanf("%lld", &a[i][j]);
// 预处理：计算每个位置作为炮台时的初始总伤害，遍历曼哈顿距离不超过2的所有位置
for(int i = 2; i <= n + 1; i++)
for(int j = 2; j <= m + 1; j++)
b[i][j] = a[i][j - 1] + a[i][j + 1] + a[i - 1][j - 1] + a[i - 1][j + 1] +
a[i + 1][j - 1] + a[i + 1][j + 1] + a[i][j - 2] + a[i][j + 2] +
a[i + 1][j] + a[i - 1][j] + a[i + 2][j] + a[i - 2][j] + a[i][j];
// 初始找到最大值和最大值的位置
LL ma = -1e9;
pair<int, int> idx; // 存储最大值的位置（在b数组中的坐标）
for(int i = 2; i <= n + 1; i++)
for(int j = 2; j <= m + 1; j++)
if(b[i][j] > ma)
{
ma = b[i][j]; // 更新最大值
idx.first = i; // 记录最大值所在行
idx.second = j; // 记录最大值所在列
}
while(q--)
{
int x, y, c;
scanf("%d %d %d", &x, &y, &c);
// 更新以(x+1, y+1)为中心的曼哈顿距离不超过2的所有位置
// 注意：输入的x,y是1-based坐标，对应到b数组中是(x+1, y+1)
for(int i = -2; i <= 2; i++)
for(int j = -2; j <= 2; j++)
{
// 跳过曼哈顿距离超过2的位置
if(abs(i) + abs(j) > 2) continue;
int nx = x + 1 + i; // 在b数组中的行坐标
int ny = y + 1 + j; // 在b数组中的列坐标
// 确保位置在地图范围内
if(nx >= 2 && nx <= n + 1 && ny >= 2 && ny <= m + 1)
{
// 更新该位置的伤害值
b[nx][ny] += c;
// 如果更新后的值超过了当前最大值，更新最大值和位置
if(b[nx][ny] > ma)
{
ma = b[nx][ny];
idx.first = nx;
idx.second = ny;
}
}
}
//注意：坐标起点是从2开始的，因此得到的坐标减 1 就是答案
printf("%d %d\n", idx.first - 1, idx.second - 1);
}
return 0;
}
I. 初华的扭蛋机
本题主要内容： 在一个有 6 种等概率颜色小球的扭蛋机游戏中，你有 6 枚筹码，可选择下注到某颜色或留在手上；
扭蛋机会独立抽 3 次球，对每种颜色 c，若下注 x 枚筹码，则按抽到 1 颗、2 颗、3 颗该颜色球分别获得 2x、3x、10x 筹码，
最终筹码为获利 + 手上剩余筹码。你需要构造一个长度为 6 的下注方案字符串（字符为颜色代号或 #），使得最终筹码的期望值最大。
本题主要思路：可以证明得到，无论怎么下注，其期望都是小于 6 的，因此 不下注就是期望值最高的。
代码如下：
#include <iostream>
using namespace std;
int main()
{
printf("######");
return 0;
}
京公网安备 11010502036488号