首页 > 其他分享 >天梯赛赛前热身

天梯赛赛前热身

时间：2023-04-17 20:55:36浏览次数：40  
标签：idx int 热身 ++ L2 二叉树 天梯 include 赛前

题解目录

目录

L2题单

进度 标号 标题 涉及的算法
L2-001 紧急救援 图论 , dijkstra + dfs
L2-002 链表去重 模拟 + 链表
L2-003 月饼 完全背包
L2-004 这是二叉搜索树吗？ 二叉树遍历
L2-005 集合相似度 集合
L2-006 树的遍历 二叉树遍历
L2-007 家庭房产 并查集 + 排序
✔ L2-008 最长对称子串 DP
L2-009 抢红包 排序
L2-010 排座位 并查集
L2-011 玩转二叉树 二叉树遍历
L2-012 关于堆的判断 堆 + 字符串
L2-013 红色警报 并查集
L2-014 列车调度 单调队列
L2-015 互评成绩 排序
✔ L2-016 愿天下有情人都是失散多年的兄妹 并查集 + DFS
L2-017 人以群分 排序
L2-018 多项式A除以B 高精度
✔ L2-019 悄悄关注 哈希
L2-020 功夫传人 二叉树遍历
L2-021 点赞狂魔 哈希 + 排序
L2-022 重排链表 链表 + 模拟
L2-023 图着色问题 图论, 染色
L2-024 部落 并查集
✔ L2-025 分而治之 图论 + 枚举
L2-026 小字辈 二叉树遍历
L2-027 名人堂与代金券 排序
L2-028 秀恩爱分得快 字符串 + 枚举
L2-029 特立独行的幸福 数论 + 模拟
L2-030 冰岛人 LCA + BFS/DFS
L2-031 深入虎穴 二叉树遍历
L2-032 彩虹瓶 栈混洗
L2-033 简单计算器 栈
L2-034 口罩发放 大模拟 + 排序
✔ L2-035 完全二叉树的层序遍历 二叉树遍历
L2-036 网红点打卡攻略 图论, 哈密尔顿环路
L2-037 包装机 模拟
L2-038 病毒溯源 二叉树遍历
✔ L2-039 清点代码库 哈希 + 排序
L2-040 哲哲打游戏 大模拟
L2-041 插松枝 模拟 + 队列/栈
✔ L2-042 老板的作息表 排序
L2-043 龙龙送外卖 树 + 图论
✔ L2-044 大众情人 图论, Floyd

题解

L2-008 最长对称子串

st[i][j]: 区间[i, j]之间的字符串是否是回文串

st[i][j] = (s[i] == s[j]) && st[i-1][j-1]

res = max{所有长度区间}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010;
bool st[N][N];

char s[N];
int main()
{
    scanf("%[^\n]", s);
    //cin.get(s, N);
    
    int res = 1;
    int len = strlen(s);
    for(int i = 0; i < len; ++i) st[i][i] = true;
    for(int i = 0; i < len-1; ++i)
        if(s[i] == s[i+1])
            st[i][i+1] = true, res = 2;
    
    for(int j = 3; j <= len; ++j)
        for(int i = 0; i+j-1 < len; ++i)
        {
            int k = i+j-1;
            if(s[i] == s[k] && st[i+1][k-1]) {
                st[i][k] = true;
                res = max(res, j);
            }
        }
    
    cout << res;
    return 0;
}

L2-016 愿天下有情人都是失散多年的兄妹

  • 并查集 + dfs
#include<iostream>
using namespace std;

const int N = 1e5+10;
struct people{
    int f, m;
    int gender;
    people():f(-1), m(-1), gender(-1){}
}p[N];

bool find(int a, int b, int u){
    if(u == 5 || a == -1 || b == -1) return true;
    if(a == b) return false;
    return find(p[a].f, p[b].f, u+1) && find(p[a].f, p[b].m, u+1) &&
        find(p[a].m, p[b].f, u+1) && find(p[a].m, p[b].m, u+1);
}

