2022/4/16 天梯赛刷题记录&2020天梯赛

L1-1~8 语法
L2-1 栈
L2-2 模拟
L2-3 dfs
L2-4 图论
L2的题目读起来真费劲，L2-2模拟恶心坏了，L2-4没看见景点全逛一便找错找麻了，L3都没时间看

L1-1 嫑废话上代码

#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define MP make_pair
using namespace std;

int main(){
	cout<<"Talk is cheap. Show me the code."<<endl;
	return 0;
}

L1-2 猫是液体

#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define MP make_pair
using namespace std;

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<a*b*c<<endl;
	return 0;
}

L1-3 洛希极限

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int main(){
	double x,z,d;
	int y;
	cin>>x>>y>>z;
	if(y==0) d=2.455;
	else d=1.26;
	x*=d;
	printf("%.2lf ",x);
	if(x<z) printf("^_^");
	else printf("T_T");
	return 0;
}

L1-4 调和平均

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
double a[N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	double ans=0;
	for(int i=1;i<=n;i++){
		ans+=(1.0/a[i]);
	}
	printf("%.2lf",n/ans);
	return 0;
}

L1-5 胎压监测

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int a[10],pos;
int main(){
	for(int i=1;i<=6;i++) cin>>a[i];
	int manx=0,cnt=0;
	for(int i=1;i<=4;i++) manx=max(manx,a[i]);
	for(int i=1;i<=4;i++){
		if(a[i]<a[5]||(manx-a[i])>a[6]) pos=i,cnt++;
	}
	if(cnt==1) printf("Warning: please check #%d!",pos);
	if(cnt>1) printf("Warning: please check all the tires!");
	if(cnt==0) printf("Normal");
	return 0;
}

L1-6 吃火锅

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
string s;
int main(){
	int cnt=0,pos=0,sum=0;
	while(1){
		getline(cin,s);
		if(s==".") break;
		sum++;
		if(s.find("chi1 huo3 guo1")!=-1) {
			if(pos==0) pos=sum;
			cnt++;
		}
	}
	cout<<sum<<endl;
	if(cnt!=0) cout<<pos<<" "<<cnt;
	else cout<<"-_-#";
	return 0;
}

L1-7 前世档案

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;

int main(){
	int n,m;cin>>n>>m;
	while(m--){
		int ans=pow(2,n);
		string s;cin>>s;
		for(int i=0;i<n;i++){
			if(s[i]=='y') ans-=pow(2,n-i-1);
		}
		cout<<ans<<endl;
		
	}
	return 0;
}

L1-8 刮刮彩票

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int a[4][4],x[4],y[4],vis[10];
int ans[]={10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};
int main(){
	int x0,y0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			cin>>a[i][j];
			if(a[i][j]==0) x0=i,y0=j;
			vis[a[i][j]]=1;
		}
	}
	for(int i=1;i<=9;i++) if(!vis[i]) a[x0][y0]=i;
	for(int i=1;i<=3;i++) {
		cin>>x[i]>>y[i];
		cout<<a[x[i]][y[i]]<<endl;
	}
	int k;cin>>k;
	int sum=0;
	if(k<=3){
		for(int i=1;i<=3;i++)sum+=a[k][i];
	}else if(k<=6&&k>3){
		for(int i=1;i<=3;i++) sum+=a[i][k-3];
	}else if(k==7){
		for(int i=1;i<=3;i++) sum+=a[i][i];
	}else{
		for(int i=1;i<=3;i++) sum+=a[i][4-i];
	}
	cout<<ans[sum-6]<<endl;
	return 0;
}

