第三周 1.31-2.6

1.31

不会dp。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int mod = 5201314;
 6 int dp[555][555], cpy[555][555];
 7 char G[555][555];
 8 
 9 int main(void)
10 {
11     int T;
12     scanf("%d", &T);
13     while(T--)
14     {
15         int N;
16         scanf("%d", &N);
17         for(int i = 0; i < N; i++) scanf("%s", G[i]);
18         memset(dp, 0, sizeof(dp));
19         dp[0][N-1] = G[0][0] == G[N-1][N-1];
20         for(int k = 1; k < N; k++)
21         {
22             memcpy(cpy, dp, sizeof(cpy));
23             memset(dp, 0, sizeof(dp));
24             for(int x1 = 0; x1 <= k; x1++)
25             {
26                 for(int x2 = N - 1; x2 >= N - k - 1; x2--)
27                 {
28                     int y1 = k - x1, y2 = 2 * N - 2 - k - x2;
29                     if(G[x1][y1] == G[x2][y2])
30                     {
31                         if(x1 != k && x2 != N - 1 - k) dp[x1][x2] += cpy[x1][x2];
32                         if(x1 != k && x2 != N - 1) dp[x1][x2] += cpy[x1][x2+1];
33                         if(x1 != 0 && x2 != N - 1 - k) dp[x1][x2] += cpy[x1-1][x2];
34                         if(x1 != 0 && x2 != N - 1) dp[x1][x2] += cpy[x1-1][x2+1];
35                         dp[x1][x2] %= mod;
36                     }
37                 }
38             }
39         }
40         int ans = 0;
41         for(int i = 0; i < N; i++) ans = ( ans + dp[i][i] ) % mod;
42         printf("%d
", ans);
43     }
44     return 0;
45 }

Aguin

2.1

什么都没干。

2.2

CF 621 D Rat Kwesh and Cheese

精度之迷。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long double x, y, z;
char * s[] = {
    "",
    "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"
};

long double f(int op)
{
    if(x < 1.001 && y < 1.001 && z < 1.001)
    {
        if(op == 1) return pow(y, z) * log(x);
        if(op == 2) return pow(z, y) * log(x);
        if(op == 3) return z * y * log(x);

        if(op == 5) return pow(x, z) * log(y);
        if(op == 6) return pow(z, x) * log(y);
        if(op == 7) return x * z * log(y);

        if(op == 9) return pow(x, y) * log(z);
        if(op == 10) return pow(y, x) * log(z);
        if(op == 11) return x * y * log(z);
    }

    if(op == 1) return log(log(x)) + z * log(y);
    if(op == 2) return log(log(x)) + y * log(z);
    if(op == 3) return log(z * y * log(x));

    if(op == 5) return log(log(y)) + z * log(x);
    if(op == 6) return log(log(y)) + x * log(z);
    if(op == 7) return log(z * x * log(y));

    if(op == 9) return log(log(z)) + y * log(x);
    if(op == 10) return log(log(z)) + x * log(y);
    if(op == 11) return log(x * y * log(z));

}

int main(void)
{
    cin >> x >> y >> z;
    long double M = -1e300;
    int pos;
    if(x < 1.001 && y < 1.001 && z < 1.001 || x > 0.999)
        for(int i = 1; i < 4; i++)
            if(f(i) > M) M = f(i), pos = i;
    if(x < 1.001 && y < 1.001 && z < 1.001 || y > 0.999)
        for(int i = 5; i < 8; i++)
            if(f(i) > M) M = f(i), pos = i;
    if(x < 1.001 && y < 1.001 && z < 1.001 || z > 0.999)
        for(int i = 9; i < 12; i++)
            if(f(i) > M) M = f(i), pos = i;
    printf("%s
", s[pos]);
    return 0;
}

Aguin

2.3

CF 618 D Hamiltonian Spanning Tree

不是很懂你们贪心。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 const int maxn = 2e5 + 10;
 6 int cnt, h[maxn], deg[maxn];
 7 int num;
 8 
 9 struct edge
10 {
11     int to, pre;
12 } e[maxn<<1];
13 
14 void add(int from, int to)
15 {
16     cnt++;
17     e[cnt].pre = h[from];
18     e[cnt].to = to;
19     h[from] = cnt;
20 }
21 
22 int dfs(int p, int f)
23 {
24     int tmp = 0;
25     for(int i = h[p]; i; i = e[i].pre)
26     {
27         int to = e[i].to;
28         if(to == f) continue;
29         tmp += dfs(to, p);
30     }
31     if(!tmp) return 1;
32     else if(tmp == 1){ num++; return 1;}
33     else{ num += 2; return 0; }
34 }
35 
36 int main(void)
37 {
38     int n, leaf = 0;
39     LL x, y;
40     scanf("%d %I64d %I64d", &n, &x, &y);
41     for(int i = 1; i < n; i++)
42     {
43         int u, v;
44         scanf("%d %d", &u, &v);
45         add(u, v), add(v, u);
46         deg[u]++, deg[v]++;
47     }
48     for(int i = 1; i <= n; i++) if(deg[i] == 1) leaf++;
49     if(x >= y) printf("%I64d
", y * (n - 2) + (leaf >= n - 1 ? x : y));
50     else dfs(1, 0), printf("%I64d
", x * num + y * (n - 1 - num));
51     return 0;
52 }

Aguin

2.4-2.5

什么都没干。

2.6

HDU 5623 KK's Number

这个出题人有点萌。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 5e4 + 10;
 7 bool cmp(LL x, LL y){return x > y;}
 8 LL a[maxn], dp[maxn];
 9 
10 int main(void)
11 {
12     int T;
13     scanf("%d", &T);
14     while(T--)
15     {
16         int N;
17         scanf("%d", &N);
18         for(int i = 0; i < N; i++) scanf("%I64d", a + i);
19         sort(a, a + N, cmp);
20         LL M = a[N] = 0LL;
21         for(int i = N - 1; i >= 0; i--)
22         {
23             dp[i] = a[i] - M;
24             M = max(M, dp[i]);
25         }
26         printf("%I64d
", M);
27     }
28     return 0;
29 }

Aguin