第六周

T1—1726. 挤奶顺序

Farmer John 有 N 头奶牛，编号为 1…N。
他每天都要给他的奶牛们挤奶。
奶牛的社会结构非常复杂，其结构有两个关键特性。
首先，有 M 头奶牛的地位等级分明，按照地位越高越早挤奶的规则，这些奶牛的相对挤奶顺序是固定的。
此外，有 K 头奶牛的具体挤奶顺序也是固定的，比如，奶牛 4 必须在所有奶牛中的第二位挤奶。
幸运的是，Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。
不幸的是，奶牛 1 最近生病了，所以 Farmer John 想要尽早给这头奶牛挤奶，使得她可以回到牛棚休息。
请帮助 Farmer John 求出奶牛 1 可以在挤奶顺序中出现的最早位置。

输入格式
第一行包含 N，M，K，表示 Farmer John 有 N 头奶牛，其中 M 头形成了社会阶层，K 头需要在挤奶顺序中处于一个特定的位置。
下一行包含 M 个不同的整数 mi。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。
下面 K 行，每行包含两个整数 ci 和 pi，表示奶牛 ci 一定要在第 pi 位进行挤奶。
输入数据保证：在这些限制之下，Farmer John 能够建立一个符合要求的挤奶顺序。

输出格式
输出奶牛 1 可以在挤奶顺序中出现的最早位置。

数据范围
2≤N≤100,
1≤M,K<N,
1≤mi,ci,pi≤N
输入样例：
6 3 2
4 5 6
5 3
3 1
输出样例：
4
样例解释
在这个例子中，Farmer John 有六头奶牛，其中奶牛 1 生病了。
他的挤奶顺序应该为奶牛 4 在奶牛 5 之前，奶牛 5 在奶牛 6 之前。
此外，Farmer John 必须要第一个给奶牛 3 挤奶，第三个给奶牛 5 挤奶。
FJ必须第一个给奶牛 3 挤奶，由于奶牛 4 必须要在奶牛 5 之前，奶牛 4 一定是第二个挤奶的，然后奶牛 5 第三个。
于是，奶牛 1 最早在挤奶顺序中出现的位置是第四个。

太难不会。

按三种情况进行分类讨论，模拟处理。

存在c_i = 1，直接输出答案；
存在m_i = 1，从1开始逆序找到离1最近的固定位置的牛，然后从这头牛开始对相对顺序不变的这些牛（直到1号牛）紧挨着放置；
不满足前两种情况，以固定位置的牛为划分点将序列分成若干段，在每一段中考虑从后往前放置相对顺序不变的牛，若有空位就放置1号牛，若没有则考虑下一段，直到1号牛找到位置。

本题从思路转化到代码其实有一定难度。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int p[N],q[N]; // p[a] = b表示a号牛的最终位置是b
bool st[N]; // st[a] = true表示最终位置a被用过

