首页 › 题库 › C/C++编程考级 › C/C++编程八级

C/C++编程八级 题库

共 36 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
21 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

生理周期(2023.12)

人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。对于每个周期,我们会给出从当前年份的第一天开始,到出现高峰的天数(不一定是第一次高峰出现的时间)。你的任务是给定一个从当年第一天开始数的天数,输出从给定时间开始(不包括给定时间)下一次三个高峰落在同一天的时间(距给定时间的天数)。例如:给定时间为10,下次出现三个高峰同天的时间是12,则输出2(注意这里不是3)。

时间限制:1000

内存限制:65536

输入

一行,包含四个整数:p, e, i和d,相邻两个整数之间用单个空格隔开。 p, e, i分别表示体力、情感和智力高峰出现的时间(时间从当年的第一天开始计算)。d 是给定的时间,可能小于p, e, 或 i。 所有给定时间是非负的并且小于等于365, 所求的时间小于等于21252。

输出

一个整数,即从给定时间起,下一次三个高峰同天的时间(距离给定时间的天数)。


样例输入

4 5 6 7

样例输出

16994
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int p, e, i, d;
  cin >> p >> e >> i >> d;
  int k = d + 1;
  for (; k <= 21252; k++)
    if ((k - p) % 23 == 0 && (k - e) % 28 == 0 && (k - i) % 33 == 0)
      break;
  cout << k - d << endl;
  return 0;
}
题目详情
22 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

开关问题(2023.12)

有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)

时间限制:1000

内存限制:65536

输入

输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行 一个数N(0 < N < 29) 第二行 N个0或者1的数,表示开始时N个开关状态。 第三行 N个0或者1的数,表示操作结束后N个开关的状态。 接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。

输出

如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号


样例输入

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

样例输出

4
Oh,it's impossible~!!

提示

第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)

答案与解析
参考答案
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 35;
bool a[MAXN][MAXN];

inline int read() {
  int x;
  scanf("%d", &x);
  return x;
}

int gauss(int n) {
  int rank = 0;
  for (int d = 0; d < n; ++d) { /* d for diagonal */
    int i;
    /* try to find first line whose d'th element = 1 */
    for (i = d; i < n; ++i)
      if (a[i][d] == 1)
        break;

    /* not found */
    if (i == n)
      continue;

    /* found */

    /* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th
     * line and rank'th line, including the rightmost column */
    for (int j = 0; j <= n; ++j)
      swap(a[rank][j], a[i][j]);
    /* Step 2: eliminating the following line if the d'th element = 1, including
     * the rightmost column */
    for (i = rank + 1; i < n; ++i)
      if (a[i][d])
        for (int j = 0; j <= n; ++j)
          a[i][j] ^= a[rank][j];

    ++rank;
  }

  /* up to now, the rank+'th line should be all 0 */
  /* if the rightmost column is 1, bad equation, return -1 */
  for (int i = rank; i < n; ++i)
    if (a[i][n])
      return -1;

  /* otherwise, return the rank */
  return rank;
}

int main() {
  int K = read();
  for (int k = 0; k < K; ++k) {
    memset(a, 0, sizeof(a));
    int N = read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int x = 0; x < N; ++x)
      a[x][x] = 1;
    for (;;) {
      int x = read() - 1, y = read() - 1;
      if (x == -1)
        break;
      a[y][x] = 1;
    }
    int rank = gauss(N);
    if (rank == -1)
      printf("Oh,it's impossible~!!\n");
    else
      printf("%d\n", 1 << (N - rank));
  }
  system("pause");
  return 0;
}
题目详情
23 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

社交网络(2023.12)

随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你的名字将出现在“转发链”上。经过若干次转发以后,很可能A分享了一条好友C的状态,而C的这条状态实际上是分享B的,但A与B可能并不是好友,即A通过C间接分享了B的状态。

给定你N个人之间的好友关系,好友关系一定是双向的。只要两个人是好友,他们就可以互相转发对方的状态,无论这条状态是他自己的,还是他转发了其他人的。现在请你统计,对于每两个人,他们是否有可能间接转发对方的状态。

时间限制:1000

内存限制:262144

输入

第一行1个整数N(1<=N<=300)。 接下来N行每行N个整数,表示一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人是好友,0则表示不是好友。 保证矩阵的主对角线上都是1,并且矩阵关于主对角线对称。

输出

一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状态,0则表示不可能。


样例输入

5
11000
11100
01100
00011
00011

样例输出

11100
11100
11100
00011
00011

提示

在输入数据中,1与2是好友,2与3是好友,4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, fa[310];
char a[310][310];
int find(int x) {
  if (x == fa[x]) {
    return x;
  }
  return find(fa[x]);
}
void merge(int x, int y) {
  if (find(x) == find(y)) {
    return;
  }
  fa[find(x)] = find(y);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == 49 && i != j) {
        merge(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (find(i) == find(j)) {
        cout << 1;
      } else {
        cout << 0;
      }
    }
    cout << '\n';
  }
}
题目详情
24 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

旅行(2023.12)

