A.签到

C++ 代码

#include <iostream>

using namespace std;

int a, b;

int main()
{
    while (cin >> a >> b)
    {
        cout << a + b << endl;
    }
    return 0;
} 

B.两点之间线段最短

C++ 代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    double x1, y1, x2, y2, s;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        s = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
        printf("%.2lf\n", s);
    }
    return 0;
} 

C.aeiou

C++ 代码

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int main()
{
    int T, cnt = 0;
    int num1, num2, num3, num4, num5;
    cin >> T;
    while (T -- )
    {
        if (cnt) puts("");
        if (cnt == 0) getchar();
        cnt++;
        num1 = 0, num2 = 0, num3 = 0, num4 = 0, num5 = 0;
        string str;
        getline(cin, str);
        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == 'a') num1++;
            if (str[i] == 'e') num2++;
            if (str[i] == 'i') num3++;
            if (str[i] == 'o') num4++;
            if (str[i] == 'u') num5++;
        }
        printf("a:%d\n", num1);
        printf("e:%d\n", num2);
        printf("i:%d\n", num3);
        printf("o:%d\n", num4);
        printf("u:%d\n", num5);
    }
    return 0;
}

D.学长坐公交

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int n, sum = 0, res = 0;
    cin >> n;
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        sum = sum - a + b;
        res = max(res, sum);
    }

    cout << res << endl;

    return 0;
}

E.这题是冒泡吗？

归并排序求逆序对数目

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] > q[j]) 
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
        else tmp[k ++ ] = q[i ++ ];
    }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    return res;
}

int main()
{
    while (cin >> n && n)
    {
        for (int i = 0; i < n; i ++ ) cin >> q[i];

        cout << merge_sort(0, n - 1) << endl;
    }
    return 0;
} 

F.最大元素和

前缀和二维压缩

最优算法 $O(n^3)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int s[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            int x;
            cin >> x;
            s[i][j] = s[i - 1][j] + x;
        }

    int res = - 200;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
        {
            int f = 0;
            for (int k = 1; k <= n; k ++ )
            {
                int w = s[j][k] - s[i - 1][k];
                f = max(f, 0) + w;
                res = max(res, f);
            }
        }

    cout << res << endl;

    return 0;
}

暴力解法 $O(n^4)$

#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N][N], s[N][N];

int main()
{
    int res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int x = 1; x <= i; x ++ )
                for (int y = 1; y <= j; y++)
                {
                    int sm = s[i][j] - s[x - 1][j] - s[i][y - 1] + s[x - 1][y - 1];
                    res = max(res, sm);
                }
    cout << res << endl;
    return 0;
}

G.枣园开空调

浮点数二分

C++ 代码

#include <iostream>
#include <cstdio>

#define F(x) 8 * x * x * x * x + 7 * x * x * x + 2 * x * x + 3 * x + 6

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        double Y, mid;
        cin >> Y;
        double l = 0, r = 100;
        if (Y < F(0) || Y > F(100)) 
        {
            puts("No solution!");
            continue;
        }

        while (r - l > 1e-8)
        {
            mid = (l + r) / 2;
            if (F(mid) > Y) r = mid;
            else l = mid;
        }
        printf("%.4lf\n", l);
    }
    return 0;
} 

H.朋友圈

并查集+map

C++ 代码

#include <iostream>
#include <string>
#include <map>
#include <cstdio>

using namespace std;

const int N = 100010;

map<string, int> mp;
int p[N], res[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
    {
        p[fx] = fy;
        res[fy] += res[fx];
    }
    cout << res[fy] << endl;
}

int main()
{
    int T;
    while (cin >> T)
    {
        while (T -- )
        {
            for (int i = 1; i <= N; i ++ )
            {
                p[i] = i;
                res[i] = 1;
            }

            int n;
            cin >> n;
            mp.clear();
            int cnt = 0;
            while (n -- )
            {
                string a, b;
                cin >> a >> b;
                if (!mp[a]) mp[a] = ++ cnt;
                if (!mp[b]) mp[b] = ++ cnt;

                merge(mp[a], mp[b]);
            }
        }
    }
    return 0;
}

