当前位置:网站首页>Acwing week 58
Acwing week 58
2022-07-06 04:47:00 【Zqchang】
List of articles
The longest subsequence
This is a greedy question , Greedy heel dp It's very similar , That is, we can also divide all subsets into several categories , If proved , The answer must be in a certain category , This is greed , If you find that the answer is not in a certain category , If each category requires , Namely dp
This topic is not difficult to understand , The fun part is , Its proof , How to prove that the answer must be continuous
hypothesis a i a_i ai and a k a_k ak In the subsequence of answers , however a j a_j aj be not in , Prove whether it is true
That's how it turns out , The result is a j a_j aj eligible , You can put it in the answer , Then contradict the assumption , So the answer must be a large continuous segment , Then double pointer scan once
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010;
int n;
int w[N];
signed main()
{
cin >> n;
for(int i=1; i<=n; i++) cin >> w[i];
int res = 0;
for(int i=1; i<=n; i++)
{
int j = i + 1;
while(j <= n && w[j] <= w[j - 1] * 2) j++;// Here is the enumeration to the j individual , The first j If not, quit , So let's go straight to i - j
res = max(res, j - i);
i = j - 1;
}
cout << res << endl;
return 0;
}
dyeing
dyeing
It means , Dye a tree with the specified color , How many steps does it take to ask , When dyeing , One point , Including its subtree will be dyed , therefore , Whenever a root node is dyed , All operations before its subtree are invalid , So it must be from top to bottom , Dye the root node first , Then check whether the color of the child node is consistent with that of the root node , If not, dye , If you agree, look at the child nodes
So there are two ways , The first is to build drawings , Then record the color of the parent node every time , If it is different from the child node, dye it , In this way
The second is not to build a map , Directly see how many points are different from the color of child nodes , So you have to dye once , Finally, add an operation of the root node , That's the answer.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 10010;
int n;
int p[N], c[N];
signed main()
{
fast;
cin >> n;
for(int i=2; i<=n; i++) cin >> p[i];
for(int i=1; i<=n; i++) cin >> c[i];
int res = 0;
for(int i=1; i<=n; i++)
if(c[i] != c[p[i]]) res ++;
cout << res << endl;
return 0;
}
D - Trophy
Write a handy abc, It's all about water , The reason for writing is because , There are some small points , I didn't notice before , such as ,long long The maximum range of is 9e18 many
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a)
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
int a[N], b[N];
int suma[N], sumb[N];
int res[N];
signed main()
{
fast;
int n, x;
cin >> n >> x;
int ans = 8e18;
for(int i=1; i<=n; i++)
{
cin >> a[i] >> b[i];
suma[i] = suma[i-1] + a[i];
sumb[i] = sumb[i-1] + b[i];
res[i] = suma[i] + sumb[i] + b[i] * (x - i);
}
for(int i=1; i<=n; i++)
{
if(i > x) break;// Note that if x Than i Big to break, Because I can't go so far
ans = min(ans, res[i]);
}
cout << ans << endl;
return 0;
}
边栏推荐
- 优秀PM必须经历这3层蜕变!
- Selection of slow motion function
- Redis 排查大 key 的4種方法,優化必備
- [HBZ share] reasons for slow addition and deletion of ArrayList and fast query
- How to realize automatic playback of H5 video
- MySQL reported an error datetime (0) null
- The underlying structure of five data types in redis
- 也算是学习中的小总结
- 项目经理,你会画原型嘛?项目经理需要做产品设计了?
- Yyds dry goods inventory OSI & tcp/ip
猜你喜欢
Postman前置脚本-全局变量和环境变量
RTP gb28181 document testing tool
[FreeRTOS interrupt experiment]
Zynq learning notes (3) - partial reconfiguration
8. Static file
Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
ISP learning (2)
Visio draws Tai Chi
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
[mathematical modeling] differential equation -- sustainable development of fishing industry
随机推荐
Redis 排查大 key 的4种方法,优化必备
Quatre méthodes de redis pour dépanner les grandes clés sont nécessaires pour optimiser
The underlying structure of five data types in redis
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
Bubble sort
Redis —— Redis In Action —— Redis 实战—— 实战篇一 —— 基于 Redis 的短信登录功能 —— Redis + Token 的共享 session 应用— 有代码
MPLS experiment
行业专网对比公网,优势在哪儿?能满足什么特定要求?
Delete subsequence < daily question >
SharedPreferences source code analysis
[数学建模] 微分方程--捕鱼业的持续发展
Visio draws Tai Chi
Redis has four methods for checking big keys, which are necessary for optimization
flink sql 能同时读多个topic吗。with里怎么写
Summary of three log knowledge points of MySQL
win10电脑系统里的视频不显示缩略图
C'est un petit résumé de l'étude.
[NOIP2009 普及组] 分数线划定
tengine 内核参数
Embedded development program framework