第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）。
  

代码：

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long  
4. #define ull unsigned long long
6. void solve() {
7.     string ssr;
8.     cin>>ssr;
9.     int n=ssr.length();
10.     if(n%3!=0)
11.     {
12.         cout<<-1;
13.         return;
14.     }
15.     else
16.     {
17.         cout<<ssr.substr(0,n/3*2)<<" "<<ssr.substr(n/3*2,n/3);
18.     }
19. }
21. signed main() {
22.     ios::sync_with_stdio(0);
23.     cout.tie(0);
24.     cin.tie(0);
26.     ll t = 1;
27.     // std::cin >> t;
28.     while (t--) {
29.         solve();
30.     }
31. }

复制代码

 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)。
  

---

代码实现

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long  
4. #define ull unsigned long long
5. bool cmp(int a,int b)
6. {
7.     return a<b;
8. }
9. void solve() {
10.     map<int,int> ssr;
11.     map<int,int> num;
12.     int n,m,op=0;
13.     cin>>n;
14.     int sum[100010];
15.     for(int i=1;i<=n;i++)
16.     {
17.         cin>>m;
18.         ssr[m]++;
19.         if(ssr[m]==1)
20.         {
21.             sum[op]=m;
22.             num[m]=op;
23.             op++;
24.             
25.         }
26.         else
27.         {
28.             sum[num[m]]=0;
29.         }
31.     }
32.         sort(sum,sum+op,cmp);
33.         int i=0;
34.         for(;;i++)
35.         {
36.             if(sum[i]!=0)
37.             {
38.                 break;
39.             }
40.         }
41.         cout<<op-i<<endl;
42.         for(;i<=op-2;i++)
43.         {
44.             if(sum[i]!=0)
45.             {
46.                 cout<<sum[i]<<" ";
47.             }
48.         }
49.         
50.           if(sum[op-1]!=0)
51.             {
52.                 cout<<sum[op-1];
53.             }
54.    
55. }
57. signed main() {
58.     ios::sync_with_stdio(0);
59.     cout.tie(0);
60.     cin.tie(0);
62.     ll t = 1;
63.     // std::cin >> t;
64.     while (t--) {
65.         solve();
66.     }
67. }

复制代码

C小红的数字分裂

题目形貌

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

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

示例

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

---

原代码分析

代码思路

1. #include <bits/stdc++.h>
2. using namespace std;
4. void solve() {
5.     int sum[100010], n;
6.     cin >> n;
7.     for (int i = 0; i < n; i++) cin >> sum[i];
8.     sort(sum, sum + n);
10.     // 从最小值开始枚举可能的公约数
11.     for (int i = sum[0]; i >= 1; i--) {
12.         if (i == 1) { // 特殊情况处理
13.             int total = 0;
14.             for (int x : sum) total += x - 1;
15.             cout << total;
16.             return;
17.         }
18.         bool valid = true;
19.         for (int x : sum) {
20.             if (x % i != 0) {
21.                 valid = false;
22.                 break;
23.             }
24.         }
25.         if (valid) {
26.             int cnt = 0;
27.             for (int x : sum) cnt += x / i - 1;
28.             cout << cnt;
29.             return;
30.         }
31.     }
32. }

复制代码

D红的字符串同构

题目形貌

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

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

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

复制代码

输出形貌:

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

复制代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long  
4. #define ull unsigned long long;
5. int sum[100010];
6. ll ans=1e9+7;
7. ll answer=1;
8. void solve() {
9.     string ssr;
10.     cin>>ssr;
11.     int n=ssr.length();
12.     if(n==1)
13.     {
14.         cout<<0;
15.         return;
16.     }
17.     else
18.     {
19.         char op1='a';
20.         char op2='z';
21.         for(int i=0;i<=n-1;i++)
22.         {
23.             if(ssr[i]>op1)
24.             {
25.                 op1=ssr[i];
26.             }
27.             if(ssr[i]<op2)
28.             {
29.                 op2=ssr[i];
30.             }
31.         }
32.         int num=(int)('z'-op1)+(int)(op2-'a');
33.         
34.         for(int i=1;i<=n;i++)
35.         {
36.             answer*=25;
37.             answer%=ans;
38.         }
39.         if(answer>num)
40.         {
41.             answer-=num;
42.         }
43.         else
44.         {
45.             answer+=(ans-num);
46.         }
47.         cout<<answer;
48.     }
49. }
51. signed main() {
52.     ios::sync_with_stdio(0);
53.     cout.tie(0);
54.     cin.tie(0);
56.     ll t = 1;
57.     // std::cin >> t;
58.     while (t--) {
59.         solve();
60.     }
61. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。