http://www.cnblogs.com/wenruo/p/5176375.html
A. Wet Shark and Odd and Even
题意：输入n个数，选择其中任意个数，使和最大且为奇数。
题解：算出所有数的和，如果奇数的个数为奇数个，则减去最小的奇数，否则不用处理。
#include <bits/stdc++.h>
using namespace std;
#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 main()
{
int n;
int cnt = ; int minn = ;
int val;
ll ans = ;
scanf("%d", &n);
for (int i = ; i < n; ++i) {
scanf("%d", &val);ans += val;
if (val % == ) {
cnt++;
minn = min(minn, val);
}
}
if (cnt % == ) ans -= minn;
cout << ans;
return ;
}
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[];
int xAddY[];
ll c[][];
//c[i][j] := C(i, j)
void init()
{
c[][] = ;
for(int i = ; i <= ; i++)
{
c[i][] = ;
c[i][i] = ;
for(int j = ; j < i; j++)
c[i][j] = (c[i-][j-] + c[i-][j]);
}
} int main()
{
init();
int n;
int x, y;
scanf("%d", &n);
for (int i = ; i < n; ++i) {
scanf("%d%d", &x, &y);
xSubY[x-y+]++;
xAddY[x+y]++;
}
ll ans = ;
for (int i = ; i <= ; ++i) {
ans += c[ xSubY[i] ][];
ans += c[ xAddY[i] ][];
}
cout << ans;
return ;
}
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 = ; int l[N];
int r[N];
double ans[N]; int main()
{
int n, p;
scanf("%d%d", &n, &p);
for (int i = ; i < n; ++i) {
scanf("%d%d", &l[i], &r[i]);
}
l[n] = l[]; r[n] = r[];
for (int i = ; i < n; ++i) {
double a = r[i] - l[i] + ;
double b = r[i + ] - l[i + ] + ;
double pa = r[i] / p - (l[i] - ) / p;
double pb = r[i + ] / p - (l[i + ] - ) / p;
double tmp = (pa * b + pb * a - pa * pb) / (a * b);
ans[i] += tmp;
ans[i + ] += tmp;
}
double res = ;
for (int i = ; i <= n; ++i) res += ans[i];
printf("%f", res * ); return ;
}
D. Rat Kwesh and Cheese
题意：很简单，求a1 = xyz;a2 = xzy;a3 = (xy)z;a4 = (xz)y;a5 = yxz;a6 = yzx;a7 = (yx)z;a8 = (yz)x;a9 = zxy;a10 = zyx;a11 = (zx)y;a12 = (zy)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-; 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[] = {"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[];
lld x, y, z;
cin >> x >> y >> z;
a[] = cal(x, y, z);
a[] = cal(x, z, y);
a[] = ca(x, y, z);
a[] = ca(x, z, y);
a[] = cal(y, x, z);
a[] = cal(y, z, x);
a[] = ca(y, x, z);
a[] = ca(y, z, x);
a[] = cal(z, x, y);
a[] = cal(z, y, x);
a[] = ca(z, x, y);
a[] = ca(z, y, x);
lld maxn = a[];
int res = ;
for (int i = ; i < ; ++i) {
if (maxn < a[i] - ESP) {
maxn = a[i];
res = i;
}
}
printf("%s", result[res]);
return ;
}
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[];
const ll MOD = ; typedef vector<ll> vec;
typedef vector<vec> mat; mat mul(mat &A, mat &B)
{
mat C(A.size(), vec(B[].size()));
for (unsigned int i = ; i < A.size(); ++i) {
for (unsigned int k = ; k < B.size(); ++k) {
for (unsigned int j = ; j < B[].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 = ; i < A.size(); ++i)
B[i][i] = ;
while (n > ) {
if (n & ) B = mul(B, A);
A = mul(A, A);
n >>= ;
}
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 = ; i < x; ++i) { // 上一位余数
for (int j = ; j <= ; ++j) { // 首位数字
int num = (i * + j) % x; // 当前余数
f[num][i] += digit[j];
}
} mat v(x, vec());
for (int i = ; i <= ; ++i)
v[i % x][] += digit[i]; // dp[1][i%x][i] f = pow(f, n - );
v = mul(f, v);
return v[k][];
} int main()
{
int n, b, k, x;
scanf("%d%d%d%d", &n, &b, &k, &x);
int val;
for (int i = ; i < n; ++i) {
scanf("%d", &val);
digit[val]++;
}
cout << cal(b, x, k); return ;
}
总体而言这次的比赛比较简单^_^