百度松果菁英班–oj赛（第五次）

一、附庸的附庸

**题目：**蒙德城的旧贵族们存在着附庸的关系。欧洲有一位伟人说过，我的附庸的附庸不是我的附庸。尽管如此，他们还是存在着隐性的自上而下的关系，属于同一个利益集团。所以，在蒙德城，附庸的附庸也是附庸。也就是说，如果两个附庸都能追溯到同一个贵族，他们也存在附庸关系（仅仅是蒙德人这样认为）蒙德城人口众多，现在小码哥把各人的关系都梳理了出来交给了你，并想让你告诉他，某两个人存不存在附庸关系（按照蒙德人的观念）。

/**输入格式:第一行一个整数n，表示n个关系;接下来n行，每行两个数a,b，表示b是a的附庸;下一行一个整数q，表示询问次数;接下来q行，每行两个数a,b，询问α和b是否存在附庸关系。输出格式:q行，每行一个数。1表示存在附庸关系，0表示不存在。样例1   输入：51 22 31 74 55 622 71 4输出：10备注其中: 5≤n ≤10000,2≤q≤2000,1≤a,b ≤20000, a≠ b，保证涉及询问的关系中不存在环。
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 2e4 + 5;
int f[N], n, q, a, b;//并查集的模板
void init(int n){//初始化，由于无法确定附庸的人的索引for(int i = 1; i <= n; i++){f[i] = i;}
}
//查找
int find(int x){//将键与值对比，相同返回键，也就是主人；不同返回值，拿值做键在做比较return x == f[x] ? x : (f[x] = find(f[x]));//路径压缩
}int main(){cin >> n;init(N);while(n--){cin >> a >> b;f[b] = a;//b为a的附庸，因为附庸唯一做键}cin >> q;while(q--){cin >> a >> b;if(find(a) == find(b)){//判断两个值是否相同cout << "1" << endl;}else{cout << "0" << endl;}}return 0;
}

二、采蜜

**题目：**现在有n个蜂巢，每一个蜂窝都对应了一个蜂蜜值si。

小码哥发现:有一些蜂窝相互联结，使得他们可以共享蜂蜜值，即该蜂巢的蜂蜜值变为:它和它连接(直接连接或间接连接)的蜂巢的蜂蜜值的和。

现在小码哥想要查询一下一些蜂巢的蜂蜜值。

/**输入格式:第一行有两个数n(蜂巢的数量)、 m(操作的数量)第二行有n个数字(s1,……,sn)︰分别表示了每一个蜂巢的蜂蜜值。随后有m 行:第一个数字如果是1 ，则后面还有两个数字a，b，表示此次发现蜂巢α 和b是相连的。第一个数字如果是 2，则后面只有一个数字c，表示查询所有与蜂巢c相连的蜂巢(包括自己)的总蜂蜜值。输出格式:对每一次的查询操作输出查询的蜂巢的蜂蜜值。样例1   输入：4 61 1 1 11 1 2 2 11 2 32 11 3 42 1输出：234备注其中: 1≤m,n ≤100000,0≤si≤100
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 1e5 + 5;
int f[N], s[N], n, m;//并查集的模板
int find(int x){//查找根节点//将键与值对比，相同返回键；不同返回值，拿值做键在做比较return x == f[x] ? x : (f[x] = find(f[x]));//路径压缩
}
void merge(int i, int j){//合并蜂蜜值int x = find(i);//查找根节点的蜂蜜值int y = find(j);if(x != y){f[x] = y;//将节点赋值为根节点的值s[y] += s[x];//根节点的值为蜂蜜的总和}
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i];f[i] = i;//并查集初始化}while(m--){int first, a, b;cin >> first;if(first == 1){//输入为1的操作cin >> a >> b;merge(a, b);}else{//输入为2的操作cin >> a;cout << s[find(a)] << endl;//将根节点作为键查询最大的存储量}}return 0;
}

三、暧昧团

**题目：**小码哥正在整理NPU的学生信息。现在到了关键的一步:存储cp信息。

因为众所周知情网很乱，所以可能一个人和多个人暖昧，并且不分性别，而且有可能自己和自己暖昧。

同时一对暖昧关系可能会由于大意等原因多次记录。

现在我们知道n个人，并且有m个暖昧关系。

现在我们对暧昧团进行定义:一个人所有和他有直接暧昧关系以及间接暧昧关系的集合。

比如1与2暧昧，2与3暖味，3与4暧味，5与3暖味，6与2暧昧，那么{1,2,3,4,5,6}，{2,3},{1,4,5,6}, {空集合}就均属于暧昧团，其中，{1,2,3,4,5,6}就是极大暧昧团。

现在小码哥告诉你一个人名的编号x，让你回答与x所处极大暧味团的大小。

如果一个人和谁都不暧昧，那么答案就是1

/**输入格式:第一行一个整数n，m ( 1 ≤n，m ≤le5)，表示人数，和暧昧关系的数量;接下来m行，每行两个整数a,b ( 1≤a， b≤n )，表示a，b之间存在暧昧关系;最后一行一个整数x，表示询问x所处极大暖昧团的大小。输出格式:一行一个整数表示答案。样例1   输入：6 81 25 23 64 51 42 23 63 63输出：2
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 1e5 + 5;
int f[N], s[N], n, m;//并查集的模板
int find(int x){//查找根节点//将键与值对比，相同返回键；不同返回值，拿值做键在做比较return x == f[x] ? x : (f[x] = find(f[x]));//路径压缩
}
void merge(int i, int j){//合并暧昧值int x = find(i);//查找根节点的暧昧值int y = find(j);if(x != y){f[x] = y;//将节点赋值为根节点的值s[y] += s[x];//根节点的值为暧昧值的总和}
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++){s[i] = 1;//暧昧值每个人都为1f[i] = i;//并查集初始化}while(m--){int a, b;cin >> a >> b;merge(a, b);}int x;cin >> x;cout << s[find(x)];//返回根节点的索引对应的最大暧昧值return 0;
}

四、上楼梯

**题目：**小码哥是个调皮的孩子，他上楼梯喜欢蹦蹦跳跳，也就是说，每次他会随机向上走1级或2级台阶。无聊的你想知道他从地面上到n层共有多少种走法。每层楼之间有m.级台阶。

/**输入格式:输入两个正整数m，n，代表每层台阶数以及要去到的楼层。输出格式:输出一个数，代表所有可能的走法的总个数。样例1   输入：1 4输出：3备注上楼哦! n* m≤90。
*/         
#include<bits/stdc++.h> using namespace std;
int n, m, num;
long long dp[95];
int main(){cin >> m >> n;num = (n - 1) * m;//总台阶数dp[1] = 1;//边界值，1个台阶一种走法dp[2] = 2;//边界值，2个台阶两种走法for(int i = 3; i <= num; i++){//转态转换方程dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[num];//最后的台阶总走法return 0;
}

