A. Hard Way

Code

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;

void solve()
{
	PDD p[5];
	for (int i = 1; i <= 3; i++)	cin >> p[i].y >> p[i].x;
	sort(p + 1, p + 1 + 3);
	
	if (p[3].x == p[2].x)	printf("%.9lf\n", abs(p[3].y - p[2].y));
	else cout << 0 << endl;
}

int main()
{
	int T;
	cin >> T;
	while (T--)	solve();
	return 0;    
}

B. Power Walking

Code

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    
    int n; cin >> n;
    set<int> s;
    
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        s.insert(x);
    }

    for (int i = 1; i <= n; i++)    cout << max(i, int(s.size())) << ' ';
    cout << endl;
}

int main()
{
	int T;
	cin >> T;
	while (T--)	solve();
	return 0;    
}

C. Great Sequence

题目大意

题意：给定 $x$ ，在数组中添加尽可能少的数，使得数组可以分成若干对 $(p,q)$ ，数组中每个元素恰好在一个pair中。并且每个pair的 $p,q$ 满足：

• $p = xq$

解题思路

将数组排序后从小到大枚举，如果存在一个数 $p$ ，必然需要有一个 $xq$ 与之配对，如果不存在，则答案加一；如果存在，则删去一个 $xq$ 。

供上自己的错误TLE做法(人生中第一次被hack!)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, x, t;

void solve()
{
    map<ll, ll> mp;  // 用map可以实现自动排序
    cin >> n >> x;
    
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        mp[t]++; 
    }

    ll res = 0;
    for (auto item : mp)
    {
        if (!mp.count(item.first * x))    res += item.second;  // 一次性全部加上
        else
        {
            mp[item.first * x] -= item.second;
            if (mp[item.first * x] < 0)  
            {
                res -= mp[item.first * x];  // 此时mp[item * x]为负数, '-'相当于加上操作次数
                mp.erase(item.first * x);  // 从map中删除这个元素
            } 
        }
    }
    cout << res << '\n';
}

int main()
{
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D. Repetitions Decoding

题目大意

给定一个长度为 $n(n < 500)$ 的数组，可以选择多次向数组中的同一位置插入相同的两个数。
最多执行 $2*n^2$ 次。满足操作后，可以将数组分为多个连续的子数组，每个子数组的长度都为偶数。
对于每个子数组，前一半等于后一半。比如 [1,1,4,1,1,4] ， [5,1,4,5,1,4] 。
请输出方案。
方案的格式为
操作的次数。每次操作为：
$p,c$ 在第 $p$ 个元素的后面插入两个 $c$ 。
最后还需要输出分出的子数组的大小。

解题思路

严格鸽的题解把这题的思路讲的特别详细

另外，今天才注意到一个语法方面的东西
如果vector声明时后面没有跟‘(n)’类似的容量声明，则只能够用push_back来插入数据
否则直接用cin >> v[i]的话会因为容量不够而无法输入数据
举例:

• vector<int> v; {int x,cin >> x, v.push_back(x)};
• vector<int> v(n); {cin >> v[i]};

TIPS：代码中的删除操作不能交换，因为删除操作会使得迭代器失效的。
【C++ STL】迭代器失效的几种情况总结

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

void solve()
{   
    int n, tot = 0;  // 统计已经删除的数的个数
    cin >> n;
    vector<int> v(n), siz;  // 最后方案中每个子数组的长度
    vector<PII> ans;
    unordered_map<int, int> cnt;
    
    
    for (int i = 0; i < n; i++)  cin >> v[i], cnt[v[i]]++;

    for (auto x : cnt)  
		if (x.second % 2) 
        {
            cout << -1 << '\n'; 
            return;
        }   

    for (int i = 1; i <= n / 2; i++)
    {
        auto it = ++v.begin();
        while (*it != *v.begin()) it++;

        int dist = it - v.begin();
        for (int j = 0; j < dist - 1; j++) ans.push_back({tot + dist + 1 + j, v[j + 1]});

        reverse(v.begin() + 1, it);  // 反转中间的序列
        v.erase(it);  // 删除后面一个元素, 这里不能交换删除顺序
        v.erase(v.begin());  // 删除开头的元素

        tot += dist * 2;
        siz.push_back(dist * 2);
    }   

    cout << ans.size() << '\n';
    for (auto x : ans)  cout << x.first << ' ' << x.second << '\n';
    cout << siz.size() << '\n';
    for (auto x : siz)  cout << x << ' ';
    cout << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}