Attention: Because of the terrible input method, I couldn't input Chinese characters fluently so this blog is written in English.
A
Description:Given an expression that only contains '*', '+' and numbers, you should replace one character change it to another expression (the same character is allowed but leading zeros are not) , then find the sum of the values of all legal expressions.
The length of the expression is \(\le 100\).
Solution:Using long long can get 80 points, using the high precision algorithm can get all points.
Attention:If the high precision algorithm is not simple for you to write, the best solution may be giving up this problem because you cannot get much points by writing this algorithm (If you want a beautiful score you better get all points because it is the first problem) .
Code:Too trivial to show.
B
Description:Now there are \(n\) tasks and one machine. One machine can only finish one task and after that it will break. But you can use magic to change one machine into two machines for \(m\) time. Different machines can finish different tasks but one task can only be finished by one machine. Find the minimum time to finish all tasks.
Solution:A simple greedy strategy is not to use magic to a broken machine. Then we can find that all tasks look like a binary tree and the time of finishing the task \(i\) is \(dep[i]+time[i]\). So you can sort all \(time[i]\) from small to large and put the smallest \(time[i]\) in the deepest node. Then we can find that a subtree is an interval of tasks. So let \(f[l][r]\) be the minimum time of interval \([l,r]\), then \(f[l][r]=\min\{f[l][r],\max\{f[l][k],f[k+1][r]\}+m\}(k\in [l,r))\)
Code:
#define N 210
int n,m,t[N],f[N][N];
int main(){
Read(n),Read(m);
for(rg int i=1;i<=n;i++)Read(t[i]);
sort(t+1,t+1+n);
memset(f,0x3f,sizeof(f));
for(rg int i=1;i<=n;i++)f[i][i]=t[i];
for(rg int l=2;l<=n;l++){
for(rg int i=1;i+l-1<=n;i++){
int j=i+l-1;
for(rg int k=i;k<j;k++){
f[i][j]=min(f[i][j],max(f[i][k],f[k+1][j])+m);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
C
Description:You have a data unit of size \(m\), and the numbers in all positions are 0 at the beginning. Then you will get \(n\) numbers, for every number, it has a probability of \(p=\frac ab\) to save this number. If you save a number, it will replace any of the \(m\) positions with equal probability. Your task is to find the expectation of the sum of the numbers in the data unit from \(p1\) to \(p2\).
Two modify operation:
1.Change the probability of the position \(p\) into \(v\).
2.Increase the data from \(l\) to \(r\) by \(v\).
Solution:
Calculate the expectation of saving each number (\(q_i=p_i\prod_{j=i+1}^n (1-\frac{p_j}m)\)) , then use Segment Tree.
Then the problem is what information do we need to save and how to maintain it.
Code:Cuckoo Cuckoo Cuckoo
D
Description:You should walk from \((0,0)\) to \((x,y)\), you can only reach lattice point and the square of the distance of each step must be \(\le d\). Find the minimum number of steps.
Solution:
\(\color{red}{You\ need\ to\ know\ something\ about\ computational\ geometry.}\)
Look at the following pic, the red points are reachable and the star is \((x,y)\).
We can use Binary Search twice. First, we should find that \((x,y)\) is between which two vectors.Then, we should find that how many steps we need.
Implementation:For the first search, use vector product (\(\times\)). For the second search, let \((x_{m1},y_{m1})\) and \((x_{m2},y_{m2})\) be the point after \(m\) steps. Then connect them as \(AB\), if \((x,y)\) is in \(\triangle OAB\), the answer is ok.
Code:Cuckoo Cuckoo Cuckoo
The End
Code will appear after CSP-S 2020 and NOIp 2020