首页 › 题库 › C/C++编程考级 › 1 倍增法与ST表

C/C++编程八级 题库

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

生理周期(2022.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;
}
题目详情
2 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

最短路

给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.

时间限制:2000

内存限制:65536

输入

第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.

输出

对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.

样例输入

4

5 7 1

1 2 3

2 3 4

3 4 8

1 3 9

4 5 1

1 4 5

1 5 10

4 4 1

1 2 -4

2 3 8

1 3 5

3 4 0

3 3 2

1 2 -3

2 3 -4

3 1 6

4 2 1

1 2 1

3 4 2

样例输出

0 3 7 5 6

0 -4 4 4

Error

0 1 null null

答案与解析
参考答案
//C语言参考答案
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

#define MAXN 10001
#define MAXM 20001

typedef struct {
  int u, v, w;
} Edge;

int dist[MAXN];
Edge edges[MAXM];

void BellmanFord(int n, int m, int s) {
  int i, j;

  // 初始化距离数组
  for (i = 1; i <= n; i++) {
    dist[i] = INT_MAX;
  }
  dist[s] = 0;

  // 进行n-1轮松弛操作
  for (i = 1; i <= n - 1; i++) {
    for (j = 0; j < m; j++) {
      int u = edges[j].u;
      int v = edges[j].v;
      int w = edges[j].w;

      if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // 检查是否存在负圈
  bool hasNegativeCycle = false;
  for (j = 0; j < m; j++) {
    int u = edges[j].u;
    int v = edges[j].v;
    int w = edges[j].w;

    if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
      hasNegativeCycle = true;
      break;
    }
  }

  // 输出结果
  if (hasNegativeCycle) {
    printf("Error\n");
  } else {
    for (i = 1; i <= n; i++) {
      if (dist[i] != INT_MAX) {
        printf("%d ", dist[i]);
      } else {
        printf("null ");
      }
    }
    printf("\n");
  }
}

int main() {
  int T;
  scanf("%d", &T);

  while (T--) {
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);

    int i;
    for (i = 0; i < m; i++) {
      scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    BellmanFord(n, m, s);
  }

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

道路

N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。

时间限制:1000

内存限制:65536

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。

输出

输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。

样例输入

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

样例输出

11
答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
    int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二维数组表示临界表,G[s]表示和s邻接的路
int minLen;//全局变量,记录最短的路径长度
int totalCost;//当前状态的花费
int totalLen;//当前状态的长度
int visited[110];
int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s)
{
    if(s==N)
    {
        minLen=min(minLen,totalLen);
        return ;
    }
    int len=G[s].size();
    for(int i=0;i<len;i++)//枚举和s相邻接额情况
    {
        Road r=G[s][i];
        if(!visited[r.d])//如果没有被走过
        {
            /*下面三个if语句是三条剪枝条件*/
            if(totalCost+r.t>K)//如果当前花销大于K了
                continue;
            if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了
                continue;
            //如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue
            if(totalLen+r.L>minL[r.d][totalCost+r.t])
                continue;
            minL[r.d][totalCost+r.t]=totalLen+r.L;
            visited[r.d]=1;
            totalCost+=r.t;
            totalLen+=r.L;
            Dfs(r.d);
            visited[r.d]=0;//因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态
            totalCost-=r.t;
            totalLen-=r.L;
        }
    }
}
int main()
{
    cin>>K>>N>>R;
    for(int i=0;i<R;i++)
    {
        int s;
        Road r;
        cin>>s;
        cin>>r.d>>r.L>>r.t;
        G[s].push_back(r);
    }
    totalCost=0;
    totalLen=0;
    minLen=1<<30;//无穷大
    memset(visited,0,sizeof(visited));
    for(int i=1;i<=N;i++)
        for(int j=0;j<10010;j++)
            minL[i][j]=1<<30;
    visited[1]=1;
    Dfs(1);
    if(minLen<(1<<30))
        cout<<minLen<<endl;
    else
        cout<<-1<<endl;
    return 0;
}


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

Rainbow的商店

Rainbow开了一家商店,在一次进货中获得了N个商品。

已知每个商品的利润和过期时间。

Rainbow每天只能卖一个商品,并且过期商品不能再卖。

Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。

由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。

时间限制:1000

内存限制:262144

输入

第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。

输出

输出一个整数,表示Rainbow最终可以获得的最大收益。

样例输入

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

样例输出

185

提示

第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。

答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
	int w;
	int d;
	friend bool operator <(const Goods a, const Goods b)
	{
		if (a.w != b.w)
		{
			return a.w < b.w;//大的天数小的在前
		}
		else
		{
			return a.d > b.d;
		}
	}
}good[10005];
bool vis[10005] = {};
int main()
{
	cin >> N;
	priority_queue<Goods>que;
	int maxval=0;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &good[i].w, &good[i].d);
		que.push(good[i]);
	}
	while (!que.empty())
	{
		Goods now = que.top();
		que.pop();
		for (int i = now.d; i >= 1; i--)
		{
			if (!vis[i])
			{
				vis[i] = 1;
				maxval += now.w;
				break;
			}
		}
	}
	printf("%d\n", maxval);
	return 0;
}


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

