2.16学习总结

1.邮递员送信(dijkstra 不只是从起到到目标点,还要走回去)
2.炸铁路(并查集)
3.统计方形(数据加强版)(排列组合)
4.滑雪(记忆化)
5.小车问题(数学问题)
6.ACM(记忆化,搜索)
7.奶牛的耳语(二分)
8.计算器的改良(模拟)
9.L-shapes(遍历)
10.Alternating Heights(拓扑排序+二分)

邮递员送信https://www.luogu.com.cn/problem/P1629

题目描述

有一个邮递员要送东西,邮局在节点 11。他总共要送 �−1n−1 样东西,其目的地分别是节点 22 到节点 �n。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 �m 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 �−1n−1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数,�n 和 �m,表示城市的节点数量和道路数量。

第二行到第 (�+1)(m+1) 行,每行三个整数,�,�,�u,v,w,表示从 �u 到 �v 有一条通过时间为 �w 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

输入输出样例

输入 #1复制

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

输出 #1复制

83

说明/提示

对于 30%30% 的数据,1≤�≤2001≤n≤200。

对于 100%100% 的数据,1≤�≤1031≤n≤103,1≤�≤1051≤m≤105,1≤�,�≤�1≤u,v≤n,1≤�≤1041≤w≤104,输入保证任意两点都能互相到达。

思路:与平常最短路不同的是,这个需要走回去,那就把邻接表反过来,在走一遍dijkstra

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=1005;
int n,m;struct node{int to;int w;node(int b,int c){to=b;w=c;}
};
vector<node>e1[N];
vector<node>e2[N];
int dis1[N],dis2[N];
struct s_node{int id;int n_dis;s_node(int a,int b){id=a;n_dis=b;}bool operator < (const s_node &a )const{return n_dis>a.n_dis;}
};void dijkstra1(){priority_queue<s_node>q;bool done[N];for (int i=1;i<=n;++i){done[i]=false;dis1[i]=INF;}dis1[1]=0;q.push(s_node(1,dis1[1]));while (!q.empty()){s_node u=q.top(); q.pop();if (done[u.id]) continue;done[u.id]=true;for (int i=0;i<e1[u.id].size();++i){node y=e1[u.id][i];if (done[y.to]) continue;if (dis1[y.to]> u.n_dis+y.w){dis1[y.to]=u.n_dis+y.w;q.push(s_node(y.to,dis1[y.to])); }}}
}void dijkstra2(){priority_queue<s_node>q2;bool done[N];for (int i=1;i<=n;++i){done[i]=false;dis2[i]=INF;}dis2[1]=0;q2.push(s_node(1,dis2[1]));while (!q2.empty()){s_node u=q2.top(); q2.pop();if (done[u.id]) continue;done[u.id]=true;for (int i=0;i<e2[u.id].size();++i){node y=e2[u.id][i];if (done[y.to]) continue;if (dis2[y.to]> u.n_dis+y.w){dis2[y.to]=u.n_dis+y.w;q2.push(s_node(y.to,dis2[y.to])); }}}
}signed main(){cin>>n>>m;for (int i=0;i<m;++i){int a,b,c;cin>>a>>b>>c;e1[a].push_back(node(b,c));e2[b].push_back(node(a,c));}dijkstra1();int res=0;for (int i=1;i<=n;++i){res+=dis1[i];}dijkstra2();for (int i=1;i<=n;++i){res+=dis2[i];}cout<<res;
}
炸铁路https://www.luogu.com.cn/problem/P1656

题目描述

A 国派出将军 uim,对 B 国进行战略性措施,以解救涂炭的生灵。

B 国有 �n 个城市,这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim 发现有些铁路被毁坏之后,某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。

uim 为了尽快使该国的物流系统瘫痪,希望炸毁铁路,以达到存在某两个城市无法互相通过铁路到达的效果。

然而,只有一发炮弹(A 国国会不给钱了)。所以,他能轰炸哪一条铁路呢?

输入格式

第一行 �,� (1≤�≤150n,m (1≤n≤150,1≤�≤5000)1≤m≤5000),分别表示有 �n 个城市,总共 �m 条铁路。

以下 �m 行,每行两个整数 �,�a,b,表示城市 �a 和城市 �b 之间有铁路直接连接。