五、上楼梯2

**题目：**小码哥是个调皮的孩子，他上楼梯喜欢蹦蹦跳跳，也就是说，每次他会随机向上走1级或2级台阶。他初始在第1阶台阶上。

这道题已经做过了，现在把它升级，假设这个小码哥不是个普通的小孩，他是超人宝宝，每次最多可以向上走k级台阶(超人宝宝当然不傻，最少也会向上走一个台阶)，请你求出他从底部上到第n级台阶共有多少种可能的走法。

/**输入格式:输入一行用空格隔开的两个正整数n和k。输出格式:输出一个数，代表所有可能的走法的总个数。由于这个数可能很大，请你输出结果对114584取模的结果。样例1   输入：3 4输出：4备注其中: n≤10^5,k≤100
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 1e5 + 5;
int dp[N], n, k;
int main(){cin >> n >> k;dp[0] = dp[1] = 1;//临界值for(int i = 2; i <= n; i++){//台阶数//走的台阶数，当i小于k时，此时超人宝宝最多走i个阶梯for(int j = 1; j <= min(i, k); j++){//转态转换方程，将超人宝宝走的小于等于k总走法的总数累加dp[i] = (dp[i] + dp[i - j]) % 114584;}}cout << dp[n];//最大台阶数的值return 0;
}

六、大厨小码哥

**题目：**大厨小码哥要做一道菜，这道菜需要烹饪数个小时，达到一定的火力值。可以选择小火烹饪一次加n点火力值，中火烹饪加m点火力值，大火烹饪加k点火力值，烹饪次数不限制。这道菜总共要达到x点火力值，不多不少，才能显现出大厨小码哥的实力。但大厨小码哥觉得这还是太简单了。所以他想考考你，这道菜有多少种不同的烹饪方式(火力烹饪的顺序不同也算不同的情况，毕竟厨艺学博大精深，先小火后大火和先大火后小火烹饪的菜品会有很大不同）﹖由于数据很大，请输出答案mod le9 ＋ 7之后的值。

/**输入格式:四个整数x, n, m,k。输出格式:一个整数，表示不同的方案数;若无法烹饪则输出impossible样例1   输入:5 1 2 3输出：13备注所有数据均在longlong范围内，0<R <1000，0<n<m<k<30。
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 1e3 + 5;
const int mod = 1e9 + 7;
int x, n, m, k;
long long dp[N];int main(){cin >> x >> n >> m >> k;dp[0] = 1;//临界值，火力为0时只有一种情况for(int i = 1; i <= x; i++){if(i - n >= 0){//当火力加n就达到x时的转态转换方程dp[i] += dp[i - n];}if(i - m >= 0){//当火力加m就达到x时的转态转换方程dp[i] += dp[i - m];}if(i - k >= 0){//当火力加n就达到k时的转态转换方程dp[i] += dp[i - k];}dp[i] = dp[i] % mod;//求余}if(dp[x]){cout << dp[x];}else{cout << "impossible";}return 0;
}

七、纸带

**题目：**小码哥有一张1xn的纸带，由 n个格子组成。初始有一个点在n号格子（即左数第n个）中。

假设现在这个点在x(x > 1)号格子，每次小码哥可以对这个点进行如下操作中的一种:

减法。选择一个[1, x―1]中的正整数y ，将点移动到x -y号格子中。

除法。选择一个[2, x]中的正整数z，将点移动到Lx/z」号格子中。当点在1号格子中时无法移动，操作结束。

求将点从n号格子移到1号格子的方案数，答案对给定的模数取模。两个方案不同当且仅当有一步选择的操作或选择的数不同。

/**输入格式:一行两个数，纸带长度n和模数m。输出格式:一行一个数，表示答案对m取模的结果。样例1   输入：3 998244353输出：5备注2 ≤n ≤4e6, 1e8 <m< 1e9, m是质数。
*/         
#include<bits/stdc++.h> 
#define ll long longusing namespace std;
const int N = 4e6 + 5;
int n, mod;
ll dp[N], sum[N];int main(){cin >> n >> mod;dp[n] = 1;//临界值sum[n] = 1;//后缀和的数组//将题目逆序，变成从1号格子移动到n号格子//此时操作，变为加法和乘法for(int i = n - 1; i >= 1; i--){dp[i] = sum[i + 1];//加法//乘法for(int j = 2; j * i <= n; j++){//乘法时，余数的区间int r = min(n, i * j + j - 1);//由于是后缀和，从右向左，数值越来越大，即左边减右边+1得到区间的值的和dp[i] = (dp[i] + sum[i * j] - sum[r + 1]) % mod;}//后缀和sum[i] = (sum[i + 1] + dp[i]) % mod;}cout << dp[1];return 0;
}