转眼毕业了,曾经朝夕相处的同学们不得不都各奔东西,大家都去了不同的城市开始新的生活。在各自城市居住了一段时间后,他们都感到了一些厌倦,想去看看其他人的生活究竟如何,于是他们都选择到另一个同学所在城市去旅游,并且希望旅游的城市各不相同,他们想知道有多少种不同的方案,可是数量实在太多了,他们无法计算出来,你能帮助他们吗。

时间限制:10000

内存限制:131072

输入

一个正整数n(n<200),表示人数。

输出

一个数,表示有多少不同的方案。


样例输入

3

样例输出

2

提示

有如下两种方案: 同学1去同学2的城市,同学2去同学3的城市,同学3去同学1的城市; 同学1去同学3的城市,同学3去同学2的城市,同学2去同学1的城市。

答案与解析
参考答案
#include <iostream>
using namespace std;
unsigned long long a[22];
long long ans(int x) {
  if (a[x])
    return a[x];
  else if (x == 1)
    return a[x] = 0;
  else if (x == 2)
    return a[x] = 1;
  else if (x == 3)
    return a[x] = 2;
  else
    return a[x] = ans(x - 1) * (x - 1) + ans(x - 2) * (x - 1);
}
int main() {
  int n;
  cin >> n;
  ans(20);
  cout << ans(n);
  // printf("%llu",ans(n));
  return 0;
}
题目详情
25 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

夺宝大赛

夺宝大赛的地图是一个由 n×m 个方格子组成的长方形,主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里,同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格(“相邻”是指两个方格有一条公共边)所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时,必将发生火拼,造成参与火拼的所有队伍无法继续比赛。大赛规定:最先到达大本营并能活着夺宝的队伍获得胜利。

假设所有队伍都将以最快速度冲向大本营,请你判断哪个队伍将获得最后的胜利。

时间限制:5000

内存限制:65535

输入

输入首先在第一行给出两个正整数 m 和 n(2 < m,n ≤ 100),随后 m 行,每行给出 n 个数字,表示地图上对应方格的状态:1 表示方格可通过;0 表示该方格有障碍物,不可通行;2 表示该方格是大本营。题目保证只有 1 个大本营。 接下来是参赛队伍信息。首先在一行中给出正整数 k(0 < k < m×n/2),随后 k 行,第 i(1 ≤ i ≤ k)行给出编号为 i 的参赛队的初始落脚点的坐标,格式为 x y。这里规定地图左上角坐标为 1 1,右下角坐标为 n m,其中 n 为列数,m 为行数。注意参赛队只能在地图范围内移动,不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。

输出

在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量,数字间以 1 个空格分隔,行首尾不得有多余空格。若没有队伍能获胜,则在一行中输出 No winner.

样例输入

样例1:

5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4

样例2:

5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5

样例输出

样例1:

7 6

样例2:

No winner.

提示

样例 1 说明: 七支队伍到达大本营的时间顺次为:7、不可能、5、3、3、5、6,其中队伍 4 和 5 火拼了,队伍 3 和 6 火拼了,队伍 7 比队伍 1 早到,所以获胜。

