http://codeforces.com/contest/1474
C. Array Destruction
题意：给定一个数组。先选择一个数 x，再从数组中选择两个和为 x 的数，从数组中删去，并 x 变成这两个数中大的那个。问是否可行，以及每一步的选择。
最开始的用来合成 x 的两个数中，必定有一个是数组中最大的数，否则它以后就用不到了。所以只需要再枚举另一个数。
这样就已知 x 与两个数中大的那个数了，之后的每一步就都是可以模拟下去的了。
所以对每一次枚举，O(n) 模拟进行验证。
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 <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n;
int a[N];
multiset<int, greater<int> >st;
typedef pair<int, int>pii;
vector<pii>vc;
bool ck(int x) {
st.clear();
vc.clear();
for (int i = 1; i <= 2 * n; i++)st.insert(a[i]);
while (!st.empty()) {
int mx = *st.begin();
st.erase(st.begin());
int tmp = x - mx;
auto p = st.find(tmp);
if (p == st.end())return false;
vc.push_back({ tmp,mx });
st.erase(p);
x = mx;
}
return true;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
st.clear();
for (int i = 1; i <= 2 * n; i++)scanf("%d", &a[i]);
sort(a + 1, a + 2 * n + 1, greater<int>());
bool flg = 0;
for (int i = 2; i <= 2 * n; i++) {
if (ck(a[i] + a[1])) {
flg = 1;
puts("YES");
printf("%d\n", a[i] + a[1]);
for (auto p : vc)printf("%d %d\n", p.first, p.second);
break;
}
}
if (!flg)puts("NO");
}
return 0;
}
|
E. What Is It?
题意：给定 n，要求构造出一个长度为 n 的排列。对这个排列进行操作，直到这个排列有序，每次操作选择两个位置 i,j，满足 pj=i，交换 pi,pj，代价为 (j−i)2。问使排列有序的最大代价与操作。
构造
从小的开始尝试，大概在 n=4 的时候要猜出构造方法。
下面是 n=6 时。
最后一步是最外层两个交换，倒数第二第三步是1，5交换与2，6交换，倒数第四第五步是1，4交换与3，6交换。
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 <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n;
typedef pair<int, int>pii;
stack<pii>st;
int a[N];
void dfs(int dep) {
if (dep > (n + 1) / 2)return;
if (dep == 1) {
st.push({ 1,n });
swap(a[1], a[n]);
}
else if (dep == (n + 1) / 2) {
int l = n / 2, r = n / 2 + 1;
if (n & 1)st.push({ r,1 }), swap(a[1], a[r]);
else {
st.push({ l,n });
st.push({ r,1 });
swap(a[l], a[n]);
swap(a[r], a[1]);
}
return;
}
else {
st.push({ dep,n });
st.push({ n - dep + 1,1 });
swap(a[dep], a[n]);
swap(a[n - dep + 1], a[1]);
}
dfs(dep + 1);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
ll ans = 1ll * (n - 1)*(n - 1);
for (int i = 1; i < n / 2; i++) {
ans += 2ll * (n - i - 1)*(n - i - 1);
}
if (n & 1)ans += 1ll * (n / 2)*(n / 2);
for (int i = 1; i <= n; i++)a[i] = i;
dfs(1);
printf("%lld\n", ans);
for (int i = 1; i <= n; i++)printf("%d%c", a[i], " \n"[i == n]);
printf("%d\n", n - 1);
while (!st.empty()) {
printf("%d %d\n", st.top().first, st.top().second);
st.pop();
}
}
return 0;
}
|
