牛客小白月赛32部分题题解
这次小白赛由于放在周六，所以没时间去打。
稍微做了几题，看了一下题解，好像大部分是码量较大的题。这里稍微做了几道记录一下。
- A 拼三角
题目大意：
给6根棍子，问能不能找出3根组成一个三角形，同时剩下的3根也能组成三角形？
思路：
一开始的时候觉得拍个序找最小的3根组成三角形和较大的3根组成三角形就可以了。结果返回一发wa，后来发现是有反例的。
那么还是暴力枚举吧，枚举其中的3根，然后看剩下的3根是否能同时组成三角形。
复杂度O(n^4)
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
int a[11],vis[11];
while(t--){
int flag=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=6;i++)cin>>a[i];
sort(a+1,a+7);
for(int i=1;i<=6;i++){
for(int j=i+1;j<=6;j++){
for(int k=j+1;k<=6;k++){
if(a[i]+a[j]>a[k]){
vis[i]=vis[j]=vis[k]=1;
int x[4],t=0;
for(int l=1;l<=6;l++){
if(!vis[l])x[++t]=a[l],vis[l]=1;
}
if(x[1]+x[2]>x[3]){
flag=1;break;
}
if(flag)break;
}
memset(vis,0,sizeof(vis));
}
}
}
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}- C 消减整数
题目大意：
给一个数n，从1开始减，第一次必须减1，每次减的数字都必须和上一次相同或者是上一次的两倍，请问最少需要几次能把H恰好减到0。
思路：
应该会有一个比较贪心的想法，如果能剪下，就是尽量让被减的数乘2去减。如果减不下了，那么剩下的数我可以在之前的时候选择不乘2然后减掉。那么之前要减多少次呢？显然如果剩下的数为x,我们只要对x进行二进制转换枚举1的个数就好了，有多少个1就是再减多少次。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--){
int x;
cin>>x;
int ans=1;
long long now=1;
x--;
while(x){
if(x>=now*2){
now*=2;
x-=now;
}
else {
while(x){
int r=x%2;
if(r==1)ans++;
x/=2;
}
break;
}
ans++;
}
cout<<ans<<endl;
}
return 0;
}- E 春游
题目大意：
有n个人坐船，如果做双人船一艘船要a元，坐三人船一艘船要b元。可以不坐满，问最少花费。
思路：
这道题目感觉很简单，但是就是写不对！
思路不好，其实如果分不清楚，把所有情况都列一下找最小值也是一个办法。
我们可以通过比较a/2和b/3的大小，判断选双人还是三人。
如果a/2<b/3，我们先选双人，此时可能会多出来一个人，这个时候我们可以让这个人自己坐一个双人，或者拿出前面的2人拼成3人船。
如果a/2>b/3，先选3人，此时可能多出来1个或者2个。
如果多出来1个，我们可以让他自己坐1个3人或者1个双人，或者拿出前面的3人拼成2个双人（共4人）；
如果多出来2个，我们可以让他们坐1个3人或者1个双人，或者拿出前面的3人拼成3个双人
代码：
#include<bits/stdc++.h>
using namespace std;
long long a,b,n;
long long solve(long long n){
long long ans=0;
if(n<6){
if(n<=2)ans+=min(a,b);
else {
if(n==3){
ans=min(2*a,b);
}
if(n==4){
ans=min(2*a,a+b);
ans=min(ans,2*b);
}
if(n==5){
ans=min(3*a,a+b);
ans=min(ans,2*b);
}
}
}
return ans;
}
int main()
{
int T;
cin>>T;
while(T--){
cin>>n>>a>>b;
long long ans=0;
if(3*a<2*b){
if(n%2==0)ans+=(n/2)*a;
else {
ans=min((n/2)*a+a,(n/2)*a-a+b); //多余1人开双人，找2人拼3人
}
}
else {
if(n%3==0)ans+=(n/3)*b;
else if(n%3==1){
ans=min((n/3)*b+a,(n/3)*b+b); //多余1人开3人，多余1人开双人，
ans=min(ans,(n/3)*b-b+2*a);//找3人拼2个双人
}
else {
ans=min((n/3)*b+a,(n/3)*b+b); //多余2人开双人，多余2人开三人
ans=min(ans,(n/3)*b-b+3*a);//找3人拼3个双人
}
}
if(n<=2)ans=min(a,b);
cout<<ans<<endl;
}
}- F 五连珠
题目大意：
给两个5*5矩阵，每个格子上随机放了1 ~ 25中的一个整数。给出一个序列由1~25组成，每次读取序列中的一个数字就在两个矩阵中分别找到这个数字所在的位置，然后把这个数字划掉。
问：当矩阵中的某一行或某一列或主对角线或副对角线上的数字都被划掉，就输出先满足条件的那个矩阵，如果两个同时满足输出0。
思路：
数据很小，直接暴力也可以做。
我这边是map记录下每个数字在矩阵中的行和列所在的位置。然后枚举序列中的数，每划掉一个判断当前所在行和列是否满了，还有判断主副对角线是否满了。
代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int row1[10],col1[10],row2[10],col2[10],d1,d2,dd1,dd2;
map<string,pair<int,int> >p1,p2;
int main()
{
int T;
cin>>T;
while(T--){
memset(row1,0,sizeof(row1));
memset(row2,0,sizeof(row2));
memset(col2,0,sizeof(col2));
memset(col1,0,sizeof(col1));
d1=d2=dd1=dd2=0;
p1.clear();p2.clear();
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
cin>>s;
p1[s]=make_pair(i,j);
}
}
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
cin>>s;
p2[s]=make_pair(i,j);
}
}
string c;
int flag=0,tt=0;
for(int i=1;i<=25;i++){
cin>>c;
int x,y;
x=p1[c].first;
y=p1[c].second;
row1[x]++;
col1[y]++;
if(x==y)d1++;
if(x+y==4)dd1++;
if((row1[x]==5||col1[y]==5)||(d1==5||dd1==5))flag++;
x=p2[c].first;
y=p2[c].second;
row2[x]++;
col2[y]++;
if(x==y)d2++;
if(x+y==4)dd2++;
if((row2[x]==5||col2[y]==5)||(d2==5||dd2==5))flag+=2;
if(flag>0){
tt=flag;
flag=-100000;
}
}
if(tt==3)cout<<0<<endl;
else cout<<tt<<endl;
}
return 0;
}-J 统计个数
题目大意：
给出n个点m条边，问有多少条线和三角形。
具体线和三角形的定义可以参考题目。
思路：
根据定义，其实线就是两条相邻的边组成一条新的线，三角形就是看这条新的线两端有没有一条线连成一个环。
发现点的数量比较少，我们可以直接枚举边。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int mp[222][222],v[10000009];
int main()
{
int T;
cin>>T;
while(T--){
memset(v,0,sizeof(v));
memset(mp,0,sizeof(mp));
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
mp[a][b]=mp[b][a]=1;
}
int p,q;
p=q=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]){
for(int k=1;k<=n;k++){
if(mp[j][k]&&i!=k){
int tmp=i*44100+j*210+k; //简单的判重
if(!v[tmp]){
q++;
if(mp[i][k])p++;
}
v[tmp]=1;
tmp=k*44100+j*210+i;
v[tmp]=1;
}
}
}
}
}
int x=__gcd(p,q);
p=p/x;q=q/x;
if(p==0)cout<<"0/1"<<endl;
else
cout<<p<<"/"<<q<<endl;
}
}
投递莉莉丝游戏等公司7个岗位 >