八、围栏木桩

**题目：**某农场有一个由按编号排列的n根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩高度成一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选取出t根木桩的方案总数c 。

/**输入格式:文件中的第一行只有一个数m，表明随后有m个问题的描述信息。每个问题的描述信息格式为n, h1, h2, h3, . . . , hn(其中hi(i=1，2，3，...，n）表示第à根木桩的高度)。输出格式:依次输出每个问题中t和c的解，每行输出一个问题的解。样例1   输入：39 10 1 9 8 7 6 3 4 63 100 70 1026 40 37 23 89 91 12输出：4 12 23 3备注其中: 1≤m≤5,1≤n≤20, 1 ≤hi≤150
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 25;
int n, m, h[N], dp[N], f[N], ans_t, ans_c;
int main(){cin >> m;while(m--){ans_t = 0;ans_c = 0;memset(h, 0, sizeof(h));memset(dp, 0, sizeof(dp));memset(f, 0, sizeof(f));cin >> n;for(int i = 1; i <= n; i++){cin >> h[i];dp[i] = 1;f[i] = 1;}for(int i = 2; i <= n; i++){for(int j = i - 1; j >= 1; j--){if(h[j] <= h[i]){if(dp[j] + 1 > dp[i]){dp[i] = dp[j] + 1;f[i] = f[j];}else if(dp[j] + 1 == dp[i]){f[i]++;}}}}for(int i = 1; i <= n; i++){ans_t = max(ans_t, dp[i]);}for(int i = 1; i <= n; i++){if(dp[i] == ans_t){ans_c += f[i];}}cout << ans_t << " " << ans_c << endl;}return 0;
}

九、最长字段和

**题目：**给出一个长度为n的序列a ，选出其中连续且非空的一段使得这段和最大。

/**输入格式:第一行是一个整数，表示序列的长度n;第二行有n个整数，第i个整数表示序列的第i个数字ai。输出格式:输出一行一个整数表示答案。样例1   输入：72 -4 3 -1 2 -4 3输出：4备注其中:1≤n≤2e5，- 1e4≤ai≤ 1e4*/         
#include<bits/stdc++.h> using namespace std;
const int N = 2e5 + 5;
int n, dp[N], ans;
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> dp[i];//省略一个数组的内存开销}ans = dp[1];for(int i = 2; i <= n; i++){//如果前面的和大于0，则将结果相加if(dp[i - 1] >= 0){dp[i] += dp[i - 1]; }//若前面和小于0，则最大值为本身ans = max(ans, dp[i]);}cout << ans;return 0;
}

