A very sacrificial tournament, nothing.
Title List:
and Black
and White
and Black
and White
and Black
\(0 pts\)
Topic Meaning:
You are given a tree with root 1 , initially all points are white, each query gives a set of points, if all the points in the set are colored black, ask how many nodes need to be flipped at least to make the whole tree all white. No solution output -1. queries are independent of each other
Flipping is defined as flipping the color of node u and all nodes in its subtree.
Race Time Analysis:
Not during the race, thought of the time complexity\(O(n * m)\) on the tree of DP, thought it was a positive solution (time complexity wanted to be false)\(n\) check or refer to\(log\large{n}\) (calculated), only to find out after typing that the time complexity was wrong, and after that it was just a matter of thinking about how to optimize on top of that, and have been thinking about putting the\(n\) change into\(log \large{n}\)The local runtime is a large sample from the\(36s\) The card is always optimized to\(1.9s\), but the time complexity did not change, probably tuned more than an hour anxious, directly handed over, thinking that can take a\(30pts\)The special nature was not thought of, and the resultant bundle of tests was actually scored\(0pts\)。
In the future, the simulation game can not be a thought consuming, can not be too overestimated, like this question, the nature of not so difficult to think, but I just did not think of what nature, has been optimizing their own dp, it seems that in the future, we need to timely deny their own change of mind.
Positive solution:
Note: The phrases "blacken a point" and the like below all refer to blackening the subtree rooted at that point.
Thoughts:
We enumerate each point that is blackened, set to\(u\)As a result of\(u\) It's already stained black, so we're definitely going to stain it back if the\(u\) The father node of the\(fa\) is also a black point, then we are in the process of converting the\(fa\) After the operation of coloring to white spots, naturally together with the\(u\) Dyed white;
enumerate again\(u\) child node of\(son\)If\(son\) is white, then after putting the\(u\) Dye back in the operation\(son\) It's blackened at the point, so it needs to be dyed again.\(son\) Point.
Calculate the answer\(ans\) time, then we only need to iterate over each point that is colored black, or once if its parent node is not black.\(ans++\), then iterate through its children, and if the children are white dots, then dye the children once more.\(ans++\)。
This is the idea, but it is easier to see that the time complexity is\(O(Q n m)\)，（\(Q\) (for the number of queries) that would\(T\) Drop.
code of violence
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, Q, m, in[N];
int color[N], fa[N];
map<pair<int, int>, int>son;
signed main(){
// freopen("", "r", stdin); freopen("", "w", stdout);
scanf("%d%d", &n, &Q);
for(int i=2; i<=n; i++){
scanf("%d", &fa[i]);
son[mp(fa[i], ++son[mp(fa[i], 0)])] = i;
}
while(Q--)
{
scanf("%d", &m);
for(register int i=1; i<=m; i++){
scanf("%d", &in[i]);
color[in[i]] = 1;
}
int ans = 0;
for(int i=1; i<=m; i++){
if(!color[fa[in[i]]]) ans++;
for(int j=1; j<=son[mp(in[i], 0)]; j++){
if(!color[son[mp(in[i], j)]]) ans++;
}
}
printf("%d\n", ans);
for(register int i=1; i<=m; i++) color[in[i]] = 0;
}
return 0;
}
Consider optimization:
The one with more time complexity\(n\) It is the enumeration of the son nodes of each black point that leads to this, so we consider whether we can not enumerate each son, we can preprocess out of the number of sons of each node when the number of sons of each node, these numbers do not change, "do not care whether the black son or the white son is a son".
So when enumerating each black point, we can just add the number of sons of that point. But this adds more black sons ah, according to our thinking only add white sons, but don't forget, black sons are dyed black points, so we enumerate all the black points will always enumerate these extra black sons, then we enumerate, determine the enumeration of the point's father node is black, if the father node is white, then add an operation, otherwise put the subtraction of an operation, which subtracts the extra black sons.
Successfully optimized to\(O(Q n)\) Up!
Final Code:
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, Q, m, in[N];
int color[N], fa[N], son[N];
signed main(){
// freopen("", "r", stdin); freopen("", "w", stdout);
scanf("%d%d", &n, &Q);
for(int i=2; i<=n; i++){
scanf("%d", &fa[i]);
son[fa[i]]++;
}
while(Q--)
{
scanf("%d", &m);
for(register int i=1; i<=m; i++){
scanf("%d", &in[i]);
color[in[i]] = 1;
}
int ans = 0;
for(int i=1; i<=m; i++){
if(!color[fa[in[i]]]) ans++;
else ans--;
ans += son[in[i]];
}
printf("%d\n", ans);
for(register int i=1; i<=m; i++) color[in[i]] = 0;
}
return 0;
}
White and White
Topic Meaning:
White has a length of\(n\) series of positive integers\(A\) , and now he's working on a method of dividing the series.
The division is to divide this this series into\(k\) A number of non-empty consecutive segments, each of which is valued as the sum of all the numbers in the segment for a given Wyatt number\(p\) The value after taking the mold.
feasible\(k\) The division method that minimizes the sum of the values of the segments becomes known as White's division.
Black and Black
Topic Meaning:
Blake now has a length of\(n\) sequences\(A\)But since his dp is not good, the\(A\) The sequence will only have the numbers 1,-1, and he doesn't know what that's for, but it makes it easier when you need a dp, right?
To be more prepared for future dp's, now he wants to solve for a Blake sequence\(B\) The Blake Sequence\(B\) The following restrictions are met
- The sequence length is also\(n\)
- \(∣Bi∣≤2×10^{12}；\)
- The sequence is strictly increasing, i.e.\(∀1≤i<n，Bi<Bi+1\)；
- \(∑_{i=1}^nAiBi=0\)。
Given a sequence, find whether it is a Blake sequence.
Race Time Analysis:
In fact, I basically thought of the positive solution during the match, but because I was stuck in T2 for too long, I didn't even dare to think carefully about T3 even though the positive solution had already appeared in my mind, and I just played through the violence of T3 and T4 in the last half hour.
Positive solution:
Construct. We'll start by adding the\(b_i\) assign\(i\)and seek\(∑_{i=1}^n b_i * a_i\) The sum of is denoted by\(sum\)Ask for one.\(s\) The array is\(a\) The prefix of the array.
-
as\(sum=0\) Just output it directly
-
\(sum>0\) hour
- Sweep it from top to bottom.\(s\)Find the first one.\(s_i>0\) case, (since it's the first one, then there must be a found\(s_i=1\) ) then that means we can put\(b_j(j\in[1, i])\) both minus\(sum\), which is equivalent to the entire\(b\) The sum of the arrays minus the\(sum\)If it is not, then the sum will be 0;
- If you don't get it, then sweep again from end to end and find the first one\(s_n - s_i<0\) case (ibid.\(s_n-s_i=-1\)), so that we put\(b_j (j\in[i, n])\) All of it.\(sum\) Ready to go;
- If you still can't find it, then it means there is no solution and outputs -1.
-
\(sum<0\) If you do not want to use it, just do the opposite of the above.
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, a[N]; ll b[N], sum;
ll s[N];
inline void print(){
puts("Yes");
for(int i=1; i<=n; i++) printf("%lld ", b[i]);
}
int main(){
// freopen("", "r", stdin); freopen("", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
s[i] = s[i-1] + a[i];
b[i] = i; sum += i * a[i];
}
if(sum == 0) print();
else if(sum < 0){
for(int i=n; i>=1; i--){
if(s[n] - s[i-1] > 0){
for(int j=i; j<=n; j++){
b[j] += -sum;
}
print();
return 0;
}
}
for(int i=1; i<=n; i++){
if(s[i] - s[0] < 0){
for(int j=1; j<=i; j++){
b[j] += sum;
}
print();return 0;
}
}
puts("No");
}
else{
for(int i=n; i>=1; i--){
if(s[n] - s[i-1] < 0){
for(int j=i; j<=n; j++)
b[j] += sum;
print();
return 0;
}
}
for(int i=1; i<=n; i++){
if(s[i] - s[0] > 0){
for(int j=1; j<=i; j++)
b[j] -= sum;
print();
return 0;
}
}
puts("No");
}
return 0;
}
Black and White
Topic Meaning:
Given a tree with all sides of length 1 and all points initially black, there are the following two operations:
-
C ucheck mark\(u\) of color reversal, i.e., black to white and white to black; -
GAsk the distance between the two farthest black dots;
For each operation G, output an integer indicating the distance between the two farthest black points.