答案与解析
参考答案
#include<iostream>
#include<map>
#include<queue>
using namespace std;
struct node{
	int xt,yt;
};
int u,v,n,m;
int mp[111][111];
int ct[111][111];
int ans[10000];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
void bfs(int x,int y){
	queue<node>q;
	q.push({x,y});
	while(!q.empty()){
		node n1=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int xtp=n1.xt+dx[i];
			int ytp=n1.yt+dy[i];
			if(ct[xtp][ytp]||!mp[xtp][ytp]) continue;
			if(xtp<=0||xtp>n||ytp<=0||ytp>m) continue;
		    ct[xtp][ytp]=ct[n1.xt][n1.yt]+1;
		    q.push({xtp,ytp});
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	 {
	 	scanf("%d",&mp[i][j]);
	 	if(mp[i][j]==2){
	 		u=i,v=j;
		 }
	 }
	 bfs(u,v); 
	int k; cin>>k;
	for(int i=1;i<=k;i++){
		int a,b;
		scanf("%d%d",&b,&a);
		if(ct[a][b]){
			if(ans[ct[a][b]]==0) ans[ct[a][b]]=i;
			else ans[ct[a][b]]=-1;
	    }
    }
    int flag=1;
    for(int i=1;i<10000;i++)
    {
    	if(ans[i]>0)
    	{
    		printf("%d %d",ans[i],i);
    		flag=0;
    		break;
		}
	}
	if(flag) printf("No winner.");
	  return 0;
}
题目详情
26 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

清点代码库

很久之前新浪微博有人发过:“阿里代码库有几亿行代码,但其中有很多功能重复的代码,比如单单快排就被重写了几百遍。请设计一个程序,能够将代码库中所有功能重复的代码找出。各位大佬有啥想法,我当时就懵了,然后就挂了。。。”

这里我们把问题简化一下:首先假设两个功能模块如果接受同样的输入,总是给出同样的输出,则它们就是功能重复的;其次我们把每个模块的输出都简化为一个整数(在 int 范围内)。于是我们可以设计一系列输入,检查所有功能模块的对应输出,从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

时间限制:7000

内存限制:262144

输入

输入在第一行中给出 2 个正整数,依次为 N(≤ 104)和 M(≤ 102),对应功能模块的个数和系列测试输入的个数。 随后 N 行,每行给出一个功能模块的 M 个对应输出,数字间以空格分隔。

输出

首先在第一行输出不同功能的个数 K。随后 K 行,每行给出具有这个功能的模块的个数,以及这个功能的对应输出。数字间以 1 个空格分隔,行首尾不得有多余空格。输出首先按模块个数非递增顺序,如果有并列,则按输出序列的递增序给出。 注:所谓数列 { A1, …, AM } 比 { B1, …, BM } 大,是指存在 1 ≤ i < M,使得 A1=B1,…,Ai=Bi 成立,且 Ai+1 > Bi+1。

样例输入

7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74

样例输出

4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35
答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>

const int INF = 0x3f3f3f3f;
const int N = 1e4+10;

struct cmp{	//自定义set排序
    bool operator() (const pair<int,vector<int> >&a, const pair<int,vector<int> >&b) const{
        if(a.first!=b.first) return a.first>b.first;
        else return a.second<b.second;
    }
};

int main(){
	int n, m; scanf("%d%d", &n, &m);
	set<vector<int> > st;		//存模块
	map<vector<int>, int> mp;	//存每个模块的个数
	set<pair<int,vector<int> >,cmp > St;//排序
	for ( int i = 0 ; i < n ; i ++ ){
		vector<int> v;
		for ( int j = 0 ; j < m ; j ++ ){
			int x; scanf("%d", &x);
			v.push_back(x);
		}
        mp[v] ++;
        st.insert(v);
	}
	
	printf("%d\n", st.size());
	//把所有模块存入ST排序 
	set<vector<int> >::iterator it;
    for(it = st.begin() ; it != st.end() ; it ++)
    	St.insert({mp[*it],*it});
	//输出ST 
	set<pair<int,vector<int> > >::iterator ite;
    for(ite = St.begin() ; ite != St.end() ; ite ++){
    	cout << (*ite).first;
        for(int i = 0; i < (*ite).second.size() ; i++)
            cout<<' '<<(*ite).second[i];
        cout<<endl;
	}
	return 0;
}
题目详情
27 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

逆散列问题

给定长度为 N 的散列表,处理整数最常用的散列映射是 H(x) = x%N。如果我们决定用线性探测解决冲突问题,则给定一个顺序输入的整数序列后,我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后,将得到HT[0]=3,HT[1]=1,HT[2]=2的结果。

但是现在要求解决的是“逆散列问题”,即给定整数在散列表中的分布,问这些整数是按什么顺序插入的?

时间限制:5000

内存限制:65536

输入

输入的第一行是正整数 N(≤ 1000),为散列表的长度。第二行给出了 N 个整数,其间用空格分隔,每个整数在序列中的位置(第一个数位置为0)即是其在散列表中的位置,其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。

输出

按照插入的顺序输出这些整数,其间用空格分隔,行首尾不能有多余的空格。注意:对应同一种分布结果,插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表,我们会得到跟 1、2、3 顺序插入一样的结果。在此规定:当前的插入有多种选择时,必须选择最小的数字,这样就保证了最终输出结果的唯一性。

样例输入

11
33 1 13 12 34 38 27 22 32 -1 21

样例输出

1 13 12 21 33 34 38 27 22 32
答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int m;
int main()
{
	cin >> m;
	vector<int>v(m);
	vector<int>temp;
	for (int i = 0; i < m; i++)
	{
		cin >> v[i];
		if (v[i] != -1)
			temp.push_back(v[i]);
	}
	sort(temp.begin(), temp.end());
	int length = temp.size();
	vector<bool>finding_value(length, 0);
	vector<bool>hashtable(m, 0);
	int num = 0, index = 0;
	//length 为插入数据长度
	while (num != length)
	{
		for (int i = 0; i < length; i++)
		{
			if (!finding_value[i]) //如果这个值没有找到位置
			{
				int posi = temp[i] % m;
				//temp[i]的线性探测初始位置
				if (v[posi] == temp[i])
				{
					printf("%d ", temp[i]);
					finding_value[i] = 1;
					hashtable[posi] = 1;
					num++;
					break;
				}
				else
				{
					for (int t = 0; t < m; t++)
					{
						int new_posi = (posi + t) % m;
						if (hashtable[new_posi])
							continue;
						if (!hashtable[new_posi] && v[new_posi] != temp[i])
							break;
						finding_value[i] = hashtable[new_posi] = 1;
						printf("%d ", temp[i]);
						num++;
						break;
					}
				}
			}
		}
	}
}
题目详情
28 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

可怜的简单题

九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:

1 . 最开始,数列 A 为空。

2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。

3 . 如果不存在一个大于 1 的正整数 w,满足 A 中所有元素都是 w 的倍数,数组 A 将会作为随机生成的结果返回。否则,可怜将会返回第二步,继续增加 A 的长度。

现在,可怜告诉了你数列 n 的值,她希望你计算返回的数列 A 的期望长度。

时间限制:60000

内存限制:1048576

输入

输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012),p 是一个质数。

输出

在一行中输出一个整数,表示答案对 p 取模的值。具体来说,假设答案的最简分数表示为 x/y,你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。

样例输入

样例1:

2 998244353

样例2:

