• “蔚来杯“2022牛客暑期多校训练营10 EF题解

    E-Reviewer Assignment

    题目大意：
    有n个审稿人和m篇论文，要求给每个审稿人安排一篇论文，给出每个审稿人能够审的论文集合。
    定义f(i)为至少被i个审稿人审核的论文数量，要求f(1),f(2),...,f(n)组成的字典序最大。输出每个审稿人都审核哪篇论文。
    数据范围：1<= n,m <=400

    思路：
    首先注意到题目中的点数是比较少的，所以用邻接矩阵存边的容量跑最大流的话可以很方便的知道流量的流向。
    那么可以这样建图：
    源点向每个审稿人连一条容量为1的边，每个审稿人向能够审的论文连一条容量为1的边，每篇论文向汇点连一条容量为x的边，x从1取到n，一共跑n次最大流，相当于每次在上一次的基础上找增广路，不会影响到上一次的f值，这样就可以让f(1),f(2),...,f(n)的字典序最大了。
    如何得到流向：例如审稿人x和论文y，如果边xy的容量为0，yx的容量不为0，说明审稿人x审的就是论文y。

    AC代码：

    #include 
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 805;
using namespace std;

vector<int> e[N];
int n, m, cap[N][N];
char str[N];
int deep[N], cur[N], tot, S, T; // tot为最大点编号，一般tot=T,S为源点，T为汇点
bool bfs()
{
    mem(deep, 0), mem(cur, 0);
    queue<int> q;
    q.push(S);
    deep[S] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (auto v : e[u])
        {
            if (deep[v] || !cap[u][v]) continue;
            q.push(v);
            deep[v] = deep[u] + 1;
        }
    }
    return deep[T] != 0; //如果T点无法到达说明没有增广路了
}
int dfs(int u, int flow)
{
    if (u == T || flow == 0) return flow;
    int out = 0;
    for (int &i = cur[u]; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (!cap[u][v] || deep[u] + 1 != deep[v]) continue;
        int delta = dfs(v, min(flow, cap[u][v]));
        flow -= delta;
        out += delta;
        cap[u][v] -= delta; //正向边减去流量
        cap[v][u] += delta; //反向边加流量
        if (flow == 0) break;
    }
    if (out == 0) deep[u] = 0;
    return out;
}
int Dinic() //计算从源点出来的最大流量
{
    int maxflow = 0, delta;
    while (bfs())
        while (delta = dfs(S, 1e9))
            maxflow += delta;
    return maxflow;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    mem(cap, 0);
    cin >> n >> m;
    S = 0;
    tot = T = n + m + 1;
    for (int i = 1; i <= n; i++)
    {
        cap[S][i] = 1; //源点向审稿人连边
        e[S].push_back(i);
        e[i].push_back(S);

        cin >> str + 1;
        for (int j = 1; j <= m; j++) //审稿人向论文连边
        {
            if (str[j] == '1')
            {
                cap[i][j + n] = 1;
                e[i].push_back(j + n);
                e[j + n].push_back(i);
            }
        }
    }
    for (int i = 1; i <= m; i++) //论文向汇点连边
    {
        e[i + n].push_back(T);
        e[T].push_back(i + n);
    }
    int maxflow = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) //论文向汇点的容量加1
            cap[j + n][T]++;
        maxflow += Dinic();
    }
    if (maxflow == n)
    {
        for (int i = 1; i <= n; i++)
            for (auto v : e[i]) //正向流量为0，反向流量不为0，则可以确定流量方向
                if (!cap[i][v] && cap[v][i]) cout << v - n << " ";
    }
    else
        cout << "-1";
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101

    F-Shannon Switching Game?

    题目大意：
    给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，Cut Player先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。

    思路：
    当时想到了一个点到t点如果有两种路径的话，那么这个点一定可以到达。不过当时直接跑dfs找点超时了。
    题解给的做法是维护一个点的集合。集合中初始有一个点t。如果一个没有在集合中的点有两条以上的边连向集合里的点，那么这个点肯定也可以归到集合中。不断重复这个过程，最后判断s点是否在集合中即可。

    至于为什么要从t开始扩展集合而不是从s开始扩展，下面这组数据可以进行说明：

    1