输出格式

输出有若干行。

每行包含两个数字 �,�a,b,其中 �<�a<b,表示 〈�,�〉〈a,b〉 是 key road。

请注意:输出时,所有的数对 〈�,�〉〈a,b〉 必须按照 �a 从小到大排序输出;如果�a 相同,则根据 �b 从小到大排序。

输入输出样例

输入 #1复制

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

输出 #1复制

1 2
5 6

思路:用并查集,先每次循环去掉一个遍,然后验证一边是否成立

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=200;
int n,m;struct node{int from;int to;
}a[5005];bool cmp(const node& a, const node& b){if (a.from==b.from) return a.to<b.to;else return a.from<b.from;
}int f[N],cnt=0;int find(int x){if (f[x]==x){return x;}else if (f[x]!=x){f[x]=find(f[x]);return f[x];}
}node b[5005];void unionn(int i,int j){f[find(i)]=find(j);
}void check(){for (int i=1;i<=m;++i){for (int i=1;i<=n;++i) f[i]=i;for (int j=1;j<=m;++j){if (i==j)continue;unionn(a[j].from,a[j].to);}for (int k=1;k<n;++k){if (find(k)!=find(k+1)){cnt++;b[cnt].from=a[i].from;b[cnt].to=a[i].to;break;}}}for (int i=1;i<=cnt;++i){if (b[i].from>b[i].to){int tmp=b[i].from;b[i].from=b[i].to;b[i].to=tmp;}}sort(b+1,b+1+cnt,cmp);for (int i=1;i<=cnt;++i){cout<<b[i].from<<" "<<b[i].to<<endl;}
}signed main(){cin>>n>>m;for (int i=1;i<=m;++i){cin>>a[i].from>>a[i].to;}sort(a+1,a+1+m,cmp);check();
}
统计方形(数据加强版)https://www.luogu.com.cn/problem/P2241

题目背景

1997年普及组第一题

题目描述

有一个 �×�n×m 方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。

输入格式

一行,两个正整数 �,�n,m(�≤5000,�≤5000n≤5000,m≤5000)。

输出格式

一行,两个正整数,分别表示方格包含多少正方形、长方形(不包含正方形)。

输入输出样例

输入 #1复制

2 3

输出 #1复制

8 10

思路:用数学的想法,在n×m的棋盘中,一个可以有C_{n+1}^{2}\textrm{}×C_{m+1}^{2}\textrm{}个矩形,然后正方形的最大边长是到min{m,n},所以正方形的个数是\sum_{1}^{n}(n+1-i)(m+1-i)(这里假定n<m),所以矩形的数量减去正方形就是长方形的数量

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fint n,m;signed main(){cin>>n>>m;int cnt=0;int x=((n+1)*n/2)*((m+1)*m/2);for (int i=1;i<=min(m,n);++i){cnt+=(n-i+1)*(m-i+1);}cout<<cnt<<" "<<x-cnt;
}
滑雪https://www.luogu.com.cn/problem/P1434

题目描述

Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24−17−16−124−17−16−1(从 2424 开始,在 11 结束)。当然 2525-2424-2323-……-33-22-11 更长。事实上,这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 �R 和列数 �C。下面是 �R 行,每行有 �C 个数,代表高度(两个数字之间用 11 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

输入 #1复制

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出 #1复制

25

说明/提示

对于 100%100% 的数据,1≤�,�≤1001≤R,C≤100。

思路:记忆化+dfs,每个点来一遍dfs,就可以找到最大长度了,记忆化可以减少时间消耗

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N =105;
int a[N][N],s[N][N];
int m,n;int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};void dfs(int x,int y){if (s[x][y]) return;s[x][y]=1;for (int i=0;i<4;++i){int xx=x+dir[i][0],yy=y+dir[i][1];if (xx < 1 || xx >m || yy<1 || yy >n) continue;if (a[x][y]>a[xx][yy]){dfs(xx,yy);s[x][y]=max(s[x][y],s[xx][yy]+1);}}
}signed main(){cin>>m>>n;for (int i=1;i<=m;++i){for (int j=1;j<=n;++j){cin>>a[i][j];}}int ans=0;for (int i=1;i<=m;++i){for (int j=1;j<=n;++j){dfs(i,j);ans=max(ans,s[i][j]);}}cout<<ans;
}
小车问题https://www.luogu.com.cn/problem/P1258

