Description

Bobo has $n$tuples$(a_1, b_1, c_1), (a_2, b_2, c_2), \dots, (a_n, b_n, c_n)$ .
He would like to find the lexicographically smallest permutation $p_1, p_2, \dots, p_n$of$1, 2, \dots, n$ such that for$i \in \{2, 3, \dots, n\}$ it holds that

$\frac{a_{p_{i - 1}} + b_{p_{i - 1}}}{a_{p_{i - 1}} + b_{p_{i - 1}} + c_{p_{i - 1}}} \leq \frac{a_{p_i} + b_{p_i}}{a_{p_i} + b_{p_i} + c_{p_i}}$

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer $n$.

The $i$-th of the following $n$lines contains $3$integers $a_i$,$b_i$ and$c_i$.

Output

For each test case, print $n$integers$p_1, p_2, \dots, p_n$ seperated by spaces.
DO NOT print trailing spaces.

Constraint

• $1 \leq n \leq 10^3$
• $1 \leq a_i, b_i, c_i \leq 2 \times 10^9$
• The sum of $n$does not exceed$10^4$.

Sample Input

1
2
3
4
5
6
7
8
9
10

2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

Sample Output

1
2
3

2 1
1 2
1 2 3

题解

题目大意

给你 $n$个三元组，要求给出这 $n$个三元组的一个排列，使得对$i \in \left \{ 2, 3, \cdots, n \right \}$ 都满足题给关系。

分析

题给关系中的不等式只涉及 $p_{i - 1}$和$p_{i}$ 两个元素，实际上相当于对三元组重载了小于号。因此，本题实际上是对读入的三元组序列进行排序。因此，我们用一个Node结构体存储三元组的三个变元和读入时在原序列中的位置即可。

1
2
3
4

struct Node {
    long long a, b, c;
    int id;
}

同时，在比较三元组关系时，因为本题数据卡精度较严，因此不能用double，而应交叉相乘再比较，同时在这过程中约去一些相同的项（避免爆long long）。

$(a_{p_{i-1}}+b_{p_{i-1}})(a_{p_{i}}+b_{p_{i}}+c_{p_{i}}) \leq (a_{p_{i}} + b_{p_{i}})(a_{p_{i-1}}+b_{p_{i-1}}+c_{p_{i-1}}))$

$(a_{p_{i-1}} + b_{p_{i-1}})c_{p_{i}} \leq (a_{p_{i}} + b_{p_{i}})c_{p_{i-1}}$

代码

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
typedef long long ll;

struct Node {
    ll a, b, c;
    int id;

    bool operator < (const Node& x) const {
        ll q1 = c * (x.a + x.b);
        ll q2 = x.c * (a + b);

        if(q2 == q1) return id < x.id;
        else return q2 < q1;
    }
} t[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    while(cin >> n) {
        for(int i = 1; i <= n; i++) {
            cin >> t[i].a >> t[i].b >> t[i].c;
            t[i].id = i;
        }

        sort(t + 1, t + n + 1);

        for(int i = 1; i <= n; i++)
            if(i != n) cout << t[i].id << " ";
            else cout << t[i].id << endl;
    }

    return 0;
}

题目

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。
ZZT 需要在这个队列上执行 P 次操作，操作分两种：
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。
在 P 次操作之后，ZZT 想知道队列中的元素的排列方式，由于他最近很忙，因此需要请你帮他解决这个问题。

输入描述:

1
2
3
4
5
6
7
8
9
10

第一行输入一个正整数 N，表示队列的大小。
第二行输入 N 个正整数，Q1, Q2, Q3, ... ..., QN，Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。
第三行输入一个正整数 P，表示接下来要进行的操作次数。

接下来 P 行，第 i 行输入一个字符串 Si 以及一个正整数 Xi，表示一次操作。
1 ≤ N ≤ 105.
1 ≤ Qi ≤ N.
1 ≤ P ≤  105.
Si  { “FIRST”, “LAST” }.
1 ≤ Xi ≤ 105.

输出描述:

1

