A. 宙天
本题主要内容：若存在自然数 k，满足 x=k×(k+1)，则称 x 为「终极答案」。
由于 x 在0 - 100 之间，直接暴力枚举即可。
代码如下：
#include <iostream>
using namespace std;
int main()
{
int x;
cin>>x;
if(x== 0 || x==2|| x==6 || x==12 || x==20 || x==30 || x==42 || x==56 || x==72 || x==90)
cout<<"YES"<<endl;
else cout <<"NO"<<endl;
return 0;
}
B. Random
本题主要内容：一个长为 n 的数组， 选择其中两个不同位置的元素，要求这两个元素的最大公约数大于 1。
主要思路：
从头开始将数组的每个元素按质数分解，并存入哈希表中，如果在分解某一元素的时候，刚好出现了这一元素的素数因子之前出现过，就直接退出循环进行输出。
代码如下：
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 100;
int t, n;
int a[N];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
unordered_map<int, int> m; // 用于存储质因子和对应的数字
bool res = false; // 标记是否找到结果
for (int i = 0; i < n; i++)
{
if (a[i] == 1) continue; // 跳过数字1，因为它没有质因子
int tmp = a[i];
// 处理质因子2
if (a[i] % 2 == 0)
{
if (m.find(2) != m.end())
{
// 如果质因子2已经出现过，输出对应的一对数字
printf("%d %d\n", m[2], a[i]);
res = true;
break;
}
else
m[2] = a[i]; // 否则记录质因子2和当前数字
// 移除所有的因子2
while (tmp % 2 == 0)
tmp /= 2;
}
// 处理其他奇质因子
for (int j = 3; j * j <= tmp; j += 2)
{
if (tmp % j == 0)
{
if (m.find(j) != m.end())
{
// 如果质因子j已经出现过，输出对应的一对数字
printf("%d %d\n", m[j], a[i]);
res = true;
break;
}
else
m[j] = a[i]; // 否则记录质因子j和当前数字
// 移除所有的因子j
while (tmp % j == 0)
tmp /= j;
}
// 如果已经找到结果，提前结束循环
if (res) break;
}
// 处理剩余的质因子（大于sqrt(tmp)的质因子）
if (tmp > 1 && !res)
{
if (m.find(tmp) != m.end())
{
// 如果质因子tmp已经出现过，输出对应的一对数字
printf("%d %d\n", m[tmp], a[i]);
res = true;
break;
}
else
m[tmp] = a[i]; // 否则记录质因子tmp和当前数字
}
// 如果已经找到结果，提前结束循环
if (res) break;
}
// 如果没有找到任何符合条件的数字对，输出-1
if (!res)
printf("-1\n");
}
return 0;
}
C. Inverted World
本题主要内容： 一个仅由字符 0 和 1 组成的长为 n 的字符串 s ，选择 s 的一个非空子序列 ，该子序列 任意两个相邻元素都不相同，将该子序列进行01反置 ，最少需要多少次操作才能使得 s 中任意两个相邻元素都不相同。
本题主要思路： 目标字符串就是"010101.....010101" 和 "101010.......101010" 这两种，可以把字符串对比两种目标字符串，将与目标字符串一样的字符放入字符串 tmp_0 和 tmp_1 中，
将 1 的权值记为 1 ，0 的权值记为 -1，通过找到 tmp_0 和 tmp_1 中的某一段连续子串，计算其 1 所占的优势和 0所占的优势（ 即某段子串的权值和 ），而题目中所做的操作，可以让权值差缩减1.
所以我们要找到对应的1 所占的优势的最大值（即权值最大的子串） 和 0所占的优势的最大值（即权值最小的子串），最终二者的绝对值的最大值即为该字符串的答案。
最终比较 tmp_0 和 tmp_1 两者答案的最小值，即为最终答案。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int t, n;
string s;
/**
* 函数 f: 计算将一个字符串变为交替序列所需的最小操作次数
* 参数 a: 输入字符串，由 '0' 和 '1' 组成
* 返回值: 最小操作次数
*/
int f(string a)
{
int res1 = 0, res2 = 0; // res1: 最大子段和, res2: 最小子段和
int now = 0; // 当前子段和
// 计算最大子段和（将 '1' 视为 +1，'0' 视为 -1）
for (int i = 0; i < (int)a.size(); i++)
{
if (a[i] == '1')
now++; // 遇到 '1'，当前和 +1
else
now--; // 遇到 '0'，当前和 -1
if (now < 0) // 如果当前和小于0，重置为0
now = 0;
res1 = max(res1, now); // 更新最大子段和
}
now = 0; // 重置当前和为0
// 计算最小子段和
for (int i = 0; i < (int)a.size(); i++)
{
if (a[i] == '0')
now--;
else
now++;
if (now > 0)
now = 0;
res2 = min(res2, now);
}
// 返回最大子段和与最小子段和绝对值的较大者
return max(res1, abs(res2));
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
cin >> s;
string tmp_0 = "", tmp_1 = "";
// 构建 tmp_0：针对目标模式 0101...（偶数位为0，奇数位为1）
for (int i = 0; i < (int)s.size(); i++)
{
if (i % 2 == 0 && s[i] == '0')
tmp_0 += s[i];
else if (i % 2 == 1 && s[i] == '1')
tmp_0 += s[i];
}
// 构建 tmp_1：针对目标模式 1010...（偶数位为1，奇数位为0）
for (int i = 0; i < (int)s.size(); i++)
{
if (i % 2 == 0 && s[i] == '1')
tmp_1 += s[i];
else if (i % 2 == 1 && s[i] == '0')
tmp_1 += s[i];
}
// 计算两种目标模式的最小操作次数，取较小值作为答案
printf("%d\n", min(f(tmp_0), f(tmp_1)));
}
return 0;
}
F. Energy Synergy Matrix
本题主要内容：选择一个当前为空且不为起点的格子放置障碍，使小小红无法进入该格子，并且必须要保证存在通路，求小红到达第 n 列所需的最少步数。
主要思路：
首先明确两个人放置障碍物的作用是什么，小紫放置障碍物的作用是让小红多走一步，即让小红换一行行走，是她多走一步。
小红放置障碍物的作用是：利用必须保证存在通路这个性质，让小紫尽可能后的放置障碍物，使得他在行走到目标列的时候，小紫放的障碍物尽量的少。
由于小红先手，所以每个人的最优放置如下所示： 小红的障碍物用：红 表示，小紫的用：紫 表示
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 始 |
|
|
|
紫 |
|
|
红 |
|
|
|
|
|
|
紫 |
|
|
|
红 |
|
|
|
|
|
|
紫 |
|
|
红 |
|
|
因此小红走的步数为 n - 1 + n /5
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int t,n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",n-1+n/5);
}
return 0;
}
G. スピカの天秤
本题主要内容： 求解最少拿走多少块砝码，可以更改天平的状态。
主要思路：
当左侧的重量等于右侧的时候，只要拿走任意一块，天平的状态一定会改变。
当左侧的重量不等于右侧的时候，要想改变天平状态，肯定需要从重的一侧拿，直到重的一侧变得与另一侧相等或者比另一侧轻。那么为了拿的块数更少，就要尽可能的拿最重的砝码，这样才能保证拿的块数最少。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 100;
int t, n, m;
int a[N], b[N];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
long long sum1 = 0, sum2 = 0; // 用于存储两个数组的总和
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
sum1 += a[i];
}
for (int i = 0; i < m; i++)
{
scanf("%d", &b[i]);
sum2 += b[i];
}
// 如果两个数组的总和相等，直接输出1
if (sum1 == sum2)
{
printf("1\n");
continue;
}
// 如果数组a的总和大于数组b的总和
if (sum1 > sum2)
{
sort(a, a + n); // 对数组a进行升序排序
int cnt = 0; // 计数器，记录需要移出的砝码个数
// 不断从数组a中移出最大的元素，直到总和不再大于sum2
while (sum1 > sum2)
{
sum1 -= a[n - 1 - cnt]; // 减去最大的元素
cnt++;
}
printf("%d\n", cnt);
}
// 如果数组b的总和大于数组a的总和
else
{
sort(b, b + m); // 对数组b进行升序排序
int cnt = 0;
// 不断从数组b中移出最大的元素，直到总和不再大于sum1
while (sum1 < sum2)
{
sum2 -= b[m - 1 - cnt]; // 减去最大的元素
cnt++;
}
printf("%d\n", cnt);
}
}
return 0;
}
H. Tic Tac DREAMIN’
本题主要内容：在 x 轴上寻找一个锚点 O(x,0)，使得以 A,B,O 为顶点的三角形面积恰好等于 2。
主要思路：在坐标系上的三角形面积公式：
|(Xa - X) * Yb - (Xb - X) * Ya| = S
整理得到公式：| XaYb - XbYa + (Ya - Yb )X | = 4 这个方程的 X 的解即为所求的答案。
这里需要了解： 当Ya - Yb相等的时候，x是可以取任何值的，但必须要保证 | XaYb - XbYa | = 4 成立， 否则无解。
当Ya - Yb不相等的时候，只需要求解 XaYb - XbYa + (Ya - Yb )X = 4 的X的取值即为答案。（因为题目说输出一个答案即可，所以可以直接去掉绝对值）。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 2e5 + 100;
double xa ,xb ,ya ,yb;
int main()
{
scanf("%lf %lf",&xa, &ya);
scanf("%lf %lf",&xb, &yb);
if( abs(ya - yb) < 1e-9)
{
if( abs( abs( xa * yb - xb * ya) - 4) < 1e-9)
printf("0");
else printf("no answer");
}
else
printf("%.8lf",(4 - xa * yb + xb * ya) / (ya - yb));
return 0;
}
J. Branch of Faith
本题主要题意： 一棵包含 nn 个节点的完全二叉树，输出与 x 号节点深度相同的节点有多少个。
根据完全二叉树的性质我们可以得知：
深度为0时 ，即根节点 1 ，就是区间[ 20 , 21 - 1 ]
深度为1时， 即节点 2 ， 3， 就是区间 [ 21 , 22 - 1 ]
深度为2时， 即节点 4 ，5，6， 7 就是区间 [ 22 ， 23 - 1 ]
因此 我们可以得知，当节点 k 位于 [ 2n , 2n+1-1 ] 的区间时， 深度相同的节点有 2n+1-1 - 2n + 1 个
需要注意的是：当深度是最深的时候，未必会将最后一层全部填满，所以需要特判一下 n 和 2n+1-1 的大小。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int t, q;
long long n;
// 函数f: 根据给定的n和x计算某个值
// 参数: n - 限制值, x - 查询值
long long f(long long n, long long x)
{
// 当x为1时，直接返回1
if (x == 1) return 1;
int idx = 2; // 从idx=2开始寻找合适的指数
// 找到满足条件的idx，使得x在[2^(idx-1), 2^idx-1]区间内
while (x > ((1LL << idx) - 1) || x < (1LL << (idx - 1)))
idx++;
// 计算结果: min(n, 2^idx-1) - 2^(idx-1) + 1
return min(n, ((1LL << idx) - 1)) - (1LL << (idx - 1)) + 1;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%lld %d", &n, &q);
for (int i = 0; i < q; i++)
{
long long x;
scanf("%lld", &x);
printf("%lld\n", f(n, x));
}
}
return 0;
}
京公网安备 11010502036488号