小白月赛33题解
A、字符统计
解析：
用getline(cin,s)函数读取整行字符串直到遇到换行符
行数：每输入一行，行数+1
单词个数：因为单词是空格或者换行符隔开的连续字符，所以只用从0~len-2扫一遍字符串，只要s[i]不为空格且s[i+1]为空格的就是单词，结尾的单词特判（len！=0，单词数+1）
字符数：s.size()
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d ",&T);
string s;
int n=0,m=0,q=0;//n:行数 m：单词数 q：字符数
while(getline(cin,s)){
if(s == "====="){
cout<<n<<' '<<m<<' '<<q<<endl;
n=0;
m=0;
q=0;
continue;
}
n++;
int len=s.size();
for(int i=0;i<len-1;i++)
if(s[i] != ' ' && s[i+1] == ' ')
m++;
if(len != 0) //特判结尾的单词
m++;
q+=len;
}
cout<<n<<' '<<m<<' '<<q<<endl;
}B、连分数
解析：
先把分母部分当成一个整体m
第一步求a：
a是带分数的整数部分，a=P/Q（取整）
第二步求m：
第三步：
将得到的分数的分子（Q）赋值给P，分母（P-aQ）赋值给Q，重复步骤一、二、三直到P%Q==0
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,a;
cin>>T;
while(T--){
int p,q,sum=0;
bool boo=false;
cin>>p>>q;
cout<<p<<'/'<<q<<" = ";
while(p%q != 0){
a=p/q;
if(! boo)
cout<<a<<"+1/";
else
cout<<"{"<<a<<"+1/",sum++;
boo=true;
int t;
t=p-a*q;
p=q;
q=t; //分子分母重新赋值
}
cout<<p/q;
while(sum--) //sum为统计的'{'个数，输出相应个数的'}'
cout<<'}';
cout<<endl;
}
}C、挪酒瓶
解析：
我们先假想一种情况：有两排位置，第一排N个位置放酒，第二排是N个空位置，我们现在要做的是把第一排的酒放到第二排中对应的空位置上，在所有的酒位置都打乱的情况下我们花费的体力为
但是实际情况是只有一排位置，我们在把酒放到相应位置的同时还需要额外搬动当前位置上的酒瓶，我们当然希望额外消耗的体力越小越好，所以我们每次都优先把目标位置是最小酒瓶所处位置的大酒瓶搬过来，最优的情况是最小重量的酒瓶（重量记为m1）是最后一次交换时放对位置的，这是我们消耗的体力为
最优情况其实就是整个序列只包含一个置换群，但是实际情况是序列会包含一个到多个的置换群，现在我们讨论序列只包含两个置换群的情况（记两个置换群的大小分别为a、b，两个置换换群中最小酒瓶的重量分别为m1、m2），按照我们之前的策略，可以计算出消耗的体力为
但是这个策略一定是最优的吗？
答案：不是
对于已经放好的第一个置换群，我们可以把当中最小重量的酒瓶（m1）与第二个置换群中重量最小的酒瓶（m2）交换位置，额外花费的体力为（m1+m2),组成一个大小为b的新置换群，再按照我们之前的策略摆放酒瓶，可以计算出花费的体力为
说明：（m1+m2）*2是交换两个最小重量酒瓶两次，一次交换，一次复原
+m1-m2是因为生成的新置换群中拿出了重量为m1的酒瓶而放入了重量为m的酒瓶，但是前面累加重量时全算上了
当满足下式时，显然我们原来的策略并不是最优的
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[100005],w[100005],v[100005];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
v[i]=0;
if(p[i] == i)
v[i]=1;
}
int m1=105;
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
m1=min(m1,w[i]);
}
for(int i=1;i<=n;i++){
if(v[i])
continue;
int x=i,m2=105,cnt=0;
while(!v[x]){
v[x]=1;
sum+=w[x];
m2=min(m2,w[x]);
x=p[x];
cnt++;
}
sum+=min(m2*(cnt-2),(cnt-2)*m1+2*(m1+m2)-m2+m1);
}
cout<<sum<<endl;
}
}D、购物
解析：
先假设每个人把每种商品都买一遍，输入每个人已有某种商品时再把该商品数+1
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int sum=0;
map<string,int>M;
map<string,int>M1; //M代表每种商品数目，M1代表是否统计过该商品
int s,n,a;
string str;
cin>>s>>n;
for(int i=1;i<=s;i++){
cin>>str>>a;
M[str]=a;
M[str]-=n; //每个人都买一遍
if((M[str] > 0) && M1[str]==0){
sum++;
M1[str]=1;
}
}
for(int i=1;i<=n;i++){
cin>>a;
for(int j=1;j<=a;j++){
cin>>str;
M[str]++;
if((M[str] > 0) && M1[str]==0){
sum++;
M1[str]=1;
}
}
}
if(sum > 0)
cout<<sum<<endl;
else
cout<<"Need to be lucky"<<endl;
}
}E、喝可乐
解析：
从0到N枚举购买蜂蜜可乐的数量，记录最大能喝的可乐瓶数即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int n,a,b;
cin>>n>>a>>b;
int sum=0,t;
int A,B;
for(int i=0;i<=n;i++){
t=0; //总共能得到的可乐数量
A=i; //蜂蜜可乐数量
B=n-i; //生姜可乐数量
while(A >= a || B >= b){ //换到不能再换购为止
t+=A/a;
B+=A/a;
A%=a;
t+=B/b;
A+=B/b;
B%=b;
}
sum=max(sum,t);
}
cout<<sum+n<<endl;
}
}F、天旋地转
解析：
Next[4][2]={0,1,1,0,0,-1,-1,0}代表前、右、后、左，
d1,d2,d3,d4代表w,d,s,a四个方向，初始状态：
d1指向Next[0]
d2指向Next[1]
d3指向Next[2]
d4指向Next[3]
为什么这样做？因为世界在变，当世界顺时针旋转了90度，你的前方还是你的前方吗，不是！他是你原来的左边，你的左边呢？它变成了你原来的后面......，所以当世界顺时针旋转了90度后，状态变为：
d1指向Next[3]
d2指向Next[0]
d3指向Next[1]
d4指向Next[2]
当世界顺时针旋转了180度后，状态变为：
d1指向Next[2]
d2指向Next[3]
d3指向Next[0]
d4指向Next[1]
当世界顺时针旋转了270度后，状态变为：
d1指向Next[1]
d2指向Next[2]
d3指向Next[3]
d4指向Next[0]
当世界顺时针旋转了360度后，你的世界又变回来了：
d1指向Next[0]
d2指向Next[1]
d3指向Next[2]
d4指向Next[3]
逆时针旋转同理......
AC代码
#include<bits/stdc++.h>
using namespace std;
long long Next[4][2]={0,1,1,0,0,-1,-1,0};
int main(){
int T;
cin>>T;
while(T--){
char a;
long long k,n,x=0,y=0,d1=0,d2=1,d3=2,d4=3; //不开long long 会爆
cin>>n;
while(n--){
cin>>a>>k;
if(a == 'w')
x+=Next[d1][0]*k,y+=Next[d1][1]*k;
if(a == 'd')
x+=Next[d2][0]*k,y+=Next[d2][1]*k;
if(a == 's')
x+=Next[d3][0]*k,y+=Next[d3][1]*k;
if(a == 'a')
x+=Next[d4][0]*k,y+=Next[d4][1]*k;
if(a == 'r')
k%=4,d1=(d1+4-k)%4;
if(a == 'l')
d1=(d1+k)%4;
d2=(d1+1)%4;
d3=(d2+1)%4;
d4=(d3+1)%4;
}
cout<<x<<' '<<y<<endl;
}
}I、三角尼姆
解析：
一共可操作的情况就4种：（1，1）、（1，3）、（3，1）、（3，3），题目没说A同学和B同学都选择最优策略下棋，这说明什么？这说明不管以何种方式下棋都不会对最后的结果产生影响，那为什么我们不选择最快乐的方式，你一枚、我一枚、你一枚、我一枚......
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
n=(n+1)*n/2;
if(n%2 == 1)
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
}J、线段的交
解析：
如果已知两条线段相交，如何求面积：
将四边形化成两个三角形，因为四个点坐标我们都知道，所以这两个三角形的每一条边的边长我们都可以算出来
根据公式：
很容易可以求出四边形的面积
关键在于如何判断两线段是否相交
为方便描述，用a、b代表线段1两端点，用c、d代表线段2两端点，因为两线段相交，则c、d两点必定在线段1两侧，这里可以用到叉乘，首先我们要明白一个定理：向量a×向量b（×为向量叉乘），若结果小于0，表示向量b在向量a的顺时针方向；若结果大于0，表示向量b在向量a的逆时针方向；若等于0，表示向量a与向量b平行。（等于0的情况不考虑，题目已保证无三点共线），当（向量ab×向量ac）与（向量ab×向量ad）异号时，c、d两点在线段1两侧，同理还需要判断a、b在线段2两侧，只有同时满足这两个条件，线段1、2才相交
AC代码
#include<bits/stdc++.h>
using namespace std;
struct node{
double x,y;
}e[5];
int cha(node m,node n){
return (m.x*n.y-m.y*n.x)>0?1:-1;
}
double len(node m,node n){
return sqrt((m.x-n.x)*(m.x-n.x)+(m.y-n.y)*(m.y-n.y));
}
int main(){
for(int i=1;i<=4;i++)
cin>>e[i].x>>e[i].y;
node t1,t2,t3,t4,t5,t6;
t1.x=e[4].x-e[1].x;
t1.y=e[4].y-e[1].y;
t2.x=e[2].x-e[1].x;
t2.y=e[2].y-e[1].y;
t3.x=e[3].x-e[1].x;
t3.y=e[3].y-e[1].y;
t4.x=e[1].x-e[3].x;
t4.y=e[1].y-e[3].y;
t5.x=e[4].x-e[3].x;
t5.y=e[4].y-e[3].y;
t6.x=e[2].x-e[3].x;
t6.y=e[2].y-e[3].y;
if(cha(t2,t1)*cha(t2,t3) > 0 || cha(t5,t4)*cha(t5,t6) > 0)
cout<<0<<endl;
else{
double a,b,c,s=0,cosC,sinC;
a=len(e[1],e[4]);
b=len(e[1],e[3]);
c=len(e[3],e[4]);
cosC=(a*a+b*b-c*c)/(2*a*b);
sinC=sqrt(1-cosC*cosC);
s+=0.5*a*b*sinC;
a=len(e[2],e[4]);
b=len(e[2],e[3]);
cosC=(a*a+b*b-c*c)/(2*a*b);
sinC=sqrt(1-cosC*cosC);
s+=0.5*a*b*sinC;
printf("%.10lf\n",s);
}
}
美团公司氛围 509人发布
投递美团等公司10个岗位 >
查看4道真题和解析