2021第三届传智杯决赛全题解
A - 课程
题⽬描述
传智专修学院提供 A,B 两个课程，分别有 n,m 个学⽣报名。报名 A 的学⽣的编号为 an ，报名 B 的学⽣的编号为 bm，求有多少个学⽣同时报名了两个课程。对于所有数据，
保证每个课程报名的学⽣编号不会重复。
输⼊格式
输⼊共 3 ⾏。
第 1 ⾏输⼊ 2 个正整数 n,m。
第 2 ⾏输⼊ n 个正整数 a1…an，表⽰报名课程 A 的学⽣编号。
第 3 ⾏输⼊ m 个正整数 b1…bm，表⽰报名课程 B 的学⽣编号。
输出格式
输出共 1 ⾏ 1 个整数，表⽰答案。
输⼊ #1
5 5
1 2 3 4 5
1 3 4 5 6
输出 #1
4
说明/提⽰
样例解释
我们发现，1,3,4,5 这 4 名学⽣同时报名了两门课程，所以答案是 4。
思路：数据不⼤，可以直接暴⼒，⼆重循环判断即可。数据⼤的话应该可以采⽤ “双指针” 算法。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[99],b[99],sum;
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++)
if(a[i]==b[j])  sum++;
}
cout<<sum<<endl;
return 0;
}
B - 序列
题⽬描述
传智专修学院有 n 名同学，每个同学都有⼀个数字 an 。同时还知道⼀个常数 k 。如果有两名同学，第 i 名同学和第 j 名同学，满⾜ i<j 且 ai x aj ≤ k，那么这两名同学就被称为“和谐的⼀对”。请问这些同学中，有多少对“和谐的⼀对”呢？
对于所有数据，n<=1e3，ai<=1e5，k<=1e9。
输⼊格式
输⼊共 2 ⾏。
第 1 ⾏输⼊两个正整数 n,k。
第 2 ⾏输⼊ n 个正整数 a1…an。
输出格式
输出共 1 ⾏ 1 个整数，表⽰答案。
输⼊ #1
5 5
1 2 3 4 5
输出 #1
4
说明/提⽰
样例解释
样例中，(1,2),(1,3),(1,4),(1,5) 这 4 对都是“和谐的⼀对”。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[1010],sum,k;
int main()
{
cin>>n;
scanf("%lld",&k);
for(int i=1; i<=n; i++)  cin>>a[i];
for(int i=1; i<n; i++) {
for(int j=i+1; j<=n; j++) {
if(a[i]*a[j]<=k)  sum++;
}
}
cout<<sum<<endl;
return 0;
}
C - ⼦串
题⽬描述
在传智的开发课堂上，希望您开发⼀款⽂档处理软件。给定 T 组询问，每次给定 2 个长度为 n,m 的只含英⽂字母的字符串 a,b，求 a 在 b 中的出现次数，相同字符不区分⼤⼩写。注意 a 是 b 中连续⼦序列。
输⼊格式
输⼊共 3T+1 ⾏。
第 1 ⾏输⼊ 1 个正整数 T。
接下来共 T 组输⼊，每组输⼊共 3 ⾏。
第 1 ⾏输⼊ 2 个正整数 n,m。
第 2 ⾏输⼊⼀个长度为 n 的字符串 a。
第 3 ⾏输⼊⼀个长度为 m 的字符串 b。
输出格式
输出共 T ⾏，第 i ⾏输出 1 个整数，表⽰询问 i 的答案。
输⼊ #1
5
3 10
abc
abcabcabca
2 10
aa
AAaAaaAaAa
5 5
AbCdE
eDcBa
5 5
abcde
ABCDE
3 10
aba
ABaBaAbaBA
输出 #1
3
9
1
4
说明/提⽰
// ***KMP算法***
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1000;
int n,m;
char a[N],b[N];
int f[N];
void init()
{
for(int i=1;i<=n;i++)
if(a[i]>='A'&&a[i]<='Z')
a[i]=a[i]+'a'-'A';
for(int i=1;i<=m;i++)
if(b[i]>='A'&&b[i]<='Z')
b[i]=b[i]+'a'-'A';
for(int i=2,j=0;i<=n;i++)
{
while(j&&a[i]!=a[j+1]) j=f[j];
if(a[i]==a[j+1]) j++;
f[i]=j;
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m>>a+1>>b+1;
init();
int cnt=0;
for(int i=1,j=0;i<=m;i++)
{
while(j&&b[i]!=a[j+1])  j=f[j];
if(b[i]==a[j+1]) j++;
if(j==n)
{
cnt++;
j=f[j];
字符串截取第几行
}
}
cout<<cnt<<endl;
}
return 0;
}
D - 打牌
题⽬描述
三名同学在学习编程的休息时间（编号 1,2,3）打扑克，每⼈⼀开始 n 张牌，牌⼀共 m 种，若⼲张相同的牌可以⼀起出。⼀开始由第⼀个⼈出，打出⾃⼰的牌⾥最⼩的牌。接下来，以玩家 1,2,3,… 的顺序轮流出牌，每⼈打出⼀组⽐上个⼈打出的牌⼤的，⾃⼰能打出的最⼩的牌，若没有则跳过。牌的⼤⼩是这么决定的：⼀组张数多的牌⽐张数少的牌⼤，如果张数同样多，那么点数⼤的牌⽐较⼤。例如，(1,1,1)>(3,3)> (2,2)>(4)>(1)。若⼀轮中，其余两个⼈都⽆法打出牌，则重新下次由打出最后⼀张牌的⼈开始打。谁最先打完所有的牌，谁就赢了。请问最后谁会胜利呢？输出胜者的编号。
对于所有数据，n,m≤50。
输⼊格式
输⼊共 4 ⾏。
第 1 ⾏输⼊ 2 个正整数 n,m。
第 2 到 4 ⾏，每⾏输⼊ n 个数，表⽰每个⼈⼀开始的牌。
输出格式
输⼊共 1 ⾏ 1 个正整数，表⽰胜者的编号。
输⼊ #1
10 3
1 3 3 1 3 3 1
2
3 3
3 2 1 2 2 3 3 1 1 2
2 2 1 2
3 1 2 3 3 1
输出 #1
3
说明/提⽰
样例中的玩法
第 1 回合：
【1】：1 3 3 1 3 3 1 2 3 3，打出 [1]
【2】：3 2 1 2 2 3 3 1 1 2，打出 [2]
【3】；2 2 1 2 3 1 2 3 3 1，打出 [3]
【1】：3 3 1 3 3 1 2 3 3，打出 [1,1]
【2】：3 1 2 2 3 3 1 1 2，打出 [2,2]
【3】；2 2 1 2 1 2 3 3 1，打出 [3,3]
【1】：3 3 3 3 2 3 3，打出 [3,3,3]
【2】：3 1 3 3 1 1 2，出不起【3】；2 2 1 2 1 2 1，打出 [2,2,2,2]【1】：3 2 3 3，出不起
【2】：3 1 3 3 1 1 2，出不起
第 2 回合：
【3】；1 1 1，打出 [1]
【1】：3 2 3 3，打出 [2]
【2】：1 3 3 1 1 2，打出 [3]【3】；1 1，打出 [1,1] <- 获胜
/
/ ***⼤模拟***
#include <bitsdc++.h>
using namespace std;
const int N=1e3+15;
typedef long long ll;
ll a[N],mp[70][70],ans[70];
ll n,m,cnt=1,x=0,f=0;
ll solve(ll k)
{
if(k==f) {
for(int i=1; i<=m; i++) {
if(mp[k][i]) {
mp[k][i]--;
ans[k]--;
cnt=1;f=k;x=i;
if(ans[k]==0)  return k;
return 0;
}
}
if(ans[k]==0)  return k;
else  return -1;
}
for(int i=1; i<=m; i++)
{
if(i>x&&mp[k][i]>=cnt)
{
mp[k][i]-=cnt;
f=k;    x=i;
ans[k]-=cnt;
if(ans[k]==0)  return k;
else  return -1;
}
}
for(int i=1; i<=m; i++)
{
if(mp[k][i]>cnt)
{
cnt++;
mp[k][i]-=(cnt);
f=k;  x=i;
ans[k]-=cnt;
if(ans[k]==0)  return k;
else  return -1;
}
}
return 0;
}
int main()
{
cin>>n>>m;
ans[1]=ans[2]=ans[3]=n;
for(int j=1; j<=3; j++) {
for(int i=1; i<=n; i++) {
cin>>x;
mp[j][x]++;
}
}
x=0;
ll op=0;
while(1) {
op++;
if(op>3)  op-=3;
ll okk=solve(op);
if(okk>0) {
cout<<okk<<endl;
return 0;
}
}
return 0;
}
E - 商店
题⽬描述
有 n 名同学去逛商店，店⾥有 m 个物品，第 i ⼈有 wi 块钱，第 i 个物品价格 ci 元。每个⼈⾄多买⼀个物品，每个物品只能被买⼀次，问最多有多少⼈能买到物品。对于所有数据，n,m<=1e5，wi,ci<=1e9。
输⼊格式
输⼊共 3 ⾏。
第 1 ⾏输⼊ 2 个正整数 n,m。
第 2 ⾏输⼊ n 个整数 w1…wn，wi 表⽰第 i ⼈的钱。
第 3 ⾏输⼊ m 个整数 c1…cm，ci 表⽰第 i 个物品的价格。
输出格式
对于所有数据，n,m<=1e5，wi,ci<=1e9。
输⼊ #1
15 20
4 3 9 10 7 7
5 3
6 1 8 6 6 1 5
12 4 1 9 8 5 8 6 4 5 18 8 14 9 9 7 20 11 8 19
输出 #1
10
思路：排序，从最⼩的开始，买的起就下⼀个，然后break；买不起，直接break。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
ll n,m,w[N],c[N],sum;
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)  cin>>w[i];
for(int i=1; i<=m; i++)  cin>>c[i];
sort(w+1,w+1+n);
sort(c+1,c+1+m);
for(int i=1,j=1; i<=n; i++)
{
if(w[i]>=c[j])
{
sum++;
j++;
}
}
printf("%lld",sum);
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。