I.皇后的领地

DFS(两种搜索顺序)

打表

#include <iostream>

using namespace std;

int a[] = {0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724};

int main()
{
    int n;
    while (cin >> n && n)
    {
        cout << a[n] << endl;
    }
    return 0;
}

第一种搜索顺序

#include <iostream>

using namespace std;

const int N = 20;

int n, ans;
bool row[N], col[N], dg[N], udg[N]; // 行、列、从左下方到右上方的对角线、从左上方到右下方的对角线 

void dfs(int x, int y, int s) // (x, y) 是当前搜索的坐标, s 表示当前已经放置的皇后的数目 
{
    if (s > n) return;
    if (y == n) x ++ , y = 0;
    if (x == n)
    {
        if (s == n) ans ++ ;
        return;
    }

    dfs(x, y + 1, s); // 当前位置不放皇后

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) 
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1); // 当前位置放皇后
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    while (cin >> n && n)
    {
        ans = 0;
        dfs(0, 0, 0);
        cout << ans << endl;
    }
    return 0;
}

第二种搜索顺序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n, ans;
int col[N], dg[N], udg[N];

void dfs(int x)
{
    if (x == n) 
    {
        ans ++ ;
        return;
    }

    for (int y = 0; y < n; y ++ )
        if (!col[y] && !dg[x + y] && !udg[x - y + n])
        {
            col[y] = dg[x + y] = udg[x - y + n] = true;
            dfs(x + 1);
            col[y] = dg[x + y] = udg[x - y + n] = false;
        }
}

int main()
{
    while (~scanf("%d", &n) && n)
    {
        ans = 0;
        dfs(0);
        cout << ans << endl;
    }
    return 0;
}

J.最长公共子序列

DP

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010;

char a[N], b[N];
int f[N][N];

int main()
{
    while (~scanf("%s%s", a, b))
    {
        int n = strlen(a), m = strlen(b);
        memset(f, 0, sizeof f);

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                if (a[i - 1] == b[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = max(f[i - 1][j], f[i][j - 1]);

        cout << f[n][m] << endl;
    }
    return 0;
} 

K.找对象

DFS+剪枝
令门开启的时间为T，某点到终点的奇偶性step=abs（xi-di）+abs(yj-dj);
奇偶剪枝：由题可以知道我们到达出口一定要走T步（门只在时间T时开启）,我们在深搜的过程中判断从当前点到（xi,yi）到终点(di,dj)的距离S减最短距离step的奇偶性。由上的结论可知，只有当奇偶性为偶的时候才可以到终点

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 10;

const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

char mp[N][N];
int vis[N][N];
int n, m, t;
int flag, ax, ay, bx, by;

void dfs(int x, int y, int step)
{
    for (int i = 0; i < 4; i ++ )
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx == bx && ny == by && t == step + 1)
        {
            flag = 1;
            return;
        }
        if (step >= t) return;
        else if (nx >= 0 && nx < n && ny >= 0 && ny < m && vis[nx][ny] == 0 && mp[nx][ny] == '.')
        {
            vis[nx][ny] = 1;
            dfs(nx, ny, step + 1);
            if (flag) return;
            vis[nx][ny] = 0;
        }
    }
}

int main()
{
    while (cin >> n >> m >> t &&  (n + m + t))
    {
        flag = 0;
        memset(mp, 0, sizeof mp);
        memset(vis, 0, sizeof vis);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                cin >> mp[i][j];
                if (mp[i][j] == 'S') ax = i, ay = j;
                if (mp[i][j] == 'D') bx = i, by = j;
            }

        int w = abs(ax - bx) + abs(ay - by);
        if ((t - w) % 2 == 0)
        {
            vis[ax][ay] = 1;
            dfs(ax, ay, 0);
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}