天梯赛模拟训练【3】
A.7-1 计算摄氏温度 (5分)
签到：
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"fahr = 100, celsius = ";
cout<<5 * (100-32)/9<<endl;
return 0;
} B.7-2 后天 (5分)
思路：取余，注意周五不能让其取余为0.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
if(n == 5) cout<<"7"<<endl;
else cout<<(n+2)%7<<endl;
return 0;
} C.7-3 奇偶分家 (10分)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int res;
int o =0;
int q=0;
for(int i=1;i<=n;i++){
cin>>res;
if(res % 2 == 1) q++;
else o++;
}
cout<<q<<" "<<o<<endl;
return 0;
} D.7-4 大笨钟 (10分)
#include<bits/stdc++.h>
using namespace std;
main()
{
int m, n,h,i,k;
char c;
scanf("%d%c%d", &m, &c, &n);
if (m >= 13 && m < 24)
{
h = m - 12;
if (n != 0) k = h + 1;
else if (n == 0) k = h;
for (i = 0; i < k; i++){
printf("Dang");
}
}
else
printf("Only %02d:%02d. Too early to Dang.",m,n);
return 0;
}E.7-5 一帮一 (15分)
思路：一个从前往后遍历，一个从后往前，要设置一个flag，表示当前这个人是否匹配成功，当都匹配成功后就break。
#include<stdio.h>
struct node
{
int sex;
char name[10];
int flag;
}data[51];
int main()
{
int n;
int count=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %s",&data[i].sex,&data[i].name);
data[i].flag=0;
}
for(int i=0;i<n/2;i++)
{
for(int j=n-1;j>=n/2;j--)
{
if((data[i].sex!=data[j].sex)&&data[i].flag==0&&data[j].flag==0)
{
data[i].flag =1;
data[j].flag =1;
count=count+2;
printf("%s %s\n",data[i].name ,data[j].name );
}
}
if(count==n)
break;
}
return 0;
}F.7-6 幸运彩票 (15分)
#include<bits/stdc++.h>
using namespace std;
bool solve(string s){
if(s[0]-'0' + s[1]-'0' +s[2]-'0' == s[3]-'0'+s[4]-'0'+s[5]-'0') return true;
else return false;
}
int main(){
int n;
cin>>n;
string res;
while(n--){
cin>>res;
if(solve(res)) cout<<"You are lucky!"<<endl;
else cout<<"Wish you good luck."<<endl;
}
return 0;
} G.7-7 阅览室 (20分)
思路：模拟。设置一个vis[]记录是否用书还书。
#include<bits/stdc++.h>
using namespace std;
int ti[1005];
bool vis[1005];
int main(){
int day,n=0,id,th,tm;
int E=0,T=0;
char s[2];
scanf("%d",&day);
while(scanf("%d%s%d:%d",&id,s,&th,&tm)!=EOF){
if(id==0){
n++;
printf("%d %.0f\n",E,E==0?E:T * 1.0/E);
E=0,T=0;
memset(vis,false,sizeof vis);
continue;
}
if(day==n) break;
if(s[0]=='S') ti[id]=th*60+tm,vis[id]=true;
else if(s[0]=='E'&&vis[id]) vis[id]=false,E++,T+=th*60+tm-ti[id];
}
return 0;
}H.7-8 古风排版 (20分) 思路：用二维数组存起来是最直接，最好想到的思路。 要注意的是，存的时候如果要存的大于等于字符串长度，这个时候就要break。
#include<bits/stdc++.h>
#define maxn 1001
using namespace std;
char aa[110][maxn];
int main(){
int n;
scanf("%d",&n);
getchar();
string s;
getline(cin,s);
int len = s.size();
int lie = len / n;
if(len % n != 0) lie++;
int k = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=lie;j++){
aa[i][j] = ' ';
}
}
//cout<<s[0]<<endl;
bool flag = 0;
for(int j=lie;j>=1;j--){
for(int i=1;i<=n;i++){
//cout<<i<<" "<<j<<endl;
aa[i][j] = s[k++];
if(k>=len){
flag = 1;
break;
}
}
if(flag) break;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=lie;j++){
cout<<aa[i][j];
}
cout<<endl;
}
//cout<<lie<<endl;
//cout<<s<<endl;
return 0;
}I.7-9 彩虹瓶 (25分) 思路：很直接的一个栈的题目，就是对栈中元素个数有限制罢了。 注意：每次要清空栈。
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
stack<int>st;
int main(){
cin >> n >> m >> k;
while(k--){
int num;
int front = 1;
bool flag = true;
for(int i = 1;i <= n;i++){
cin >> num;
if(front == num){
front++;
while(st.size())
{
int top = st.top();
if(top == front)
{
front++;
st.pop();
}
else
{
break;
}
}
}
else
{
st.push(num);
if(st.size() > m)
{
flag = false;
}
}
}
while(st.size())
{
int top = st.top();
if(top == front)
{
front++;
st.pop();
}
else
{
flag = false;
break;
}
}
while(st.size()) st.pop();
if(flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}J.7-10 秀恩爱分得快 (25分) — 补题 思路： 我们预先存储所有照片的人员信息，对于某张照片来说，只有包含a元素时（500次访问），我们才再次遍历该照片以获得a和异性的亲密度（500次访问，250次更新），跟新至一个存储a和其他人员亲密度的桶数组中。对于需要考虑的b元素，同样的方式来一遍。那么对于这张照片，最多进行2000次访问，500次更新亲密度存储桶即可，总共1000张照片也不过200w次访问，50w次更新，这个时间开销我们是可以接受的。如果再简单优化一下，获得a和b是否存在的信息只需要一次遍历，同理获得亲密度时也只需要另一次遍历即可。
注意一下，-0代表人员0为女，当且仅当查询情侣双方均为对方最亲密的异性朋友时才只输出该对情侣。
#include<bits/stdc++.h>
using namespace std;
bool gender[1000]={0}; //gender[person-id]=if-is-a-girl, 1 for girl, 0 for boy
int read(){
int input=0, flag=0;
char a=getchar();
while((a<'0' || a>'9') && a!='-')
a=getchar();
if(a=='-'){
flag=1;
a=getchar();
}
while(a>='0' && a<='9'){
input=input*10+a-'0';
a=getchar();
}
gender[input]=flag; //upgrade gender[] before exit
return input;
}
int main(){
int n, m, k, cnt, a, b;
double pa_max=0.0, pb_max=0.0;
scanf("%d%d",&n,&m);
vector<vector<int>> p(n); //photos
vector<double> pa(n,0.0), pb(n,0.0); //buckets, pa[person-id] = intimacy between a & person-id
for(unsigned int i=0;i<m;++i){ //read photos
scanf("%d",&cnt);
p[i].resize((unsigned int)cnt);
for(unsigned int j=0;j<cnt;++j)
p[i][j]=read();
}
a=read(), b=read();
for(unsigned int i=0;i<m;++i){
bool founda=find(p[i].begin(),p[i].end(),a)!=p[i].end(); //if this photo has a
bool foundb=find(p[i].begin(),p[i].end(),b)!=p[i].end(); //if this photo has b
if(founda || foundb){
for(unsigned int j=0;j<p[i].size();++j){
if(founda && gender[a]!=gender[p[i][j]]){ //if found a && current assessing person-id (p[i][j]) has a different gender from a's
pa[p[i][j]]+=(double)1/p[i].size();
pa_max=max(pa_max,pa[p[i][j]]);
}else if(foundb && gender[b]!=gender[p[i][j]]){ //else found b && current assessing person-id (p[i][j]) has a different gender from b's
pb[p[i][j]]+=(double)1/p[i].size();
pb_max=max(pb_max,pb[p[i][j]]);
}
}
}
}
if(pa_max==pa[b] && pb_max==pb[a]) //if a & b are each other's most intimate person
printf("%s%d %s%d\n",gender[a]?"-":"",a,gender[b]?"-":"",b);
else{
for(unsigned int i=0;i<n;++i){
if(pa[i]==pa_max)
printf("%s%d %s%d\n",gender[a]?"-":"",a,gender[i]?"-":"",i);
}
for(unsigned int i=0;i<n;++i){
if(pb[i]==pb_max)
printf("%s%d %s%d\n",gender[b]?"-":"",b,gender[i]?"-":"",i);
}
}
return 0;
}7-11 冰岛人 (25分)----- 补题
#include<bits/stdc++.h>
using namespace std;
struct Peoson
{
char sex;
string father;
};
map<string, Peoson> people;
int judge(string a,string b)
{
int i=1,j;
for(string A=a;!A.empty();A=people[A].father,i++)
{
j=1;
for(string B=b;!B.empty();B=people[B].father,j++)
{
if(i>=5&&j>=5)
return 1;
if(A==B&&(i<5||j<5))
return 0;
}
}
return 1;
}
int main()
{
int n, m;
string str, a, b;
cin.sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b;
if (b.back() == 'n') //儿子
people[a] = { 'm',b.substr(0,b.size() - 4) };
else if (b.back() == 'r') //女儿
people[a] = { 'f',b.substr(0, b.size() - 7) };
else people[a].sex = b.back(); //其他人
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> a >> str >> b >> str; //姓氏没有用
if (people.find(a) == people.end() || people.find(b) == people.end())
printf("NA\n");
else if(people[a].sex == people[b].sex)
printf("Whatever\n");
else
printf("%s\n", judge(a, b) ? "Yes" : "No");
}
return 0;
}7-12 图着色问题 (25分)
#include<bits/stdc++.h>
using namespace std;
int v,e,k,a,b,n,color[501];
vector <int> mp[501];
set <int> s;
int main(){
scanf("%d%d%d",&v,&e,&k);
for(int i = 0;i < e;i++){
scanf("%d%d",&a,&b);
mp[a].push_back(b);
mp[b].push_back(a);
}
scanf("%d",&n);
while(n--){
bool flag = true;
s.clear();
for(int i = 1;i <= v;i++){
scanf("%d",&color[i]);
s.insert(color[i]);
}
if(s.size()!=k)
flag = false;
for(int i = 1;i <= v;i++){
for(int j = 0;j < mp[i].size();j++){
if(color[i]==color[mp[i][j]]){
flag = false;
break;
}
}
if(!flag)
break;
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}7-13 天梯地图 (30分) ---- 补题 恶心题…
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int ma[505][505];//存路径长度
int tim[505][505];//存路径时间
int point[505],vis[505]; //存结点数和访问标记
int dis[505],dit[505];//存最短路径、最短时间
int pretim[505],predis[505];//存前驱
int main()
{
int n,m,s,e,i,j;
int x,y,k,t,l;
vector<int> v1,v2;//存输出
memset(pretim,-1,sizeof pretim);
memset(predis,-1,sizeof predis);
memset(tim,inf,sizeof tim);
memset(ma,inf,sizeof ma);
memset(dis,inf,sizeof dis);
memset(dit,inf,sizeof dit);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d%d%d",&x,&y,&k,&l,&t);
ma[x][y]=l;
tim[x][y]=t;
if(k==0)
{
ma[y][x]=l;
tim[y][x]=t;
}
}
scanf("%d%d",&s,&e);
//time
dit[s]=0;
dis[s]=0;
vis[s]=1;
for(i=0;i<n;i++)
{
int mi=s,maxi=inf;
for(j=0;j<n;j++)
{
if(vis[j]==0&&dit[j]<maxi)
{
maxi=dit[j];
mi=j;
}
}
vis[mi]=1;
for(j=0;j<n;j++)
{
if(vis[j]==0)
{
if(dit[j]>dit[mi]+tim[mi][j])
{
dit[j]=dit[mi]+tim[mi][j];
dis[j]=dis[mi]+ma[mi][j];
pretim[j]=mi;
}
else if(dit[j]==dit[mi]+tim[mi][j])
{
if(dis[j]>dis[mi]+ma[mi][j])
{
dis[j]=dis[mi]+ma[mi][j];
pretim[j]=mi;
}
}
}
}
}
int TIME=dit[e];
//distance
memset(point,0,sizeof point);
memset(vis,0,sizeof vis);
memset(dis,inf,sizeof dis);
memset(dit,inf,sizeof dit);
dit[s]=0;
dis[s]=0;
vis[s]=1;
for(i=0;i<n;i++)
{
int mi=s,maxi=inf;
for(j=0;j<n;j++)
{
if(vis[j]==0&&dis[j]<maxi)
{
maxi=dis[j];
mi=j;
}
}
vis[mi]=1;
for(j=0;j<n;j++)
{
if(vis[j]==0)
{
if(dis[j]>dis[mi]+ma[mi][j])
{
dis[j]=dis[mi]+ma[mi][j];
point[j]=point[mi]+1;
predis[j]=mi;
}
else if(dis[j]==dis[mi]+ma[mi][j])
{
if(point[j]>point[mi]+1)
{
point[j]=point[mi]+1;
predis[j]=mi;
}
}
}
}
}
y=e;
while(y!=-1)
{
v1.push_back(y);
y=pretim[y];
}
y=e;
while(y!=-1)
{
v2.push_back(y);
y=predis[y];
}
reverse(v1.begin(),v1.end());
reverse(v2.begin(),v2.end());
int f=1;
if(v1.size()==v2.size())
{
f=2;
for(i=0;i<v1.size();i++)
{
if(v1[i]!=v2[i])f=1;
}
if(f==2)
f=0;
}
if(f)
{
printf("Time = %d: %d",TIME,s);
for(i=1;i<v1.size();i++)
printf(" => %d",v1[i]);
printf("\nDistance = %d: %d",dis[e],s);
for(i=1;i<v2.size();i++)
printf(" => %d",v2[i]);
}
else
{
printf("Time = %d; Distance = %d: %d",TIME,dis[e],s);
for(i=1;i<v1.size();i++)
printf(" => %d",v1[i]);
printf("\n");
}
}7-14 迎风一刀斩 (30分)
7-15 Oriol和David (30分)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/11/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