青蛙的约会(2023年5月8级)

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

时间限制:1000

内存限制:65536

输入

输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。

输出

输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"

样例输入

1 2 3 4 5

样例输出

4
答案与解析
参考答案
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	ll gcd = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return gcd;
}
ll inv(ll a, ll b, ll c) {
	ll x, y;
	ll gcd = exgcd(a, b, x, y);
	if(c % gcd != 0)	return -1;
	x *= c / gcd; //得到当前情况下的一个x
	b /= gcd; //根据通解x = x0 + (b * t) / gcd 所以b = b / gcd
	b = abs(b); //为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的
	ll ans = x % b;
	if(ans < 0)	ans += b;
	return ans;
}
int main() {
	ll x, y, n, m, L;
	cin >> x >> y >> m >> n >> L;
	ll res = inv(m - n, L, y - x);
	if(res == -1)
		cout << "Impossible";
	else
		cout << res;
	return 0;
}


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

Freda的越野跑(2023.3)

Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。

假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?

时间限制:1000

内存限制:262144

输入

第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。

输出

一个整数,表示有多少对参赛者之间发生赶超事件。

样例输入

5
1 3 10 8 5

样例输出

7

提示

我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。

答案与解析
参考答案
#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= r)
    if (a[i] > a[j])
      t[k++] = a[i++];
    else {
      t[k++] = a[j++];
      c += 1 + m - i;
    }
  while (i <= m)
    t[k++] = a[i++];
  while (j <= r)
    t[k++] = a[j++];
  for (i = l; i <= r; ++i)
    a[i] = t[i];
}
void divide(int l, int r) {
  int m;
  if (r > l) {
    m = (r + l) / 2;
    divide(l, m);
    divide(m + 1, r);
    merge(l, m, r);
  }
}
int main() {
  int n, i = 0;
  std::cin >> n;
  while (i < n)
    std::cin >> a[i++];
  divide(0, n - 1);
  std::cout << c;
}
题目详情
7 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

旅行

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

时间限制: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;
}
题目详情
8 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

最短路

给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.

时间限制:2000

内存限制:65536

输入

第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.

输出

对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.

样例输入

4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2

样例输出

0 3 7 5 6
0 -4 4 4
Error
0 1 null null
答案与解析
参考答案

整理中……

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

道路(2024.3八级)

N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。

时间限制:1000

内存限制:65536

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。

输出

输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。


样例输入

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

样例输出

11
答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
    int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二维数组表示临界表,G[s]表示和s邻接的路