100000000 998244353

样例输出

样例1:

2

样例2:

3054970
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Lim=2.2e7, MAXN=Lim+10;
ll n, p;
inline ll fmul(ll a,ll x) { return (__int128)a*x%p; }
inline ll fpow(ll a,ll x) { ll ans=1; for(;x;x>>=1,a=fmul(a, a) ) if(x&1) ans=fmul(ans, a); return ans; }
inline ll inv(ll a) { return fpow(a, p-2); }

ll smu[MAXN];
int prime[MAXN],  cntprime;
bool nprime[MAXN];
unordered_map<ll, ll>  M;
inline ll summu(ll n){
    if(n<=Lim) return smu[n];
    if(M.count(n)) return M[n];
    for(ll r=n, l, d;r>=1; r=l-1){
        d=n/r;
        l=n/(d+1)+1;
        if(d<=Lim||M.count(d)) continue;
        ll tmp=1;
        for(ll ll=2, rr, dd;ll<=d;ll=rr+1){
            dd=d/ll;
            rr=d/dd;
            if(dd<=Lim) tmp-=fmul(rr-ll+1, smu[dd]);
            else tmp-=fmul(rr-ll+1, M[dd]);
        }
        M[d]=(tmp%p+p)%p;
    }
    return M[n];
}
inline void sieve(){
    smu[1]=1;
    for(int i=2;i<=Lim;++i){
        if(!nprime[i]) prime[++cntprime]=i, smu[i]=-1;
        for(int j=1;j<=cntprime;++j)
            if(i*prime[j]>Lim) break;
            else if(i%prime[j]){
                nprime[i*prime[j]]=1;
                smu[i*prime[j]]=-smu[i];
            }
            else{
                nprime[i*prime[j]]=1;
                smu[i*prime[j]]=0;
                break;
            }
    }
    for(int i=2;i<=Lim;++i){
        smu[i]+=smu[i-1];
        if(smu[i]>=p) smu[i]-=p;
        else if(smu[i]<0) smu[i]+=p;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>p;
    sieve();
    ll ans=0;
    summu(n);
    for(ll l=2, r, d, tmp=n%p;l<=n;l=r+1){
        d=n/l;
        r=n/d;
        ans+=fmul( summu(r)-summu(l-1) , inv(d-tmp+p) );
    }
    ans=(ans%p+p)%p;
    ans=( fmul(ans, n)+summu(n)+p )%p;
    cout<<ans;
    cout.flush();
    return 0;
}
题目详情
29 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

产品研发

题目描述

一家公司正在研发一款新产品。该产品共有 K 项关键性能指标,初始时所有指标均为 0。公司的最终目标是让 每一项指标都不低于 P。

研发团队提出了 N 个独立的改进方案。第 i 个方案一旦实施,会同时为第 j 项指标(1≤j≤K)带来 Ai,j 的提升,但实施该方案需要投入 Ci 的研发成本。每个方案最多只能执行一次。

你需要判断:是否存在一系列方案的选择,使得所有指标均达到或超过 P?如果存在,请给出 最小的总研发成本;如果不存在,输出 −1。

输入格式

第一行,三个整数 N,K,P,分别表示方案数量、指标数量和目标阈值。

接下来 N 行,每行 K+1 个整数 Ci,Ai,1,Ai,2,…,Ai,K,分别表示第 i 个方案的成本,以及执行后各指标的提升值。

输出格式

输出一个整数,表示达成目标所需的最小总成本。若无法达成,输出 −1。

输入样例#1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

输出样例#1

9

输入样例#2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

输出样例#2

-1

说明提示

1≤N≤100

1≤K,P≤5

0≤Ai,j≤P(1≤i≤N, 1≤j≤K)

1≤Ci≤109(1≤i≤N)

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int N, K, P;
// 每个方案:cost,k个增量
struct Plan {
	ll c;
	vector<int> add;
};
vector<Plan> pl;

// 多维dp,K维,每一维0~P
// 用递归式编码/解码K维下标转一维索引
int encode(const vector<int>& st) {
	int res = 0;
	int base = 1;
	for (int i = 0; i < K; i++) {
		res += st[i] * base;
		base *= (P + 1);
	}
	return res;
}

void decode(int idx, vector<int>& st) {
	st.assign(K, 0);
	int base = 1;
	for (int i = 0; i < K; i++) {
		st[i] = (idx / base) % (P + 1);
		base *= (P + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> K >> P;
	pl.resize(N);
	for (int i = 0; i < N; i++) {
		ll c; cin >> c;
		vector<int> a(K);
		for (int j = 0; j < K; j++) cin >> a[j];
		pl[i] = {c, a};
	}
	
	int stateCnt = 1;
	for (int i = 0; i < K; i++) stateCnt *= (P + 1);
	vector<ll> dp(stateCnt, INF);
	vector<int> zero(K, 0);
	dp[encode(zero)] = 0;
	
	// 01背包,逐个方案更新
	for (auto& p : pl) {
		ll cost = p.c;
		auto& add = p.add;
		// 倒序遍历所有状态,避免重复选取
		vector<ll> tmp = dp;
		for (int idx = 0; idx < stateCnt; idx++) {
			if (dp[idx] == INF) continue;
			vector<int> st;
			decode(idx, st);
			// 计算新状态
			vector<int> nst(K);
			for (int j = 0; j < K; j++) {
				nst[j] = min(st[j] + add[j], P);
			}
			int nidx = encode(nst);
			tmp[nidx] = min(tmp[nidx], dp[idx] + cost);
		}
		dp.swap(tmp);
	}
	
	// 目标状态:全部指标=P
	vector<int> target(K, P);
	ll ans = dp[encode(target)];
	if (ans >= INF) cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}
题目详情
30 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

传话对象

题目描述

在一个公司里,有 n 名员工,编号 1 到 n。每名员工都有一个“传话对象”,即第 ii 名员工只会把消息告诉第 ti 名员工(允许告诉自己)。现在,从每名员工出发,依次沿着传话对象传递消息,可以证明经过有限步后,消息一定会回到一个已经传过的员工。

请你分别计算:从第 i 名员工开始,需要传递多少步后,才会第一次遇到一个已经传过消息的员工。

输入格式

第一行,一个整数 n。

第二行,n 个整数 t1,t2,…,tn,表示第 i 名员工的传话对象。

输出格式

输出 n 行,第 i 行一个整数,表示从第 i 名员工出发的答案。

输入样例

4
2 1 1 4

输出样例

2
2
3
1

说明提示

1≤n≤5×105

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 5e5 + 10;
int t[MAXN];
int vis[MAXN]; // 0未访问 1访问中 2已处理
int ans[MAXN];
vector<int> path;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	
	for (int i = 1; i <= n; i++) {
		if (vis[i] != 0) continue;
		path.clear();
		int cur = i;
		while (true) {
			if (vis[cur] == 1) {
				// 找到环起点:cur在path中的位置
				int pos = 0;
				while (path[pos] != cur) pos++;
				// 环部分 [pos, end]
				int ring_len = path.size() - pos;
				for (int j = pos; j < path.size(); j++) {
					ans[path[j]] = ring_len;
					vis[path[j]] = 2;
				}
				// 树链部分 [0, pos-1] 倒推
				for (int j = pos - 1; j >= 0; j--) {
					ans[path[j]] = ans[t[path[j]]] + 1;
					vis[path[j]] = 2;
				}
				break;
			}
			if (vis[cur] == 2) {
				// 当前路径全部是树链,用已处理点倒推
				for (int j = path.size() - 1; j >= 0; j--) {
					ans[path[j]] = ans[t[path[j]]] + 1;
					vis[path[j]] = 2;
				}
				break;
			}
			// 未访问,加入路径标记为访问中
			vis[cur] = 1;
			path.push_back(cur);
			cur = t[cur];
		}
	}
	
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}
题目详情
31 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

能量护盾

题目描述

在一处被宇宙射线笼罩的星域中,你驾驶着一艘小型探索飞船,需要从坐标 (xs,ys) 航行到坐标 (xt,yt)。

飞船可以以速度 1 向任意方向移动,自身视为一个点。

星域中分布着 N 个圆形能量护盾,第 i 个护盾的圆心为 (xi,yi),半径为 ri。护盾之间可能相互重叠,也可能存在包含关系。

飞船一旦进入某个护盾的内部,就能免受宇宙射线的伤害。若一个点不在任何护盾内部,则飞船会持续受到宇宙射线的照射。

你的目标是:在从起点到终点的航行过程中,尽可能减少受到宇宙射线照射的总时间。

请你计算这个最小照射时间。

输入格式

第一行,四个整数 xs,ys,xt,yt,分别表示起点和终点的坐标。

第二行,一个整数 N,表示圆形护盾的数量。

接下来 N 行,每行三个整数 xi,yi,ri,描述第 i 个护盾的圆心坐标和半径。

输出格式

输出一个实数,表示受到宇宙射线照射的最小时间,保留 10 位小数。

输入样例#1

-2 -2 2 2
1
0 0 1

输出样例#1

3.6568542495

输入样例#2

-2 0 2 0
2
-1 0 2
1 0 2

输出样例#2

0.0000000000

输入样例#3

4 -2 -2 4
3
0 0 2
4 0 1
0 4 1

输出样例#3

4.0000000000

说明提示

−109≤xs,ys,xt,yt≤109

(xs,ys)≠(xt,yt)

1≤N≤1000

−109≤xi,yi≤109

1≤ri≤109

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long long ll;
const double INF = 1e18;
const double eps = 1e-8;

struct Point {
	ll x, y;
	Point() {}
	Point(ll x_, ll y_) : x(x_), y(y_) {}
};

struct Circle {
	ll x, y, r;
	Circle() {}
	Circle(ll x_, ll y_, ll r_) : x(x_), y(y_), r(r_) {}
};

// 两点距离
double dis_pp(const Point& a, const Point& b) {
	ll dx = a.x - b.x;
	ll dy = a.y - b.y;
	return sqrt(1.0 * dx * dx + 1.0 * dy * dy);
}

// 点到圆的暴露长度,点在圆内返回0
double dis_pc(const Point& p, const Circle& c) {
	double d = dis_pp(p, Point(c.x, c.y));
	if (d <= c.r + eps) return 0.0;
	return d - c.r;
}

// 两个圆之间暴露长度,相交/包含返回0
double dis_cc(const Circle& a, const Circle& b) {
	double d = dis_pp(Point(a.x, a.y), Point(b.x, b.y));
	double sumr = a.r + b.r;
	if (d <= sumr + eps) return 0.0;
	return d - sumr;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	
	ll xs, ys, xt, yt;
	cin >> xs >> ys >> xt >> yt;
	Point S(xs, ys), T(xt, yt);
	int N;
	cin >> N;
	vector<Circle> cir(N);
	for (int i = 0; i < N; i++) {
		cin >> cir[i].x >> cir[i].y >> cir[i].r;
	}
	
	// 总点数:0起点,1~N护盾,N+1终点
	int tot = N + 2;
	vector<vector<double>> g(tot, vector<double>(tot, INF));
	for (int i = 0; i < tot; i++) g[i][i] = 0;
	
	// 0(S) <-> N+1(T)
	g[0][N+1] = dis_pp(S, T);
	g[N+1][0] = dis_pp(S, T);
	
	// 0(S) 和所有护盾 1~N
	for (int i = 1; i <= N; i++) {
		double d = dis_pc(S, cir[i-1]);
		g[0][i] = d;
		g[i][0] = d;
	}
	
	// N+1(T) 和所有护盾 1~N
	for (int i = 1; i <= N; i++) {
		double d = dis_pc(T, cir[i-1]);
		g[N+1][i] = d;
		g[i][N+1] = d;
	}
	
	// 护盾之间 i,j (1~N)
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			double d = dis_cc(cir[i-1], cir[j-1]);
			g[i][j] = d;
			g[j][i] = d;
		}
	}
	
	// Floyd 求全源最短路,N<=1000 tot=1002,1e9?不行!换Dijkstra单源
	vector<double> dist(tot, INF);
	vector<bool> vis(tot, false);
	dist[0] = 0;
	for (int step = 0; step < tot; step++) {
		int u = -1;
		double minv = INF;
		for (int i = 0; i < tot; i++) {
			if (!vis[i] && dist[i] < minv) {
				minv = dist[i];
				u = i;
			}
		}
		if (u == -1) break;
		vis[u] = true;
		for (int v = 0; v < tot; v++) {
			if (g[u][v] < INF && dist[v] > dist[u] + g[u][v]) {
				dist[v] = dist[u] + g[u][v];
			}
		}
	}
	
	cout << dist[N+1] << endl;
	return 0;
}
题目详情
32 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

