上海理工大学第二届联想杯K题、C题和A题（set）题解
K题：azusa’s Party
题目描述
Hojo High School light music club has accomplished their final performance on stage. After the performance, Kazusa invites Haruki and Setsuna to her home to join a party.
As people in this party are not familiar with each other, Kazusa comes up with an idea: she gives an integer to everyone.
And a BOY with integer aaa can match a GIRL with integer bbb if and only if:
gcd(a,b)>1
Besides, a BOY can only match at most one GIRL.
As Kazusa is careless, different people may have the same integer. Now Kazusa wants to know the maximum number of matches she can get.
题目大意
在一个派对上，Kazusa想要帮男生与女生配对，他发了几张写有数字的卡片，当男生与女生上卡片的最大公因数不为1的时候，男生和女生就可以配对，问：男生和女生最大可以配对多少对
输入描述:
The first line contains one integer n(n≤8)n(n\leq 8)n(n≤8) indicating the number of boys and girls in this party.The second line contains nnn numbers indicating the integer of different boys.
The third line contains nnn numbers indicating the integer of different girls.
All integers are greater than 000 and smaller or equal to 10910^9109.
输入描述
输入的第一行是男生女生都有多少人（男生女生的数量一样），输入第二行是男生的卡片数字，输入的第三行是女生的卡片数字
输出描述:
Output one single integer indicating the maximum number of matches.
输出描述：
输出最多可以匹配多少对
示例1
输入
3
2 4 6
3 10 2
输出
3
示例2
输入
3
2 4 8
5 7 9
输出
0
题解思路：
图的最大匹配问题，首先想到匈牙利算法，在结合最大公因数来建立边的联系，就可以AC了
代码实现：
核心代码：匈牙利算法，如果对匈牙利算法不了解的小伙伴可以看看这篇博客
因为我也不太会QAQ
https://blog.csdn.net/dark_scope/article/details/8880547#commentBox
然后就是判断最大公因数是否为1的函数__gcd(x,y);
ps： gcd前面有两个下划线哦
步骤1：预处理
#include<bits/stdc++.h>
using namespace std;
const int INF = 505;
const int maxn=100;
int edge[INF][INF];//建图的数组
int n; //题目的输入
int arr[maxn];//存放男生的卡片数字
int brr[maxn];//存放女生的卡片数字
int main()
{
cin>>n;
memset(edge, -1, sizeof(edge));//初始化
for(int i=1;i<=n;i++)
{
cin>>arr[i]; //输入卡片数字存入数组中
}
for(int i=1;i<=n;i++)
{
cin>>brr[i];
}
步骤二：对关系进行判断并记录关系与建图数组中
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(__gcd(arr[i],brr[j])!=1)
edge[i][j]=1;
}
}
步骤三：匈牙利算法
int vx[INF], vy[INF];
int vis[INF]; //定义男生卡片数组和女生卡片数组和判断数组
memset(vx, -1, sizeof(vx));//初始化
memset(vy, -1, sizeof(vy));
int result = 0;
for(int u = 1; u <= n; u++) //对1到n进行dfs 遍历来实现匈牙利算法
{
memset(vis, 0, sizeof(vis));
result += dfs(u) ;
}
printf("%d\n", result) ;
return 0;
}
int dfs(int u) //匈牙利算法的深度优先搜索
{
for(int v = 1; v <= n; v++)
{
if(edge[u][v] == 1 && vis[v] == 0)
{
vis[v] = 1;
if(vy[v] == -1 ||dfs(vy[v]) == 1)
{
vx[u] = v;
vy[v] = u;
return 1;
}
}
}
return 0;
}
完整代码
#include<bits/stdc++.h>
using namespace std;
const int INF = 505;
const int maxn=100;
int dfs(int u);
int edge[INF][INF];
int n, k;
int arr[maxn];
int brr[maxn];
int vx[INF], vy[INF];
int vis[INF];
int main()
{
cin>>n;
memset(edge, -1, sizeof(edge));
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
for(int i=1;i<=n;i++)
{
cin>>brr[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(__gcd(arr[i],brr[j])!=1)
edge[i][j]=1;
}
}
memset(vx, -1, sizeof(vx));
memset(vy, -1, sizeof(vy));
int result = 0;
for(int u = 1; u <= n; u++)
{
memset(vis, 0, sizeof(vis));
result += dfs(u) ;
}
printf("%d\n", result) ;
return 0;
}
int dfs(int u)
{
for(int v = 1; v <= n; v++)
{
if(edge[u][v] == 1 && vis[v] == 0)
{
vis[v] = 1;
if(vy[v] == -1 ||dfs(vy[v]) == 1)
{
vx[u] = v;
vy[v] = u;
return 1;
}
}
}
return 0;
}
C题：Counting Cats!
链接：https://ac.nowcoder.com/acm/contest/17574/C
来源：牛客网
题目描述
As we all know, there are so many cats in USST!
They are so cute that many students will take a lot of photos of them, so it is a huge job to identify how many cats there are in each photo.
Now we will give you nnn strings which indicate some items in a photo, and you need to find how many cats in the photo.
In each string,“cat” means there’s a cat. However, some cats will hide on bush, so there may occur some parts of cat in the photo. Formally,“c”,“a”,“t”,“ca”,“at” means some part of cat appear, and if some of them can combine to the wordcat, we also regard it as a cat. Besides, there also may be other objects, so other strings will appear too.
题目大意
给你许多个字符串，其中有’c’,‘a’,‘t’,‘ca’,‘at’,‘cat’,问你最合理选取字符串让这些字符串合成最多的cat
输入描述:
On the first line, there’s a single integer n(1≤n≤2×105)n(1 \leq n \leq 2\times 10^5)n(1≤n≤2×105), indicating the number of strings.On the second line, there’s nnn strings separated by space, and it is guaranteed that the length of each string is no more than 10.
输出描述:
Only a single integer indicates the number of cat can be formed by strings.
示例1
输入
5
a c a cat cat
输出
2
示例2
输入
3
ca at a
输出
0
示例3
输入
9
ca ca c c t t at at uakioi
输出
4
示例4
输入
3
c a t
输出
1
解题思路
最开始做题我感觉不难，但是做完了发现身边好多人不会，可能是我和别人对这个题看法不一样，我的思路也就和我周围的人不怎么一样（笑死），我的思路是都丢进map里存起来，能先配对的就先配对，单字母最后配对，这样就能保证所得的cat最大化
代码：
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int n,m;
string str;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>str;
mp[str]++;
} //用map把每个字符串有多少个存起来
int a1=0,a2=0,a3=0;
a1=min(mp["ca"],mp["t"]); //先把双字母和单字母的先匹配掉
mp["ca"]-=a1; //然后记得这些字符串用过了，所以就把他减掉
mp["t"]-=a1;
a2=min(mp["c"],mp["at"]); //这个双字母也是一样
mp["c"]-=a2;
mp["at"]-=a2;
a3=min(mp["c"],mp["a"]);
a3=min(mp["t"],a3); //最后取单字母的最小值就是这些单字母说能匹配到的最大的cat了
int sum=0;
sum+=(a1+a2+a3+mp["cat"]); //最后的最后不要忘记把cat这个字符串的数量加上去
cout<<sum;
}
A题：A-SOUL!
虽说是签到，但我想了另一种方法来写这个（嘿嘿嘿）
One day, when small Diana is on live, a Super Chat asks her a very strange question.
Super Chat tells her that a lll-length sequence of numbers aia_iai is kkk-good if and only if ai=ai−1+ka_i=a_{i-1}+kai=ai−1+k holds for i∈[2,l]i \in [2,l]i∈[2,l], where kkk is a constant.
Then Super Chat gives her nnn numbers aia_iai and a number kkk. Diana needs to choose as many numbers as she can from {ai}{a_i}{ai} and put them into a new sequnce(in any order), so that the new sequence is kkk-good.
题目大意：
有n个数字，和一个数字k，问这n个数字可以选出多少个数组成以k为公差的等差数列
（注意：一个数也可以构成等差数列（样例不给我还真忽略了哈哈哈））
输入描述:
The first line gives you two integers n(1≤n≤105)n(1\leq n\leq 10^5)n(1≤n≤105) and k(1≤k≤109)k(1\leq k\leq 10^9)k(1≤k≤109), indicating the length of sequence and the constant.The second line gives you nnn numbers ai(1≤ai≤109)a_i(1\leq a_i\leq 10^9)ai(1≤ai≤109).
输出描述:
Only a single integer shows the maximum number of numbers Diana can choose from the given numbers.
示例1
输入
1 2
6
输出
1
示例2
输入
5 2
1 3 3 5 7
输出
4
解题思路：
由于可能有相同的，而且此题不需要去遍历，所以我选用了自动去重的set
步骤1：预处理
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
long long arr[maxn];
int brr[maxn];
set<int>s;
int main()
{
long long n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
s.insert(arr[i]); //把数字存到数组和set里面
}
int ans=1;
sort(arr+1,arr+n+1); //对arr数组进行sort以至于每次访问到的都会是让等差数列首项最小的
步骤2：对arr数组进行遍历
让arr数组的每一个数作为等差数列首项，看sort里面有没有值使他构成等差数列
for(int i=1;i<=n;i++)
{
int cnt=1;
for(int j=arr[i];j<=arr[n];) //遍历arr
{
if(s.find(j+k)!=s.end()) //当set里不存在这个值就退出，进行arr的下一个循环
{
s.erase(j);
j+=k;
cnt++;
}
else
{
break;
}
}
brr[ans]=cnt; //计数器啥的懂得都懂哈
ans++;
}
ps：这里面最重要的一步是s.erase(j),没有的话就要超时
因为我们是从最小找的，所以如果能找到，那么就是这个数所能在的最长的等差数列里面，这个值用掉了就不需要再用了，就算再用所形成的数组也不会比这个大，所以直接erase掉，这样可以减少大多数不必要的查询
步骤三：当然是输出结果啦，不过要先排序再输出哦
sort(brr+1,brr+ans+1);
cout<<brr[ans];
}
完整代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
long long arr[maxn];
int brr[maxn];
set<int>s;
int main()
{
long long n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
s.insert(arr[i]);
}
int ans=1;
sort(arr+1,arr+n+1);
for(int i=1;i<=n;i++)
{
int cnt=1;
for(int j=arr[i];j<=arr[n];)
{
if(s.find(j+k)!=s.end())
{
s.erase(j);
j+=k;
cnt++;
}
else
{
break;
}
}
brr[ans]=cnt;
ans++;
}
sort(brr+1,brr+ans+1);
cout<<brr[ans];
}