526互联

《看了受制了》第二十三天，4道题，合计107道题

发布时间 2023-09-23 09:33:43作者: wxzcch

2023年9月22日

哎，再一次意识到弱小。。

Acwing1127 香甜的黄油

题目理解

求n遍最短路，求出每个点到某个点到所有牧场的最短路即可。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7, N = 810, M = 3000;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }

int h[N], e[M], ne[M], w[M], idx;
int p, n, k;
int id[N];
int d[N], q[M];
bool st[N];

int spfa(int u)
{
    memset(d, INF, sizeof d);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 1;

    d[u] = 0;
    q[0] = u;
    st[u] = true;


    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];


            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }

        }
    }

    int sum = 0;

    for(int i = 1; i <= p; i++)
    {
        if(d[id[i]] == INF) return INF;

        sum += d[id[i]];
    }
    return sum;
}

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int ans = INF;
int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d%d", &p, &n, &k);

    for(int i = 1; i <= p; i++)
        scanf("%d", &id[i]);

    for(int i = 1; i <= k; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        add(a, b, c);
        add(b, a, c);
    }

    for(int i = 1; i <= n; i++)
        ans = min(ans, spfa(i));

    printf("%d", ans);
    return 0;
}

Acwing 1126最小花费

题目理解

因为每次会扣除手续费那么比如x元，就是x * (1 - rate1) * (1 - rate2) * (1 - rate3) ... ，这样下去。那么我们就需要。

\[max\prod_{i=1}^n{(1 - rate_i)} \]

其实就是乘积的最大路，然后让100 / rate积即可。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7, N = 2010;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }

double g[N][N];
int n, m;
double d[N];
bool st[N];

double dijkstra(int a, int b)
{

    d[a] = 1;

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

        st[t] = true;

        for(int j = 1; j <= n; j++)
            d[j] = max(d[j], d[t] * g[t][j]);
    }

    return d[b];
}

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

    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        double z = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b], z);
    }
    int a, b;
    cin >> a >> b;
    double rate = dijkstra(a, b);

    printf("%.8lf",  100 / rate);
    return 0;
}

Acwing920 最优乘车

题目理解

这个题的建图方式比较特殊，要按照公交车的路线去建图。而且能到哪个？每个站台都要建图。
比如4 5 6 7，就要4 5\ 4 6\ 4 7\ 5 6\ 5 7\ 6 7\都进行建边，这样就可以求出1到n站的最小乘车次数，那么最小的转车次数就是最小乘车次数 - 1。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7, N = 510;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }

int g[N][N], d[N] ,stop[N];
bool st[N];
int n, m;

int dijkstra()
{
    memset(d, INF, sizeof d);
    d[1] = 0;

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

        st[t] = true;

        for(int j = 1; j <= n; j++)
            d[j] = min(d[j], d[t] + g[t][j]);
    }


    return d[n];    
}

int main()
{
    memset(g, INF, sizeof g);
    cin >> m >> n;

    string line;
    getline(cin, line);
    while (m -- )
    {
        getline(cin, line);
        stringstream ssin(line);
        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]] = 1;
    }

    int t = dijkstra();

    if(t == INF)
        cout << "NO";
    else
        cout << max(0, t - 1);

    return 0;
}

牛客周赛 A题

题目理解

这周赛就会一个题。。。
这个题就是奇数项个，第一个是谁谁就多。如何判断第l项是谁？那就直接把他们拆开，因为数据范围比较大，不能进行(l - 1) * k,python的话就好办了。
如果是偶数项个：

  • 那么就看所有的序列是不是都是偶数，如果是那么只能输出-1。都是偶数的话就是首项和公差都是偶数即可。
  • 都是奇数就是首项是奇数，公差是偶数
  • 不然就相等

代码实现

#include<iostream>
using namespace std;

typedef long long ll;

ll a, k, q, l, r;

int main()
{
    cin >> a >> k >> q;
    
    while(q -- )
    {
        cin >> l >> r;
        ll t = r - l + 1;
        
        if(t % 2)   // 奇数项
        {
            // 判断第一个是奇还是偶数
            if(a % 2 == 1 && k % 2 == 1 && (l - 1) % 2 == 1)
                cout << -1 << endl;
            else if(a % 2 == 0 && ((l - 1) % 2 == 0 || k % 2 == 0))
                cout << -1 << endl;
            else
                cout << 1 << endl;
        }else{
            if(a % 2 == 1 && k % 2 == 0)
                cout << 1 << endl;
            else if(a % 2 == 0 && k % 2 == 0)
                cout << -1 << endl;
            else
                cout << 0 << endl;
        }
    }
    return 0;
}