十、旅费

**题目：**提瓦特大陆上有个贫穷的占星术士小码哥，他要从蒙德去往璃月，两个地方相隔很远，所以要搭乘车队。但是搭乘车队需要金币，而小码哥没有太多金币，幸运的是，车队在这一路上有n个停靠点，每两个停靠点之间所需要的金币数不一样，如果能选择好的话说不定能省点钱。于是小码哥找来了每个站点之间所需的路费，请你帮他找出他完成这一旅途所需要的最少的旅费。

/**输入格式:第一行输入一个数n，表示马车中间停靠的站点数;接下来一个n＋1行的半矩阵，表示从蒙德开始，每个站点到接下来每个站点所需要的金币数。输出格式:输出一行一个正整数，表示完成这一旅途所需要的最少的旅费（金币数)。样例1   输入：16 189输出：15820备注其中: 1≤n <1000任意两站间所需旅费不超过10000样例解释:蒙德–-6- ->站点1，蒙德–-18- ->璃月站点1 - -9- ->璃月
*/         
#include<bits/stdc++.h> using namespace std;
const int N = 1e3  + 5;
int a[N][N], dp[N], n;
int main(){cin >> n;n++;//由于n为中间停靠站点数for(int i = 0; i < n; i++){for(int j = i + 1; j <= n; j++){cin >> a[i][j];}dp[i] = 0x3f3f3f3f;//由于求最小值将dp初始化为无穷大}for(int i = n - 1; i >= 0; i--){for(int j = i + 1; j <= n; j++){//转态转换方程//a[i][j] + dp[j]的含义：从出发到第j个点+第j到终点的费用dp[i] = min(dp[i], dp[j] + a[i][j]);}}cout << dp[0];return 0;
}

记录每一个学习瞬间