int minLen;//全局变量,记录最短的路径长度
int totalCost;//当前状态的花费
int totalLen;//当前状态的长度
int visited[110];
int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s)
{
    if(s==N)
    {
        minLen=min(minLen,totalLen);
        return ;
    }
    int len=G[s].size();
    for(int i=0;i<len;i++)//枚举和s相邻接额情况
    {
        Road r=G[s][i];
        if(!visited[r.d])//如果没有被走过
        {
            /*下面三个if语句是三条剪枝条件*/
            if(totalCost+r.t>K)//如果当前花销大于K了
                continue;
            if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了
                continue;
            //如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue
            if(totalLen+r.L>minL[r.d][totalCost+r.t])
                continue;
            minL[r.d][totalCost+r.t]=totalLen+r.L;
            visited[r.d]=1;
            totalCost+=r.t;
            totalLen+=r.L;
            Dfs(r.d);
            visited[r.d]=0;//因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态
            totalCost-=r.t;
            totalLen-=r.L;
        }
    }
}
int main()
{
    cin>>K>>N>>R;
    for(int i=0;i<R;i++)
    {
        int s;
        Road r;
        cin>>s;
        cin>>r.d>>r.L>>r.t;
        G[s].push_back(r);
    }
    totalCost=0;
    totalLen=0;
    minLen=1<<30;//无穷大
    memset(visited,0,sizeof(visited));
    for(int i=1;i<=N;i++)
        for(int j=0;j<10010;j++)
            minL[i][j]=1<<30;
    visited[1]=1;
    Dfs(1);
    if(minLen<(1<<30))
        cout<<minLen<<endl;
    else
        cout<<-1<<endl;
    return 0;
}
题目详情
10 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

Freda的越野跑(2024.3八级)

Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。

假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?

时间限制:1000

内存限制:262144

输入

第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。

输出

一个整数,表示有多少对参赛者之间发生赶超事件。


样例输入

5
1 3 10 8 5

样例输出

7

提示

我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。

答案与解析
参考答案
#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= r)
    if (a[i] > a[j])
      t[k++] = a[i++];
    else {
      t[k++] = a[j++];
      c += 1 + m - i;
    }
  while (i <= m)
    t[k++] = a[i++];
  while (j <= r)
    t[k++] = a[j++];
  for (i = l; i <= r; ++i)
    a[i] = t[i];
}
void divide(int l, int r) {
  int m;
  if (r > l) {
    m = (r + l) / 2;
    divide(l, m);
    divide(m + 1, r);
    merge(l, m, r);
  }
}
int main() {
  int n, i = 0;
  std::cin >> n;
  while (i < n)
    std::cin >> a[i++];
  divide(0, n - 1);
  std::cout << c;
}
题目详情
11 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 1 倍增法与ST表

Rainbow的商店(2024.3八级)

Rainbow开了一家商店,在一次进货中获得了N个商品。

已知每个商品的利润和过期时间。

Rainbow每天只能卖一个商品,并且过期商品不能再卖。

Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。

由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。

时间限制:1000

内存限制:262144

输入

第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。

输出

输出一个整数,表示Rainbow最终可以获得的最大收益。


样例输入

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

样例输出

185


提示

第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。

答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
	int w;
	int d;
	friend bool operator <(const Goods a, const Goods b)
	{
		if (a.w != b.w)
		{
			return a.w < b.w;//大的天数小的在前
		}
		else
		{
			return a.d > b.d;
		}
	}
}good[10005];
bool vis[10005] = {};
int main()
{
	cin >> N;
	priority_queue<Goods>que;
	int maxval=0;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &good[i].w, &good[i].d);
		que.push(good[i]);
	}
	while (!que.empty())
	{
		Goods now = que.top();
		que.pop();
		for (int i = now.d; i >= 1; i--)
		{
			if (!vis[i])
			{
				vis[i] = 1;
				maxval += now.w;
				break;
			}
		}
	}
	printf("%d\n", maxval);
	return 0;
}
题目详情
12 简答题 偏难 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;
}
题目详情
13 简答题 偏难 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;
}
题目详情
14 简答题 偏难 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;
}
题目详情
15 简答题 偏难 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;
}
题目详情
16 简答题 偏难 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;
}
题目详情
17 简答题 偏难 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;
}
题目详情
18 简答题 偏难 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;
}
题目详情
19 简答题 偏难 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;
}
题目详情
20 简答题 偏难 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,貌似有错误。

题目详情