Home > Article > Web Front-end > SRM 400 Div1_html/css_WEB-ITnose
This set of questions makes my balls hurt
250
Simple questions. Asking whether a number can be expressed as several powers of a certain prime number
I used a method that loses accuracy
In fact, as long as the square determination is completed and the prime numbers are directly enumerated, it will be OK
vector<int>ans;bool check(int x) { int m = (int)sqrt(x * 1.0) + 1; if(x == 2) return true; for(int i = 2; i <= m; i++) { if(x % i == 0) return false; } return true;}void gao(long long x) { int x1 = -1, x2 = -1; for(int i = 2; i < 60; i++) { int f = (int)(pow((double)x, 1.0 / i) + eps); long long tmp = 1; for(int j = 0; j < i; j++) tmp = tmp * (long long)f; if(tmp == x) { if(check(f)) { x1 = f, x2 = i; } } } if(x1 != -1) { ans.push_back(x1); ans.push_back(x2); }}
500
Interval DP
The meaning of the question is Say, given an A string, a B string
only contains 0 and 1, and then use a series of reverse operations to turn A into B
reverse(i,j) means The interval i, j is reversed
and then there is a restriction on this series of operations
that is, after an operation is completed, the next operation must be performed in a sub-interval of the interval of this operation, each time This is true for every operation
Then this is definitely convenient for interval DP
I saw someone wrote a very violent DFS, but I didn’t dare to try it because the complexity is impossible to calculate
dp[k][i][j][0] represents the number of steps required to convert a substring with length k starting at position i of string a into a substring with length k starting at position j of string b without flipping
dp[k][i][j][1] represents the number of steps required to flip the substring of length k starting at position i of string a into a substring of length k starting at position j of string b
int n = a.size(); memset(dp, 0x3f, sizeof(dp)); for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) dp[0][j][k][0] = dp[0][j][k][1] = 0; for(int i = 1; i <= n; i++) for(int j = 0; j + i <= n; j++) for(int k = 0; k + i <= n; k++) { if(a[j] == b[k]) { dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j + 1][k + 1][0]); } if(a[j + i - 1] == b[k + i - 1]) { dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][0]); } if(a[j] == b[k + i - 1]) { dp[i][j][k][1] = min(dp[i][j][k][1], dp[i - 1][j + 1][k][1]); } if(a[j + i - 1] == b[k]) { dp[i][j][k][1] = min(dp[i][j][k][1], dp[i - 1][j][k + 1][1]); } dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j][k][1] + 1); dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j][k][0] + 1); } return dp[n][0][0][0] >= 1000 ? -1: dp[n][0][0][0];
1000
The formula for this question is very simple
n*(1/n 1 /(n - 1) 1/ (n - 2) ... 1/(n - k 1) )
Here comes the key question
n and k are huge
Then I discovered that this is a harmonic series summation
When the number is large, there is only an approximate formula
Then try it
(1/n 1/(n - 1 ) 1/ (n - 2) ... 1/(n - k 1) ) is approximately equal to log(n 1) R
R is Euler’s constant
Use this formula when you finish k. Otherwise, just for
But wa came out
Finally I found someone else did this. The original formula was log((n 1) / ( n - k 1))
Then there is a function called log1p, what does it do? log1p(x) returns log(x 1)
But the problem comes, when x is huge When using log1p, the accuracy of log1p is relatively high. When using log, x 1 will lose the accuracy
Then we just make do with it. If log1p is not enough, the denominator is reduced by 0.5, which is used to control the accuracy.
This makes my balls hurt.
After finishing it, I found that there were a lot of things in the room that didn’t need log1p, so I deleted them all
double expectedBuy(string n, string k) { long long x = gao(n); long long y = gao(k); double ans = 0; long long s = x - y + 1; long long mx = 10000000; while(s <= mx) { ans += 1.0 / s; if(s == x) return x * ans; s++; } ans += log1p((double)(x - s + 1) / (s - 0.5)); return ans * x; }