SRM 400 Div1_html/css_WEB-ITnose

この一連の質問は金玉が痛くなります

250

簡単な質問。 ある数値をある素数の何乗として表現できるかを問う

精度が落ちる方法を使いました

実は二乗判定さえ済んでいれば直接素数を列挙しても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

この質問は、A 文字列と B 文字列

が与えられた場合、両方とも 0 と 1 のみを含み、一連の逆演算を使用して A を B に変えることを意味します。

reverse(i,j) i, j の区間を反転することを意味します

すると、この一連の演算には限界があります

つまり、演算が完了した後、次の演算はサブ区間で実行されなければなりませんこれはすべての操作に当てはまります

これは間隔 DP に間違いなく便利です

誰かが非常に暴力的な DFS を書いているのを見ましたが、複雑だと感じたので試しませんでした。計算不可能

dp[k][i][j][0] は文字列を表します 位置 i から始まる長さ k の部分文字列が、反転せずに位置 j から始まる長さ k の部分文字列になるまでに必要なステップ数文字列 b

dp[k][i][j][1] は、文字列 a の位置 i での開始長さを表します。文字列の位置 j から開始して、k の部分文字列を長さ k の部分文字列に反転するのに必要なステップ数です。 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

この質問の式はとても簡単です

n*(1/n+ 1/(n - 1) + 1/ (n - 2) +...+ 1/(n - k + 1) )

重要な質問が来ます

n , k は巨大です

そして、これが級数の和であることが分かりました

数値が大きいときは、近似値しかありません数式

それでは試してみてください

(1/n+1/(n - 1) + 1/ (n - 2) +...+ 1/(n - k + 1) ) は log(n とほぼ等しい) + 1) + R

R はオイラー定数

k が大きい場合にこの式を使用します。それ以外の場合は、

のためだけです

しかし、私は出てきました

最終的に、他の人がこれをやったことがわかりました、元の式はlog((n + 1) / (n - k + 1))でした

それから、次があります。 log1p と呼ばれる関数です。何をするのでしょうか? log1p(x) が返すのは log(x + 1) です

しかし、ここで問題が発生します。log、x を使用すると、log1p の精度が高くなります。 +1 では精度が失われます

そこで、精度を制御するために使用される分母を 0.5 減らすだけでは不十分です。

これではタマが痛くなります。

終わったら、部屋にlog1p要らない人がたくさんいたので全部削除しました

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