前言
过了样例不要着急，多测几组自己的数据，错一次20分钟的罚时还是很伤的。
第一题
题目： Changing Volume
题意：
给我们两个数a和b，每次可以在a上加 [-5,-2,-1,1,2,5] 六个数之一，问最少几次可以将a变为b。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例包含两个整数a和b。
输出格式
对每个样例输出一个整数。
数据范围
1 ≤ t ≤ 1000
1 ≤ a, b ≤ 109
输入样例：
3
4 0
5 14
3 9输出样例：
2
3
2思路：
- 思维题。因为可操作的六个数是对称的，所以我们可以将a变为b视为将a和b中较小的数变为较大的数。
- 从5到1每次贪心减去最多能减的数即可。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int d[] = { 1,2,5 };
int get_num(int a, int b)
{
if (a > b)swap(a, b);
int num = 0;
for (int i = 2; i >=0; --i)
{
if (b == a)break;
int t = (b - a) / d[i];
num += t;
b -= d[i]*t;
}
return num;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a, b;
cin >> a >> b;
cout << get_num(a, b) << endl;
}
return 0;
}第二题
题目： Fridge Lockers
题意：
有n个住户，每个住户有一个房间，住户自己可以开自己的房间，每个房间会有一个代价。我们可以将n个房间上m把锁，每把锁会把两个房间连在一起。如果一个房间通过两把锁以上连接了另外两个以上不同的房间，那么这些房间的主人可以共同打开这个房间。但是代价是这些锁所连接的房间的代价之和。可以在两个房间之间上多把锁，问在没有任何一个房间是私有的前提下（私有是指只有房间主人可以打开该放房间），打开所有房间的最小代价。感觉我描述的好繁琐晦涩，但是原文比这还难理解啊，起码这算是人话了
输入格式
输入包含多个样例，第一行是一个整数t，代表有t个样例。
每个样例第一行是两个整数n和m，表示有n个房间和可以上m把锁。
每个样例第二行是n个整数，表示每个房间的代价。
输出格式
对于每个样例，如果不存在输出-1。
否则第一行输出一个整数，表示总代价。
接下来m行每行两个整数，表示该锁所连接的两个房间。
数据范围
1 ≤ t ≤ 10
2 ≤ n ≤ 1000, 1 ≤ m ≤ n
0 ≤ ai ≤104
保证所有的n之和不会大于2×105
输入样例：
3
4 4
1 1 1 1
3 1
1 2 3
3 3
1 2 3输出样例：
8
1 2
4 3
3 2
4 1
-1
12
3 2
1 2
3 1思路：
- 首先要满足所有房间都不是私有的，也就是说任何房间都起码有两把锁和两个不同的房间相连，那么n个房间最少需要n把锁。同时如果只有两个房间，是无法实现非私有化的。
- 如果满足
m>=n，首先为了满足非私有化需要所有房间两两上锁，然后将多余的锁都上在代价最小的两个房间即可。
代码：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e4 + 10;
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int m, n;
cin >> n >> m;
int num = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>p;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
num += a[i];
p.push({ a[i],i });
}
num *= 2;
if (m < n||n==2)
{
cout << -1 << endl;
continue;
}
else
{
sort(a + 1, a + n + 1);
num += (a[1] + a[2]) * (m - n);
cout << num << endl;
for (int i = 1; i < n; ++i)cout << i << " " << i + 1 << endl;
cout << n << " "<<1 << endl;
int x = p.top().second;
p.pop();
int y = p.top().second;
p.pop();
for (int i = n+1; i <= m; ++i)cout << x << " " << y << endl;
}
}
return 0;
}
第三题-赛后补题
题目： League of Leesins
题意:
有n个整数组成的数列，每三个相邻的三个整数可以组成一个三元组，可以任意交换三元组内的元素和不同组的顺序，但是不能交换不同组内的元素，求出原序列。
输入格式
输入第一行是一个整数n表示原数列有n个整数。
接下来有 n-2 行，每行是一个三元组。
输出格式
输出一行n个整数，两个整数之间用空格间隔。
数据范围
5 ≤ n ≤ 105
1 ≤ qi, qj ≤ n
输入样例：
5
4 3 2
2 3 5
4 1 2输出样例：
1 4 2 3 5 思路：
- 首先我们可以会发现，原数列的开始位置和结束位置的数字都只出现了一次，第二个和倒数第二个数字都只出现了二次，中间所有数字都出现了三次。
- 因为正序输出还是倒序输出都是可接受的，所以我们可以先随便选一个只出现一次的数字作为起始位置，然后找到和它一组的另外两个元素，判断一下出现两次或者三次，起始位置先输出出现两次的，结束位置后输出出现两次的。而确定两个数之后，可以根据前两个数来找到后面那个元素，因为相邻三个数一定在一个三元组中。
- 这就涉及到一个问题，怎么判断两个三元组有两个元素相同，暴力遍历最终会超时。
- 考虑如何优化，如果通过三元组的关系将所有点画成图，我们会发现所谓出现的次数其实对应着每个点的入度，那么就可以用拓扑排序的做法来解决。需要注意的是在移去某个点时，可能会导致倒数第三个点和倒数第二点的入度同时变为1，为了使顺序不变，我们可以先将所有点根据初始入度排序。
超时代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int a[N][4],b[4];
unordered_map<int, int>p;
int judge(int j)
{
unordered_map<int, int>p;
for (int i = 1; i <= 3; ++i)
{
p[b[i]]++;
p[a[j][i]]++;
}
int res = 0, num = 0;
for (auto t : p)
{
if (t.second == 1)
{
res++;
for (int k = 1; k <= 3; ++k)if (t.first == a[j][k])num = k;
}
}
if (res == 2)return num;
else return 0;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n - 2; ++i)
{
for (int j = 1; j <= 3; ++j)
{
cin >> a[i][j];
p[a[i][j]]++;
}
}
int x=0,y=0;
for (int i = 1; i <= n-2; ++i)
{
if (x)break;
for (int j = 1; j <= 3; ++j)
if (p[a[i][j]] == 1)x = i, y = j;
}
a[x][0] = 1;
cout << a[x][y] << " ";
pair<int, int>s[5];
for (int i = 1; i <= 3; ++i)
{
b[i] = a[x][i];
s[i].first = p[a[x][i]]; s[i].second = a[x][i];
}
sort(s + 1, s + 4);
cout << s[2].second << " " << s[3].second << " ";
for (int i = 1; i <= n - 3; ++i)
{
for (int j = 1; j <= n - 2; ++j)
{
if (!a[j][0])
{
int f = judge(j);
if (f)
{
a[j][0] = 1;
cout << a[j][f] << " ";
for (int k = 1; k <= 3; ++k)b[k] = a[j][k];
break;
}
}
}
}
return 0;
}拓扑排序代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
vector<int>v[N];
unordered_map<int, int>p;
bool find(int a, int b)
{
//如果数组v[a]已经存在b，那么就不用再存
for (int i = 0; i < v[a].size(); ++i)if (v[a][i] == b)return false;
//说明没有出现过，需要存b
return true;
}
//建立一个在vector中a为下标的数组，存的数是和a有关的所有三元组的其它元素。
void rudu(int a, int b, int c)
{
if (find(a,b))v[a].push_back(b);
if (find(a, c))v[a].push_back(c);
}
bool cmp(int a, int b)
{
return p[a] > p[b];
}
int main()
{
int n;
cin >> n;
int m = n - 2;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
p[a]++, p[b]++, p[c]++;
rudu(a, b, c), rudu(b, a, c), rudu(c, a, b);
}
//将入度大的排在前面，防止倒数第二个和倒数第三个入度同时变为1，导致顺序混乱。
for (int i = 1; i <= n; ++i)sort(v[i].begin(), v[i].end(), cmp);
//找到起始位置和结束位置
int l=0, r=0;
for(int i=1;i<=n;++i)
if (p[i] == 1)
{
if (l == 0)l = i;
else r = i;
}
queue<int>q;
q.push(l);
while (q.size())
{
int t = q.front();
q.pop();
cout << t << " ";
for (int i = 0; i < v[t].size(); ++i)
{
//当三元组的某个元素出队后，与之相关的元素入度都要减一
p[v[t][i]]--;
if (p[v[t][i]] == 1)q.push(v[t][i]);
}
}
//不要忘记输出最后一个元素
cout << r;
return 0;
}
