书海扬帆的博客

学了半天,吭哧吭哧的,终于学到图论啦。。。

本篇文章仅供个人复习,因此以自己理解为首要目标,新人不懂勿喷,感谢。</blockquote>

一、引言


图论是组合数学中的一个分支,是组合数学中一颗璀璨的明珠。无论是在数学研究和计算机科学中都有着广泛的应用。图这个东西,说简单不简单,说难也确实不难。虽然有些知识可能有些晦涩,但只要理解透彻,搞清算法的详细意义,就能茅塞顿开。

二、图的基本概念


一般的算法书以及老师都会介绍。如果实在不懂,买本书,或者学会善用搜索引擎。

基本概念:无向图、有向图、完全图、连通图、稠密图、稀疏图、边权、权值、连通分量等

三、图的存储


对于图论知识的理解,一定是一个从具体到抽象的过程。如果真的理解不了,就把图画出来吧。

比如我们考察下面这个无向图(用什么软件画好呢?想了半天决定用OneNote):

图有邻接矩阵和邻接表两种存储方法。
邻接矩阵就是考察每两点连线,然后运用二维数组存储这个连线的边权。比如上图中1号点到2号点连线的边权是10,则我们的二维数组a[1][2]=10. 以此类推。

邻接表的特点则是省空间,用链表存储节点之间的关系。

四、Prim算法求解最小生成树


核心:建立在邻接表的基础之上,然后……其实就是暴力啦

朴素实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define INT_MAX 1000000000 //开1<<30也可
int n,m,cnt,dis[100100],ans;
struct node{
int d;
int v;
node *next;
//链表
}pool[400000],*e[100010]; //内存池
void addedge(int u,int v,int d){
node *p=&pool[++cnt],*q=&pool[++cnt]; //p: dis(u,v) q:dis(v,u)
p->v=v,p->d=d,p->next=e[u],e[u]=p; //第一个d是结构体中的d,第二个是形参
q->v=u,q->d=d,q->next=e[v],e[v]=q;
}

int main(){
scanf("%d%d",&n,&m);
int u,v,d;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
addedge(u,v,d);
}
dis[1]=0;
for(int i=2;i<=n;i++) dis[i]=INT_MAX;
int k=1,min_d,min_p; //md表示最小距离 mp表示最小的点的编号
for(int i=1;i<n;i++){
for(node *p=e[k];p;p=p->next) //找链 p;表示p!=NULL
if(dis[p->v] > p->d) dis[p->v]=p->d;
//找最小值
min_d=INT_MAX;
for(int j=1;j<=n;j++)
if(dis[j] && dis[j]<min_d)
min_d=dis[j],min_p=j;
ans+=dis[min_p];
dis[k=min_p]=0;
}
printf("%d\n",ans);
return 0;
}

优化:

在找最小值的时候,能不能再降一些复杂度呢?由此我们想到了堆结构(跟线段树非常非常相似)。下面是优化后的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
typedef long long ll;
ll n,m,cnt,dis[500500],ans,flag[500500]; //flag[i]=1表示已经找过了 =0表示尚未找过
struct node{
ll d;
ll v;
node *next;
//链表
}pool[500500],*e[500500]; //内存池
void addedge(ll u,ll v,ll d){
node *p=&pool[++cnt],*q=&pool[++cnt]; //p: dis(u,v) q:dis(v,u)
p->v=v,p->d=d,p->next=e[u],e[u]=p; //第一个d是结构体中的d,第二个是形参
q->v=u,q->d=d,q->next=e[v],e[v]=q;
}
struct heap{
ll d,p;
}h[500500];
ll L=1;
void change(ll i,ll d){ //第i个点的值修改为d
h[i+L-1].d=d;
for(ll j=(i+L-1)/2;j;j/=2)
if(h[2*j].d<h[2*j+1].d) h[j]=h[2*j];
else h[j]=h[2*j+1];
}
int main(){
scanf("%d%d",&n,&m);
ll u,v,d;
for(ll i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
addedge(u,v,d);
}
dis[1]=0;
for(ll i=2;i<=n;i++) dis[i]=ll_MAX;
//建立堆结构
while(L<n) L*=2;
for(ll i=L;i<=L+n-1;i++) h[i].d=dis[i-L+1],h[i].p=i-L+1;
for(ll i=L+n;i<2*L;i++) h[i].d=ll_MAX;
for(ll i=L-1;i>0;i--){
if(h[2*i].d<h[2*i+1].d) h[i]=h[2*i];
else h[i]=h[2*i+1];
//结构体中的每一个元素都赋值
}
//printf("%d %d\n",h[1].p,h[1].d);
ll k;
for(ll i=1;i<=n;i++){
k=h[1].p; //k=最小值的编号
ans+=dis[k];
flag[k]=1;
//下面改结构体
change(k,ll_MAX);
for(node *p=e[k];p;p=p->next)
if(flag[p->v]==0 && dis[p->v]>p->d){
dis[p->v]=p->d;
change(p->v,p->d);
}
}
printf("%d\n",ans);
return 0;
}

