A.绝对值排序

C++ 代码

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

using namespace std;

const int N = 110;

int n;
int a[N];

bool cmp(int a, int b) {
    return abs(a) > abs(b);
}

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

            cin >> a[i];

        sort(a, a + n, cmp);

        for (int i = 0; i < n; i ++ ) {

            cout << a[i];

            if (i != n - 1)
                cout << ' ';
        }

        cout << endl;
    }

    return 0;
}

B.今年暑假不AC

C++ 代码

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

using namespace std;

const int N = 110;

int n;

struct node {
    int start;
    int end;
} a[N];

bool cmp(node x, node y) {
    if (x.end < y.end)
        return true;
    else if (x.end == y.end && x.start < y.start)
        return true;
    return false;
}

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

            cin >> a[i].start >> a[i].end;

        sort(a, a + n, cmp);

        int res = 1;

        for (int i = 1; i < n; i ++ )

            if (a[i].start >= a[i - 1].end)
                res ++ ;
            else
                a[i].end = min(a[i].end, a[i - 1].end);

        cout << res << endl;
    }

    return 0;
}

C.Encoding

C++ 代码

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

using namespace std;

int n;

int main() {
    cin >> n;

    while (n -- ) {
        string str;
        cin >> str;

        int sum = 0;

        for (int i = 0; i < str.size(); i ++ ) {

            while (str[i] == str[i + 1]) {
                sum ++ ;
                i ++ ;
            }

            if (sum) {
                cout << sum + 1 << str[i];
                sum = 0;
            } else
                cout << str[i];
        }

        cout << endl;
    }

    return 0;
}

D.最短路

C++ 代码

朴素版dijkstra

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

spfa

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

using namespace std;

const int N = 110;

int n, m;
int dist[N];
int h[N], w[N * N], e[N * N], ne[N * N], idx;
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ;
}

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];

                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main() {
    while (~scanf("%d%d", &n, &m), n, m) {
        memset(st, false, sizeof st);
        memset(h, -1, sizeof h);
        idx = 0;

        while (m -- ) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }

        cout << spfa() << endl;
    }

    return 0;
}

E.Maximum Product

求连续序列的最大乘积

C++ 代码

暴力(枚举每一个起点和终点)

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

using namespace std;

const int N = 20;

typedef long long LL;

int n, casei = 1;
int a[N];
LL res, re;

int main() {
    while (scanf("%d", &n) != EOF) {
        res = 0;

        for (int i = 0; i < n; i ++ )

            cin >> a[i];

        for (int i = 0; i < n; i ++ )

            for (int j = i; j < n; j ++ ) {

                re = 1;

                for (int k = i; k <= j; k ++ )

                    re *= a[k];
                res = max(res, re);
            }

        printf("Case #%d: The maximum product is %lld.\n\n", casei, res);
        casei ++ ;
    }

    return 0;
}

dp
维护两个dp数组，一个维护最大正值，一个维护最小负值

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

using namespace std;

const int N = 20;

typedef long long LL;

int n, casei = 1;
LL dp_max[N], dp_min[N];

int main() {
    while (scanf("%d", &n) != EOF) {
        dp_max[0] = dp_min[0] = 0LL;
        LL res = 0;
        int x;

        for (int i = 0; i < n; i ++ ) {

            cin >> x;

            if (x > 0) {
                dp_max[i] = dp_max[i - 1] * x;
                dp_min[i] = dp_min[i - 1] * x;

                if (!dp_max[i])
                    dp_max[i] = x;
            } else if (x < 0) {
                dp_max[i] = dp_min[i - 1] * x;
                dp_min[i] = dp_max[i - 1] * x;

                if (!dp_min[i])
                    dp_min[i] = x;
            } else {
                dp_max[i] = dp_min[i] = 0LL;
            }

            if (res < dp_max[i] && x)
                res = dp_max[i];
        }

        printf("Case #%d: The maximum product is %lld.\n\n", casei, res);
        casei ++ ;
    }

    return 0;
}

F.Digit Generator

超时做法

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