1 4 1 3
1 3
1 2
2 3
2 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    显然结果是Join Player，但是从s开始扩展的话结果是Cut Player。

    AC代码：

    #include 
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e2 + 5;
using namespace std;

struct edge
{
    int to, next;
} e[2 * N * N];
int head[N], ecnt;
void add(int u, int v) { e[++ecnt].next = head[u], e[ecnt].to = v, head[u] = ecnt; }
void einit()
{
    ecnt = 0;
    for (int i = 0; i < N; i++)
        head[i] = 0;
}
int d[N];
bool vis[N];
void solve()
{
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t;
    einit();
    mem(d, 0);
    mem(vis, 0);
    while (m--)
    {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    queue<int> q;
    q.push(t);
    vis[t] = 1;
    while (q.size())
    {
        u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].next)
        {
            v = e[i].to;
            if (vis[v]) continue;
            d[v]++;
            if (d[v] >= 2)
            {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    if (d[s] >= 2)
        cout << "Join Player\n";
    else
        cout << "Cut Player\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    I-Yet Another FFT Problem?

    题目大意：
    有两个序列a和b，从a中找两个数字 ai 和 aj ，从b中找两个数字 bk 和 bl ，使得 |ai - aj|= |bk - bl|，如果不存在就输出-1。两个序列中的数字都不大于107

    思路：
    如果a和b中都有重复的数字，那么直接输出两个序列中重复数字的位置即可。
    否则将序列先进行去重，因为不可能在一个序列中选两个相同的数字而在另一个序列中选不同的数字。
    不妨设 i 将式子进行变形，也就是 ai + bl= aj + bk 。
    实际上这题没有什么很高深的算法，注意到数字都不大于107，也就是说，如果我们不断枚举 ai 和 bl，最多枚举2x107次，就会出现相同的。所以直接用一个二重循环暴力枚举即可，不用担心复杂度爆炸。这就是鸽笼定理的一个典型应用。

    AC代码：

    #include 
const int N = 1e6 + 5;
using namespace std;

int idxa[N * 10], idxb[N * 10], posi[N * 20], posj[N * 20], a[N], b[N], pa1, pa2, pb1, pb2;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (idxa[a[i]]) //如果之前出现过相同的数字
        {               //记录两个相同数字的下标
            pa1 = idxa[a[i]];
            pa2 = i;
        }
        else
            idxa[a[i]] = i;
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        if (idxb[b[i]]) //如果之前出现过相同的数字
        {               //记录两个相同数字的下标
            pb1 = idxb[b[i]];
            pb2 = i;
        }
        else
            idxb[b[i]] = i;
    }

    if (pa1 && pb1) //两个序列都有相同的数字，直接输出相同数字的下标
    {
        cout << pa1 << " " << pa2 << " " << pb1 << " " << pb2;
        return 0;
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    int len_a = unique(a + 1, a + 1 + n) - a - 1;
    int len_b = unique(b + 1, b + 1 + m) - b - 1;
    for (int i = 1; i <= len_a; i++)
    {
        for (int j = 1; j <= len_b; j++)
        {
            int sum = a[i] + b[j];
            if (posi[sum]) //之前出现过值相同的组合，直接输出
            {
                cout << posi[sum] << " " << idxa[a[i]] << " " << idxb[b[j]] << " " << posj[sum];
                return 0;
            }
            posi[sum] = idxa[a[i]];
            posj[sum] = idxb[b[j]];
        }
    }
    cout << "-1";
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
  • 相关阅读:
    2022-10-28 开源会议分享开场词
    C. Fibonacci Words-April Fools Day Contest 2021
    我的十年程序员生涯--无锡之旅，开启岗前培训
    什么是会话劫持以及如何阻止它
    join、inner join、left join、right join、outer join的区别
    ASP.net相关目录，相关配置文件和.后缀名解释
    OPTEE的系统调用
    Fluidd摄像头公网无法正常显示修复一例
    《深度学习进阶：自然语言处理》读书笔记：第2章 自然语言和单词的分布式表示
    Taurus.MVC WebMVC 入门开发教程1：框架下载环境配置与运行
  • 原文地址：https://blog.csdn.net/Shanhj/article/details/126679445