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;    }