图书馆

题目描述

某城市有 n 条东西向街道和 n 条南北向街道,构成一个 n×n 的街区网格。每个交叉路口处恰好建有一座图书馆,且每一行、每一列的交叉路口都恰好有一座图书馆。已知第 i 座图书馆的坐标 (xi,yi) 表示它位于第 xi 条东西向街道与第 yi 条南北向街道的交汇处。

城市规划师想要知道:有多少个 正方形区域(由连续的若干条东西向街道和连续的若干条南北向街道围成),使得该区域内每一行、每一列也恰好各有一座图书馆?

输入格式

第一行,一个整数 n。

第二行,n 个整数 x1,x2,…,xn,表示第 i 座图书馆的东西向街道编号。

第三行,n 个整数 y1,y2,…,yn,表示第 i 座图书馆的南北向街道编号。

输入保证:1≤xi,yi≤n,且每行每列恰好只有一座图书馆。

输出格式

输出一个整数,表示满足条件的正方形区域个数。

输入样例

7
1 2 3 4 5 6 7
4 3 1 6 2 5 7

输出样例

10

说明提示

1≤n≤105

1≤xi,yi≤n

输入保证每行每列恰好有一座图书馆。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<int> a, leftBig, rightBig;
ll total = 0;

void dfs(int l, int r, int mid) {
    int maxVal = a[mid];
    vector<int> minLeft, minRight;
    int mn = maxVal;
    minLeft.push_back(mn);
    for (int i = mid - 1; i >= l; i--) {
        mn = min(mn, a[i]);
        minLeft.push_back(mn);
    }
    mn = maxVal;
    minRight.push_back(mn);
    for (int i = mid + 1; i <= r; i++) {
        mn = min(mn, a[i]);
        minRight.push_back(mn);
    }
    int L = minLeft.size() - 1;
    int R = minRight.size() - 1;
    int i = 0, j = 0;
    while (i <= L && j <= R) {
        int curMin = min(minLeft[i], minRight[j]);
        if (maxVal - curMin == i + j) total++;
        if (i == L) j++;
        else if (j == R) i++;
        else if (minLeft[i+1] < minRight[j+1]) i++;
        else j++;
    }
    int lm = leftBig[mid], rm = rightBig[mid];
    if (lm >= l) dfs(l, mid-1, lm);
    if (rm <= r) dfs(mid+1, r, rm);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    a.resize(n+2);
    leftBig.assign(n+2, 0);
    rightBig.assign(n+2, n+1);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> y[i];
    for (int i = 0; i < n; i++) a[x[i]] = y[i];

    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) leftBig[i] = st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) rightBig[i] = st.top();
        st.push(i);
    }
    int root = 1;
    for (int i = 2; i <= n; i++) if (a[i] > a[root]) root = i;
    dfs(1, n, root);
    total += n;
    cout << total << endl;
    return 0;
}