输出 N 个正整数，表示 P 次操作之后的队列。

示例1

输入

1
2
3
4
5
6

4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1

输出

1

4 3 2 1

题解

这个题的数据量比较大，用类似插入排序的方法只能过65%的数据，但因为题目给出的数据是n的全排列，因此队列中不会有重复的数据，所以可以另开一个数组维护队列中每个元素的位置，之后要用到某个元素的位置时根据值反查位置。

同时因为移动位置操作开销较大，可开一个较大的数组（大概5e5），并从数组的中部开始存入队列的数据，并维护一个start和end指针来指示数组第一个元素的前一个位置和数组最末元素的后一个位置，每当出现元素移动位置事件时，修改start和end指针的位置，并采用懒惰删除的策略标记数组中原有位置，最后遍历整个队列数组打印队列。时间复杂度O(n+q)。

代码

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 <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define FIRST "FIRST"
#define LAST "LAST"

const int MAXN = 1e5;
int q[MAXN * 5];
int h[MAXN + 100];

int main(){
	int n = 0;
	
	while(scanf("%d", &n) != EOF) {
		int start = 2e5 - 1; 
		int end = start + n + 1;

		for(int i = 1; i <= n; i++) {
			scanf("%d", &q[i + start]);
			h[q[i + start]] = i + start;
		}

		int p =0;
		scanf("%d", &p);

		char tmp[10]; int x  =0;
		for(int i = 0; i < p; i++) {
			scanf("%s %d", tmp, &x);

			if(strcmp(FIRST, tmp) == 0) {
				q[start] = q[h[x]];
				q[h[x]] = -1;
				h[x] = start;
				start--;
			} else if(strcmp(LAST, tmp) == 0) {
				q[end] = q[h[x]];
				q[h[x]] = -1.;
				h[x] = end;
				end++;
			}
		}

		int ok = 0;
		for(int p = start + 1; p != end; p++) {
			if(q[p] != -1) {
				ok ? putchar(' ') : 1;

				printf("%d", q[p]);

				!ok ? ok = 1 : 1;
			} 
		}
		putchar('\n');
	}

	return 0;
}

题目

题目描述

集合要满足互异性，即一个集合不能包含相同的元素。但是有的时候，我们需要集合中包含相同的元素，这种集合叫做多重集合（multiset）。
现在有一个多重集合，其中有n个整数。现在需要你从其中选出k个整数，使得k个数中任意两个的差都可以被m整除。
问题来了，能否从多重集合中找到k个数，若果可以的话，输出Yes，否则输出No。

回溯策略的基本思想

回溯策略是暴力搜索法中的一种。对于某些约束满足问题，要求给出问题全部或最优解时，尤其适合使用回溯策略。

回溯策略的基本思想是试错法，它尝试分步地去解决一个问题。在解决问题的过程中，当回溯策略发现现有的分步答案不能给出有效的解答时，它将向上回溯，取消前一步甚至是前几步的计算结果，然后再通过其他可能的分步解答再次尝试寻找问题的答案。通俗地说，就是选定一条路往前走，直到“撞了南墙”再回头换一条别的路。

题目

Problem Description

Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

枚举策略的基本思想

1. 在问题所有可能解之集合中一一枚举所有可能元素。
2. 以问题所给检验条件判断每个元素的状态（符合或不符合检验条件），符合条件的元素构成问题的解集。

题目

Problem Description
对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。

Input
输入数据包括多个测试实例，每个实例由一行长度不超过100的字符串组成，字符串仅由大小写字母构成。

Output
对于每个测试实例输出一行字符串，输出的结果是插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入"(max)"。

Sample Input

abcdefgfedcba
xxxxx

Sample Output

abcdefg(max)fedcba
x(max)x(max)x(max)x(max)x(max)

约瑟夫环问题：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。

程序输入说明：输入两个数 n和m，1<=n<=100,1<=m<=n

程序输出说明：每组输出一行，表示n个人出圈的顺序，相邻两个数字之间隔一个空格

程序输入样例：6 2

程序输出样例：2 4 6 3 1 5