L2-1 简单计算器

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
stack<int>q1;
stack<char>q2;
int n;
int solve(int x,char op,int y){
	if(op=='+') return x+y;
	if(op=='-') return y-x;
	if(op=='*') return x*y;
	if(op=='/') return y/x;
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){	
		int x;cin>>x;
		q1.push(x);
	}
	for(int i=1;i<n;i++){
		char op;cin>>op;
		q2.push(op);
	}
	while(q1.size()>1&&!q2.empty()){
		int x=q1.top();
		q1.pop();
		int y=q1.top();
		q1.pop();
		char op=q2.top();
		q2.pop();
		if(op=='/'&&x==0) {
			cout<<"ERROR: "<<y<<"/"<<x<<endl;
			return 0;
		}
		int ans=solve(x,op,y);
		q1.push(ans);
	}
	cout<<q1.top()<<endl;
	return 0;
}

L2-2 口罩发放

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
struct node{
    string name,id;
    int con,tme,idx;
};
int cmp(const node &a,const node &b){
    if(a.tme==b.tme)
        return a.idx<b.idx;
    return a.tme<b.tme;
}
int d,p,t,s,tme,con,minute,i,j,k,ma;
char c[30],a[30];
vector<node> v,vp,vps;
map<string,int> mp;
set<string> ss;
int main(){
    scanf("%d%d",&d,&p);
    for(i=1;i<=d;i++) {
        scanf("%d%d",&t,&s);
        for(j=0;j<t;j++){
            scanf("%s%s%d%d:%d",a,c,&con,&tme,&minute);
            if(strlen(c)==18)
            {
                for(k=0;c[k];k++)
                    if(!isdigit(c[k]))
                        break;
                if(c[k]) continue;
                node no;
                no.name=string(a);
                no.id=string(c);
                no.con=con;
                no.idx=j;
                no.tme=tme*100+minute;
                if(mp[no.id]==0||mp[no.id]+p<i) v.emplace_back(no);
                if(con){
                    if(!ss.count(no.id)){
                        ss.insert(no.id);
                        vp.emplace_back(no);
                    }
                }
            }
        }
        sort(v.begin(),v.end(),cmp);
        for(auto it=v.begin();it!=v.end()&&s>0;it++){
            if(mp[it->id]!=i) {
                cout<<it->name<<" "<<it->id<<endl;
                mp[it->id]=i;
                s--;
            }
        }
        v.clear();
    }
    for(auto it=vp.begin();it!=vp.end();it++)  cout<<it->name<<" "<<it->id<<endl;
}

L2-3 完全二叉树的层序遍历

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int n,cnt,a[N],ans[N];
void dfs(int u){
	if(u>n)return;
	dfs(u*2);
	dfs(u*2+1);
	ans[u]=a[cnt++];
}
int main(){
    cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cnt=1;
	dfs(1);
	cout<<ans[1];
	for(int i=2;i<=n;i++) cout<<" "<<ans[i];
	return 0;
}

L2-4 网红点打卡攻略

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int n,m,k,q,a[N],mp[1000][1000];
vector<PII>ans;
bool cmp(PII x,PII y){
	if(x.second==y.second) return x.first<y.first;
	return x.second<y.second;
}
int main(){
    cin>>n>>m;
	while(m--){
		int u,v,z;cin>>u>>v>>z;
		mp[u][v]=z;
		mp[v][u]=z;		
	}
	cin>>k;
	for(int p=1;p<=k;p++){
		cin>>q;
		set<int>st;
		st.clear();
		for(int i=1;i<=q;i++) {
			cin>>a[i];
			st.insert(a[i]);
		}
		int sum=0,f=1;
		if(st.size()!=q||q!=n) continue; 
		a[0]=0,a[q+1]=0;
		for(int i=0;i<=q;i++){
			if(!mp[a[i]][a[i+1]]) f=0;
			sum+=mp[a[i]][a[i+1]];
		}
		if(!f) continue;
		else ans.push_back({p,sum});
	}
	sort(ans.begin(),ans.end(),cmp);
	cout<<ans.size()<<endl;
	cout<<ans[0].first<<" "<<ans[0].second<<endl;
	return 0;
}