3577.选择数字

氵题使我快乐！

题目描述

芜湖~上古周赛！

挑战全网最短C语言代码(doge)

C 代码

#include <stdio.h>
main(){int n, m, x, y, a, b; for (scanf("%d", &n); n -- ; ) scanf("%d", &x), a = x > a ? x : a; for (scanf("%d", &m); m -- ; ) scanf("%d", &y), b = y > b ? y : b; printf("%d %d", a, b);}

4805.加减乘

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

using namespace std;

typedef long long LL;

const int N = 1e7 + 10;

LL n, x, y;
LL f[N];

int main()
{
    scanf("%lld%lld%lld", &n, &x, &y);

    memset (f, 0x3f, sizeof f), f[0] = 0;

    for (int i = 1; i < N; i ++ )
    {
        f[i] = min(f[i], f[i - 1] + x);
        if (i & 1) f[i] = min(f[i], f[(i + 1) / 2] + x + y);
        else f[i] = min(f[i], f[i / 2] + y);
    }

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

4804.构造矩阵

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

using namespace std;

const int N = 110;

int A[N][N];
bool st[N][N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> A[i][j];
            if (!A[i][j])
            {
                for (int a = 1; a <= n; a ++ ) st[a][j] = true;
                for (int b = 1; b <= m; b ++ ) st[i][b] = true;
            }
        }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (A[i][j])
            {
                int f = 0;
                for (int a = 1; a <= n; a ++ ) f += !st[a][j];
                for (int b = 1; b <= m; b ++ ) f += !st[i][b];

                if (!f)
                {
                    puts("NO");
                    return 0;
                }
            }
        }

    puts("YES");
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
            cout << !st[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

1135.新年好

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

using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, K = 10, INF = 0x3f3f3f3f;

int n, m;
int id[K], d[K][N];
int h[N], e[M], w[M], ne[M], idx;

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

void Dijkstra(int s, int *dist)
{
    bool st[N] = {false};

    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

    while (heap.size())
    {
        int t = heap.top().second;
        heap.pop();

        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset (h, -1, sizeof h);
    memset (d, 0x3f, sizeof d);

    scanf("%d%d", &n, &m);
    id[1] = 1;
    for (int i = 2; i <= 6; i ++ ) scanf("%d", id + i);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 1; i <= 6; i ++ ) Dijkstra(id[i], d[i]);
    int a[K];
    for (int i = 1; i <= 6; i ++ ) a[i] = i;

    int res = INF;
    do
    {
        int ans = d[a[1]][id[a[2]]];
        for (int i = 2; i <= 5; i ++ ) ans += d[a[i]][id[a[i + 1]]];
        res = min(res, ans);
    }while (next_permutation(a + 2, a + 7));

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

903.昂贵的聘礼

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

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N][N], level[N];
int dist[N];
bool st[N];

int Dijkstra(int down, int up)
{
    memset (dist, 0x3f, sizeof dist);
    memset (st, false, sizeof st);

    dist[0] = 0;
    for (int i = 1; i <= n + 1; i ++ )
    {
        int t = -1;
        for (int j = 0; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j ++ )
            if (level[j] >= down && level[j] <= up)
            dist[j] = min(dist[j], dist[t] + w[t][j]);
    }

    return dist[1];
}

int main()
{
    cin >> m >> n;

    memset (w, 0x3f, sizeof w);
    for (int i = 1; i <= n; i ++ ) w[i][i] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int price, cnt;
        cin >> price >> level[i] >> cnt;
        w[0][i] = min(price, w[0][i]);
        while (cnt -- )
        {
            int id, cost;
            cin >> id >> cost;
            w[id][i] = min(w[id][i], cost);
        }
    }


    int res = INF;
    for (int i = level[1] - m; i <= level[1]; i ++ )
        res = min(res, Dijkstra(i, i + m));

    cout << res << endl;

    return 0;
}

343.排序

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

using namespace std;

const int N = 30, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;

int n, m;
int d[N][N];
PII res[N];

void Floyd(int k)
{
    for (int i = 1; i <= n; i ++ )  
        for (int j = 1; j <= n; j ++ )
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

bool check()
{
    for (int i = 1; i <= n; i ++ )
    {
        int cnt = 0;
        for (int j = 1; j <= n; j ++ )
            if (d[i][j] != INF) cnt ++ ;

        res[i] = {cnt, i};

        for (int j = 1; j <= n; j ++ )
            if (i != j && d[j][i] != INF) cnt ++ ;

        if (cnt != n) return false;
    }

    sort (res + 1, res + n + 1);
    return true;
}

int main()
{
    while (cin >> n >> m, n, m)
    {
        bool f = false;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = i == j ? 0 : INF;

        for (int i = 1; i <= m; i ++ )
        {
            char a, k, b;
            cin >> a >> k >> b;
            int x = a - 'A' + 1, y = b - 'A' + 1;
            if (!f && d[x][y] != INF) 
            {
                printf("Inconsistency found after %d relations.\n", i);
                f = true;
            }

            d[y][x] = 1, Floyd(x), Floyd(y);
            if (!f && check())
            {
                printf("Sorted sequence determined after %d relations: ", i);
                for (int j = 1; j <= n; j ++ ) 
                    cout << char(res[j].second + 'A' - 1);
                puts(".");
                f = true;
            }
        }

        if (!f) puts("Sorted sequence cannot be determined.");
    }

    return 0;
}

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 30, INF = 0x3f3f3f3f;

int n, m;
int dist[N][N];
PII res[N];

void Floyd (int k)
{
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= n; j ++ )
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

bool check () {
    for (int i = 1; i <= n; i ++ )
    {
        int cnt = 0;
        for (int j = 1; j <= n; j ++ )
            if (dist[i][j] != INF) cnt ++ ;

        res[i] = {cnt, i};

        for (int j = 1; j <= n; j ++ ) 
            if (i != j && dist[j][i] != INF) cnt ++ ;

        if (cnt != n) return false;
    }

    sort (res + 1, res + n + 1);
    return true;
}

int main()
{
    while (cin >> n >> m, n)
    {
        bool f = false;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i != j) dist[i][j] = INF;

        for (int i = 1; i <= m; i ++ )
        {
            char a, t, b;
            cin >> a >> t >> b;

            int x = a - 'A' + 1, y = b - 'A' + 1; 

            if (!f && dist[x][y] != 1e9)  
            {
                printf("Inconsistency found after %d relations.\n", i);
                f = true;
            }

            dist[y][x] = 1; 
            Floyd(x), Floyd(y); 

            if (!f && check())
            { 
                printf("Sorted sequence determined after %d relations: ", i);
                for(int j = 1; j <= n; j ++ ) cout << char(res[j].y +'A' - 1);
                puts(".");
                f = true;
            }
        }

        if (!f) puts ("Sorted sequence cannot be determined.");
    }

}

920.最优乘车

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int m, n;
bool g[N][N];
int dist[N];
int stop[N], q[N];

void bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset (dist, 0x3f, sizeof dist), dist[1] = 0;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = 1; i <= n; i ++ )
            if (g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q[ ++ tt] = i;
            }
    }
}

int main()
{
    cin >> m >> n;

    string str;
    getline(cin, str);
    while (m -- )
    {
        getline(cin, str);
        stringstream ssin(str);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt ++ ] = p;
        for (int j = 0; j < cnt; j ++ )
            for (int k = j + 1; k < cnt; k ++ )
                g[stop[j]][stop[k]] = true;
    }

    bfs();

    if (dist[n] == INF) puts("NO");
    else cout << max(dist[n] - 1, 0) << endl;

    return 0;
}