第6届传智杯复赛第一场

A小红劈字符串

题目链接

题目链接：A-小红劈字符串（B组）_第6届传智杯复赛第一场（补题） (nowcoder.com)

---

题目描述

小红拿到了一个仅由小写字母组成的字符串，她希望将其分割成两个非空子串，使得第一部分的长度是第二部分的两倍。
你需要判断是否存在合法分割方案，若存在则输出分割结果，否则输出 -1。

输入输出格式

• ​输入：一个长度不超过 10e5 的字符串。
• ​输出：
  • 若存在合法分割，输出两个子串，用空格分隔。
  • 若无解，输出 -1。

示例

输入	输出	说明
abc	ab c	第一部分长度2，第二部分1
ad	-1	总长度2，无法满足条件

---

解题思路

数学推导

设字符串总长度为 n，第二部分长度为 k，则第一部分长度需为 2k。
根据题意，总长度满足：

2k+k=n⇒3k=n⇒k=3n​

因此，​合法分割的必要条件是：

1. n 必须是3的倍数（即 n%3=0）。
2. 分割后两部分均非空（即 k≥1）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
#define ull unsigned long longvoid solve() {string ssr;cin>>ssr;int n=ssr.length();if(n%3!=0){cout<<-1;return;}else{cout<<ssr.substr(0,n/3*2)<<" "<<ssr.substr(n/3*2,n/3);}
} signed main() {ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);ll t = 1; // std::cin >> t;while (t--) {solve();}
}

 B赝品

题目链接

牛客网竞赛72647-B题
题目链接：https://ac.nowcoder.com/acm/contest/72647/B

---

题目描述

给定一批商品，每个商品有一个型号。已知真品的型号至少出现两次，而赝品的型号只出现一次。要求找出所有赝品的型号并按升序输出。

输入输出格式

• ​输入：
  • 第一行：整数 n 表示商品总数。
  • 第二行：n 个正整数，表示每个商品的型号。
• ​输出：
  • 第一行：赝品数量 k。
  • 第二行：k 个按升序排列的赝品型号。

示例

输入	输出	说明
5\n2 5 3 2 2	2\n3 5	真品为2，赝品为3和5
4\n9 9 2 9	1\n2	真品为9，赝品为2

---

解题思路

核心逻辑

1. ​统计出现次数：遍历所有型号，统计每个型号的出现次数。
2. ​筛选赝品：收集所有出现次数为1的型号。
3. ​排序输出：对赝品型号升序排序后输出。

数学验证

• 真品出现次数 ≥ 2，赝品出现次数 = 1。
• 时间复杂度：统计次数需 O(n)，排序需 O(klogk)，总复杂度为 O(n+klogk)。

---

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
#define ull unsigned long long
bool cmp(int a,int b)
{return a<b;
}
void solve() {map<int,int> ssr;map<int,int> num;int n,m,op=0;cin>>n;int sum[100010];for(int i=1;i<=n;i++){cin>>m;ssr[m]++;if(ssr[m]==1){sum[op]=m;num[m]=op;op++;}else{sum[num[m]]=0;}}sort(sum,sum+op,cmp);int i=0;for(;;i++){if(sum[i]!=0){break;}}cout<<op-i<<endl;for(;i<=op-2;i++){if(sum[i]!=0){cout<<sum[i]<<" ";}}if(sum[op-1]!=0){cout<<sum[op-1];}} signed main() {ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);ll t = 1; // std::cin >> t;while (t--) {solve();}
}

C小红的数字分裂

题目描述

小红有一个整数数组，她可以通过将某个元素 x 拆分为两个整数 a 和 b（满足 a + b = x）来增加数组长度。要求找到使数组中所有元素相等所需的最少操作次数。

输入输出格式

• ​输入：
  • 第一行：整数 n 表示数组长度。
  • 第二行：n 个正整数表示数组元素。
• ​输出：最少操作次数。

示例

输入	输出	说明
2\n2 4	1	将4拆分为2和2，得到[2,2,2]

---

原代码分析

代码思路

#include <bits/stdc++.h>
using namespace std;void solve() {int sum[100010], n;cin >> n;for (int i = 0; i < n; i++) cin >> sum[i];sort(sum, sum + n);// 从最小值开始枚举可能的公约数for (int i = sum[0]; i >= 1; i--) {if (i == 1) { // 特殊情况处理int total = 0;for (int x : sum) total += x - 1;cout << total;return;}bool valid = true;for (int x : sum) {if (x % i != 0) {valid = false;break;}}if (valid) {int cnt = 0;for (int x : sum) cnt += x / i - 1;cout << cnt;return;}}
}

D红的字符串同构

题目描述

小红定义两个字符串同构，当且仅当对于i∈[1,n],b[i]−a[i]i∈[1,n],b[i]-a[i]i∈[1,n],b[i]−a[i]是定值。例如，"bacd"和"edfg"是同构的。

现在小红拿到了一个长度为nnn的字符串aaa，她想知道，有多少长度为nnn的字符串bbb同时满足以下两个条件：
1.bbb的每一位都和aaa不同。
2.bbb和aaa不同构。

输入描述:

输入一个仅由英文小写字母组成的字符串，代表字符串aaa。
字符串长度不超过10510^5105。

输出描述:

一个整数，代表合法的字符串bbb的数量。由于答案过大，请对109+710^9+7109+7取模。

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
#define ull unsigned long long;
int sum[100010];
ll ans=1e9+7;
ll answer=1;
void solve() {string ssr;cin>>ssr;int n=ssr.length();if(n==1){cout<<0;return;}else{char op1='a';char op2='z';for(int i=0;i<=n-1;i++){if(ssr[i]>op1){op1=ssr[i];}if(ssr[i]<op2){op2=ssr[i];}}int num=(int)('z'-op1)+(int)(op2-'a');for(int i=1;i<=n;i++){answer*=25;answer%=ans;}if(answer>num){answer-=num;}else{answer+=(ans-num);}cout<<answer;}
} signed main() {ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);ll t = 1; // std::cin >> t;while (t--) {solve();}
}