题目描述

甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车,可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎样利用小车才能使两人尽快同时到达。

输入格式

仅一行,三个实数,分别表示 AB 两地的距离 �s,人的步行速度 �a,车的速度 �b。

输出格式

两人同时到达 B 地需要的最短时间,保留 66 位小数。

输入输出样例

输入 #1复制

120 5 25

输出 #1复制

9.600000

说明/提示

数据规模与约定

对于 100%100% 的数据,保证 0≤�,�,�≤1090≤s,a,b≤109。

思路:解方程

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fdouble s,a,b;signed main(){cin>>s>>a>>b;double t=((a+3*b)/(b*(3*a+b)))*s;printf("%.6lf",t);
}
ACMhttps://www.luogu.com.cn/problem/P7793

题目背景

Zagreb 大学的团队的成员 Stjepan、Ivan 和 Gustav 正在摩洛哥参加 ACM 国际大学生程序设计竞赛的世界决赛。他们的技术指导 Goran 想出了一个无敌的策略,用于解决决赛中的题目。

题目描述

在一开始,每个团队成员迅速估计 �n 道题目中每题的难度。这些难度用 11 到 55 的数字描述,数字越大,难度也就越大。

在这之后,他们之间将分配任务。为了简单起见,任务阵列将被分成三部分,以便每个团队成员得到一个非空的连续任务序列来思考。这种分配是为了使估计的难度之和最小,而只计算被分配到该任务的团队成员的估计难度值。你的任务是计算这个最小的可能总和。

输入格式

输入共四行。

第一行输入一个整数 �n,表示问题的数量。
第二到第四行,第 �+1i+1 行 �n 个整数 ��,1,��,2,…,��,�di,1​,di,2​,…,di,n​,表示第 �i 号成员对于这 �n 道题目估计的难度。

输出格式

输出仅一行,一个整数,表示最小可能的估计难度总和。

输入输出样例

输入 #1复制

3
1 3 3
1 1 1
1 2 3

输出 #1复制

4

输入 #2复制

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

输出 #2复制

19

说明/提示

【样例 1 解释】

给第 11 号成员分配第 11 题,给第 22 号成员分配第 33 道题,给第 33 号成员分配第 22 道题。这样分配的难度总和为 1+1+2=41+1+2=4。可以证明没有难度总和更小的分配方案。

【数据范围】

对于所有数据,3⩽�⩽1.5×1053⩽n⩽1.5×105,1⩽��,�⩽51⩽di,j​⩽5。

思路:动态规划,遍历所有的情况,因为一共的三个人,所以C_{3}^{1}\textrm{}C_{2}^{1}\textrm{}一共6种情况(需要在意顺序)确定状态转移方程:可以从上一个编号的人或自己做上一题进行转移

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=2e5+5;int n,dp[4][N],f[4][N],minn=INF;void dfs(int a,int b,int c){memset(dp,0x3f,sizeof(dp));dp[a][1]=f[a][1];for (int i=2;i<=n;++i){dp[a][i]=dp[a][i-1]+f[a][i];dp[b][i]=min(dp[a][i-1],dp[b][i-1])+f[b][i];dp[c][i]=min(dp[b][i-1],dp[c][i-1])+f[c][i];}minn=min(minn,dp[c][n]);
}signed main(){cin>>n;for (int i=1;i<=3;++i){for (int j=1;j<=n;++j){cin>>f[i][j];}}dfs(1,2,3);dfs(1,3,2);dfs(2,1,3);dfs(2,3,1);dfs(3,2,1);dfs(3,1,2);cout<<minn;
}
奶牛的耳语https://www.luogu.com.cn/problem/P1296

题目描述

在你的养牛场,所有的奶牛都养在一排呈直线的牛栏中。一共有 �n 头奶牛,其中第 �i 头牛在直线上所处的位置可以用一个整数坐标 ��(0≤��≤108)pi​(0≤pi​≤108) 来表示。在无聊的日子里,奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的,而由于声波的能量衰减,某头奶牛发出的声音只能被与它距离不超过 �(0≤�≤104)d(0≤d≤104) 的奶牛所听到,这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 �d ,请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

