当前位置:网站首页>【Acwing】第58场周赛 题解
【Acwing】第58场周赛 题解
2022-07-04 21:38:00 【玄澈_】
AcWing 4488. 寻找1
AC代码
#include <iostream> using namespace std; int main() { int n; cin >> n; bool f = false; while(n -- ) { int num; cin >> num; if(num == 1) f = true; } if(f) puts("YES"); else puts("NO"); return 0; }
AcWing 4489. 最长子序列
输入样例1:
10 1 2 5 6 7 10 21 23 24 49
输出样例1:
4
输入样例2:
5 2 10 50 110 250
输出样例2:
1
输入样例3:
6 4 7 12 100 150 199
输出样例3:
3
要充分利用好题目中的 严格单调递增 这一条件
对于 ,其下一个满足的数应该要满足这两个条件
由单调性可知, 的范围完全覆盖了 ,所以选择后面的数可以使选择的范围更大
综上,当后面的数满足小于等于前面数的两倍时,必选这个数(贪心)
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int main()
{
int res = 0;
int n; cin >> n;
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for(int i = 0; i < n; i ++ )
{
int j = i + 1;
while(a[j] <= 2 * a[j - 1] && j < n) j ++ ; j -- ;
res = max(res, j - i + 1);
i = j;
}
cout << res << endl;
return 0;
}
AcWing 4490. 染色
输入样例1:
6 1 2 2 1 5 2 1 1 1 1 1
输出样例1:
3
输入样例2:
7 1 1 2 3 1 4 3 3 1 1 1 2 3
输出样例2:
5
由于染色操作具有覆盖性,而且对于一棵(子)树的根节点只有在根节点这一点能够对其进行染色
如果从子节点进行染色的话,最后到达根节点时的染色将会覆盖之前的操作,不满足 最少操作 这一性质
所以我们需要从根节点开始进行染色,然后不断递归处理每个子节点直到叶节点(贪心思路)
- 如果子节点和父节点的颜色相同,则不需要重复染色
- 如果子节点和父节点的颜色不同,则需要多一次染色操作 , ret ++
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010;
int n;
int e[N], ne[N], h[N], idx;
int w[N];
int ret;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
if(u == 1) ret ++ ;
// 叶节点
if(h[u] == -1) return;
for(int i = h[u]; ~i; i = ne[i])
{
// 是根节点
int j = e[i];
if(h[j] == -1)
{
if(w[j] != w[u]) ret ++ ;
}
else
{
// 不是根节点
if(w[j] != w[u]) ret ++ ;
dfs(j);
}
}
return ;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i = 2; i <= n; i ++ )
{
int p; cin >> p;
add(p, i);
}
for(int i = 1; i <= n; i ++ )
{
cin >> w[i];
}
dfs(1);
cout << ret << endl;
return 0;
}
边栏推荐
- 2022 version of stronger jsonpath compatibility and performance test (snack3, fastjson2, jayway.jsonpath)
- 能源势动:电力行业的碳中和该如何实现?
- Cloudcompare & open3d DBSCAN clustering (non plug-in)
- How to remove the black dot in front of the title in word document
- 更强的 JsonPath 兼容性及性能测试之2022版(Snack3,Fastjson2,jayway.jsonpath)
- El tree combined with El table, tree adding and modifying operations
- Which securities company is better to open an account? Is online account opening safe
- Golang interview finishing three resumes how to write
- 应用实践 | 蜀海供应链基于 Apache Doris 的数据中台建设
- Master the use of auto analyze in data warehouse
猜你喜欢
How was MP3 born?
Sorting and sharing of selected papers, systems and applications related to the most comprehensive mixed expert (MOE) model in history
案例分享|金融业数据运营运维一体化建设
bizchart+slider实现分组柱状图
力扣98:验证二叉搜索树
[weekly translation go] how to code in go series articles are online!!
开源之夏专访|Apache IoTDB社区 新晋Committer谢其骏
Cloudcompare & open3d DBSCAN clustering (non plug-in)
做BI开发,为什么一定要熟悉行业和企业业务?
How to implement Devops with automatic tools
随机推荐
【米哈游2023届秋招】开启【校招唯一专属内推码EYTUC】
Caduceus从未停止创新,去中心化边缘渲染技术让元宇宙不再遥远
Spatiotemporal prediction 3-graph transformer
Which securities company has the lowest Commission for opening an account online? I want to open an account. Is it safe to open an account online
Lambdaquerywrapper usage
HUAWEI nova 10系列发布 华为应用市场筑牢应用安全防火墙
EhLib 数据库记录的下拉选择
What is the stock account opening process? Is it safe to use flush mobile stock trading software?
Delphi SOAP WebService 服务器端多个 SoapDataModule 实现相同的接口方法,接口继承
Analyzing the maker space contained in steam Education
Go language loop statement (3 in Lesson 10)
挖财学院股票开户安全吗?开户只能在挖财开户嘛?
Super detailed tutorial, an introduction to istio Architecture Principle and practical application
[early knowledge of activities] list of recent activities of livevideostack
时空预测3-graph transformer
能源势动:电力行业的碳中和该如何实现?
Three or two things about the actual combat of OMS system
TCP shakes hands three times and waves four times. Do you really understand?
【C语言进阶篇】数组&&指针&&数组笔试题
Open3d surface normal vector calculation