问题描述

有一个 SNS 被 NN 个用户使用，他们的编号从 11 到 NN。

在这个 SNS 中，两个用户可以成为朋友。

友谊是双向的；如果用户 X 是用户 Y 的朋友，那么用户 Y 也一定是用户 X 的朋友。

目前，在 SNS 上有 MM 对朋友关系，第 ii 对由用户 AiAi 和用户 BiBi 组成。

确定可以执行以下操作的最大次数：

• 操作：选择三个用户 X、Y 和 Z，使得 X 和 Y 是朋友，Y 和 Z 是朋友，但 X 和 Z 不是朋友。让 X 和 Z 成为朋友。

约束条件

• 2≤N≤2×1052≤N≤2×105

• 0≤M≤2×1050≤M≤2×105

• 1≤Ai<Bi≤N1≤Ai<Bi≤N

• 这些对  是不同的。

  (Ai,Bi)(Ai,Bi)

• 所有输入值都是整数。

输入

输入以以下格式从标准输入给出：

NNMMA1A1B1B1⋮⋮AMAMBMBM

输出

输出答案。

示例 1

Inputcopy	Outputcopy
`4 3
1 2
2 3
1 4`	3

可以发生三次新的朋友关系，方法如下：

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  11

  22

  33

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  33

  11

  44

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  22

  11

  44

不会有四次或更多的新朋友关系。

示例 2

Inputcopy	Outputcopy
3 0	0

如果没有初始的朋友关系，就不会发生新的朋友关系。

示例 3

Inputcopy	Outputcopy
`10 8
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10`	12

错误代码：不知道错哪了求大佬教一教QWQ

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2e5 + 5;
int NEXT[M];
int vis[M], bj[M];
int n, m, u, v;
int ans = 0;
int val[1000];
int find(int x) {if (x != NEXT[x])return NEXT[x] = find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {if (find(x) != find(y))NEXT[find(y)] = find(x);
}
int sy(int a[], int x,int n) {for (int i = 0; i < n; i++) {if (a[i] == x)return 1;}return 0;
}
int main() {cin >> n >> m;for (int i = 0; i <= n; i++)NEXT[i] = i;for (int i = 1; i <= m; i++) {cin >>u >> v;Union(u, v);}for (int i = 1; i <= n; i++)vis[i] = find(i);int k = 1;for (int i = 1; i <= n; i++) {if (!sy(bj, vis[i], k)) {val[k - 1] = i - 1;bj[k++] = vis[i];}}val[k-1] = n;for (int i = 0; i < k - 1; i++) {int c = val[i + 1] - val[i];ans += c * (c - 1) / 2;}cout << ans - m;return 0;
}

昨天这个错题的错误点

1.数据类型错误，题中的数据量很大可能会超过int

2.sy函数这种遍历方式效率太低

下面是改进后的代码：

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int M = 2e5 + 5;
int NEXT[M];
ll vis[M], bj[M];
ll n, m, u, v;
ll ans = 0;
ll val[M];
int find(int x) {if (x != NEXT[x])return NEXT[x] = find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {if (find(x) != find(y))NEXT[find(y)] = find(x);
}
int main() {cin >> n >> m;for (int i = 0; i <= n; i++)NEXT[i] = i;for (int i = 1; i <= m; i++) {cin >>u >> v;Union(u, v);}for (int i = 1; i <= n; i++) {int root = find(i);vis[root]++;}for (int i = 0; i <= n; i++) {ans += vis[i] * (vis[i] - 1) / 2;}cout << ans - m << endl;return 0;
}

数据类型只要进行更改就行了，主要还是计算每个连通块（就是由几个成员构成的整体，就比如7个人可以分成3个人和4个人的小团体，而这两个小团体之间没有联系）的成员个数的优化。昨天使用的vis数组存储根结点的，在找出根结点不同的位置（也就小团体断掉的位置），再通过这个位置之差来求出每个小团体的关系的最大数量。改进后直接通过循环，如果根结点相同，数组上对应下标的数值就自增1，这样就可以直接反应出每个连通块的人数

Background

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

Description

给出项数为 nn 的整数数列 a1…na1…n。

定义函数 f(i)f(i) 代表数列中第 ii 个元素之后第一个大于 aiai 的元素的下标，即 f(i)=min⁡i<j≤n,aj>ai{j}f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0f(i)=0。

试求出 f(1…n)f(1…n)。

Input

第一行一个正整数 nn。

第二行 nn 个正整数 a1…na1…n。

Output

一行 nn 个整数表示 f(1),f(2),…,f(n)f(1),f(2),…,f(n) 的值。

Sample 1

Inputcopy	Outputcopy
`5
1 4 2 3 5`	2 5 4 5 0

Hint

【数据规模与约定】

对于 30%30% 的数据，n≤100n≤100；

对于 60%60% 的数据，n≤5×103n≤5×103 ；

对于 100%100% 的数据，1≤n≤3×1061≤n≤3×106，1≤ai≤1091≤ai≤109。

**思路：**用数组模拟模拟单调栈，因为题目要求的是找到这个数右边第一比他大的数，所以只要让右边的数先进栈那么右边的数就都访问过了，如果当前元素比他右边的第一个元素（也就是当前栈顶元素）大的话就让他出栈，直到出现比他大的数为止，否则就是0，因此我们要倒序访问数组

源代码：

#include<iostream>
using namespace std;
const int N = 3e6 + 5;
int n, k;
int a[N], f[N], stack[N];
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = n; i >= 1; i--) {while (stack[1] != 0 && a[stack[k]] <= a[i])stack[k--] = 0;if (stack[1] == 0)f[i] = 0;elsef[i] = stack[k];stack[++k] = i;}for (int i = 1; i <= n; i++)cout << f[i] << " ";return 0;
}

