2022418 天梯赛刷题记录&2022天梯赛热身赛

L1 1~8 语法到模拟
L2-1 栈、map
L2-2 set、排序
L2-4 模拟
L3-2 背包

L2-3 写不出来，二叉树这方面是真的薄弱
周日热身赛的时候因为一直内部错误直接润了，今天重新做一下

目录

• • L1-1 自动编程
  • L1-2 太神奇了
  • L1-3 洛希极限
  • L1-4 吃鱼还是吃肉
  • L1-5 不变初心数
  • L1-6 字母串
  • L1-7 矩阵列平移
  • L1-8 均是素数
  • L2-1 盲盒包装流水线
  • L2-2 点赞狂魔
  • L2-4 哲哲打游戏
  • L3-2 拼题A打卡奖励

L1-1 自动编程

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
int x;
int main(){
    cin>>x;
    printf("print(%d)",x);
    return 0;
}

L1-2 太神奇了

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
int x,y;
int main(){
    cin>>x>>y;
    cout<<x+y-1;
    return 0;
}

L1-3 洛希极限

#include 
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 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
void solve(){
    int id,h,w;
    cin>>id>>h>>w;
    if(id==1){
        if(h<130) cout<<"duo chi yu! ";
        if(h==130) cout<<"wan mei! ";
        if(h>130)cout<<"ni li hai! ";
        if(w<27) cout<<"duo chi rou!";
        if(w==27) cout<<"wan mei!";
        if(w>27) cout<<"shao chi rou!";
    }else{
        if(h<129) cout<<"duo chi yu! ";
        if(h==129 ) cout<<"wan mei! ";
        if(h>129) cout<<"ni li hai! ";
        if(w<25) cout<<"duo chi rou!";
        if(w==25) cout<<"wan mei!";
        if(w>25) cout<<"shao chi rou!";
    }
    cout<<endl;
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

L1-5 不变初心数

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
int check(int x){
    int ans=0;
    while(x){
        ans+=x%10;
        x/=10;
    }
    return ans;
}
void solve(){
    int n;cin>>n;
    int pos=check(n*2);
    for(int i=3;i<=9;i++){
        if(pos!=check(n*i)){
            cout<<"NO"<<endl;
            return ;
        }
    }
    cout<<pos<<endl;
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

L1-6 字母串

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
string s;
void solve(){
    cin>>s;
    int f=1;
    for(int i=0;i<s.size()-1;i++){
        if(s[i]<='Z'&&s[i]>='A'){
            if(s[i+1]!=tolower(s[i])&&s[i+1]!=(s[i]+1)) {
                f=0;
            }
        }
        if(s[i]>='a'&&s[i]<='z'){
            if(s[i+1]!=toupper(s[i])&&s[i+1]!=(s[i]-1)){
                f=0;
            }
        }
    }
    if(!f) {
        cout<<"N"<<endl;
    }else{
        cout<<"Y"<<endl;
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

L1-7 矩阵列平移

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e2+10,mod=1e9+7;
int n,k,x,a[N][N],b[N][N];
int main(){
    cin>>n>>k>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    int kt=0;
    for (int j = 1; j <= n; j++) {
        if (j % 2 == 0) {
            for (int i = 1; i <= n; i++){
                int now=kt + 1 + i;
                b[now][j] = a[i][j];
            }
            kt++;
            kt %= k;
        }
        else{
            for (int i = 1; i <= n; i++) b[i][j] = a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j=1;j<=n;j++) {
            if(b[i][j]) ans+=b[i][j];
            else ans+=x;
        }
        if(i!=n) cout<<ans<<" ";
        else cout<<ans;
    }
    return 0;
}

L1-8 均是素数

要先对素数打个标记，不然全放一个if 里面check的话会超时

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e3+10,mod=1e9+7;
int m,n,vis[N];
bool check(int x){
    if(x==1) return false;
    if(x==2||x==3) return true;
    for(int i=2;i<=x/i;i++) {
        if(x%i==0 )return false;
    }
    return true;
}
int main(){
    cin>>m>>n;
    int ans=0;
    for(int i=m;i<=n;i++) vis[i]=check(i);
    for(int i=m;i<n-1;++i){
        if(!vis[i]) continue;
        for(int j=i+1;j<n;j++){
            if(!vis[j]) continue;
            for(int k=j+1;k<=n;k++){
                if(!vis[k]) continue; 
                if(check(i*j+k)&&check(i*k+j)&&check(j*k+i)) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

L2-1 盲盒包装流水线

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int  N=1e5+10,mod=1e9+7;
int n,s,k,b[N];
string a[N];
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    int k=n/s,tt1=0;
    map<string,int> mp;
    for(int i=1;i<=k;i++){
        int tt=0;
        for(int j=1;j<=s;j++) cin>>b[j];
        stack<string>q;
        while(tt<s){
            tt++;
            q.push(a[++tt1]);
        }
        int cnt=0;
        while(!q.empty()){
            mp[q.top()]=b[++cnt];
            q.pop();
        }
    }
    int p;cin>>p;
    while(p--){
        string str;cin>>str;
        if(mp[str]) {
            cout<<mp[str]<<endl;
        }else {
            cout<<"Wrong Number"<<endl;
        }
    }
    return 0;
}

L2-2 点赞狂魔

#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n';
typedef long long ll;
typedef pair<string,int> PII;
const int N=1e4+10,mod=1e9+7;
struct node{
	string name;
	int num,pos;
}a[N];
bool cmp(node x,node y){
	if(x.num==y.num) return x.pos<y.pos;
	return x.num>y.num;
}
set<int>st;
int n,x,k;
string s;
int main(){
	IOS;
	cin>>n;
	st.clear();
	for(int i=1;i<=n;i++) {
		cin>>a[i].name>>a[i].pos;
		for(int j=1;j<=a[i].pos;j++){
			cin>>x;
			st.insert(x);
		}
		a[i].num=st.size();
		st.clear();
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=min(3,n);i++){
		if(i<3) cout<<a[i].name<<" ";
		else cout<<a[i].name;
	}
	if(n==1) cout<<"- -";
	if(n==2) cout<<"-";
	return 0;
}

L2-4 哲哲打游戏

#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n';
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=1e5+10,mod=1e9+7;
int n,m;
vector<int>e[N];
int a[N];
int main(){
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		for(int j=1;j<=k;j++){
			int x;cin>>x;
			e[i].push_back(x);
		}
	}
	int ans=1;
	for(int i=1;i<=m;i++) {
		int op,y;cin>>op>>y;
		if(op==0) ans=e[ans][y-1];
		else if(op==1){
			a[y]=ans;
			cout<<ans<<endl;
		}else{
			ans=a[y];
		}
	}
	cout<<ans<<endl;
	return 0;
}

L3-2 拼题A打卡奖励

#include 
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair<int,int> PII;
const int  N=1e6+10,mod=1e9+7;
int n,m,a[N],c[N],dp[N];
int main(){
    cin>>n>>m;
    memset(dp,0x3f,sizeof(dp));
    int sum=0;
    dp[0]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>c[i],sum+=c[i];
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=c[i];j--){
            dp[j]=min(dp[j],dp[j-c[i]]+a[i]);
        }
    }
    while(dp[sum]>m)sum--;
    cout<<sum;
    return 0;
}