输出应该是9,题目给出的输出为10,貌似有错误。

题目详情
33 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

旅游规划

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

时间限制:1000

内存限制:65536

输入

输入说明:输入数据的第 1 行给出 4 个正整数 n、m、s、d,其中 n(2 ≤ n ≤ 500)是城市的个数,顺便假设城市的编号为 0~(n-1);m 是高速公路的条数;s 是出发地的城市编号;d 是目的地的城市编号。随后的 m 行中,每行给出一条高速公路的信息,分别是:城市 1、城市 2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过 500。输入保证解的存在。

输出

在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。


样例输入

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

样例输出

3 40
答案与解析
参考答案
//参考代码1
#include <bits/stdc++.h>
using namespace std;
 
struct Edge { int to, dist, cost; };
 
int main() {
    int n, m, s, d; cin >> n >> m >> s >> d;
    vector<vector<Edge>> g(n);
    for (int i = 0, a, b, c, f; i < m; ++i) {
        cin >> a >> b >> c >> f;
        g[a].push_back({b, c, f});
        g[b].push_back({a, c, f});
    }
    vector<int> dist(n, INT_MAX), fee(n, INT_MAX);
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    dist[s] = 0, fee[s] = 0; pq.emplace(0,  0, s);
    while (!pq.empty())  {
        auto [d, f, u] = pq.top();  pq.pop(); 
        if (d > dist[u] || (d == dist[u] && f > fee[u])) continue;
        for (auto &[v, dd, ff] : g[u]) {
            if (d + dd < dist[v] || (d + dd == dist[v] && f + ff < fee[v])) {
                dist[v] = d + dd, fee[v] = f + ff;
                pq.emplace(dist[v],  fee[v], v);
            }
        }
    }
    cout << dist[d] << " " << fee[d];
}
//参考代码2
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