int main()
{
    int n;
    cin >> n;
    
    int id, fid, mid;
    char g;
    while(n --){
        cin >> id >> g >> fid >> mid;
        p[id].gender = (g == 'M' ? 1 : 0);
        p[id].f = fid, p[id].m = mid;
        p[fid].gender = fid == -1 ? -1 : 1;
        p[mid].gender = mid == -1 ? -1 : 0;
    }
    
    cin >> n;
    while(n --){
        int a, b;
        cin >> a >> b;
        if(p[a].gender == p[b].gender) cout << "Never Mind\n";
        else {
            bool ret = find(a, b, 0);
            if(ret) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

L2-019 悄悄关注

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

map<string, int> focus_mp;
map<string, int> unfocus_mp;
vector<string> v;

int main()
{
    int n, m;
    cin >> n;
    
    string s;
    for(int i = 0; i < n; ++i){
        cin >> s;
        focus_mp[s] = 0;
    }
    
    cin >> m;
    int cnt, num = 0;
    for(int i = 0; i < m; ++i){
        cin >> s >> cnt;
        num += cnt;
        if(focus_mp.find(s) != focus_mp.end()) focus_mp[s] = cnt;
        else unfocus_mp[s] = cnt;
    }
    double avg = num/m;

    for(auto t : unfocus_mp)
        if(t.second > avg) 
            v.push_back(t.first);

    if(v.size()){
        sort(v.begin(), v.end());
        for(auto t : v) cout << t << "\n";
    }else cout << "Bing Mei You";
    
    return 0;
}

L2-025 分而治之

  • 图论, 模拟

  • 管理好图的出入度即可

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e4+10, M = 2e4+10;
int n, m;
int h[N], in[N], backup_in[N];
int e[M], ne[M], idx;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    int a, b;
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &a, &b);
        ++in[a], ++in[b];
        add(a, b), add(b, a);
    }
//     for(int i = 1; i <= n; ++i) printf("in[%d]: %d\n", i, in[i]);
    int t, tt, x;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &tt);
        
        for(int i = 1; i <= n; ++i) backup_in[i] = in[i];
        for(int i = 0; i < tt; ++i){
            scanf("%d", &x);
            for(int j = h[x]; ~j; j = ne[j]){
                int u = e[j];
                --backup_in[x], --backup_in[u];
            }
        }
        
        bool ret = true;
        for(int i = 1; i <= n; ++i){
            if(backup_in[i] > 0){
                ret = false;
                break;
            }
        }
        if(ret) printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

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

#include<iostream>
using namespace std;

const int N = 110;
int n;
int post[N], tree[N], idx;

void build(int u){
    if(u > n) return ;
    build(u << 1), build(u << 1 | 1);
    tree[u] = post[idx++];
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> post[i];
    build(1);
    for(int i = 1; i <= n; ++i) {
        cout << tree[i];
        if(i != n) cout << " ";
    }
    return 0;
}

L2-039 清点代码库

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

const int N = 10010;
map<vector<int>, int> vec2key;
map<int, vector<int>> key2vec;
vector<int> v[N];

int idx;
struct Example{
    int num = 0;
    int key;
}e[N];


bool cmp(Example a, Example b){
    if(a.num == b.num) return key2vec[a.key] < key2vec[b.key];
    else return a.num > b.num;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    int x;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            scanf("%d", &x);
            v[i].push_back(x);
        }
    }
    
    for(int i = 0; i < n; ++i)
    {
        if(vec2key.find(v[i]) != vec2key.end()) 
            e[vec2key[v[i]]].num++;
        else {
            vec2key[v[i]] = ++idx;
            key2vec[idx] = v[i];
            e[idx].num = 1;
            e[idx].key = idx;
        }
    }
    
    sort(e+1, e+idx+1, cmp);
    printf("%d\n", idx);
    
    for(int i = 1; i <= idx; ++i)
    {
        printf("%d", e[i].num);
        vector<int> t = key2vec[e[i].key];
        
        for(auto j : t) printf(" %d", j);
        printf("\n");
    }
    
    return 0;
}

L2-042 老板的作息表

  • 自定义排序, 模拟
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 220000;
struct TimeNode{
    int l, r;
    bool operator < (struct TimeNode& b) const{
        if(l != b.l) return l < b.l;
        return r < b.r;
    }
}tn[N];

int time2num(int h, int m, int s){
    return h*3600+m*60+s;
}

void num2time(int t1, int t2){
    int h1 = t1/3600, h2 = t2/3600;
    t1 %= 3600, t2 %= 3600;
    int m1 = t1/60, m2 = t2/60;
    t1 %= 60, t2 %= 60;
    int s1 = t1, s2 = t2;
    printf("%02d:%02d:%02d - %02d:%02d:%02d\n", h1, m1, s1, h2, m2, s2);
}