输入格式

第一行包含两个整数 �,�n,d。

第二行包含 �n 个整数,每个整数都是一个坐标 ��pi​,描述一头奶牛在直线上的位置。

输出格式

一个数,表示养牛场中可以相互交流奶牛的对数。

输入输出样例

输入 #1复制

5 10
10 12 16 37 40

输出 #1复制

4

说明/提示

数据规模

对于 40%40% 的数据,1≤�≤1031≤n≤103。

对于 100%100% 的数据,1≤�≤1061≤n≤106。

思路:运用二分的思想,先对数组排序,然后用二分找到第一个听不见的位置,然后,加到计数器里面

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=1e6+5;int n,d,a[N];signed main(){cin>>n>>d;for (int i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n);int ans=0;for (int i=1;i<=n;++i){int p=upper_bound(a+i+1,a+1+n,a[i]+d)-a;ans+=p-i-1;}cout<<ans;
}
计算器的改良https://www.luogu.com.cn/problem/P1022

题目背景

NCL 是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手 ZL 先生。

题目描述

为了很好的完成这个任务,ZL 先生首先研究了一些一元一次方程的实例:

  • 4+3�=84+3x=8。

  • 6�−5+1=2−2�6a−5+1=2−2a。

  • −5+12�=0−5+12y=0。

ZL 先生被主管告之,在计算器上键入的一个一元一次方程中,只包含整数、小写字母及 +-= 这三个数学符号(当然,符号“-”既可作减号,也可作负号)。方程中并没有括号,也没有除号,方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做,或者说可认为键入的一元一次方程均为合法的,且有唯一实数解。

输入格式

一个一元一次方程。

输出格式

解方程的结果(精确至小数点后三位)。

输入输出样例

输入 #1复制

6a-5+1=2-2a

输出 #1复制

a=0.750

思路:模拟

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=100;int l;
double x,flag,mid,a[N];
char c,p;signed main(){l=1,flag=1;while (c!='='){c=getchar();if (c=='+'){flag=1;l++;}else if (c=='-'){flag=-1;l++;}if (c>='0' && c<='9'){if (a[l]==0){a[l]+=(c-'0')*flag;}else{a[l]=a[l]*10+(c-'0')*flag;}}if (c>='a' && c<='z'){p=c;if (a[l]==0) x+=flag;else x+=a[l];a[l]=0;l--;}}mid=l,l++,flag=1;while (c!='\n'){c=getchar();if (c=='+'){flag=1;l++;}else if (c=='-'){flag=-1;l++;}if (c>='0' && c<='9'){if (a[l]==0){a[l]+=(c-'0')*flag;}else{a[l]=a[l]*10+(c-'0')*flag;}}if (c>='a' && c<='z'){p=c;if (a[l]==0) x-=flag;else x-=a[l];a[l]=0;l--;}}int sum=0;for (int i=1;i<=l;++i){if (i<=mid){sum-=a[i];}else {sum+=a[i];}}if (!(sum/x)){printf("%c=0.000",p);}else {printf("%c=%.3lf",p,sum/x);}
}
L-shapeshttps://www.luogu.com.cn/problem/CF1722F

题目描述

An L-shape is a figure on gridded paper that looks like the first four pictures below. An L-shape contains exactly three shaded cells (denoted by *), which can be rotated in any way.

You are given a rectangular grid. Determine if it contains L-shapes only, where L-shapes can't touch an edge or corner. More formally:

  • Each shaded cell in the grid is part of exactly one L-shape, and
  • no two L-shapes are adjacent by edge or corner.

For example, the last two grids in the picture above do not satisfy the condition because the two L-shapes touch by corner and edge, respectively.

输入格式

