P9954 [USACO20OPEN] Cowntact Tracing B 题解

· · 题解

[USACO20OPEN] Cowntact Tracing B 题解

思路

既然 N \leq 100，T \leq 250，那就有一种最暴力的解法：

  1. 将时间戳以 t 为关键字从小到大排序。
  2. 枚举零号病人 z（[1, N]），对于每个零号病人，枚举 k（[1, \color{#900021}{T + 1}\color{black}]）。
  3. 对于每对 z, k 顺序遍历时间戳数组，暴力模拟感染。
  4. 如果感染结果与输入的字符串一致，那么可能为零号病人的奶牛数量+1，并更新 k 的上下限。
  5. 输出，如果 k 的上限是 T + 1 就输出Infinity，否则正常输出。

时间复杂度为 \mathcal{O}(NT^2)。

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct lst_t
{
    int t, x, y;
} lst[255];
int n, t, cnt, mx, mn = LLONG_MAX;
string s;

bool cmp(lst_t x, lst_t y)
{
    return x.t < y.t;
}

signed main()
{
    cin >> n >> t >> s;
    for(int i = 1; i <= t; i++)
    {
        cin >> lst[i].t >> lst[i].x >> lst[i].y;
    }
    sort(lst + 1, lst + 1 + t, cmp);
    for(int z = 1; z <= n; z++)
    {
        bool f = 0;
        for(int k = 0; k <= t + 1; k++)
        {
            bool f2 = 1;
            int cs[n + 5] = {};
            memset(cs, -1, sizeof(cs));
            cs[z] = k;
            for(int i = 1; i <= t; i++)
            {
                if(cs[lst[i].x] == -1 && cs[lst[i].y] > 0)
                {
                    cs[lst[i].y]--;
                    cs[lst[i].x] = k;
                }
                else if(cs[lst[i].y] == -1 && cs[lst[i].x] > 0)
                {
                    cs[lst[i].x]--;
                    cs[lst[i].y] = k;
                }
                else if(cs[lst[i].x] >= 0 && cs[lst[i].y] >= 0)
                {
                    cs[lst[i].x] = max(0ll, cs[lst[i].x] - 1);
                    cs[lst[i].y] = max(0ll, cs[lst[i].y] - 1);
                }
            }
            for(int i = 1; i <= n; i++)
            {
                if((s[i - 1] == '1' && cs[i] == -1) || (s[i - 1] == '0' && cs[i] != -1))
                {
                    f2 = 0;
                }
            }
            if(f2)
            {
                mx = max(mx, k);
                mn = min(mn, k);
                f = 1;
            }
        }
        cnt += f;
    }
    cout << cnt << " " << mn;
    if(mx == t + 1)
    {
        cout << " Infinity";
    }
    else
    {
        cout << " " << mx;
    }

    return 0;
}