五、Kruskal算法求解最小生成树


核心:在邻接表的基础之上,跑并查集。

下面看一下代码实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,p[100100],ans;
struct node{
int u,v,d;
}e[300100];
int find(int i){
if(p[i]==0) return i;
else return p[i]=find(p[i]);
}
void Union(int i,int j){
p[i]=j;
}
bool cmp(node x,node y){
return x.d<y.d;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].v,&e[i].u,&e[i].d);
for(int i=1;i<=m;i++)
if(find(e[i].u)!=find(e[i].v)){
ans+=e[i].d;
Union(find(e[i].u) , find(e[i].v));
}
printf("%d\n",ans);
return 0;
}

六、结语


由于最小生成树是一类题目,因此AC掉模板题至关重要。

Luogu的数据好像很水的样子,暴力都可以轻松过掉。

不过LOJ好像就不行了,Luogu AC代码交上去只得10分。

Luogu题目地址(点我点我)

LOJ题目地址(点我点我)

总之就是学习完新知识后要及时复习总结,上课讲的理论下课后一定要手动实现,重要的部分尤其是解题思路、算法复杂度和证明方法一定要记下来。这样可以避免出现遗忘现象。

“同学,这个学过吗?”
“学过啊!”

“来写一个我看看。”

“我……我不会啊!怎么写来着。。。”

要上考场了还像上面这样,就彻底凉了。

本题运用图论中的差分约束算法即可解决。差分约束需要连一些表示变量间大小关系的边,然后运用SPFA算法求解。

我们把顶点0作为“超级源点”,在主函数的开始首先执行下面一段代码。

1
for(int i=1;i<=n;i++) addEdge(n+1,i,0);

之后学网络流等知识还会遇到“超级汇点”。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100100,maxm=500500;
struct Node
{
int v,c;
Node *next;
}*h[maxn],pool[maxm];
int tot=0;
int num[maxn];
int q[maxn],head=1,tail=1,vis[maxn],dis[maxm];
void addEdge(int u, int v, int c)
{
Node *p=&pool[++tot];
p->v=v; p->c=c; p->next=h[u]; h[u]=p;
}
int n,m,k,root;
int spfa()
{
root=n+1;
q[tail]=root;
tail++;
vis[root]=1;
for(int i=0;i<=n+1;i++) dis[i]=0x3f;
dis[root]=0;
while(head<tail)
{
if(tail>maxn) return 0;
k=q[head];
for(Node *p=h[k];p;p=p->next)
{
if(dis[p->v]>dis[k]+p->c)
{
dis[p->v]=dis[k]+p->c;
if(vis[p->v]==0)
{
q[tail]=p->v;
tail++;
vis[p->v]=1;
}
}
}
vis[q[head]]=0;
head++;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) addEdge(n+1,i,0);
for(int i=1;i<=m;i++){
int u,v,c,res;
scanf("%d",&res);
if(res==1){
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
}
else if(res==2){
scanf("%d%d%d",&u,&v,&c);
addEdge(v,u,-c);
}
else if(res==3){
scanf("%d%d",&u,&v);
addEdge(u,v,0);
}
}
if(spfa()==1) printf("Yes");
else printf("No");
return 0;
}

题面


德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号为1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。

给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入格式:


第一行: 4个由空格隔开的整数: T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出格式:


一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

题目分析


求单源最短路径的题目。俗话说得好,“图论一堆套模板”。以前觉得这只是调侃,现在渐渐接触到图论的内容了,感觉此话真的很有理。

