题解 | #比赛安排（PDF题面存放于本题）#
比赛安排（PDF题面存放于本题）
https://ac.nowcoder.com/acm/contest/120562/A
这里是A,B,I,F,H,E的个人想法
A
对于任意连续的3场比赛的类型互不相同，即三种比赛当且仅当以abcabc的方式进行，换句话说，最少和最多的比赛场次不能差超出1
代码展示
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--) {
long long a,b,c;
cin>>a>>b>>c;
long long m=max({a, b, c});
long long n=min({a, b, c});
if (m<=n+1){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
}
return 0;
}
B
获胜的唯一条件：成为「严格唯一」的最大值
游戏规则的本质是：
任意两个不同值对决，值大的留下、小的淘汰；值相等的对决，两者都淘汰。 推导结论：
1.如果选手的美味值不是数组最大值 → 一定会在某一轮被最大值选手淘汰，无法获胜；
2.如果最大值出现≥2 次 → 任意两个最大值对决会双双淘汰，最终无选手存活，所有位置都无法获胜；
3.只有最大值「仅出现 1 次」时，这个最大值选手可以通过 “逐个淘汰其他选手” 的策略最终获胜，其余选手都无法获胜。
代码展示
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<long long>a(n);
long long maxi=LLONG_MIN;
int m1= 0;
int m2= -1;
for(int i=0; i<n; i++){
cin >> a[i];
if(a[i] > maxi){
maxi=a[i];
m1= 1;
m2= i;
}else if(a[i] == maxi){
m1++;
}
}
string res(n, '0');
if(m1== 1){
res[m2] = '1';
}
cout<<res<<'\n';
}
return 0;
}
I
对于每个位置 (i,j)，只要存在一个相邻的格子（上下左右）和它的数字相同，就一定能构造出满足条件的回文路径（比如走两步：(i,j) → (x,y) → (i,j) 虽然是简单路径，但终点是起点，所以我们需要找一个非起点的位置。其实更简单的是：只要存在两个相邻的相同数字，那么从这两个数字中的任意一个出发，都可以直接走到另一个，形成长度为 2 的回文串，比如 "00" 或 "11"，这显然是回文的）。
所以，一个位置 (i,j) 输出 Y 的充要条件是：
1.它的四个相邻方向中，至少有一个格子的数字和它相同；
2.或者，整个矩阵中至少有两个和它相同的数字，并且这两个数字在矩阵中是连通的（在 01 矩阵里，只要数量 ≥2 就一定能找到路径，因为矩阵是连通的网格）。
思路：
1.先遍历整个矩阵，标记每个位置 (i,j) 是否有相邻的相同数字。
2.如果一个位置有相邻的相同数字，那么它的答案就是 Y。
3.如果一个位置没有相邻的相同数字，再看：
如果矩阵中至少有 2 个和它相同的数字，那么答案是 Y（因为可以绕路走到另一个相同数字，形成长度 ≥2 的回文串）。
如果矩阵中只有 1 个和它相同的数字，那么答案是 N。
代码展示
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<bool>> has_same(n, vector<bool>(m, false));
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
if (a[i][j] == a[ni][nj]) {
has_same[i][j] = true;
break;
}
}
}
}
}
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == '0') cnt0++;
else cnt1++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (has_same[i][j]) {
cout << 'Y';
} else {
if (a[i][j] == '0' && cnt0 >= 2) {
cout << 'Y';
} else if (a[i][j] == '1' && cnt1 >= 2) {
cout << 'Y';
} else {
cout << 'N';
}
}
}
cout << '\n';
}
}
return 0;
}
F
利用数论中 “相邻整数互质” 的核心性质，构造满足 gcd(x,y)=n 的两个数即可
代码展示
#include <bits/stdc++.h>
using namespace std;
int main() {
const long long BASE = 1LL << 31;
const long long BASE_PLUS_1 = BASE + 1;
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
long long x = n * BASE;
long long y = n * BASE_PLUS_1;
cout << x << " " << y << "\n";
}
return 0;
}
H
我们要计算数组所有非空子串的权值之和，这里的权值定义为：从左到右遍历子串，每遇到一个新的数字，就把当前累计的不同数字个数加到总权值里。
直接暴力枚举所有子串会超时，所以我们用贡献法：
每个数字 a[i] 对总权值的贡献，等于它作为 “首次出现” 的那个数字，在所有包含它的子串中，对权值的贡献之和。
对于位置 i 上的数字 a[i]，设它上一次出现的位置是 last（如果没出现过则为 0），那么：
- 它能作为 “首次出现” 的子串左端点范围是 [last+1, i]，共 i - last 种选择。
- 子串右端点范围是 [i, n]，共 n - i + 1 种选择。
- 每个这样的子串中，a[i] 会贡献 1 次权值（因为它是首次出现的新数字）。
因此，a[i] 的总贡献为：(i - last) * (n - i + 1)。
把所有位置的贡献相加，就是最终答案。
代码展示
#include<bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin >> T;
while(T--){
int n;
cin >> n;
map<int, vector<int>> mp;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
mp[x].push_back(i);
}
long long ans = 0ll;
for(pair<const int, vector<int>> &p : mp){
vector<int> &y = p.second;
y.insert(y.begin(), 0);
for(int i = 1; i < y.size(); i++){
int l = y[i - 1];
int r = n - y[i] + 1;
ans += 1ll * r * (r + 1) / 2 * (y[i] - l);
}
}
cout << ans << endl;
}
return 0;
}
E
行和与列和的排列：我们可以让第 i 行的和为 i-1，这样行和自然就是 0 ~ n-1 的排列。
- 构造矩阵：我们可以构造一个矩阵，使得第 i 行的前 i-1 个元素为 1，后面的为 0。这样行和就是 i-1。
- 调整列和：为了让列和也成为 0 ~ n-1 的排列，我们可以对矩阵进行转置或其他变换。
- 控制连通块：通过构造 “对角线” 或 “阶梯” 状的 0 和 1 分布，可以精确控制连通块的数量
代码展示
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cout<<(min(i,j)&1);
cout <<endl;
}
return 0;
}
查看7道真题和解析