第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
因此，合法分割的必要条件是：
- n 必须是3的倍数（即 n%3=0）。
- 分割后两部分均非空（即 k≥1）。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
void 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。
- 时间复杂度：统计次数需 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();
}
}