struct Edge {
	int to, len, cost;
};

int main() {
	int n, m, s, d;
	cin >> n >> m >> s >> d;
	
	vector<vector<Edge>> graph(n);
	for (int i = 0; i < m; ++i) {
		int u, v, len, c;
		cin >> u >> v >> len >> c;
		graph[u].push_back({v, len, c});
		graph[v].push_back({u, len, c});
	}
	
	vector<int> dist(n, INF);
	vector<int> cost(n, INF);
	dist[s] = 0;
	cost[s] = 0;
	
	using pii = pair<int, int>;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, s});
	
	while (!pq.empty()) {
		auto [cur_dist, u] = pq.top();
		pq.pop();
		
		if (cur_dist > dist[u]) continue;
		
		for (auto &edge : graph[u]) {
			int v = edge.to;
			int new_dist = cur_dist + edge.len;
			int new_cost = cost[u] + edge.cost;
			
			if (new_dist < dist[v] || (new_dist == dist[v] && new_cost < cost[v])) {
				if (new_dist < dist[v]) {
					dist[v] = new_dist;
					cost[v] = new_cost;
				} else {
					cost[v] = new_cost;
				}
				pq.push({new_dist, v});
			}
		}
	}
	
	cout << dist[d] << " " << cost[d] << endl;
	
	return 0;
}
题目详情
34 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

取帽子

拼题er们觉得戴帽子会令自己看上去很帅,所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅,服务员把他们的帽子收集了堆起来保管。当大家要离开的时候,发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队,使得每个人都能按顺序顺利取到自己的帽子。

已知每顶帽子的大小都不相同,并且帽子的尺寸跟帽子主人的体重有关 —— 越重的人戴的帽子就越大。

时间限制:1000

内存限制:65536

输入

输入第一行给出一个正整数 n (≤ 104),为拼题er的人数。随后一行给出 n 个不同的帽子尺寸,为不超过 105 的正整数,顺序是从帽子堆的底部向上给出。最后一行给出 n 个不同的体重,顺序对应编号从 1 到 n 的拼题er。体重是不超过 106 的正整数。一行中的数字以空格分隔。

输出

在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

10
12 19 13 11 15 18 17 14 16 20
67 90 180 98 87 105 76 88 150 124

样例输出

3 4 8 6 10 2 1 5 9 7

提示

样例说明: 第一顶帽子的尺寸是最大的 20,所以对应第 3 个人的最大体重 180,于是第 3 个人排在最前面。 第二顶帽子的尺寸是第 6 小的 16,对应第 6 小的体重 98,是第 4 个人,于是第 4 个人下一个走。 以此类推。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct User {
	int id;
	int weight;
};