int main(){
    int n,m,k;
    cin >> n >> m >> k;
    
    bool flag = false;
    for (int i = 1;i <= m;i ++){
        cin >> q[i];
        if (q[i] == 1) flag = true;
    }
    
    int a,b;
    for (int i = 1;i <= k;i ++){
        cin >> a >> b;
        if (a == 1){ // 情况1,1号牛有固定位置
            cout << b;
            return 0;
        }
        p[a] = b;
        st[b] = true;
    }
    
    if (flag){ // 情况2,1号牛有相对位置，j表示可用的排序位置
        for (int i = 1,j = 1;i <= m;i ++){ // 当1号牛有相对顺序时，这m头牛尽可能往前排
            while (st[j]) j ++;
            if (p[q[i]]) j = p[q[i]]; // q[i]奶牛有固定位置，在两个固定位置之间排序
            else{ // q[i]奶牛没有固定位置，从前往后占据j位置
                if (q[i] == 1){
                    cout << j;
                    return 0;
                }
                st[j] = true;j ++;
            }
        }
    }
    else{ // 情况3,不满足前两种情况
        for (int i = m,j = n; i; i --){ // 对于每一段区间，在其中的有序位置按从后往前放置
            while (st[j]) j --;
            if (p[q[i]]) j = p[q[i]];
            else{
                st[j] = true;j --;
            }
        }
        
        for (int i = 1;i <= n;i ++){ // 找到1号牛的最靠前位置
            if (!st[i]){
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

T2—1715. 桶列表

Farmer John 正在考虑改变他给奶牛分配牛奶桶的方式。
他希望使用尽量少的牛奶桶，请帮助他！
Farmer John 有 N 头奶牛，编号为 1…N。
第 i 头奶牛需要从时刻 si 到时刻 ti 之间挤奶，并且挤奶过程中需要用到 bi 个桶。
多头奶牛可能在同一时刻都在挤奶；每个桶在每个时刻只能供一头奶牛使用。
也就是说，第 i 头奶牛在时刻 si 到时刻 ti 之间挤奶时，如果用到了某个桶，则该桶在这段时间不能被其他奶牛使用。
当然，这个桶在这段时间之外可以被其他奶牛所使用。
为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 si 和 ti 各不相同）。
FJ 有一个储藏室，里面有编号为 1、2、3、…… 的桶。
在他的挤奶策略中，当某一头奶牛（比如说，奶牛 i）开始挤奶（在时刻 si），FJ 就跑到储藏室取出编号最小的 bi 个桶分配给第 i 头奶牛用来挤奶。
请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

输入格式
输入的第一行包含 N。
以下 N 行，每行描述了一头奶牛，包含三个空格分隔的数 si,ti,bi。
其中 si 和 ti 均为 1…1000 之间的整数，bi 为 1…10 之间的整数。

输出格式
输出一个整数，为 FJ 需要的桶的数量。

数据范围
1≤N≤100
输入样例：
3
4 10 1
8 13 3
2 6 2
输出样例：
4
样例解释
在这个例子中，FJ 需要 4 个桶：他用桶 1 和桶 2 来给奶牛 3 挤奶（从时刻 2 开始）。
他用桶 3 给奶牛 1 挤奶（从时刻 4 开始）。
当奶牛 2 在时刻 8 开始挤奶时，桶 1 和桶 2 可以再次利用，然而桶 3 不可以，所以他会使用桶 1、桶 2 和桶 4。

简单的差分题，直接秒了。

#include <iostream>
using namespace std;
const int N = 1005;
int q[N];

int main(){
    int n;
    cin >> n;
    
    int a,b,c;
    for (int i = 1;i <= n;i ++){
        cin >> a >> b >> c;
        q[a] += c,q[b+1] -= c;
    }
    
    int ans = 0;
    for (int i = 1;i < N;i ++){
        q[i] += q[i-1];
        ans = max(ans,q[i]);
    }
    
    cout << ans;
    return 0;
}

T3—1696. 困牛排序

Farmer John 正在尝试将他的 N 头奶牛，方便起见编号为 1…N，在她们前往牧草地吃早餐之前排好顺序。
当前，这些奶牛以 p1,p2,p3,…,pN 的顺序排成一行，Farmer John 站在奶牛 p1 前面。
他想要重新排列这些奶牛，使得她们的顺序变为 1,2,3,…,N，奶牛 1 在 Farmer John 旁边。
今天奶牛们有些困倦，所以任何时刻都只有直接面向 Farmer John 的奶牛会注意听 Farmer John 的指令。
每一次他可以命令这头奶牛沿着队伍向后移动 k 步，k 可以是范围 1…N−1 中的任意数。
她经过的 k 头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。
例如，假设 N=4，奶牛们开始时是这样的顺序：
FJ: 4, 3, 2, 1
唯一注意 FJ 指令的奶牛是奶牛 4。
当他命令她向队伍后移动 2 步之后，队伍的顺序会变成：
FJ: 3, 2, 4, 1
现在唯一注意 FJ 指令的奶牛是奶牛 3，所以第二次他可以给奶牛 3 下命令，如此进行直到奶牛们排好了顺序。
Farmer John 急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。
请帮助他求出将奶牛们排好顺序所需要的最小操作次数。

输入格式
输入的第一行包含 N。
第二行包含 N 个空格分隔的整数，p1,p2,p3,…,pN，表示奶牛们的起始顺序。

输出格式
输出一个整数，为 Farmer John 采用最佳策略可以将这 N 头奶牛排好顺序所需要的操作次数。

数据范围
1≤N≤100
输入样例：
4
1 2 4 3
输出样例：
3

不会。

思维题。

由题意可知，每次均处理第一头牛，最后将其排序为1234n；

因为往后插是随意的，所以我们肯定能使其达到目的位置；

我们可以知道，只要后面的数小于前者，则所有前面的牛均要进行插入操作；

所有我们只要寻找从后面来看第几个要小于前者即可。

可以证明最小操作数 = i，从后往前看，要处理第一个逆序对，只有把前面的所有数都进行插入排序。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int q[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 1;i <= n;i ++) cin >> q[i];
    
    for (int i = n-1;i >= 1;i --){
        if (q[i] > q[i+1]){ // 从后往前找到第一个逆序对
            cout << i;
            return 0;
        }
    }
    // 如果不存在逆序对，说明数组有序，不需要操作
    cout << 0;
    return 0;
}

T4—1684. 大型植被恢复

长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。
随着雨季即将到来，现在应当是重新种植的时候了。
在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。
他想要在每块草地上播种其中一种草。
作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。
他的 M 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。
已知每块草地最多被 3 头奶牛喜爱。
请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。

输入格式
输入的第一行包含 N 和 M。
以下 M 行，每行包含两个范围为 1…N 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。

输出格式
输出一个 N 位数，每一位均为 1…4 之一，表示每一块草地上所种的草的种类。
第一位对应草地 1 的草的种类，第二位对应草地 2，以此类推。
如果有多种可行的解，只需输出所有解中最小的 N 位数。

数据范围
2≤N≤100,
1≤M≤150
输入样例：
5 6
4 1
4 2
4 3
2 5
1 2
1 5
输出样例：
12133

没有思路。

建图，将每头奶牛喜爱的两块草地连起来作为一条无向边，两个端点的草的种类是不一样的。

求所有解中最小的N位数，只要从小到大枚举就行，从1号草地开始枚举，然后考虑与它相连的端点的草的种类。

由于每块草地最多被 3 头奶牛喜爱，所以每块草地一定至少有一种可选的草的种类，所以这样爆搜枚举一定能找到满足条件的解，不需要从不可行状态中回溯。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
int e[3*N],ne[3*N],h[N],idx; // 每个顶点最多连三条边
bool st[N][5]; // st[i][j] = true表示第i块草地j类草不能用
int n,m;

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

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    
    int a,b;
    for (int i = 0;i < m;i ++){
        cin >> a >> b;
        add(a,b),add(b,a); // 建立双向边
    }
    
    for (int i = 1;i <= n;i ++){ // 这种枚举方式最先找到的一定是符合条件的最优解
        for (int j = 1;j <= 4;j ++){ // 先枚举点，再枚举草地种类
            if (!st[i][j]){
                cout << j; // 第i块草地种植j类草
                for (int u = h[i]; ~u;u = ne[u]){ // 与它相连的草地不能种同样的草
                    st[e[u]][j] = true;
                }
                break; // 每块草地确定一种草就退出
            }
        }
    }
    return 0;
}

T5—1471. 牛奶工厂

牛奶生意正红红火火！
农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，约翰在每条通道上安装了传送带。
不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！
所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，约翰认为事情可能还不算完全失败，只要至少还存在一个加工站 i 满足从其他每个加工站出发都可以到达加工站 i。
注意从其他任意一个加工站 j 前往加工站 i 可能会经过 i 和 j 之间的一些中间站点。
请帮助约翰求出是否存在这样的加工站 i。

输入格式
输入的第一行包含一个整数 N，为加工站的数量。
以下 N−1行每行包含两个空格分隔的整数 ai 和 bi，满足 1≤ai,bi≤N 以及 ai≠bi。
这表示有一条从加工站 ai 向加工站 bi 移动的传送带，仅允许沿从 ai 到 bi 的方向移动。

输出格式
如果存在加工站 i 满足可以从任意其他加工站出发都可以到达加工站 i，输出最小的满足条件的 i。
否则，输出 −1。

数据范围
1≤N≤100
输入样例：
3
1 2
3 2
输出样例：
2

题解一：DFS遍历图，简单题，无脑爆搜。

时间复杂度：O(n^2)。代码稍长。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
int h[N],e[N],ne[N],idx;
bool st[N];

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

void dfs(int u){
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        dfs(e[i]);
    }
}

int main(){
    int n;
    cin >> n;
    memset(h,-1,sizeof h);
    
    int a,b;
    for (int i = 0;i < n-1;i ++){
        cin >> a >> b;
        add(b,a); // 反向建边，问题转化为从i能到达其他所有点
    }
    
    for (int i = 1;i <= n;i ++){
        memset(st,0,sizeof st);
        dfs(i);
        bool flag = true;
        for (int i = 1;i <= n;i ++){
            if (!st[i]){
                flag = false;
                break;
            }
        }
        
        if (flag){
            cout << i;
            return 0;
        }
    }
    
    cout << -1;
    return 0;
}

题解二：Floyd传递闭包判断连通性。

时间复杂度：O(n^3)。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int g[N][N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 1;i <= n;i ++) g[i][i] = 1; // 注意处理连向自己的边
    
    int a,b;
    for (int i = 0;i < n - 1;i ++){
        cin >> a >> b;
        g[a][b] = 1; // g[a][b] = 1表示a能走到b，0表示不能走到
    }
    
    for (int k = 1;k <= n;k ++)
        for (int i = 1;i <= n;i ++)
            for (int j = 1;j <= n;j ++)
                if (g[i][k] && g[k][j])
                    g[i][j] = 1;
                    
    for (int i = 1;i <= n;i ++){
        bool flag = true;
        for (int j = 1;j <= n;j ++){
            if (!g[j][i]){
                flag = false;
                break;
            }
        }
        if (flag){
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

题解三：数学证明推导结论。

时间复杂度：O(n)。

n个点n-1条边且连通的图一定是一棵树。（定理）

结论1：如果有解，解一定是唯一的，否则不满足边数，反证法。

结论2：有解等价于唯一的出度为0的点，反证法。首先可以证明有解推出有唯一的出度为0的点，反之也成立。

参考题解： https://www.acwing.com/solution/content/90754/。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int d[N];

int main(){
    int n;
    cin >> n;
    
    int a,b;
    for (int i = 0;i < n - 1;i ++){
        cin >> a >> b;
        d[a] ++;
    }
    
    int cnt = 0,id;
    for (int i = 1;i <= n;i ++){
        if (!d[i]){
            cnt ++;
            id = i;
        }
    }
    if (cnt == 1) cout << id; // 有解等价于存在唯一的出度为0的点
    else cout << -1;
    return 0;
}

T6—1460. 我在哪？

农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 N 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。

输入格式
输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。

输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K 值。

数据范围
1≤N≤100
输入样例：
7
ABCDABC
输出样例：
4

不会。

求最小的K值，首先考虑二分。

题目满足二段性，可以二分处理。

接下来的问题是如何判断两字符串是否相等？可以用字符串哈希，预处理需要O(n)，查询O(1)。

手写字符串哈希代码较长，适合数据量大的情况，这里直接用STL哈希表。

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
int n;
string str;

bool check(int mid){
    unordered_set<string> hash;
    for (int i = 0;i + mid - 1 < str.size();i ++){
        string s = str.substr(i,mid);
        if (hash.count(s)) return false;
        hash.insert(s);
    }
    return true;
}

int main(){
    cin >> n >> str;
    
    int l = 1,r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

grant's Blog

2022寒假每日一题笔记（六）

第六周