int main()
{
    int n;
    cin >> n;
    
    int h1, h2, m1, m2, s1, s2;
    for(int i = 0; i < n; ++i){
        scanf("%d:%d:%d - %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        tn[i] = {time2num(h1,m1,s1), time2num(h2,m2,s2)};
    }
    
    sort(tn, tn+n);
    int pre = 0;
    for(int i = 0; i < n; ++i){
        if(tn[i].l > pre) num2time(pre, tn[i].l);
        pre = tn[i].r;
    }
    
    int end = time2num(23,59,59);
    if(pre != end) num2time(pre, end);
    return 0;
}

L2-044 大众情人

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int d[N][N], g[N];
int mx[N];	//mx[i]: 其他异性到i的距离最大值 

int main()
{
	int n, m;
	cin >> n;
	
	memset(d, 0x3f, sizeof d);
	for(int i = 1; i <= n; ++i) d[i][i] = 0;
	
    char gender;
    int b, c;
	for(int i = 1; i <= n; ++i){
		cin >> gender >> m;
		g[i] = gender=='M';
		for(int j = 0; j < m; ++j){
			scanf("%d:%d", &b, &c);
			d[i][b] = c;
		} 
	}
	
	//floyd 
	for(int k = 1; k <= n; ++k)
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
	
	
	for(int k = 0; k < 2; ++k) //k: 0->女 ; 1->男 
	{
		int mi = INF;	//得到当前性别(K)的mx[]最小值 
		for(int i = 1; i <= n; ++i){
			if(g[i] == k) {
				for(int j = 1; j <= n; ++j)
					if(g[j] != k) 
						mx[i] = max(mx[i], d[j][i]);
					
				mi = min(mi, mx[i]);
			}
		}
		
        vector<int> v;  //只来控制最后输出的格式, (pta真傻呗)
		for(int i = 1; i <= n; ++i)
			if(g[i] == k && mx[i] == mi) 
				v.push_back(i);
				
		for(int i = 0; i < v.size(); ++i){
            if(i) cout << " ";
            cout << v[i];
        }
        cout << '\n';
	} 
	return 0;
}

标签：idx,int,热身,++,L2,二叉树,天梯,include,赛前
From： https://www.cnblogs.com/Knight02/p/pta-L2.html

相关文章

  • 显卡性能排行天梯图
    笔记本中所需要的CPU并不是说越高越好，需要和显卡想配对，一般来说，笔记本电脑上的CPU性能都比较高，而显卡的型号较低点，如果不能够相互适配的话，会导致无法发挥出显卡或者CPU的真正性能等，这一次来详细查看一下CPU的排行榜天梯图，然后根据自己的需求酌情选择吧~【CPU天梯图】【天梯图大......
  • 团体天梯练习 L2-011 玩转二叉树
    L2-011玩转二叉树给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数\(N（≤30）\)，是二叉树中结点的个数。第二行给......
  • 团体天梯练习 L2-010 排座位
    L2-010排座位布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。输入格式：输入第一行给出3个正整数：\(N（≤100）\)，即前来参宴的宾客总人数，则......
  • 团体天梯练习 L2-009 抢红包
    L2-009抢红包没有人没抢过红包吧……这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。输入格式：输入第一行给出一个正整数\(N（≤10^{4}）\)，即参与发红包和抢红包的总人数，则这些人从\(1\)到\(N\)编号。随后\(N\)行，第\(i\)行给出编号为\(i\)的......
  • 团体天梯练习 L2-008 最长对称子串
    L2-008最长对称子串对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定IsPAT&TAPsymmetric?，最长对称子串为sPAT&TAPs，于是你应该输出11。输入格式：输入在一行中给出长度不超过1000的非空字符串。输出格式：在一行中输出最长对称子串的长度。输入样例：IsPAT&TAP......
  • 团体天梯练习 L2-007 家庭房产
    L2-007家庭房产给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。输入格式：输入第一行给出一个正整数$N（≤1000）$，随后N行，每行按下列格式给出一个人的房产：编号父母\(k\)孩子1...孩子\(k\)房产套数总面积其中编号是每个......
  • 团体天梯练习 L2-001 紧急救援
    L2-001紧急救援作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快......
  • 最后一周天梯赛
    感觉很难害题目有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？输入格式输入有多组，每组只有一个数N，代表地板的长度输出格式对于每组数据，输出一个数，占一行，代表所有不同的瓷砖铺放方法......
  • 天梯赛L1-027 出租
    一、问题描述下面是新浪微博上曾经很火的一张图：一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推……很容易得到电话号码是18013820100。本题要......
  • 天梯赛练习题 L3-008 喊山（bfs）
    https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805050709229568输入样例：75412233145561457输出样例：2640#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLMAX......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99