int main() {
	int n;
	cin >> n;
	vector<int> hats(n);
	for (int i = 0; i < n; ++i) {
		cin >> hats[i];
	}
	
	vector<User> users(n);
	for (int i = 0; i < n; ++i) {
		cin >> users[i].weight;
		users[i].id = i + 1;
	}
	
	// 按帽子尺寸降序排序
	vector<int> sorted_hats = hats;
	sort(sorted_hats.begin(), sorted_hats.end(), greater<int>());
	unordered_map<int, int> hat_rank;
	for (int i = 0; i < sorted_hats.size(); ++i) {
		hat_rank[sorted_hats[i]] = i;
	}
	
	// 按体重降序排序用户
	sort(users.begin(), users.end(), [](const User& a, const User& b) {
		return a.weight > b.weight;
	});
	vector<int> sorted_users;
	for (const User& u : users) {
		sorted_users.push_back(u.id);
	}
	
	// 取出顺序是原帽子数组的逆序
	vector<int> reversed_hats(hats.rbegin(), hats.rend());
	vector<int> result;
	for (int hat : reversed_hats) {
		result.push_back(sorted_users[hat_rank[hat]]);
	}
	
	// 输出结果
	for (size_t i = 0; i < result.size(); ++i) {
		if (i != 0) cout << " ";
		cout << result[i];
	}
	cout << endl;
	
	return 0;
}
题目详情
35 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

最短工期

一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目中各个任务之间的关系,请你计算出这个项目的最早完工时间。

时间限制:1000

内存限制:65536

输入

首先第一行给出两个正整数:项目里程碑的数量 N(≤ 100)和任务总数 M。这里的里程碑从 0 到 N-1 编号。随后 M 行,每行给出一项任务的描述,格式为“任务起始里程碑 任务结束里程碑 工作时长”,三个数字均为非负整数,以空格分隔。

输出

如果整个项目的安排是合理可行的,在一行中输出最早完工时间;否则输出"Impossible"。


样例输入

样例#1:

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

样例#2:

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

样例输出

样例#1:

18

样例#2:

Impossible
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	
	vector<vector<pair<int, int>>> adj(N);
	vector<int> in_degree(N, 0);
	
	for (int i = 0; i < M; ++i) {
		int u, v, d;
		cin >> u >> v >> d;
		adj[u].emplace_back(v, d);
		in_degree[v]++;
	}
	
	queue<int> q;
	vector<int> earliest_time(N, 0);
	for (int i = 0; i < N; ++i) {
		if (in_degree[i] == 0) {
			q.push(i);
		}
	}
	
	int count = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		count++;
		
		for (auto& edge : adj[u]) {
			int v = edge.first;
			int d = edge.second;
			if (earliest_time[u] + d > earliest_time[v]) {
				earliest_time[v] = earliest_time[u] + d;
			}
			in_degree[v]--;
			if (in_degree[v] == 0) {
				q.push(v);
			}
		}
	}
	
	if (count != N) {
		cout << "Impossible" << endl;
	} else {
		int max_time = 0;
		for (int t : earliest_time) {
			if (t > max_time) {
				max_time = t;
			}
		}
		cout << max_time << endl;
	}
	
	return 0;
}
题目详情
36 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

城市间紧急救援

作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。

时间限制:1000

内存限制:65536

输入

输入第一行给出 4 个正整数 n、m、s、d,其中 n(2 ≤ n ≤ 500)是城市的个数,顺便假设城市的编号为 0 ~ (n-1);m 是快速道路的条数;s 是出发地的城市编号;d是目的地的城市编号。 第二行给出 n个正整数,其中第 i 个数是第 i 个城市的救援队的数目,数字间以空格分隔。随后的 m 行中,每行给出一条快速道路的信息,分别是:城市 1、城市 2、快速道路的长度,中间用空格分开,数字均为整数且不超过 500。输入保证救援可行且最优解唯一。

输出

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 s 到 d 的路径中经过的城市编号。数字间以空格分隔。


样例输入

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

样例输出

2 60
0 1 3
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int main() {
	int n, m, s, d;
	cin >> n >> m >> s >> d;
	vector<int> team(n);
	for (int i = 0; i < n; ++i) {
		cin >> team[i];
	}
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i < m; ++i) {
		int u, v, len;
		cin >> u >> v >> len;
		adj[u].emplace_back(v, len);
	}
	
	vector<int> dist(n, INF);
	vector<int> num(n, 0);
	vector<int> rescue(n, 0);
	vector<int> prev(n, -1);
	
	dist[s] = 0;
	num[s] = 1;
	rescue[s] = team[s];
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, s});
	
	while (!pq.empty()) {
		auto [cur_dist, u] = pq.top();
		pq.pop();
		
		if (cur_dist > dist[u]) continue;
		
		for (auto [v, len] : adj[u]) {
			int new_dist = dist[u] + len;
			if (new_dist < dist[v]) {
				dist[v] = new_dist;
				num[v] = num[u];
				rescue[v] = rescue[u] + team[v];
				prev[v] = u;
				pq.push({new_dist, v});
			} else if (new_dist == dist[v]) {
				num[v] += num[u];
				if (rescue[u] + team[v] > rescue[v]) {
					rescue[v] = rescue[u] + team[v];
					prev[v] = u;
					pq.push({new_dist, v});
				}
			}
		}
	}
	
	cout << num[d] << " " << rescue[d] << endl;
	
	vector<int> path;
	int current = d;
	while (current != s) {
		path.push_back(current);
		current = prev[current];
	}
	path.push_back(s);
	reverse(path.begin(), path.end());
	
	for (size_t i = 0; i < path.size(); ++i) {
		if (i > 0) cout << " ";
		cout << path[i];
	}
	cout << endl;
	
	return 0;
}
题目详情