上海市计算机学会竞赛月赛2025年2月份丙组
T1电话号码
【题目链接】
原题链接：上海市计算机学会竞赛平台与YACS项目（https://www.iai.sh.cn/problem/1027）
【考点】
数位拆解、判断
【题目大意】
由五个不带开头零的数字构成的有效电话码必须满足五位长度且无前导零的规定；而不具备五位且无前导零特征的号码被视为无效号码。Alice每日存储x元资金，在持续n日后，请计算其存款总额是否符合有效的A国通话码标准？
【解析】
通过C++语言进行格式化输入操作，分别读取每天存入金额x和持续时间n的数据字段；随后进行算术运算得出总额sum；接着将sum进行各位数字分离以便后续处理；最后统计数字位数并完成判断其是否为5的任务。
【难度】
GESP二级
【代码参考】
#include<bits/stdc++.h>
using namespace std;
int main(){
int t, n, x;
cin >> t;
while(t--){
cin >> n >> x;
int sum = n * x, len = 0;
while(sum){
len++;
sum /= 10;
}
if(len == 5)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}T2 新二进制
【题目链接】
原题链接：上海计算机学会竞赛平台 | YACS
【考点】
权重、二进制
【题目大意】
新的二进制仅由1和-1组成，并且可以用公式b₁×2⁰ + b₂×2¹ + … + bₙ×2ⁿ⁻¹来表示。其转换规则与二进制至十进制转换一致，在某些区间[l, r]中计算结果既可能大于零也可能小于零。我们需要确定在给定的一串新二进制数值中，在各个区间内计算得到正数值的数量减去负数值的数量，并取其绝对值。
【解析】
该问题可简化为判断第i位元素的性质（正或负）。由于区间[i,i]的计算结果必然超过区间[1,i-1]的结果,因此可以通过排列组合的方法确定区间[1,i]内正数与负数的数量。例如,当区间[i,i]计算结果若为正值,则表示区间[1,i]内的所有数值均为正值;若结果为负值,则表示所有数值均为负值。具体实现时,需遍历输入数组中的每一个元素,依次判断其对应的第i位属性,并将计数值根据属性分别累加至变量a或b中（其中a用于记录正值的数量）。最后将变量a与b中的数值差取绝对值得到最终结果
【难度】
GESP四级
【代码参考】
#include<bits/stdc++.h>
using namespace std;
int main(){
long long t, n, a, b, m[100005];
cin >> t;
while(t--){
cin >> n;
a = 0, b = 0;
memset(m, 0, sizeof(m));
for(int i = 1; i <= n; i++)cin >> m[i];
for(int i = 1; i <= n; i++){
if(m[i] == -1)b += i;
else if(m[i] == 1)a += i;
}
cout << abs(a-b) << endl;
}
return 0;
}T3 区间求和
【题目链接】
上海计算机学会竞赛平台 | YACS
【考点】
前缀和、差分、排序、贪心
【题目大意】
这道题是一个新的前缀和问题，在重新排列数列中的各个数字的位置后 运用前缀和计算方法进行处理 可以得到所有相关查询答案之和的最大总值
【解析】
交换元素的位置会直接影响每个查询涉及的区间总和。为了使所有查询的答案总和最大化，应该优先将较大的元素分配给那些被频繁查询的区间。可以计算每个位置被包含在多少个查询区间中，从而确定其重要性程度。被更多查询所包含的位置应放置更大的数值。为了快速统计这些值出现的情况，请采用差分数组技巧来实现快速统计。具体来说，在序列b[l]处加1，在b[r+1]处减1之后通过前缀和的方式即可得到各个位置上的覆盖次数s[i]值。接下来将序列a中的数值按照从大到小排序，并将这些数值依次分配给s[i]值最大的对应位置上就能达到最优效果
其中，数组a用于存储原始数据；其中一种常见的处理方式是将原始数据通过某种编码方式转换成二进制表示；接下来我们引入一个辅助结构——差分数组b；通过差分方法记录区间变化次数，并特别注意边界情况；随后我们需要利用前缀和计算得到最终的覆盖次数；最后一步是按降序排序这两个新生成的序列，并基于贪心算法依次将较大的元素分配给覆盖次数较高的位置。
【难度】
GESP四级
【代码参考】
#include<bits/stdc++.h>
using namespace std;
long long t, n, q;
bool cmp(int a, int b){
return a > b;
}
int main(){
cin >> t;
while(t--){
cin >> n >> q;
vector<long long> a(n);
for(int i = 0; i < n; i++)scanf("%d", &a[i]);
int l, r;
vector<long long> b(n + 2, 0);
for(int i = 0; i < q; i++){
scanf("%d%d", &l, &r);
b[l] += 1;
if(r+1 <= n)
b[r+1] -= 1;
}
long long ans = 0;
vector<long long> s(n);
for(int i = 1; i <= n; i++){
ans += b[i];
s[i-1] = ans;
}
sort(a.rbegin(), a.rend());
sort(s.rbegin(), s.rend());
long long sum = 0;
for(int i = 0; i < n; i++){
sum += a[i] * s[i];
}
cout << sum << endl;
}
return 0;
}T4 数阵交换
【题目链接】
上海市计算机学会竞赛平台 | YACS
【考点】
并查集
【题目大意】
考虑一个由两行n列组成的数字矩阵A。每一行都是从1到n的一个排列。Alice可以选择任意一列并进行元素交换的操作以改善其位置关系，并重复这一过程直至满足特定条件。我们的目标是确定通过这种元素交换操作后能够生成的所有满足条件的不同矩阵的数量，并将结果对10^9 +7取模
【解析】
每次对某一列进行调整时等价于对该列内的两行进行调换
并查集封装知识：
联合查找算法及其封装实现（节日快乐！）-博客
【难度】
GESP七级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7; // 定义模数
// 并查集数据结构
struct DSU {
vector<int> parent, rank; // parent数组存储每个节点的父节点，rank数组存储树的秩
DSU(int n) : parent(n + 1), rank(n + 1, 1) { // 构造函数，初始化parent和rank数组
for (int i = 0; i < n; ++i) {
parent[i] = i; // 每个元素初始时指向自己
}
// 查找函数，带路径压缩
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
// 合并函数，带按秩合并
void unite(int x, int y) {
x = find(x), y = find(y); // 找到x和y的根节点
if (x == y) return; // 如果已经在同一个集合中，直接返回
if (rank[x] < rank[y]) swap(x, y); // 按秩合并，将较小的树合并到较大的树
parent[y] = x; // 将y的根节点指向x
if (rank[x] == rank[y])
rank[x]++; // 如果秩相同，增加x的秩
}
};
int main() {
int t; // 数据组数
cin >> t;
while (t--) {
int n; // 每行数字的个数
cin >> n;
vector<int> p1(n), p2(n); // 存储两行的数字
for (int i = 0; i < n; ++i)
cin >> p1[i]; // 读取第一行的数字
for (int i = 0; i < n; ++i)
cin >> p2[i]; // 读取第二行的数字
DSU dsu(n); // 初始化并查集
for (int i = 0; i < n; ++i) {
int a = p1[i], b = p2[i]; // 获取当前列的两个数字
dsu.unite(a, b); // 将这两个数字合并到同一个集合中
}
unordered_set<int> roots; // 用于存储所有连通分量的根节点
for (int x = 1; x <= n; ++x)
roots.insert(dsu.find(x)); // 找到每个节点的根节点并插入集合中
int k = roots.size(); // 连通分量的数量
long long ans = 1; // 初始化结果为1
for (int i = 0; i < k; ++i)
ans = ans * 2 % MOD; // 每个连通分量有两种选择，乘2并取模
cout << ans << endl; // 输出结果
}
return 0;
}T5 子矩阵和
【题目链接】
原题链接：上海市计算机学会竞赛平台 | YACS
【考点】
前缀和、哈希表（map）
【题目大意】
旨在统计每一个子矩阵其元素之和与给定值 t 相等的数量。
其中每个元素对应于s[i]乘以s[j]的结果；这里s[i]表示字符串s中第i个字符所对应的数值。
旨在统计每一个子矩阵其元素之和与给定值 t 相等的数量。
其中每个元素对应于s[i]乘以s[j]的结果；这里s[i]表示字符串s中第i个字符所对应的数值。
【解析】
通过观察可以发现，在二维问题中利用子矩阵及其相关属性可将其简化为一个一维的问题。例如, (x+y)^2 = x^2 + 2xy + y^2, 其中矩阵元素（除第一行和第一列）具有行与列相乘的关系, 因此, 子矩阵之和等于其所在行之和与所在列之积。
t != 0 情况，遍历找到能够整除 t 的数，总子矩阵 ans += pre[i] * pre[t/i]。
当 t 等于 0 的时候，在程序运行过程中可以直接获取 pre[0] 的值而无需进行复杂的运算。此外，在处理某些特定情况时（例如某个行列中的某个元素值为零），该矩阵对应的整个行和列的所有元素都会被置零。
【难度】
GESP六级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, pre[36001];
string s;
cin >> t >> s;
memset(pre, 0, sizeof(pre));
int n = s.size();
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){
sum += s[j] - '0';
pre[sum]++;
}
}
long long ans = 0;
if(t == 0) ans = (1LL * n * n + n - pre[0]) * pre[0];
else{
for(int i = 1; i <= 36000; i++){
if(t % i == 0 && t / i <= 36000) ans += 1LL * pre[i] * pre[t/i];
}
}
cout << ans << endl;
return 0;
}