求最短路有三种方法:Dijkstra,Floyd和SPFA,这里由于Bellman-Ford算法并不优于SPFA,就不算在里面了。考虑Floyd肯定会超时,Dijkstra又不能解决负权边的问题(尽管根据实际意义,没有那条道路会倒贴给过路人钱财的),果断SPFA。

代码分享


SPFA其实就是队列优化的Bellman-Ford算法。这里使用链式前向星来表示图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=6210,maxm=400010;
struct Node
{
int v,c;
Node *next;
}*h[maxn],pool[maxm];
int tot=0;
int num[maxn];
int q[maxn],head,tail,vis[maxn],dis[maxm];
void addEdge(int u, int v, int c)
{
Node *p=&pool[++tot];
p->v=v; p->c=c; p->next=h[u]; h[u]=p;
}
int n,m,s;
inline bool spfa()
{
for(int i=1;i<=n;i++) dis[i]=2147483647;
vis[s]=1;
q[tail++]=s;
dis[s]=0;
while(head<tail)
{
int u=q[head++];
vis[u]=0;
for(Node *p=h[u];p;p=p->next)
{
if(dis[p->v]>dis[u]+p->c)
{
dis[p->v]=dis[u]+p->c;
if(vis[p->v]==0)
{
q[tail++]=p->v;
vis[p->v]=1;
num[p->v]++;
if(num[p->v]>n) return false;//存在负权回路
}
}
}
}
return true;//不存在负权回路
}
int Te;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&Te);
for(int i=1;i<=m;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
addEdge(v,u,c);
}
spfa();
printf("%d\n",dis[Te]);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
const int maxm=205*204/2, maxn=210;
int n,m,cur,time[maxn],dis[maxn][maxn];
//Floyd
int main(){
memset(dis,0x3f,sizeof(dis));
memset(time,0x3f,sizeof(time));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&time[i]);
dis[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
dis[u][v]=dis[v][u]=c;
}
int Q;
scanf("%d",&Q);
//跑Floyd
while(Q--)
{
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
while(time[cur]<=t)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dis[i][j]=min(dis[i][j],dis[i][cur]+dis[cur][j]);
cur++;
}
if(dis[x][y]==0x3f3f3f3f || time[x]>t || time[y]>t) printf("-1\n");
else printf("%d\n",dis[x][y]);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

