题解目录
目录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