Codeforces Round #341 (Div. 2) ABCDE

http://www.cnblogs.com/wenruo/p/5176375.html

A. Wet Shark and Odd and Even

题意：输入n个数，选择其中任意个数，使和最大且为奇数。

题解：算出所有数的和，如果奇数的个数为奇数个，则减去最小的奇数，否则不用处理。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define PI acos(-1.0)
 4 #define EXP exp(1.0)
 5 #define ESP 1E-6
 6 #define clr(x,c) memset(x,c,sizeof(x))
 7 typedef long long ll;
 8 
 9 using namespace std;
10 int main()
11 {
12     int n;
13     int cnt = 0; int minn = 1000000000;
14     int val;
15     ll ans = 0;
16     scanf("%d", &n);
17     for (int i = 0; i < n; ++i) {
18         scanf("%d", &val);ans += val;
19         if (val % 2 == 1) {
20             cnt++;
21             minn = min(minn, val);
22         }
23     }
24     if (cnt % 2 == 1) ans -= minn;
25     cout << ans;
26     return 0;
27 }

View Code

B. Wet Shark and Bishops

题意：一个1000*1000的棋盘，上面摆放n个棋子，同一对角线上的两个棋子可以相互攻击，求一共有多少对棋子可以相互攻击。

题解：有主对角线和副对角线，对于每一个对角线，设对角线上有棋子X个，则该对角线有C(X,2)对棋子可以相互攻击。

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define EXP exp(1.0)
#define ESP 1E-6
#define clr(x,c) memset(x,c,sizeof(x))
typedef long long ll;

using namespace std;

int xSubY[2005];
int xAddY[2005];
ll c[1005][1005];
//c[i][j] := C(i, j)
void init()
{
    c[0][0] = 1;
    for(int i = 1; i <= 1000; i++)
    {
        c[i][0] = 1;
        c[i][i] = 1;
        for(int j = 1; j < i; j++)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]);
    }
}

int main()
{
    init();
    int n;
    int x, y;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x, &y);
        xSubY[x-y+1000]++;
        xAddY[x+y]++;
    }
    ll ans = 0;
    for (int i = 0; i <= 2000; ++i) {
        ans += c[ xSubY[i] ][2];
        ans += c[ xAddY[i] ][2];
    }
    cout << ans;
    return 0;
}

View Code

C. Wet Shark and Flowers

题意：n个鲨鱼围成一圈1~n，每个鲨鱼有一个数，鲨鱼i的数字在范围l[i]~r[i]，如果相邻数字的乘积为P或P的倍数（p为素数），则两个鲨鱼各获得1000元，求一共能获得钱的期望。

题解：分别考虑相邻的每两个就可以，对于相邻两个数，只有至少一个为p的倍数，才有可能乘积是p的倍数。对于每个鲨鱼一共有r-l+1个数字，有r/p-(l-1)/p的p的倍数。具体看代码。

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define EXP exp(1.0)
#define ESP 1E-6
#define clr(x,c) memset(x,c,sizeof(x))
typedef long long ll;

using namespace std;
const int N = 100005;

int l[N];
int r[N];
double ans[N];

int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &l[i], &r[i]);
    }
    l[n] = l[0]; r[n] = r[0];
    for (int i = 0; i < n; ++i) {
        double a = r[i] - l[i] + 1;
        double b = r[i + 1] - l[i + 1] + 1;
        double pa = r[i] / p - (l[i] - 1) / p;
        double pb = r[i + 1] / p - (l[i + 1] - 1) / p;
        double tmp = (pa * b + pb * a - pa * pb) / (a * b);
        ans[i] += tmp;
        ans[i + 1] += tmp;
    }
    double res = 0;
    for (int i = 0; i <= n; ++i) res += ans[i];
    printf("%f", res * 1000);

    return 0;
}

View Code

D. Rat Kwesh and Cheese