The input consists of multiple test cases. The first line contains an integer �t ( 1≤�≤1001≤t≤100 ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers �n and �m ( 1≤�,�≤501≤n,m≤50 ) — the number of rows and columns in the grid, respectively.

Then �n lines follow, each containing �m characters. Each of these characters is either '.' or '*' — an empty cell or a shaded cell, respectively.

输出格式

For each test case, output "YES" if the grid is made up of L-shape that don't share edges or corners, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

题意翻译

L形在网格纸上形如下面的前四张图片。L形正好包含三个阴影单元(用*表示),可以以任何方式旋转。

现给你一个矩形网格。确定它是否仅包含L形,其中L形不能接触边或角,也就是说网格中的每个阴影单元正好是一个L形的一部分,并且没有两个L形通过边或角相邻。

例如,上图中的最后两个网格不满足条件,因为两个L形分别通过角和边缘接触。

如果网格满足条件,则输出“YES”,否则输出“NO”。

输入输出样例

输入 #1复制

10
6 10
........**
.**......*
..*..*....
.....**...
...*.....*
..**....**
6 10
....*...**
.**......*
..*..*....
.....**...
...*.....*
..**....**
3 3
...
***
...
4 4
.*..
**..
..**
..*.
5 4
.*..
**..
....
..**
..*.
3 2
.*
**
*.
2 3
*..
.**
3 2
..
**
*.
3 3
.**
*.*
**.
3 3
..*
.**
..*

输出 #1复制

YES
NO
NO
NO
YES
NO
NO
YES
NO
NO

思路:把*都成1,其他都是0,找到特殊的四种情况,然后判断,把可以成立的变成0,最后遍历一边数组,如果还有1那就不行

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=55;int t,n,m,a[N][N];void check(int i,int j){if (a[i+1][j] && a[i+1][j+1] && !a[i-1][j-1] && !a[i-1][j] && !a[i-1][j+1] && !a[i][j-1]  && !a[i][j+1] && !a[i][j+2]&& !a[i+1][j-1] && !a[i+1][j+2] && !a[i+2][j-1] && !a[i+2][j]  && !a[i+2][j+1] && !a[i+2][j+2]){a[i][j]=a[i+1][j] = a[i+1][j+1] = 0;return;}if (a[i][j+1] && a[i+1][j+1] && !a[i-1][j-1] && !a[i-1][j] && !a[i-1][j+1] && !a[i-1][j+2] && !a[i][j-1]  && !a[i][j+2]&& !a[i+1][j-1] && !a[i+1][j] && !a[i+1][j+2] && !a[i+2][j]  && !a[i+2][j+1] && !a[i+2][j+2]){a[i][j+1]=a[i+1][j+1] = a[i][j] = 0;return;}if (a[i+1][j] && a[i+1][j-1] && !a[i-1][j-1] && !a[i-1][j] && !a[i-1][j+1] && !a[i][j-2] && !a[i][j-1]  && !a[i][j+1]&& !a[i+1][j-2] && !a[i+1][j+1] && !a[i+2][j-1] && !a[i+2][j]  && !a[i+2][j+1] && !a[i+2][j-2]){a[i+1][j]=a[i+1][j-1] = a[i][j] = 0;return;}if (a[i][j+1] && a[i+1][j] && !a[i-1][j-1] && !a[i-1][j] && !a[i-1][j+1] && !a[i-1][j+2] && !a[i][j-1]  && !a[i][j+2]&& !a[i+1][j-1] && !a[i+1][j+1] && !a[i+1][j+2]&& !a[i+2][j-1] && !a[i+2][j]  && !a[i+2][j+1] ){a[i][j]=a[i+1][j] = a[i][j+1] = 0;return;}
}signed main(){cin>>t;while (t--){cin>>n>>m;memset(a,0,sizeof(a));for (int i=1;i<=n;++i){for (int j=1;j<=m;++j){char c;	cin>>c;if (c=='*') a[i][j]=1;}}for (int i =1 ;i<=n ;++i ){for (int j =1 ; j<=m ;++ j){if (a[i][j] == 1) check(i,j);}}bool flag=true;for (int i =1 ;i<=n ;++i ){for (int j =1 ; j<=m ;++ j){if (a[i][j] == 1){flag=false;break;}}if (!flag) break;}if (!flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;}
}
Alternating Heightshttps://www.luogu.com.cn/problem/P10050

题目描述

Troy 计划给 CCO 的学生拍一张合影,他向你寻求帮助。

有 �K 个学生,编号从 11 到 �K。Troy 忘记了学生的身高,但他记得没有两个学生的身高相同。

Troy 有一个序列 �1,�2,…,��A1​,A2​,…,AN​,表示合影中从左到右的学生顺序。一个学生可能在 �A 中出现多次。你不确定这张合影会怎么拍,但你不愿意认为 Troy 犯了错误。

Troy 会给你 �Q 个形式为 �,�x,y 的询问,每个询问为「给定学生序列 ��,��+1,…,��Ax​,Ax+1​,…,Ay​,他们的身高能否形成一个交替序列?」更具体地说,我们用 ℎ�hi​ 表示第 �i 个学生的身高。如果存在一种身高分配ℎ1,ℎ2,…,ℎ�h1​,h2​,…,hK​,使得 ℎ��>ℎ��+1<ℎ��+2>ℎ��+3<…ℎ��hAx​​>hAx+1​​<hAx+2​​>hAx+3​​<…hAy​​,回答 YES;否则回答 NO

注意,每个查询都是独立的:也就是说,询问 �i 的身高分配与询问 �j 的身高分配无关 (�≠�)(i=j)。

输入格式

第一行包含三个用空格分隔的整数 �,�N,K 和 �Q。

第二行包含 �N 个整数,表示 �1,�2,…,��(1≤��≤�)A1​,A2​,…,AN​(1≤Ai​≤K)。

接下来的 �Q 行,每行包含两个用空格分隔的整数 �x 和 �(1≤�<�≤�)y(1≤x<y≤N),表示一组查询。

输出格式

输出 �Q 行。第 �i 行,输出 YES 或者 NO,表示 Troy 的第 �i 个查询的答案。

输入输出样例

输入 #1复制

6 3 3
1 1 2 3 1 2
1 2
2 5
2 6

输出 #1复制

NO
YES
NO

说明/提示

样例说明

对于第一个询问,不可能有 ℎ1>ℎ1h1​>h1​,所以答案是 NO

对于第二个询问,ℎ1>ℎ2<ℎ3>ℎ1h1​>h2​<h3​>h1​ 的一种方案是 ℎ1=160 cm,ℎ2=140 cm,ℎ3=180 cmh1​=160 cm,h2​=140 cm,h3​=180 cm。另一种方案是 ℎ1=1.55 m,ℎ2=1.473 m,ℎ3=1.81 mh1​=1.55 m,h2​=1.473 m,h3​=1.81 m。

对于第三个询问,不可能同时有 ℎ1>ℎ2h1​>h2​ 和 ℎ1<ℎ2h1​<h2​。

数据范围

对于所有的数据,有 2≤�≤30002≤N≤3000,2≤�≤�2≤K≤N,1≤�≤1061≤Q≤106。

子任务编号

分值

�N

�K

�Q

11

1616

2≤�≤30002≤N≤3000

�=2K=2

1≤�≤1061≤Q≤106

22

2424

2≤�≤5002≤N≤500

2≤�≤min⁡(�,5)2≤K≤min(N,5)

1≤�≤1061≤Q≤106

33

2828

2≤�≤30002≤N≤3000

2≤�≤�2≤K≤N

1≤�≤20001≤Q≤2000

44

3232

2≤�≤30002≤N≤3000

2≤�≤�2≤K≤N

1≤�≤1061≤Q≤106

思路:看成图,如果存在环,那就无法成立,用拓扑排序判断是否成环,暴力搜会超时,用二分的思想,固定左端点,然后找到以此为左端点的最大区间长度

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=3005;int n,k,Q,a[N],in[N],num[N],g[N][N],max_len[N];
queue<int>q;bool check(int l,int r){	//拓扑排序 int sum=0;memset(in,0,sizeof(in));	//记录入度 memset(num,0,sizeof(num));	//记录相邻的节点数 while (!q.empty()) q.pop();for (int i=l+1;i<=r;i+=2){		//指向高的 if (i-1>0){g[a[i]][++num[a[i]]]=a[i-1];in[a[i-1]]++;}if (i+1<=r){g[a[i]][++num[a[i]]]=a[i+1];in[a[i+1]]++;}}for (int i=1;i<=k;++i){	//入度为0就入队 if (!in[i]) q.push(i);}while (!q.empty()){int p=q.front(); q.pop();sum++;for (int i=1;i<=num[p];++i){in[g[p][i]]--;	//出队后,相邻点的入度减1 if (!in[g[p][i]]) q.push(g[p][i]);}}return sum==k;
}int erfen(int m){int l=m,r=n,maxn=0;while (l<=r){int mid=l+r>>1;if (check(m,mid)){	//以m为左端点的最长区间 maxn=max(maxn,mid);l=mid+1;}else r=mid-1;}return maxn;
}signed main(){cin>>n>>k>>Q;for (int i=1;i<=n;++i) cin>>a[i];for (int i=1;i<=n;++i) max_len[i]=erfen(i);for (int i=1;i<=Q;++i){int x,y;cin>>x>>y;if (max_len[x]<y) cout<<"NO"<<endl;else cout<<"YES"<<endl;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/258075.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

枚举,#define,C中程序内存区域划分

目录 一、枚举 1.1枚举类型的声明 1.2枚举类型的优点 1.3枚举类型的使用 二、#define定义常量 三、C中程序内存区域划分 一、枚举 1.1枚举类型的声明 枚举顾名思义就是⼀⼀列举。 把可能的取值⼀⼀列举。 比如我们现实生活中&#xff1a; ⼀周的星期⼀到星期日是有限…

嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第三天-ARM Linux ADC和触摸屏开发 (物联技术666)

链接&#xff1a;https://pan.baidu.com/s/1V0E9IHSoLbpiWJsncmFgdA?pwd1688 提取码&#xff1a;1688 教学内容&#xff1a; 1、ADC S3C2440的A/D转换器包含一个8通道的模拟输入转换器&#xff0c;可以将模拟输入信号转换成10位数字编码。 在A/D转换时钟频率为2.5MHz时&…

【QT+QGIS跨平台编译】之四十:【gsl+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、GSL介绍二、GSL下载三、文件分析四、pro文件五、编译实践一、GSL介绍 GSL(GNU Scientific Library)是一个开源的数值计算库,用于提供一系列常用的数学函数和算法。它为科学计算和数据分析提供了高效、可靠的工具。 GSL库提供了丰富的功能,包括数值积分、数值…

数据分析基础之《pandas(8)—综合案例》

一、需求 1、现在我们有一组从2006年到2016年1000部最流行的电影数据 数据来源&#xff1a;https://www.kaggle.com/damianpanek/sunday-eda/data 2、问题1 想知道这些电影数据中评分的平均分&#xff0c;导演的人数等信息&#xff0c;我们应该怎么获取&#xff1f; 3、问题…

Compose 自定义 - 数据转UI的三阶段(组合、布局、绘制)

一、概念 组合阶段 Compisition 界面首次渲染时会将可组合函数转化为一个个布局节点 Layout Node, 使用多叉树的数据结构构建一个UI树。 布局阶段 Layout 多叉树中父节点会测量他们的子节点&#xff0c;然后在一个二维空间里进行摆放。通过从上往下测量&#xff08;如果存在子…

【C语言】Linux内核accept 系统调用代码

一、Linux 4.19内核accept 系统调用代码中文注释 /** 在使用accept时&#xff0c;我们尝试创建一个新的socket&#xff0c;与客户端建立连接&#xff0c;* 唤醒客户端&#xff0c;然后返回新的连接文件描述符&#xff08;fd&#xff09;。我们在内核空间收集* 连接方的地址&am…

C#利用接口实现选择不同的语种

目录 一、涉及到的知识点 1.接口定义 2.接口具有的特征 3.接口通过类继承来实现 4.有效使用接口进行组件编程 5.Encoding.GetBytes(String)方法 &#xff08;1&#xff09;检查给定字符串中是否包含中文字符 &#xff08;2&#xff09;编码和还原前后 6.Encoding.GetS…

NLP_Transformer架构

文章目录 Transformer架构剖析编码器-解码器架构各种注意力的应用Transformer中的自注意力Transformer中的多头自注意力Transformer中的编码器-解码器注意力Transformer中的注意力掩码和因果注意力 编码器的输入和位置编码编码器的内部结构编码器的输出和编码器-解码器的连接解…

【Web】小白友好的Java内存马基础学习笔记

目录 简介 文件马与内存马的比较 文件马原理 内存马原理 内存马使用场景 内存马分类 内存马注入方式 这篇文章主要是概念性的&#xff0c;具体技术细节不做探究&#xff0c;重点在祛魅。 简介 内存马&#xff08;Memory Shellcode&#xff09;是一种恶意攻击技术&…

抽象的问题1

vue3&#xff0c;在使用v-mode绑定属性时&#xff0c;发生了奇怪的问题&#xff0c;渲染失败了 代码如下 <template><div><form><div>账号<input v-model"form_user_Data.username" type"text"></div><div>密…

HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-软件定时器

目录 一、软件定时器基本概念二、软件定时器运行机制三、软件定时器状态四、软件定时器模式五、软件定时器开发流程六、软件定时器使用说明七、软件定时器接口八、代码分析&#xff08;待续...&#xff09;坚持就有收获 一、软件定时器基本概念 软件定时器&#xff0c;是基于系…

bpmn-js 事件总线处理

bpmn-js中使用EventBus作为事件的处理句柄&#xff0c;EventBus的使用和我们常规使用的事件总线没啥大的区别&#xff0c;其源码位于&#xff1a;/diagram-js/lib/core/EventBus.js &#xff08;bpmn-js使用diagram-js实现流程图的web端绘制呈现工具&#xff09;。 EventBus使用…

Kibana:如何嵌入 Kibana 仪表板

作者&#xff1a;Carly Richmond 像我这样的前端工程师经常提出的要求是将 Kibana 等来源的现有仪表板嵌入到 JavaScript Web 应用程序中。 这是我必须多次执行的任务&#xff0c;因为我们希望快速部署用户生成的视图或允许用户控制给定的视图。 从我们从精彩的开发者社区收到的…

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS&#xff08;广度优先搜索&#xff09;解决 Flood Fill 算法的基本思想是通过从起始点开始&#xff0c;逐层向外扩展&#xff0c;访问所有与起始点相连且具有相同特性&#xf…

【小沐学GIS】基于WebGL绘制三维数字地球Earth(OpenGL)

&#x1f37a;三维数字地球系列相关文章如下&#x1f37a;&#xff1a;1【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;456:OpenGL、glfw、glut&#xff09;第一期2【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;456:OpenGL、glfw、glut&#xff09;第二期3【小沐…

B端系统从0到1:有几步,其中需求分析要做啥?

一款B系统从无到有都经历了啥&#xff0c;而其中的需求分析又要做什么&#xff1f;贝格前端工场给老铁们做一下分析&#xff0c;文章写作不易&#xff0c;如果咱们有界面设计和前端开发需求&#xff0c;别忘了私信我呦&#xff0c;开始了。 一、B端系统从0到1都有哪些要走的步骤…

ZigBee学习——BDB

✨本博客参考了善学坊的教程&#xff0c;并总结了在实现过程中遇到的问题。 善学坊官网 文章目录 一、BDB简介二、BDB Commissioning Modes2.1 Network Steering2.2 Network Formation2.3 Finding and Binding&#xff08;F & B&#xff09;2.4 Touchlink 三、BDB Commissi…

PKI - 借助Nginx 实现Https 服务端单向认证、服务端客户端双向认证

文章目录 Openssl操系统默认的CA证书的公钥位置Nginx Https 自签证书1. 生成自签名证书和私钥2. 配置 Nginx 使用 HTTPS3. 重启 Nginx 服务4. 直接访问5. 不验证证书直接访问6. 使用server.crt作为ca证书验证服务端解决方法1&#xff1a;使用 --resolve 参数进行请求域名解析解…

备战蓝桥杯---搜索(完结篇)

再看一道不完全是搜索的题&#xff1a; 解法1&#xff1a;贪心并查集&#xff1a; 把冲突事件从大到小排&#xff0c;判断是否两个在同一集合&#xff0c;在的话就返回&#xff0c;不在的话就合并。 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace …

LabVIEW荧光显微镜下微管运动仿真系统开发

LabVIEW荧光显微镜下微管运动仿真系统开发 在生物医学研究中&#xff0c;对微管运动的观察和分析至关重要。介绍了一个基于LabVIEW的仿真系统&#xff0c;模拟荧光显微镜下微管的运动过程。该系统提供了一个高效、可靠的工具&#xff0c;用于研究微管与运动蛋白&#xff08;如…