题目1
题目链接
题目大意:
给出n个整数,已知这n个整数是按照下面的规则生成。
1、初始化的时候,数组中有2个整数,每次从数组中选择任意两个整数,计算得到他们差值的绝对值,重新放回数组;
2、重复n-2次操作1,得到n个元素的数组。
现在已知n个整数的数组,想知道最开始的两个元素中,会存在哪个数字?
输入:
第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200)
每个样例2行
第一行,整数𝑛 (1≤𝑛≤100)
第二行,n个整数𝑎1,𝑎2,…𝑎𝑛 (−1e9≤𝑎𝑖≤1e9 )
输出:
每个样例一行,输出初始整数中的一个,题目保证有解;
Examples
input
9
3
9 2 7
3
15 -4 11
4
-9 1 11 -10
5
3 0 0 0 3
7
8 16 8 0 8 16 8
4
0 0 0 0
10
27 1 24 28 2 -1 26 25 28 27
6
600000000 800000000 0 -200000000 1000000000 800000000
3
0 -1000000000 1000000000
output
9
11
-9
3
8
0
-1
600000000
0
题目解析:
由题目的定义可以知道,|A-B|是无法产生负数,那么如果数字中存在负数,则必然负数是初始数字;
同理假设x是数组中的最大元素,并且此时数组中并没有负数,那么x必然也是初始元素,因为|A-B|在全为正数的情况下,无法产生更大的数值。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
if (a[0] < 0) cout << a[0] << endl;
else cout << a[n - 1] << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目2
题目链接
题目大意:
给出n个整数的排列,现在可以选择排列中的2个位置,交换位置上的元素。
要求,交换之后所有子数组形成的排列尽可能的少。
输入:
第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行,整数𝑛 (3≤𝑛≤2e5)
第二行,n个整数𝑎1,𝑎2,…𝑎𝑛
输出:
每个样例一行,输出交换的两个整数的位置;
如果有多个答案,可以输出其中一个;(两个位置可以是相同的)
Examples
input
8
3
1 2 3
3
1 3 2
5
1 3 2 5 4
6
4 5 6 1 2 3
9
8 7 6 3 2 1 4 5 9
10
7 10 5 1 9 8 3 2 6 4
10
8 5 10 9 2 1 3 4 6 7
10
2 3 5 7 10 1 8 6 4 9
output
2 3
1 1
5 2
1 4
9 5
8 8
6 10
5 4
题目解析:
对于排列来说,最终的整数就是1,因为所有的排列都要从1开始;
其次就是整数2,因为排列除了1,第二位是2;
根据题目的要求,如果想要无法组成排列,那么最大数n也很重要,因为一旦1和2被n隔开,那么就无法形成排列(除非整个数组一起参与排列);
那么我们用 x,y,z来表示1,2,n这三个整数的位置。
容易知道,只要我们形成x<z<y或者y<z<x这样的位置顺序,那么所有子数组只有2个排列(1和n);
只考虑x,y,z三个位置,我们知道交换一个位置,必然可以把z交换到中间去。
为了简单实现,我们将x,y,z三个整数排序,然后将z与排序中间的位置交换即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x, y, z;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] == 1) x = i;
if (a[i] == 2) y = i;
if (a[i] == n) z = i;
}
int tmp[] = {x, y, z};
sort(tmp, tmp + 3);
cout << tmp[1] << " " << z << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目3
题目链接
题目大意:
将1、2、3、、、、n x m个整数,填入到n x m的网格中;
要求任何两个相邻的格子,格子上数字差的绝对值不是素数。
现在求其中一个填充结果。
输入:
第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例一行,整数𝑛, m (4≤𝑛, m≤1000)
输出:
每个样例输出n行,每行m个整数;(题目保证有解)
Examples
input
3
4 4
5 7
6 4
output
16 7 1 9
12 8 2 3
13 4 10 11
14 5 6 15
29 23 17 9 5 6 2
33 27 21 15 11 7 1
32 31 25 19 20 16 10
26 30 24 18 14 8 4
35 34 28 22 13 12 3
2 3 7 11
8 9 1 10
17 13 5 4
18 14 6 12
19 23 15 21
20 24 16 22
题目解析:
当n/m偶数时,从左到右,从上到小填写即可。例如n=4:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
...
每个数字和左右相邻都是1,上下相邻是2的倍数。
当n/m是奇数时,比如说k=2时,n=(2k + 1)=5;
如果还是采用原来解决方案,1和6的差距就是n=5,此时两数之差是质数;
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
....
但是知道,1和11的差是2 * n,不是质数;
那么这个整数矩阵可以做一些简化,只考虑每行第一个整数:
1
n + 1
2n + 1
3n + 1
4n + 1
...
做一些调整
1
2n + 1
4n + 1
n + 1
3n + 1
...
这样上下整数的差就变成2n、2n、3n、2n,都是n的倍数,也即是都是合数。(注意,至少n>4才能用着这种方式)
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 1010;
int a[N][N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n % 2 == 0) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = (j - 1) * n + i;
}
else {
for (int i = 1; i <= (n + 1)/2; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = (i - 1) * 2 * m + j;
}
}
for (int i = 1; i <= n/2; ++i) {
for (int j = 1; j <= m; ++j) {
a[i + (n+1)/2][j] = (i - 1) * 2 * m + j + m;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j){
cout << a[i][j] << " ";
}
cout << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目4
题目链接
题目大意:
有n个节点的树,节点序号为1、2、3、、、n,现在小明开始用下面的方式开始绘制整棵树:
1、先绘制节点1;
2、按照边输入的顺序遍历,对于每一条边,如果存在一个节点已经绘制且另外一个节点没绘制,则绘制未存在的节点;
3、遍历完成后,检查是否所有节点已经绘制完成,否则重新操作2;
现在想知道,需要遍历多少次,才能绘制完所有节点;
输入:
第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例第一行整数𝑛 (1≤𝑛≤2⋅1e5)
接下来n-1行,每行有整数𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛 , 𝑢𝑖≠𝑣𝑖 )
输出:
对于每个样例,输出需要遍历的次数;
Examples
input
2
6
4 5
1 3
1 2
3 4
1 6
7
5 6
2 4
2 7
1 3
1 2
4 5
output
2
3
题目解析:
先考虑简单的情况,假设4个节点,假如边顺序是:
1 2
2 3
3 4
那么结果,只要遍历一次即可;
如果边顺序是:
3 4
2 3
1 2
则结果需要3次,因为每次遍历完都只能绘制1个节点;
如果边顺序是:
1 2
3 4
2 3
则结果需要2次,第一次遍历可以产生1、2、3节点,第二次遍历则产生节点4;
观察这个过程,就是从节点1开始遍历,当遇到下一个节点就有两个抉择:
1、下个节点可以直接绘制,因为连接下一个节点的边,比当前节点要更晚;
2、下个节点需要等下一次遍历,因为连接下一个节点的边,比当前节点要更早;
通过上面这个方式,我们只需要遍历一次,就可以快速知道一条链路上,需要遍历多少次才能绘制完成;
当我们知道一条链路的解法之后,对于一个棵树,其实就是不断重复根节点到叶子节点的dfs过程。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
vector<int> g[N];
map<pair<int, int>, int> h;
int dfs(int u, int father) {
int ret = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v != father) {
ret = max(ret, dfs(v, u) + (h[make_pair(u, father)] > h[make_pair(u, v)]));
}
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
h.clear();
for (int i = 1; i <= n; ++i) g[i].clear();
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
h[make_pair(u, v)] = i;
h[make_pair(v, u)] = i;
}
int ans = 0;
for (int i = 0; i < g[1].size(); ++i) {
ans = max(ans, dfs(g[1][i], 1));
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目5
题目链接
题目大意:
有两个长度为n的整数数组a和b;
现在想要找到所有的(i, j)组合,满足 1≤𝑖<𝑗≤𝑛 且 𝑎𝑖⋅𝑎𝑗=𝑏𝑖+𝑏𝑗 .
输入:
第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤𝑛)
第二行整数𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛 )
输出:
对于每个样例,输出存在的组合数量。
Examples
input
3
3
2 3 2
3 3 1
8
4 2 8 2 1 2 7 5
3 5 8 8 1 1 6 5
8
4 4 8 8 8 8 8 8
8 8 8 8 8 8 8 8
output
2
7
1
题目解析:
最直接做法,只需要枚举所有的i和j,计算是否满足要求,但是复杂度O(N^2),明显超过题目要求;
分析题目的要求,组合数量对原有位置没有要求,那么可以对数组进行排序;
但是不管数组a排序还是数组b排序,都无法满足快速求解;
继续分析题目给出的条件,发现a和b的范围比较小,那么bi+bj应该小于2n;
对于组合(i,j),我们假设ai<bi,那么ai作为乘法的较小值可以满足ai <= sqrt(2n)=633,这样ai的枚举范围就缩小很多,这似乎是一个突破口。
那么是不是直接按照数组a的大小排序,然后遍历数组a,直到ai <= sqrt(2n)即可?
这样当数组所有元素ai都<= sqrt(2n)时,复杂度依然超标。
所以枚举的应该是ai所取的值。
对于组合(i, j),有数字a[i]和a[j],以及b[i]和b[j],一共四个未知数;(注意这里我们假设了a[i] < a[j])
我们枚举a[i]的值,先假设ai=x,那么对于数字a[j]和b[j]我们同样去枚举j∈[0, n]的情况,这样我们就知道了3个未知数,根据a[i]*a[j] = b[i] + b[j],我们可以推出 b[i] = y = a[i] * a[j] - b[j] = x * a[j] - b[j];
此时我们只要知道在枚举到j时,前面出现过所有的a[i] = x并且 b[i]的值为y的数字即可;
我们在遍历数组过程,要统计前面出现过的值为y的整数,可以用哈希来解决,用h[value]++的方式来记录,然后统计前面value出现次数就是h[value];
注意:数组要按照a从小到大排序。
因为,我们假设了a[i] < a[j],为了保证这个要求,我们需要对数组排序,并且在枚举到位置j时,另外一个位置i只能考虑[1, j - 1]这个区间。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 202010;
pair<int, int> a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i].first);
}
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i].second);
}
// sort(a, a + n);
int m = sqrt(n * 2) + 1;
lld ans = 0;
for (int i = 1; i <= m; ++i) {
// map<int, int> h;
vector<int> h(n+1);
for (int j = 0; j < n; ++j) {
int y = i * a[j].first - a[j].second; // x = i时, second应该等于y
if (1 <= y && y <= n) {
ans += h[y];
if (h[y]) cout << i << "*" << a[j].first << "=" << y << "+" << a[j].second << endl;
}
if (a[j].first == i) {
h[a[j].second]++;
}
}
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
网友评论