const int maxn=10010;
int a[maxn],l[maxn],t[maxn],n;
inline int turn(int x,int y) {
//变换得到的距离
return min(abs(x-y),n-abs(x-y));
}
vector<int> G[maxn];
bool vis[maxn];
inline bool find(int x) {
int v;
for(int i=0;i<G[i].size();i++) {
if(!vis[G[x][i]]) {
vis[G[x][i]]=1;
if(l[G[x][i]]==0||find(l[G[x][i]])) {
l[G[x][i]]=x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d",&n);
//加边
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
int u=i+a[i],v=n+i-a[i];
u%=n;
v%=n;
if(turn(u,i)!=a[i]) u=-3625;
if(turn(v,i)!=a[i]) v=-3625;
if(u>v) swap(u,v);
if(u!=-3625) G[i].push_back(u);
if(v!=-3625) G[i].push_back(v);
}
for(int i=n-1;i>=0;i--) {
memset(vis,0,sizeof(vis));
if(!find(i)) {
printf("No Answer");
return 0;
}
}
for(int i=0;i<n;i++) t[l[i]]=i;
for(int i=0;i<n;i++) printf("%d ",t[i]);
return 0;
}

摘要

图论的题目真是有趣QwQ
本篇文章将介绍欧拉路径、欧拉回路、哈密顿路径和哈密顿圈等知识的定义、性质、判定及简单应用。

欧拉路径

在生活中,一些图形是可以一笔画出的。同样地,在图G中,若一条路径恰好经过每条边一次,则称这条路径为图G的一条欧拉路径.

图G存在欧拉路径的充要条件

  • 图G是连通图
  • 若图G是无向图,则G中不存在度数为奇数的顶点
  • 若图G是有向图,则每个顶点的入度与出度相等

    欧拉回路


    大家都知道著名的哥尼斯堡七桥问题吧?在德国哥尼斯堡有四个岛,每两个岛之间会架一些桥,一共架起了七座桥。为了节省时间,游人希望环绕全城,使得每座桥都被走过并且只被走过一次。

在图G中,若一条路径的起点和终点相同,且这条路径恰好经过每条边一次,则称这条路径为图G的一条欧拉回路.

图G存在欧拉回路的充要条件

  • 图G是连通图
  • 若图G是无向图,则G中度数为奇数的顶点只能有0个或2个
  • 若图G是有向图,则G中存在两个入度与出度不相等的顶点:其中一个出度比入度大1,为路径的起点;另一个入度比出度大1,为路径的终点。

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=100010,maxm=500050,inf=2147483647;
int n,m,s,edgecnt;
struct node {
int v,c;
node *next;
}*h[maxn],pool[maxm];
void addEdge(int u,int v,int c) {
node *p=&pool[++edgecnt];
p->v=v;p->c=c;p->next=h[u];h[u]=p;
}
struct dij {
int id,dis;
bool operator<(const dij t) const {
return dis>t.dis;
}
};
priority_queue<dij> q;
int dis[maxn];
bool vis[maxn];
void dijkstra(int s) {
for(int i=1;i<=n;i++) dis[i]=inf;
memset(vis,0,sizeof(vis));
dij t;
t.id=s;t.dis=0;dis[s]=0;
q.push(t);
while(!q.empty()) {
t=q.top();q.pop();
if(vis[t.id]) continue;
vis[t.id]=true;
int u=t.id;
for(node *p=h[u];p;p=p->next) {
int v=p->v;
if(!vis[v] && dis[v]>dis[u]+p->c) {
dis[v]=dis[u]+p->c;
t.id=v;t.dis=dis[v];
q.push(t);
}
}
}
}
int main() {
int u,v,c;
cin >> n >> m >> s;
for(int i = 1; i<=m; i++)
{
cin >> u >> v >> c;
addEdge(u,v,c);
}
dijkstra(s);
for(int i = 1; i<=n; i++)
cout << dis[i] << " ";
cout << endl;
return 0;
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=100010,maxm=5000050,inf=2147483647;
int edgecnt;
struct node {
int v,c;
node *next;
}*h[maxn],pool[maxm];
void addEdge(int u,int v,int c) {
node *p=&pool[++edgecnt];
p->v=v;p->c=c;p->next=h[u];h[u]=p;
}
int n,m,s,tim[maxn],dis[maxn];
struct queue {
int q[maxn],head,tail;
queue() {
head=1;tail=0;
}
void push(int x) {
q[++tail]=x;
}
void pop() {
head++;
}
int front() {
return q[head];
}
bool empty() {
return head>tail;
}
int size() {
return tail-head+1;
}
}Q;
bool vis[maxn];
bool spfa(int s) {
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=inf;
Q.push(s);vis[s]=1;dis[s]=0;
int u,v;
while(!Q.empty()) {
u=Q.front();Q.pop();vis[u]=false;
for(node *p=h[u];p;p=p->next) {
v=p->v;
if(dis[v]>dis[u]+p->c) {
dis[v]=dis[u]+p->c;
if(!vis[v]) {
vis[v]=true;
tim[v]++;
Q.push(v);
if(tim[v]>n) return false;
}
}
}
}
return true;
}
int main() {
int u,v,c;
cin >> n >> m >> s;
for(int i = 1; i<=m; i++)
{
cin >> u >> v >> c;
addEdge(u,v,c);
}
spfa(s);
for(int i = 1; i<=n; i++)
cout << dis[i] << " ";
cout << endl;
return 0;
}

Floyd

Kruscal

Prim

Boruvka

Tarjan-SCC

Tarjan-BCC

缩点的类模板题。Tarjan处理完后找一下入度为0的点,统计一下即得答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn=100010,maxm=500050;
int edgecnt;
struct node {
int v;
node *next;
}*h[maxn],pool[maxm];
void addEdge(int u,int v) {
node *p=&pool[++edgecnt];
p->v=v;p->next=h[u];h[u]=p;
}
int idx,scc,dfn[maxn],low[maxn],bel[maxn],sta[maxn],top;
bool ins[maxn];
void tarjan(int u) {
dfn[u]=low[u]=++idx;sta[++top]=u;ins[u]=1;
for(node *p=h[u];p;p=p->next) {
int v=p->v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(ins[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]) {
++scc;
do {
bel[sta[--top]]=scc;
ins[sta[top]]=false;
}while(sta[top]!=u);
}
}
int n,m,ans;
int ind[maxn];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
if(a!=b) addEdge(a,b);
}
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++) {
for(node *p=h[i];p;p=p->next) {
int v=p->v;
if(bel[i]!=bel[v]) ind[bel[v]]++;
}
}
for(int i=1;i<=scc;i++) if(ind[i]==0) ans++;
printf("%d\n",ans);
return 0;
}

MO/OI双国家集训队大佬dmy出的模拟赛,文字中透露出神犇的霸气。%%%

K大和(kth.*)

题目描述

给出两个长为n的数组A,B
请你求出所有Ai+Bj (1<=i,j<=n)中第k大的值
注意:同一和出现多次时,算作多个。

格式

第一行两个正整数n,k
第二行n个数,表示 a1~an
第三行n个数,表示 b1~bn
输出一行整数,表示答案

范围与约定

对于百分之40的数据,n<=3000
对于百分之60的数据,n<=5000
对于百分之80的数据,n<=100000
对于百分之100的数据,n<=500000
$1<=K<=min(500000,n^2)$
$1<=Ai,bi<=100000000$

解题思路

由题意,同一个和出现多次时,算作多个。因此我们将A,B两数组从小到大排序。由于排序过后的数列满足单调性,所以考虑二分答案,时间复杂度$O(n \log^2 n)$.
std用的是优先队列实现,大同小异。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=500050;
int a[maxn],b[maxn];
ll n,k,ans;
inline ll check(register int x) {
ll ret=0;
for(register ll i=1;i<=n;i++) {
register ll res=upper_bound(a+1,a+n+1,x-b[i])-a-1;
ret+=res;
}
return ret;
}
int main() {
//freopen("kth.in","r",stdin);
//freopen("kth.out","w",stdout);
scanf("%lld%lld",&n,&k);
for(register ll i=1;i<=n;i++) scanf("%d",&a[i]);
for(register ll i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
register int l=a[1]+b[1],r=a[n]+b[n];
register int mid;
while(l<=r) {
mid=(l+r)/2;
if(check(mid)>=k) {
r=mid-1;ans=mid;
}
else {
l=mid+1;ans=mid+1;
}
}
printf("%lld\n",ans);
return 0;
}

波动计数(wave.*)

题目描述

给定1~n到1~n的一一映射f。
定义一个有序数对(a1,a2,a3,…,ak)为一组长度为k的波动,当且仅当满足以下四点:

  1. k>=2 1<=ai<=n
  2. ai<a(i+1) 对1<=i<=k-1成立
  3. f(ai)<f(a(i+1)) 对于<=k-1的偶数i成立
  4. f(ai)>f(a(i+1)) 对于<=k-1的奇数i成立

对于所有的波动,你要求出它们的长度之和。
答案对998244353取模。

格式

第一行一个正整数n
第二行n个整数,表示f(1)~f(n)
输出一行一个整数,表示答案。

范围与约定

对于百分之40的数据,n<=15
对于百分之70的数据,n<=5000
对于百分之100的数据,n<=300000
数据保证f(1)到f(n)是1~n的排列。

解题思路

棋盘染色(color.*)

题目描述

给定n行m列的白色棋盘。
对于任意两行两列交出的四个方格,如果有三个是黑格,则可以将第四个格子免费染黑。
同时,每个格子有一个权值c。任意时刻,可以花费c的代价将这一格子染黑。
求染黑棋盘的最小代价。
由于格子数很多,我们采取这样一种方法生成权值:
$A0 = a,$
$A(i+1) = (Ai Ai b + Ai c + d) \mod p. $
其中$A(m
(i-1)+j)$为第i行j列格子的权值。

格式

输入7个正整数n,m,a,b,c,d,p
输出一行表示答案。

范围与约定

对于百分之30的数据,n,m<=5
对于百分之50的数据,n,m<=50
对于百分之80的数据,n,m<=1000
对于百分之百的数据,a,b,c,d<p<=100000 n,m<=5000

解题思路

最小生成树。



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k