题意：很简单，求a₁ = x^{y^z};a₂ = x^{z^y};a₃ = (x^y)^z;a₄ = (x^z)^y;a₅ = y^{x^z};a₆ = y^{z^x};a₇ = (y^x)^z;a₈ = (y^z)^x;a₉ = z^{x^y};a₁₀ = z^{y^x};a₁₁ = (z^x)^y;a₁₂ = (z^y)^x.的最大值。(0.1 ≤ x, y, z ≤ 200.0)

题解：很容易想到求对数，但是，y^z也会很大，所以想当然的求了两次对数，也就是log(log(x^y^z))变成z*log(y)+log(log(x));但是log(x)会出现负数……（后来发现好多人都是这么做的，笑）。正解是取一次对数，然后使用long double，精度足够。

#include <bits/stdc++.h>
typedef long double lld;
using namespace std;
const lld ESP = 1E-8;

lld cal(lld x, lld y, lld z)
{
    //return z * log(y) + log(log(x));
    return log(x) * pow(y, z);
}

lld ca(lld x, lld y, lld z)
{
    //return log(y * z * log(x));
    return y * z * log(x);
}

int main()
{
    const char* result[12] = {"x^y^z", "x^z^y", "(x^y)^z", "(x^z)^y", "y^x^z",
                        "y^z^x", "(y^x)^z", "(y^z)^x", "z^x^y", "z^y^x", "(z^x)^y", "(z^y)^x"};

    lld a[20];
    lld x, y, z;
    cin >> x >> y >> z;
    a[0] = cal(x, y, z);
    a[1] = cal(x, z, y);
    a[2] = ca(x, y, z);
    a[3] = ca(x, z, y);
    a[4] = cal(y, x, z);
    a[5] = cal(y, z, x);
    a[6] = ca(y, x, z);
    a[7] = ca(y, z, x);
    a[8] = cal(z, x, y);
    a[9] = cal(z, y, x);
    a[10] = ca(z, x, y);
    a[11] = ca(z, y, x);
    lld maxn = a[0];
    int res = 0;
    for (int i = 1; i < 12; ++i) {
        if (maxn < a[i] - ESP) {
            maxn = a[i];
            res = i;
        }
    }
    printf("%s", result[res]);
    return 0;
}

View Code

E. Wet Shark and Blocks

题意：n个堆，每个堆有b个数字，每一个堆取一个数字，第i个堆取一个数字做第i位的数字，构成一个n位数，求构成的数字被x除余k有多少种方案。

题解：看到这题就想到了前几天做的题http://www.cnblogs.com/wenruo/p/5153790.html 不过这个简单些，然并卵，比赛时并没有写出来……dp+矩阵快速幂

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int digit[10];
const ll MOD = 1000000007;

typedef vector<ll> vec;
typedef vector<vec> mat;

mat mul(mat &A, mat &B)
{
    mat C(A.size(), vec(B[0].size()));
    for (unsigned int i = 0; i < A.size(); ++i) {
        for (unsigned int k = 0; k < B.size(); ++k) {
            for (unsigned int j = 0; j < B[0].size(); ++j) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

mat pow(mat A, int n)
{
    mat B(A.size(), vec(A.size()));
    for (unsigned int i = 0; i < A.size(); ++i)
        B[i][i] = 1;
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

/*
dp[i][k] i位数 余数为k
dp[i+1][(j+k*10)%x] = dp[i][k]*digit[j], 1<=j<=9
*/
ll cal(int n, int x, int k)
{
    mat f(x, vec(x));
    for (int i = 0; i < x; ++i) {           // 上一位余数
        for (int j = 1; j <= 9; ++j) {      // 首位数字
            int num = (i * 10 + j) % x;     // 当前余数
            f[num][i] += digit[j];
        }
    }

    mat v(x, vec(1));
    for (int i = 1; i <= 9; ++i)
        v[i % x][0] += digit[i];    // dp[1][i%x][i]

    f = pow(f, n - 1);
    v = mul(f, v);
    return v[k][0];
}

int main()
{
    int n, b, k, x;
    scanf("%d%d%d%d", &n, &b, &k, &x);
    int val;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &val);
        digit[val]++;
    }
    cout << cal(b, x, k);

    return 0;
}

View Code

总体而言这次的比赛比较简单^_^