This article is Codeforces Round #798 (Div. 2) That is to say CF1689 The antithesis of , Because I am good at cooking , So only the first four questions
A.Lex String
Title Description
The original question surface
Given two strings \(a,b\), The following two operations are required to construct a new string \(c\), bring \(c\) The order of the dictionary is the smallest , And it is required that a certain operation cannot be used continuously for more than \(k\) Time
1. from \(a\) in Optional Insert a character into \(c\) At the end of
2. from \(b\) in Optional Insert a character into \(c\) At the end of
If a string is empty, the construction is considered to be over .
If the string \(x\) Ratio string \(y\) A small dictionary order must satisfy In the following two cases One of ：
1.\(x\) by \(y\) The prefix of , And \(x \not= y\)
2. From left to right ,\(x\) And \(y\) The first different position \(x\) The lexicographic order of the characters of \(y\) The dictionary order of the characters of is small
Topic analysis
We can find one thing first ： There is no difference between the end of insertion and the beginning of insertion
So for the sake of small dictionary order, we must choose every time \(a,b\) The smallest character in the dictionary , If you exceed \(k\) Select another string at a time , Just choose it next time
It should be noted that the dictionary order here does not include ： Only the string length is smaller , So there is no need to consider the length of the constructed string
Code details
Click to view the code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
char a[MAXN],b[MAXN];
int main(){
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int i=1; i<=m; i++){
cin>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int l = 1,r = 1,tmp = 0;
bool flag = false;
while(l <= n && r <= m){
if(a[l] < b[r]){
if(flag){
cout<<a[l++];
flag = false;
tmp = 1;
}
else{
if(tmp < k){
cout<<a[l++];
tmp++;
}
else{
cout<<b[r++];
tmp = 1;
flag = true;
}
}
}
else if(a[l] >= b[r]){
if(!flag){
cout<<b[r++];
flag = true;
tmp = 1;
}
else{
if(tmp < k){
cout<<b[r++];
tmp++;
}
else{
cout<<a[l++];
tmp=1;
flag = false;
}
}
}
}
cout<<endl;
}
return 0;
}
Actually, the code is a little complicated , But the idea is simple
B. Mystic Permutation
Title Description
The original question surface
Given a \([1,n]\) Permutation , Ask you to construct a \([1,n]\) Permutation , Make any element in the same position between the two permutations different , And the lexicographic order satisfying this arrangement is the smallest .
If such a sequence cannot be constructed, output -1
Topic analysis
A very normal idea ： Insert elements from small to large , If you encounter the same or used one, skip
But there is a situation that the last element of the sequence is \(n\), So when we put the last element, we only have \(n\), Then it can't be placed anyway
This problem is also very easy to solve ： The last element \(n\) We certainly can't put ourselves in a very forward position , Because it is obvious that the dictionary order will not be the smallest , So in order to make this element fit, we put it in \(n-1\) Location , Give Way \(n-1\) The element that should have been placed in the position of the \(n\) On , This will ensure that before \(n-2\) One must be the smallest , There is no other way to make the last two elements smaller and smaller than what we are placing now \(n-2\) One remains the smallest .
One example is really strong , Otherwise, I should not have found this .
Code details
Click to view the code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
bool flag[MAXN];
int a[MAXN];
int main(){
int t;
cin>>t;
while(t--){
memset(flag,false,sizeof(flag));
int n;
cin>>n;
if(n == 1){
cin>>a[1];
printf("-1\n");
continue;
}
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int i=1; i<=n; i++){
if(i == n - 1 && !flag[a[n]]){
printf("%d ",a[n]);
flag[a[n]] = true;
}
for(int j=1; j<=n; j++){
if(!flag[j] && j != a[i]){
printf("%d ",j);
flag[j] = true;
break;
}
}
}
cout<<endl;
}
return 0;
}
Because the data range is small , So in order to write more comfortable, I wrote such a very violent practice , But it should be easier for us to understand .
C. Infected Tree
Title Description
The original question surface
Give a tree with \(1\) Binary tree with node No. as root , Now? \(1\) Node is infected with a virus , Every round, the virus will infect the nodes directly connected to the node , In this round, you can choose to delete any point that is not infected by the virus , In this way, it is disconnected from its directly connected point , Ask the maximum number of points that can not be infected by the virus , Deleted points are not considered as points that are not infected by viruses
Topic analysis
We consider keeping as many nodes as possible , Every time, we will delete a child node of the node infected by the virus , After deletion, our problem can be transformed into another son （ Note the binary tree ） The sub problem of how many nodes can be reserved by the infected root virus , So it's obvious to consider \(DP\).\(DP\) The state is also very simple ：\(dp[i]\) Said to \(i\) A subtree that is a root \(i\) Infected with a virus , The maximum number of nodes can be reserved
So the following is to consider the transfer , The transfer is obviously what we consider to delete \(i\) The child nodes of the , Because it is a binary tree, there is no need to consider more cases . Then we will consider which child node to delete , Suppose you delete \(son_1\), So it's equivalent to \(son_1\) We can keep in the subtree of \(size[son_1] - 1\) Nodes ,\(size[i]\) Representative to \(i\) Is the size of the subtree of the root （ Include nodes \(i\)）, And in the \(son_2\) In the subtree , We can still keep it \(dp[son_2]\) Nodes , So the final state is ：
\]
Note that the subtree may be empty , that \(size[son] - 1\) It's a negative number , So you need to \(0\) take \(\max\), Avoid this situation
Code details
Click to view the code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
struct edge{
int nxt,to;
edge(){}
edge(int _nxt,int _to){
nxt = _nxt,to = _to;
}
}e[2 * MAXN];
int ans = 0,cnt,head[MAXN],dp[MAXN],sz[MAXN];
//dp[now] Said to now Root subtree , hypothesis now infected , How many are reserved at most
void add_edge(int from,int to){
e[++cnt] = edge(head[from],to);
head[from] = cnt;
}
void dfs(int now,int fa){
sz[now] = 1;
int son[3] = {0,0,0};
int tot = 0;
for(int i=head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fa) continue;
son[++tot] = to;
dfs(to,now);
sz[now] += sz[to];
}
// Go to son[1] / Go to son[2]
dp[now] = max(dp[son[1]] + max(sz[son[2]] - 1,0),dp[son[2]] + max(sz[son[1]] - 1,0));
}
int main(){
int t;
cin>>t;
while(t--){
memset(head,0,sizeof(head));
memset(dp,0,sizeof(dp));
memset(sz,0,sizeof(sz));
ans = 0;
int n;
cin>>n;
for(int i=1; i<n; i++){
int from,to;
cin>>from>>to;
add_edge(from,to);
add_edge(to,from);
}
dfs(1,0);
printf("%d\n",dp[1]);
}
return 0;
}
to \(dfs\) Update again \(sz\) and \(dp\), And multiple groups of data, so you need to clear various arrays each time , Zero clearing \(head\) An array is also equivalent to an array with zeroed edges
D. Lena and Matrix
Title Description
The original question surface
Given a \(n\times m\) Matrix , Each location has a color , Black or white respectively , Ask you to choose a location （ Regardless of the color in this position ）, Minimize the maximum Manhattan distance from the whole position to all black grids .
Manhattan distance ：\(|x_1 - x_2| + |y_1 - y_2|\)
Topic analysis
The maximum value and the minimum value are required , In fact, it is found that the distance between the maximum value and any black grid may not be the maximum value , The black grid that can become the largest distance must be the top left 、 The lower right 、 The lower left 、 The black grid on the right , It can be found that if not these four grids , Then converting the distance to these four black grids will certainly increase
Here is how to find the four black squares , I think this idea is still very magical .
Consider if a grid is closer to the upper left corner ,\(x\) The smaller it is ,\(y\) The smaller it is , and \(x\) And \(y\) Reduction of , The contribution to its distance from the upper left corner is the same , Then make this contribution directly as \(x+y\), Then the point at the top left corner must be the point with the least contribution , The point at the bottom right corner must also be the point with the greatest contribution , This solves two problems .
Consider if the upper right corner of a grid is closer ,\(x\) The bigger it is ,\(y\) The smaller it is , And their contributions are the same , So consider making contributions directly to \(x-y\), So the top right point is \(x-y\) The biggest point , The bottom left point is \(x-y\) The smallest point , So far, all the four points have been solved .
Then, it is necessary to find a location to minimize the maximum distance from this location to the four locations , So just enumerate each location and look for it
Code details
Click to view the code
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
struct node{
int x,y;
node(){}
node(int _x,int _y){
x = _x,y = _y;
}
};
int main(){
int t;
cin>>t;
while(t--){
node a[6];
bool flag[6];
memset(flag,0,sizeof(flag));
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
char h;
cin>>h;
if(h == 'B'){
if(i + j > a[1].x + a[1].y || !flag[1]) a[1] = node(i,j),flag[1] = true;
// The lower right corner i + j The bigger it is
if(i + j < a[2].x + a[2].y || !flag[2]) a[2] = node(i,j),flag[2] = true;
// The more in the upper left corner i + j The smaller it is
if(i - j > a[3].x - a[3].y || !flag[3]) a[3] = node(i,j),flag[3] = true;
// The more on the top right i - j The bigger it is
if(i - j < a[4].x - a[4].y || !flag[4]) a[4] = node(i,j),flag[4] = true;
// More in the lower left corner i - j The smaller it is
}
}
}
int res = INF;
node ans;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
int h = 0;
for(int k=1; k<=4; k++){
h = max(h,abs(i - a[k].x) + abs(j - a[k].y));
}
if(h < res){
ans = node(i,j);
res = h;
}
}
}
printf("%d %d\n",ans.x,ans.y);
}
return 0;
}
First, find four points, and enumerate each position , The final output is good
【 Answer key 】Codeforces Round #798 (Div. 2) More articles about
- [ Answer key ] Codeforces Round #549 (Div. 2) B. Nirvana
Codeforces Round #549 (Div. 2) B. Nirvana [ Title Description ] B. Nirvana time limit per test1 second memory limit ...
- [ Answer key ]Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) - A. Basic Diplomacy
[ subject ] A. Basic Diplomacy [ describe ] Aleksey Yes n A friend , There is one m Days off , He needs a friend to accompany him every day . Give the number of friends who are free every day , The number of days required for the same friend to come cannot exceed m/2 Round up . seek ...
- [ Answer key ]Codeforces Round #254 (Div. 2) B - DZY Loves Chemistry
link :http://codeforces.com/contest/445/problem/B describe :n Drugs ,m Reaction relationships , Put it into the test tube in a certain order . If the currently placed drug is to react with the drug in the test tube , The risk factor becomes ...
- [ Answer key ]Codeforces Round #254 (Div. 2) A - DZY Loves Chessboard
link :http://codeforces.com/contest/445/problem/A describe : One n*m The chessboard of , There are some spaces that cannot be used for chess pieces . Now put the black and white chessmen up , It is required that the chessmen with full and adjacent grids have different colors . Output ...
- Answer key ——Codeforces Round #508 (Div. 2) T3 （ greedy ）
Greedy selection of the optimal solution And then subtract it Remember to drive long long #include <cstdio> #include <algorithm> #include <cstring ...
- Answer key ——Codeforces Round #508 (Div. 2) T2 ( structure )
Just construct a set according to the meaning of the title Pay attention to the judgment of no solution #include <cstdio> #include <algorithm> #include <cstring> #in ...
- Answer key ——Codeforces Round #508 (Div. 2) T1 ( simulation )
According to the meaning of the topic, violence simulation can A fall #include <cstdio> #include <algorithm> #include <cstring> #include &l ...
- Codeforces Round #160 (Div. 1) Answer key 【ABCD】
Codeforces Round #160 (Div. 1) A - Maxim and Discounts The question Here you are. n A discount ,m Items , Each discount can be used unlimited times , Every time you use the i At a discount , You must ...
- Codeforces Round #383 (Div. 2) Answer key 【ABCDE】
Codeforces Round #383 (Div. 2) A. Arpa's hard exam and Mehrdad's naive cheat The question seek 1378^n mod 10 Answer key direct ...
- Codeforces Round #271 (Div. 2) Answer key 【ABCDEF】
Codeforces Round #271 (Div. 2) A - Keyboard The question Give you a string , Ask you to move this string to the left in the position of the keyboard , Or move one character to the right , What does this string look like Answer key ...
Random recommendation
- jquery The page scrolls to the bottom to automatically load the plug-in collection
Many social networking sites use unlimited scrolling page flipping technology to improve the user experience , When you slide to the bottom of the list, you automatically load more content without clicking . Here's how to recommend 10 individual jQuery Unlimited scrolling plug-in : 1. jQuery ScrollPa ...
- name after, name for, name as
name after, name for, name as name after It's a common usage : 1.Her parents named her Sophia after her grandmo ...
- js Anonymous function in Array sorting
// Anonymous functions : It's actually a short form of a function var method =function(){ alert("123"); } method(); // Anonymous functions can be used to handle events fun ...
- leetcode：Isomorphic Strings
Isomorphic Strings Given two strings s and t, determine if they are isomorphic. Two strings are isom ...
- QOdbc Reading and writing excel
).toString(); ).toInt(); qDebug()<< name << age <<endl; } // Close the database db.close(); } i ...
- C# It defines itself implicit and explicit transformation
Implicit conversion and explicit conversion are often encountered in type conversion . How do we define implicit and explicit conversions for the types we define ? Let's look at a piece of code public class Rational { private Int32 _inner_ ...
- Linux The concept and operation of process and signal
process Main reference : http://www.bogotobogo.com/Linux/linux_process_and_signals.php Signals and processes control almost every task of the operating system . stay shell Lose ...
- 2017 year 11 month Dyn365/CRM Sign up for user community activities
UG It's the biggest in the world Dynamics The user organization of , Spontaneously organized by end users , A non-profit organization in which industry experienced experts volunteer their knowledge and experience , The participants were pragmatic and neutral , Don't promote products , Services and other marketing activities . In the U.S. , Microsoft Dynam ...
- node As a client, request a third party
var http = require('http'); let util = require('util'); http.get('http://www.imooc.com/u/card',funct ...
- Android Calendar control of custom control
label : android Control The calendar application demand 2015 year 09 month 26 Japan 22:21:54 25062 Human reading Comment on (109) Collection report classification : Android Custom control series (7) Copyright notice : Reprint note ...
![leetcode：926. Flip the string to monotonically increasing [prefix and + analog analysis]](/img/e8/a43b397155c6957b142dd0feb59885.png)
