C/C++编程八级 题库
生理周期(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;
}最短路
给定一个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;
}道路
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;
}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;
}青蛙的约会(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;
}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;
}旅行
转眼毕业了,曾经朝夕相处的同学们不得不都各奔东西,大家都去了不同的城市开始新的生活。在各自城市居住了一段时间后,他们都感到了一些厌倦,想去看看其他人的生活究竟如何,于是他们都选择到另一个同学所在城市去旅游,并且希望旅游的城市各不相同,他们想知道有多少种不同的方案,可是数量实在太多了,他们无法计算出来,你能帮助他们吗。
时间限制: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;
}最短路
给定一个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
整理中……
道路(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;
}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;
}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;
}生理周期(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;
}旅行(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;
}夺宝大赛
夺宝大赛的地图是一个由 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;
}清点代码库
很久之前新浪微博有人发过:“阿里代码库有几亿行代码,但其中有很多功能重复的代码,比如单单快排就被重写了几百遍。请设计一个程序,能够将代码库中所有功能重复的代码找出。各位大佬有啥想法,我当时就懵了,然后就挂了。。。”
这里我们把问题简化一下:首先假设两个功能模块如果接受同样的输入,总是给出同样的输出,则它们就是功能重复的;其次我们把每个模块的输出都简化为一个整数(在 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;
}可怜的简单题
九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 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;
}产品研发
题目描述
一家公司正在研发一款新产品。该产品共有 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;
}传话对象
题目描述
在一个公司里,有 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;
}能量护盾
题目描述
在一处被宇宙射线笼罩的星域中,你驾驶着一艘小型探索飞船,需要从坐标 (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;
}图书馆
题目描述
某城市有 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,貌似有错误。