第6届传智杯复赛第一场
A小红劈字符串题目链接
题目链接：A-小红劈字符串（B组）_第6届传智杯复赛第一场（补题） (nowcoder.com)
题目形貌
小红拿到了一个仅由小写字母构成的字符串，她希望将其分割成两个非空子串，使得第一部分的长度是第二部分的两倍。
你必要判断是否存在合法分割方案，若存在则输出分割结果，否则输出 -1。
输入输特别式
[*]输入：一个长度不超过 10e5 的字符串。
[*]输出：
[*]若存在合法分割，输出两个子串，用空格分隔。
[*]若无解，输出 -1。
示例
输入输出阐明abcab c第一部分长度2，第二部分1ad-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 22\n3 5真品为2，赝品为3和54\n9 9 2 91\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;
for(int i=1;i<=n;i++)
{
cin>>m;
ssr++;
if(ssr==1)
{
sum=m;
num=op;
op++;
}
else
{
sum]=0;
}
}
sort(sum,sum+op,cmp);
int i=0;
for(;;i++)
{
if(sum!=0)
{
break;
}
}
cout<<op-i<<endl;
for(;i<=op-2;i++)
{
if(sum!=0)
{
cout<<sum<<" ";
}
}
if(sum!=0)
{
cout<<sum;
}
}
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 41将4拆分为2和2，得到 原代码分析
代码思路
#include <bits/stdc++.h>
using namespace std;
void solve() {
int sum, n;
cin >> n;
for (int i = 0; i < n; i++) cin >> sum;
sort(sum, sum + n);
// 从最小值开始枚举可能的公约数
for (int i = sum; 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∈,b−ai∈,b-ai∈,b−a是定值。例如，"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;
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>op1)
{
op1=ssr;
}
if(ssr<op2)
{
op2=ssr;
}
}
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();
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]