神奇的队伍
题目描述
你知道吗，在重庆市第八中学校中，流传着四大不可思议的传说。接下来，你将看到四大不可思议之一——神奇的队伍。
相传在八中科技楼的五楼和六楼之间的楼梯的第七步台阶的旁边墙壁上，存在一个隐藏的空间，这个空间中存在着一支神奇的队伍，一支由名为ぎさう的怪异组成的队伍。他们性格散漫，整天以捣蛋搞恶作剧为生，这不，他们又准备出发啦！当然，在他们出发捣乱之前，肯定要先一个一个的排好队，所有的ぎさう一共需要排成n列，当带头的ぎさう喊出稍息的之后，由于这些ぎさう散漫惯了，有迈左腿的，也有迈右腿的，很不整齐。已知在第i列中，有li个ぎさう先迈出了左腿，有ri个ぎさう迈出了右腿。假设所有的ぎさう中，有L个ぎさう迈出左腿，R个ぎさう迈出右腿时，整个队伍的整齐度为|L-R|，现在，带头的ぎさう希望能改变一整列的ぎさう的动作，使得这一列的所有ぎさう之前迈出左腿的现在迈右腿，之前迈右腿的现在迈左腿（当然也可以不改变）。现在带头的ぎさう需要计算，他需要改变哪一列，才能使整个队伍的整齐度最大。如果不改变任何一列，则输出0.
输入格式
第一行一个数字n（1≤n≤100000），表示ぎさう所拥有的列数。
接下来n行，每行两个数字l_i和r_i（1≤l_i，r_i≤500），表示这一列的ぎさう迈出左腿的数量和迈出右腿的数量。
输出格式
一个数字，表示需要改变的第几列。如果不需要改变任何一列的动作，则输出0。
样例
样例输入：
1 | 2 |
样例输出：
1
1
1 | 1 |
分析
暴力可解此题
AC代码
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
using namespace std;
const int MAXN = 100005;
int n, l[MAXN], r[MAXN], totl = 0, totr = 0, ans = 0, minn;
int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n; i ++) {
scanf("%d %d", &l[i], &r[i]);
totl += l[i];
totr += r[i];
}
minn = fabs(totl - totr);
int temp;
for(int i = 1 ; i <= n; i ++) {
temp = fabs(totl - l[i] + r[i] - totr + r[i] - l[i]);
if(temp > minn) {
ans = i;
minn = temp;
}
}
printf("%d", ans);
return 0;
}
1 |
|
神奇的数
题目描述
你知道吗，在重庆市第八中学校中，流传着四大不可思议的传说。接下来，你将看到四大不可思议之二——神奇的数。
相传在八中初一的数学课上，每当数学老师们在黑板上板书了一长串的数字时，这个神奇的数字就会冷不丁的冒出来，他会将数学老师们板书的数字全部对这个神奇的数取模，然后大家会惊奇的发现，老师板书的数字全部对神奇的数取模后，得到了同一个数字。
现在告诉你老师书写在黑板上的数字的个数以及所有老师写的数字，请你求出所有的可能的神奇的数的值。
输入格式
第一行一个数字n（1≤n≤100），表示老师书写的数字个数。
接下来n行，每行一个数字a_i（1≤a_i≤10^14），表示老师书写的每一个数字分别的值。
输出格式
若干个数字，表示神奇的数的所有可能的值，中间用一个空格隔开。
样例
样例输入：
1 | 3 |
样例输出：
1
2 4
1 | 2 4 |
分析
第一反应肯定是暴力啦ヽ(￣▽￣)ﾉ 被无情地TLE
咳，暴力不行？那来分析一下题目，所要求的数为为所有元素的 同余模数 因此，我们可以用到一个数学结论：
如果有两个整数a、b ，它们除以m所得的余数相等，则a与b的差能被m整除。也就是说，a-b（a≥b）就是最大的m。
而在此题中，最大的m为最小的abs（a[i]-a[j]）的值（想一想为什么是最小的哦），可以用循环来求。还要考虑一个问题，此题的输入可能会有重复元素，所以在输入时还要进行去重。
m为满足条件的最大同余模数，然后呢，m的因数也有可能是符合题意的，所以还要求出m的所有因数，再进行判断，符合条件就输出
AC代码
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
using namespace std;
const int MAXN = 105;
priority_queue<long long, vector<long long>, greater<long long> > que;
int n, len;//len为数组去重后的元素个数
long long a[MAXN], minn;
int main() {
long long temp;
scanf("%d", &n);
len = 0;
for(int i = 1; i <= n; i ++) {
scanf("%lld", &temp);
bool flag = 1;
for(int k = 1; k <= len; k ++) {
if(a[k] == temp) {//如果temp出现过，flag设为0，跳出循环
flag = 0;
break;
}
}
if(flag) {//没有出现过，则加入集合
a[++ len] = temp;
}
}
if(len == 1) {//当长度为1时，直接输出其元素的所有非1因数
for(long long i = 2; i <= a[1]; i ++) {
printf("%lld ", i);
}
return 0;
}
sort(a + 1, a + 1 + len);//因为要求最小的fabs(a[i] - a[i - 1])，所以对其进行排序
minn = 1e14 + 5;/最大的m
for(int i = 2; i <= len; i ++) {
if(fabs(a[i] - a[i - 1]) < minn) minn = fabs(a[i] - a[i - 1]);
}
if(minn > 1) que.push(minn);//如果minn非1，则入队
for(int i = 2; i * i <= minn; i ++) {//循环m的因数
if(minn % i == 0) {
que.push(i);//符合条件即入队
if(minn / i != i) {//非平方数，则将minn / i也入队
que.push(minn / i);
}
}
}
while(!que.empty()) {
temp = que.top();
que.pop();
bool flag = 1;
long long last = a[1] % temp;
for(int i = 2; i <= len; i ++) {
if(a[i] % temp != last) {//如果a[i] % temp != a[i - 1] % temp，falg设为0，跳出循环
flag = 0;
break;
}
}
if(flag) {
printf("%lld ", temp);
}
}
return 0;
}
1 |
|
神奇的通道
题目描述
你知道吗，在重庆市第八中学校中，流传着四大不可思议的传说。接下来，你将看到四大不可思议之三——神奇的通道。
相传在八中科技楼的六楼和七楼之间，存在一条秘密通道，在这条通道内，挂满了各种各样神奇的画。而这条通道，是由n条长度不一的小通道构成。以你进入这条通道的起点为0点，如果可以从占用区间(a,b)的小通道移动到占用区间(c,d)的小通道去，那么，当且仅当c<a<d或c<b<d时成立。
接下来，你的程序会处理一下两种类型的查询：
1、“1 x y”，表示添加一条新的小通道(x,y)到整个通道中。新的通道的长度总是大于前面已有的所有小通道。
2、“2 a b”，请你回答，在当前已有的小通道中，第a条小通道能否到达第b条小通道。
注意：所有添加的小通道的范围均为开区间，且最初始秘密通道内没有小通道存在。