using namespace std;

bool flag;

int find(int x) {
    int ans = x;

    while (x) {
        ans += x % 10;
        x /= 10;
    }

    return ans;
}

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        flag = false;
        int x;
        cin >> x;

        for (int i = 1; i < x; i ++ )

            if (find(i) == x) {
                flag = true;
                cout << i << endl;
                break;
            }

        if (!flag)
            puts("0");
    }

    return 0;
}

正确做法

通过打表来减少枚举的次数

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

using namespace std;

const int N = 100010;

int a[N]; // a[i]存的是i的生成元
int t, n;

int main() {
    for (int i = 1; i < N; i ++ ) { // 一个数的生成元一定比它自身小

        int x = i, y = i;

        while (x) {
            y += x % 10;
            x /= 10;
        }

        if (a[y] == 0 || i < a[y])
            a[y] = i;
    }

    cin >> t;

    while (t -- ) {
        cin >> n;
        cout << a[n] << endl;
    }

    return 0;
}

G.Can you solve this equation?

浮点数二分

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.Olympiad

超时做法

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

using namespace std;

int cnt;
int a[15];

bool check(int x)
{
    memset(a, 0, sizeof a);
    int t;
    while (x)
    {
        t = x % 10;
        x /= 10;
        if (a[t] == 0)
            a[t] ++ ;
        else if(a[t] > 0)
            return false;
    }
    return true;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t -- )
    {
        cnt = 0;
        int a, b;
        scanf("%d%d", &a, &b);
        for (int i = a; i <= b; i ++ )
        {
            if (i >= 1 && i <= 10) cnt ++ ;
            else if (check(i))
                cnt ++ ;
        }


        printf("%d\n", cnt);
    }
    return 0;
}

正确做法(还是打表来减少枚举次数)

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

using namespace std;

const int N = 100010;

int a[15];
int array[N];

bool check(int x) {
    memset(a, 0, sizeof a);
    int t;

    while (x) {
        t = x % 10;
        x /= 10;

        if (a[t] == 0)
            a[t] ++ ;
        else if (a[t] > 0)
            return false;
    }

    return true;
}

void printList() {
    memset(array, 0, sizeof(array));

    for (int i = 0; i < N; i ++ )

        if (check(i))
            array[i] = array[i - 1] + 1;
        else
            array[i] = array[i - 1];
}

int main() {
    printList();
    int t;
    scanf("%d", &t);

    while (t -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        cout << array[b] - array[a - 1] << endl;
    }

    return 0;
}

I.A strange lift

bfs

#include <iostream>
#include <string.h>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

typedef long long LL;

bool vis[N];
int n, A, B;

struct node {
    int f, up, down, step;
    node(int a, int b, int c, int d) {
        f = a;
        up = b;
        down = c;
        step = d;
    }
    node() {};
} fl[N];


int BFS(int st, int ed) {
    memset(vis, false, sizeof(vis));
    queue<node> q;
    q.push(fl[st]);
    vis[st] = true;

    while (q.size()) {
        node temp = q.front();
        q.pop();

        if (temp.f == B)
            return temp.step;

        int up = temp.f + temp.up;
        int down = temp.f + temp.down;

        if (up >= 1 && up <= N  && !vis[up]) {
            vis[up] = true;

            if (up == ed)
                return temp.step + 1;
            else
                q.push(node(up, fl[up].up, fl[up].down, temp.step + 1));
        }

        if (down >= 1 && down <= N && !vis[down]) {
            vis[down] = true;

            if (down == ed)
                return temp.step + 1;
            else
                q.push(node(down, fl[down].up, fl[down].down, temp.step + 1));
        }
    }

    return -1;
}

int  main() {

    while (cin >> n && n) {
        cin >> A >> B;

        for (int i = 1; i <= n; i++) {

            cin >> fl[i].up;
            fl[i].f = i;
            fl[i].down = -1 * fl[i].up;
            fl[i].step = 0;
        }

        cout << BFS(A, B) << endl;
    }

    return 0;
}

dijkstra

spfa