当前位置:网站首页>Acwing - game 55 of the week
Acwing - game 55 of the week
2022-07-06 16:14:00 【Hello_ Ä】
AcWing—— The first 55 Weekly match
competition - AcWing
4479. The longest subsequence - AcWing Question bank
Given a length of n Sequence a1,a2,…,an And a length of m Sequence b1,b2,…,bm.
Now? , We want to find a sequence a The subsequence , Make the subsequence satisfy :
Every element in the subsequence is in the sequence b There has been .
The length of the subsequence should be as long as possible .
Please output the longest subsequence that meets the conditions .
Input format
The first line contains two integers n,m.
The second line contains n It's an integer a1,a2,…,an.
The third line contains m It's an integer b1,b2,…,bm.
Output format
Output the longest subsequence satisfying the condition in one line .
If the longest subsequence satisfying the condition is null , You can output nothing or a single line break .
Data range
All test points meet 1≤n,m≤10,0≤ai,bi≤9.
sample input 1:
7 3
3 5 7 1 6 2 8
1 2 7
sample output 1:
7 1 2
Problem analysis
The title requires the output of “ Sequence ”, Go straight through a Array , If a[i] stay b[i] Once it appears, just output this element .
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;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int>a(n), b(m);
unordered_map<int, int>mymap;
for (int i = 0; i < n; i++)cin >> a[i];
for (int i = 0; i < m; i++)
{
cin >> b[i];
mymap[b[i]] = 1;
}
for (int i = 0; i < n; i++)
{
if (mymap[a[i]])cout << a[i] << " ";
}
return 0;
}
4480. take out the trash - AcWing Question bank
A street can be regarded as a number axis .
On the street lived n Residents with m A trash can , Each resident's residence or trash can occupies a location .
It is known that , this n+m The two positions are different .
Every resident will go to the nearest garbage can to his home every day to take out the garbage .
If such a trash can is not unique , Then the residents will give priority to go to the garbage can with smaller location coordinates to dump garbage .
Please calculate , For each trash can , How many residents take out garbage at the garbage can every day .
Input format
The first line contains two integers n,m.
The second line contains n+m It's an integer x1,x2,…,xn+m, Indicates the location coordinates of all residents' residences and garbage cans .
The third line contains n+m It's an integer t1,t2,…,tn+m, If ti=1, It means No i At the coordinates of the first position is the garbage can , If ti=0, It means No i At the coordinates of three positions is the residence of the residents .
Input guarantee , Satisfy ti=1 Of i The quantity of is m.
Output format
You might as well follow the order of position coordinates from small to large , take m Bin number 1∼m.
Please output in one line m It's an integer a1,a2,…,am, among ai Means every day on the i The number of residents taking out garbage at the garbage cans .
Data range
The first three test points meet 1≤n,m≤5.
All test points meet 1≤n,m≤105,1≤x1<x2<…<xn+m≤109,0≤ti≤1.
sample input 1:
3 1
1 2 3 10
0 0 1 0
sample output 1:
3
sample input 2:
1 4
2 4 6 10 15
1 1 1 1 0
sample output 2:
0 0 0 1
Problem analysis
Sliding window method .
First put all the garbage cans into an array ans in , If there's only one trash can , Direct output n The value of the can , Because all the garbage can only be thrown there .
We use double pointers l、r To point to the location of the trash can , Traverse all households , If the current resident's position is between the positions pointed by our double pointer , Then we can judge by calculation that this resident is going to l Throw it well or r good ( If equal , Also go to l throw ), And write it down , When the location of residents is larger than ours r The pointer , Then move the window to the right (l Point to the original r,r Go down one , If r It's the last trash can , Just move the left pointer ), Because if the household location is greater than r 了 , So relative to l Distance of , The resident must have arrived r The distance between them is smaller . Finally, output the quantity of all records .
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;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int>a(n + m), b(m + n), ans;
unordered_map<int, int>mymap,cnt;
if (m == 1)
{
cout << n << endl;
return 0;
}
for (int i = 0; i < n+m; i++)cin >> a[i];
for (int i = 0; i < n+m; i++)
{
cin >> b[i];
if (b[i] == 1)ans.push_back(a[i]), mymap[a[i]] = 1;
}
int l = 0, r = 1;
for (int i = 0; i < n+m; i++)
{
if (a[i] > ans[r])
{
l = r;
if (r + 1 < m)r++;
}
if (mymap[a[i]] == 0)
{
if (abs(a[i] - ans[l]) <= abs(a[i] - ans[r]))
{
cnt[ans[l]]++;
}
else
{
cnt[ans[r]]++;
}
}
}
for (int i = 0; i < m; i++)cout << cnt[ans[i]] << " ";
return 0;
}
4481. Grid exploration - AcWing Question bank
Given a n That's ok m The grid matrix of columns . The row coordinates from top to bottom are 1∼n, The column coordinates from left to right are 1∼m.
Each of these squares , Or a space ( use . Express ), Or it contains obstacles ( use * Express ).
At the beginning , One person is in the r Xing di c In the space of the column .
He can move up, down, left and right , Move one space at a time .
For his movement , There are the following restrictions :
He cannot enter a square containing obstacles , Nor can it go beyond the bounds of the matrix .
Throughout the movement , The total number of times he moves to the left cannot exceed x Time .
Throughout the movement , The total number of times he moves to the right cannot exceed y Time .
Excuse me, , How many spaces can this person reach ?
Be careful , The initial space is considered as the person can reach .
Input format
The first line contains two integers n,m.
The second line contains two integers r,c.
The third line contains two integers x,y.
Next n That's ok , Each line contains a length of m By . and * Composed string , Used to describe a square matrix .
Input guarantee No r Xing di c The box of the column must be a space .
Output format
An integer , Indicates the number of reachable spaces .
Data range
The first three test points meet 1≤n,m≤5.
All test points meet 1≤n,m≤2000,1≤r≤n,1≤c≤m,0≤x,y≤10^9.
sample input :
4 5
3 2
1 2
.....
.***.
...**
*....
sample output :
10
Problem analysis
The maze problem , But here you need to record how many steps you have taken to the left or right .
The queue should make its own custom data type , To be able to store four variables :{ Abscissa , Ordinate , The number of times you have left , The number of times you have walked to the right }, Then there is the standard maze , It's just that the corresponding variables are +1, If the number is greater than the limit , Then you can't get to this level .
When we get to the first space, we have to make two marks , One is to judge whether this grid has passed before , If not, mark it , And counter ++; The other is to record that you have walked left or right several times when you came to this grid , If you want to go further , Then you must walk left and right less often , If you reach this grid again , If you walk left and right more than we recorded before, skip , If less than, replace the mark , And join the team at this point .
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;
PII cnt[2050][2050];
int mymap[2050][2050];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, x, y, a, b, res = 1;
cin >> n >> m >> x >> y >> a >> b;
vector<string>v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
queue<pair<pair<int, int>, pair<int, int>>>que;
que.push({ {x - 1,y - 1} ,{0,0} });
mymap[x - 1][y - 1] = 1;
while (!que.empty())
{
int len = que.size();
for (int i = 0; i < len; i++)
{
pair<pair<int, int>, pair<int, int>> t = que.front();
que.pop();
int l = t.second.first, r = t.second.second;
for (int j = 0; j < 4; j++)
{
int c = l + (j == 3), d = r + (j == 1);
if (c > a || d > b)continue;
int x1 = t.first.first + dx[j], y1 = t.first.second + dy[j];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && v[x1][y1] == '.')
{
if (mymap[x1][y1] && cnt[x1][y1].first <= c && cnt[x1][y1].second <= d)continue;
if (mymap[x1][y1] == 0)
{
mymap[x1][y1] = 1;
res++;
}
cnt[x1][y1] = { c,d };
que.push({ {x1,y1},{c,d} });
}
}
}
}
cout << res << endl;
return 0;
}
边栏推荐
- 滲透測試 ( 1 ) --- 必備 工具、導航
- 1323. Maximum number of 6 and 9
- C language is the watershed between low-level and high-level
- (POJ - 2739) sum of constructive prime numbers (ruler or two points)
- (POJ - 3579) median (two points)
- 指定格式时间,月份天数前补零
- Auto. Getting started with JS
- 日期加1天
- 生成随机密码/验证码
- Codeforces Round #798 (Div. 2)A~D
猜你喜欢
Suffix expression (greed + thinking)
顺丰科技智慧物流校园技术挑战赛(无t4)
7-1 understand everything (20 points)
807. Maintain the urban skyline
C language must memorize code Encyclopedia
antd upload beforeUpload中禁止触发onchange
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
Nodejs+vue online fresh flower shop sales information system express+mysql
Advancedinstaller安装包自定义操作打开文件
D - function (HDU - 6546) girls' competition
随机推荐
QNetworkAccessManager实现ftp功能总结
window11 conda安装pytorch过程中遇到的一些问题
Penetration test (4) -- detailed explanation of meterpreter command
2078. Two houses with different colors and the farthest distance
Useeffect, triggered when function components are mounted and unloaded
Essai de pénétration (1) - - outils nécessaires, navigation
C language is the watershed between low-level and high-level
7-1 understand everything (20 points)
Penetration test (3) -- Metasploit framework (MSF)
Pytorch extract skeleton (differentiable)
Input can only input numbers, limited input
The concept of C language array
读取和保存zarr文件
Alice and Bob (2021 Niuke summer multi school training camp 1)
Codeforces Round #797 (Div. 3)无F
日期加1天
Candy delivery (Mathematics)
Opencv learning log 28 -- detect the red cup cover
Write web games in C language
力扣:第81场双周赛