1.比赛安排
本题主要内容：将abc三种比赛合理排序，保证对于任意连续的 3 场比赛的类型互不相同，是否有这样的排列方式。
仔细思考，要想任意连续的 3 场比赛的类型互不相同，其主要结构就是abc abc abc ......(abc循环，此时a=b=c），只有首尾还可以添加，例如：cabc 或者 abca 或者 cabca 形如此类。
因此想要实现这种排列，需要满足的是：a, b, c三者的最大值与最小值只差不能超过 1。
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
int T,a,b,c;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&a,&b,&c);
int ma=max({a,b,c}); //求最大值
int mi=min({a,b,c}); //求最小值
if(ma-mi<=1)
printf("YES\n");
else printf("NO\n");
}
return 0;
}
2.NCPC
本题主要内容：对于数组 a[N] ,选取当前场上任意两个未被淘汰的选手 i , j ( i ≠ j ) ,如果 a[ i ] = a[ j ] 那么二者均淘汰，否则数值低的淘汰。寻找是否存在一种对决安排，使得选手 i (1 ≤ i ≤ n)最终成为唯一剩下的选手。
主要思路可以分两种情况讨论：
1.如果选手 i 所对应的 a [ i ]的值是数组中最大的，那么他可以淘汰任意一个小于他的选手，剩下的就都是和他一样同为最大值的选手，如果剩下的这些最大值选手是偶数的话，他们就会全部互相消掉，最终剩 i 自己，符合题意 ； 如果是奇数的话，最终会剩一个最大值选手与选手 i 同归于尽，导致无法找到符合题意的对决安排。
2.如果选手 i 所对应的 a [ i ]的值不是数组中最大的，那么可以先用最大值淘汰所有除了选手 i 的非最大值的选手，剩余的是最大值选手 和 选手 i ，如果最大值选手能内部消掉的话，就可以满足题意，否则就不可以。
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int T, n;
int a[N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
int cnt = 0, ma = -1e9; // cnt: 最大值出现次数, ma: 当前最大值
// 遍历数组，找出最大值及其出现次数
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if (ma == a[i]) // 如果当前元素等于最大值
cnt++; // 增加最大值计数
else if (ma < a[i]) // 如果发现更大的值
{
cnt = 1; // 重置计数为1
ma = a[i]; // 更新最大值
}
}
for (int i = 0; i < n; i++)
{
// 如果不是最大值且最大值出现次数为偶数，输出1
if (a[i] != ma && cnt % 2 == 0)
printf("1");
// 如果是最大值且 剩余最大值数量为偶数，输出1
else if (a[i] == ma && (cnt - 1) % 2 == 0)
printf("1");
else // 其他情况输出0
printf("0");
}
printf("\n");
}
return 0;
}
E 01矩阵
本题主要内容: 构建一个只由 0和1组成的 n 阶矩阵，并且行和以及列和都在集合{0,1，.......，n-1}里面，且没有重复，并且还需满足矩阵中 0 的连通块个数和 1 的连通块个数总和恰好为 n 个。
主要思路：
n=2 n=3 n=4 n=5
构建类似于这样的矩阵，可以完美的符合题意，n为偶数的时候首项为1，否则为0，然后外围包裹着另一个原则，以此类推。
首行是交替的 1 和 0 ；
后续每行的前 i （行数从0开始）个元素与上一行不同，剩下的均相同。
代码如下：
#include <iostream>
using namespace std;
int n;
// 字符取反函数：如果输入 '1' 则返回 '0'，否则返回 '1'
char f(char x)
{
if (x == '1')
return '0';
else
return '1';
}
int main()
{
scanf("%d", &n);
// 生成首行字符串
string st;
if (n % 2 == 0) // 如果 n 是偶数
st += '1'; // 首字符为 '1'
else // 如果 n 是奇数
st += '0'; // 首字符为 '0'
// 根据首字符生成交替的 0/1 序列
for (int i = 1; i < n; i++)
st += f(st[i - 1]); // 每次添加前一个字符的相反字符
// 输出首行
cout << st << endl;
// 生成并输出后续行
for (int i = 1; i < n; i++)
{
// 修改当前行的前 i 个字符（取反）
for (int j = 0; j < i; j++)
st[j] = f(st[j]); // 对前 i 个字符进行取反操作
// 输出当前行
cout << st << endl;
}
return 0;
}
F x?y?n!
本题主要内容：给定一个整数 n，你需要找到两个整数x,y 满足：gcd( x, y)= n ,并使得 x⊕y 的值最小。
主要思路： 由于 n ≤ | x - y | ≤ x⊕y，我们只需要找到 x ⊕ y = n 即为所求得的答案。
因此需要满足 x 和 y 在二进制位上与n无交集 ，因此我们可以选定 x = n × 231，y =n × (231+1) 。
这样由于 231 和 231+1 互质，所以满足gcd( x, y)= n ，并且这样构造让x , y 在高32位的数一样，并且 x 在低32位的为 0 ， y 在低32位的为 n
最终异或结果即为 n 。（注意用 long long）
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int T;
LL n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
LL x = n * ( (LL)1 << 31);
LL y = n * ( ((LL)1 << 31) + 1);
printf("%lld %lld\n", x, y);
}
return 0;
}
H 权值计算
本题主要内容：定义一个数组的权值为其所有前缀中不同数字的个数，求所有子数组的权值之和。
解题思路：可以从考虑一个数字能给多少个子数组贡献答案以及所贡献的多少来看。
a[ i ]对子数组[ l, r ]的贡献是：a[i]在所有包含它的前缀子数组[l, i], [l, i+1], ..., [l, r]中的出现次数，
在[l, i]中，a[i]是第一次出现，所以贡献1
在[l, i+1]中，a[i]仍然存在，所以再贡献1
...
在[l, r]中，a[i]也存在，所以再贡献1
所以，a[i]对子数组[l, r]的总贡献 = (r - i + 1) 并且 L≤ l ≤i && i ≤ r ≤ n-1
在[l, i+1]中，a[i]仍然存在，所以再贡献1
...
在[l, r]中，a[i]也存在，所以再贡献1
所以，a[i]对子数组[l, r]的总贡献 = (r - i + 1) 并且 L≤ l ≤i && i ≤ r ≤ n-1
对于固定的 l ,a[i]所做的总贡献为[l, i] + [l, i+1] +........+[l,r]=(i - i + 1)+(i + 1 - i + 1)+........+(r - i + 1)=1+2+3+......+( r - i + 1)
(i - j) × (1 + 2 + ... + (n - i + 1))
所以a[ i ]所做的总贡献即为：(i - j) × (1 + 2 + ... + (n - i + 1)) 其中j为a[ i ]上一次所出现的位置，因此保证a[ i ]是这段数组最先出现的这个数，因此右端可以一直到 n
所以a[ i ]所做的总贡献即为：(i - j) × (1 + 2 + ... + (n - i + 1)) 其中j为a[ i ]上一次所出现的位置，因此保证a[ i ]是这段数组最先出现的这个数，因此右端可以一直到 n
例如：数组为[1, 2, 1, 3]，考虑a[3]=1（第三个元素，值为1）：
上一个相同值位置j=1（a[1]=1）
i=3, n=4
i=3, n=4
可能的左端点l：
l=2：子数组[2,3], [2,4]
l=3：子数组[3,3], [3,4]
计算贡献：
子数组[2,3]：a[3]贡献1次
子数组[2,4]：a[3]贡献2次（在[2,3]和[2,4]中都出现）
子数组[3,3]：a[3]贡献1次
子数组[3,4]：a[3]贡献2次
总贡献 = 1 + 2 + 1 + 2 = 6 = (3-1) × (1+2)
代码如下：
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 100;
typedef long long LL;
int T, n;
int a[N];
int pre[N]; // 记录前一个相同值的索引
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
unordered_map<int, int> last_pos;
// 第一次遍历：记录前一个相同值
for (int i = 1; i <= n; i++)
{
if (last_pos.count(a[i]))
pre[i] = last_pos[a[i]];
else
pre[i] = 0; // 0表示没有前一个相同值
last_pos[a[i]] = i; // 更新该值最近出现位置
}
LL res = 0;
for(int i = 1; i <= n; i++)
{
LL left = i - pre[i]; // 左端点个数
LL len = n - i + 1; // 右端点可以取的长度
res += left * len * (len + 1) / 2;;
}
printf("%lld\n", res);
}
return 0;
}
I 01回文
本题主要内容：给定n×m的01矩阵，询问任意一个位置开始拼接字符，任意非起始位置结束，能否拼接得到一个回文串。
主要思路：在某点，只要能在该点附近找到一个离该点最近的与该点值相同的地方，就可以组成一个回文串。
如果该点是0，那么找到离该点最近的且值同为0的地方，那么这段路径一定为0111....1110,中间一定全为1，否组不满足离得最近这一特点。
同理当该点是1的时候，那么这段路径一定为100....001,中间一定全为0.
因此我们可以得出，只要是还存在与该点值相同的地方，那么一定会找到对应的回文串，一定是Y，否则是N。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 100;
int T, n, m;
string a[N]; // 存储输入的n行字符串
int main()
{
scanf("%d", &T); // 读取测试用例数量
while (T--)
{
scanf("%d %d", &n, &m); // 读取n和m
// 读取n行字符串
for (int i = 0; i < n; i++)
cin >> a[i];
int cnt = 0; // 统计矩阵中'1'的个数
// 遍历整个矩阵，统计'1'的数量
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j] == '1') cnt++;
// 逐行输出结果
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// 如果当前字符是'1'，且矩阵中还有其他'1'，则输出'Y'
if (a[i][j] == '1' && cnt - 1 != 0)
printf("Y");
// 如果当前字符是'0'，且矩阵中还有其他'0'，则输出'Y'
else if (a[i][j] == '0' && n * m - cnt - 1 != 0)
printf("Y");
// 否则输出'N'
else
printf("N");
}
puts(""); // 换行
}
}
return 0;
}
京公网安备 11010502036488号