当前位置:网站首页>Acwing: Game 58 of the week
Acwing: Game 58 of the week
2022-07-06 16:16:00 【Hello_ Ä】
AcWing: The first 58 Weekly match
4488. seek 1 - AcWing Question bank
Given a length of n Of 01 Sequence a1,a2,…,an.
Please judge , Whether it contains 1.
Input format
The first line contains an integer n.
The second line contains n It's an integer a1,a2,…,an.
Output format
If the sequence contains 1, The output YES
, Otherwise output NO
.
Data range
The first three test points meet 1≤n≤3.
All test points meet 1≤n≤100,0≤ai≤1.
sample input 1:
3
0 0 1
sample output 1:
YES
sample input 2:
1
0
sample output 2:
NO
Problem analysis
Traversal array , find 1 It outputs yes end , If it has not been output yes, It outputs no.
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin>>n;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
if(x==1)
{
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}
4489. The longest subsequence - AcWing Question bank
Given a length of n Strictly monotonically increasing sequence of integers a1,a2,…,an.
Sequence a The subsequence of can be expressed as ai1,ai2,…,aip, among 1≤i1<i2<…<ip≤n.
We hope to find one a The subsequence , Make the subsequence satisfy : about j∈[1,p−1],aij+1≤aij×2 Hang up .
We think , The length is 1 The subsequence of always satisfies the condition .
Please calculate and output the maximum possible length of the subsequence that meets the conditions .
Input format
The first line contains an integer n.
The second line contains n It's an integer a1,a2,…,an.
Output format
An integer , Represents the maximum possible length of the subsequence that meets the condition .
Data range
front 5 Test points meet 1≤n≤10.
All test points meet 1≤n≤2×105,1≤a1<a2<…<an≤109.
sample input 1:
10
1 2 5 6 7 10 21 23 24 49
sample output 1:
4
sample input 2:
5
2 10 50 110 250
sample output 2:
1
Problem analysis
At first glance , Like finding the longest increasing subsequence nlogn practice , Just change the judgment conditions .
But it's not that complicated ( And I didn't write two points correctly ), The first sequence we are looking for is , The current digit is twice or less than the previous digit . Then the title said that the given array is strictly increasing , that , If we are looking for this sequence , The current element of the array is greater than twice the previous element , Then we don't have to go back to the previous elements , Because arrays are incrementing , If twice the number of the previous element is smaller than the current element , Then there is no need to think about the later element that is smaller than this element . So this question is not so much a sequence , It's more like a subarray .
We directly traverse the array , If the current element is less than or equal to twice the previous element , Let's treat him as the last element of the sequence , At the same time, the sequence length ++. If this element is not satisfied , Then let's assume that this element is the beginning of the sequence , Restore the sequence length to 1. In this process, maintain the maximum value of the sequence .
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int>v(n), f(n + 2,0);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
int res = 0,ans=0;
for (int i = 0; i < n; i++)
{
if (f[ans] * 2 >= v[i])
{
f[ans + 1] = v[i];
res = max(res, ++ans);
}
else
{
f[1] = v[i];
ans = 1;
res = max(res, ans);
}
}
cout << res << endl;
return 0;
}
4490. dyeing - AcWing Question bank
Given a n Tree of nodes , Node number is 1∼n.
1 Node number is the root node of the tree .
At the beginning , The color of all nodes is 0.
Now? , You need to re dye the tree , Where nodes i The target color of is ci.
The specific process of each dyeing operation is as follows :
Select a node v And a color x.
Will be in the form of nodes v All nodes in the subtree of the root node ( Including nodes v) All dyed in color x.
Please calculate , In order to make each node be dyed into the target color , At least how many dyeing operations are needed .
Input format
The first line contains integers n.
The second line contains n−1 It's an integer p2,p3,…,pn, among pi Representation node i The parent node number of .
The third line contains n It's an integer c1,c2,…,cn, among ci Representation node i Target color of .
Ensure that the input given graph is a tree .
Output format
An integer , Indicates the minimum number of dyeing operations required .
Data range
The first three test points meet 2≤n≤10.
All test points meet 2≤n≤10^ 4,1≤pi<i,1≤ci≤n.
sample input 1:
6
1 2 2 1 5
2 1 1 1 1 1
sample output 1:
3
sample input 2:
7
1 1 2 3 1 4
3 3 1 1 1 2 3
sample output 2:
5
Problem analysis
First of all, let's think about the dyeing , Because we dye a root node and its subtree in the same color at one time . Then if the color of the subtree is different from the root node , Then it must have dyed the root node first , Then dye the subtree . So our coloring step is to start from the root node , Gradually dyed .
Then we can dfs To deal with it , If the current color of this node is different from the target color , We will dye the whole subtree into its target color , Dyeing times ++, Then traverse all its children , And the target color of this node is the new color of their children . Then when the child's target color is different from this color , Just keep dyeing .
Finally, output the dyeing times .
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
unordered_map<int, int>color;
unordered_map<int, vector<int>>mymap;
int cnt = 0;
//x Is the value of the current node ,y Is the color of the parent node of this node
void dfs(int x,int y)
{
if (y != color[x])cnt++;
for (auto i : mymap[x])
{
dfs(i, color[x]);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, x;
cin >> n;
for (int i = 2; i <= n; i++)
{
cin >> x;
mymap[x].push_back(i);
}
for (int i = 1; i <= n; i++)
{
cin >> x;
color[i] = x;
}
dfs(1,0);
cout << cnt << endl;
return 0;
}
边栏推荐
- Auto.js入门
- [exercise-4] (UVA 11988) broken keyboard = = (linked list)
- It is forbidden to trigger onchange in antd upload beforeupload
- 去掉input聚焦时的边框
- Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
- HDU - 6024 building shops (girls' competition)
- 1529. Minimum number of suffix flips
- E. Breaking the Wall
- C language must memorize code Encyclopedia
- Analysis of protobuf format of real-time barrage and historical barrage at station B
猜你喜欢
Data storage in memory & loading into memory to make the program run
2078. Two houses with different colors and the farthest distance
Analysis of protobuf format of real-time barrage and historical barrage at station B
分享一个在树莓派运行dash应用的实例。
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
QWidget代码设置样式表探讨
树莓派4B64位系统安装miniconda(折腾了几天终于解决)
Programmers, what are your skills in code writing?
(POJ - 3579) median (two points)
力扣:第81场双周赛
随机推荐
window11 conda安装pytorch过程中遇到的一些问题
C basic grammar
AcWing:第56场周赛
Opencv learning log 27 -- chip positioning
Codeforces - 1526C1&&C2 - Potions
Classic application of stack -- bracket matching problem
969. Pancake sorting
QT按钮点击切换QLineEdit焦点(含代码)
useEffect,函數組件掛載和卸載時觸發
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
875. Leetcode, a banana lover
2027. Minimum number of operations to convert strings
(POJ - 3579) median (two points)
TCP's three handshakes and four waves
Codeforces Round #800 (Div. 2)AC
Determine the Photo Position
Opencv learning log 26 -- detect circular holes and mark them
1855. Maximum distance of subscript alignment
[exercise-6] (UVA 725) division = = violence
7-1 understand everything (20 points)