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
![[online problem] timeout waiting for connection from pool](/img/f0/7e8444ed7d0921b98d5e998e274bc8.png)