描述(由于AI翻译大部分i翻译成了我)

Farmer John's N （1 <= N <= 100,000） 奶牛，方便地编号为 1...N，再次站成一排。奶牛 i 的身高为 H_i （1 <= H_i <= 1,000,000）。

每头奶牛都向左看向索引数较高的奶牛。如果我们< j 和 H_i < H_j，我们就说奶牛 i '仰望' 奶牛 j。对于每头奶牛 i，FJ 想知道奶牛 i 所仰望的排队第一头奶牛的索引。

注意：大约 50% 的测试数据将具有 N <= 1,000。

约翰的 N(1≤N≤105)N（1≤N≤105) 头奶牛站成一排，奶牛 我我 的身高是 H我(1≤H我≤106)H我(1≤H我≤106)。 现在，每只奶牛都在向右看齐。 对于奶牛 我我，如果奶牛 jj 满足 i<j我<j 且 H我<HjH我<Hj，我们可以说奶牛 我我 可以仰望奶牛 jj。 求出每只奶牛离她最近的仰望对象。

输入

输入

1. 第 1 行：单个整数：N

• 第 2 行...N+1：第 i+1 行包含单个整数：H_i

第 11 行输入 NN，之后每行输入一个身高 H我H我。

输出

• 1 号线...N：第 i 行包含一个整数，表示一头奶牛到 i 所查找的奶牛的最小索引。如果不存在这样的 cow，则打印 0。

共 NN 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 00。

示例 1

输入复制	输出复制
`6
3
2
6
1
1
2`	`3
3
0
6
6
0`

提示

FJ 有六头奶牛，身高分别为 3、2、6、1、1 和 2。

奶牛 1 和 2 都仰望奶牛 3;奶牛 4 和 5 都仰望奶牛 6;奶牛 3 和 6 不仰望任何奶牛。

【输入说明】66 头奶牛的身高分别为 3,2,6,1,1,2。

【输出说明】奶牛 #1,#2 仰望奶牛 #3，奶牛 #4,#5 仰望奶牛 #6，奶牛 #3 和 #6 没有仰望对象。

【数据规模】

对于 20%20% 的数据：1≤N≤101≤N≤10；

对于 50%50% 的数据：1≤N≤1031≤N≤103；

对于 100%100% 的数据：1≤N≤105,1≤H我≤1061≤N≤105，1≤H我≤106。

和上面一题写法一模一样

源代码：

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int n, k;
int h[N], f[N], stack[N];
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> h[i];for (int i = n; i >= 1; i--) {while (stack[1] != 0 && h[stack[k]] <= h[i])stack[k--] = 0;if (!stack[1])f[i] = 0;elsef[i] = stack[k];stack[++k] = i;}for (int i = 1; i <= n; i++)cout << f[i] << endl;return 0;
}