Problem A 题目大意：由N个正整数组成的序列，我们可以从中取出任意长短序列进行如下操作：序列中(最大值maxn%最小值minn = A),如果A为0则删除maxn，否则用A替换,询问要使得整个序列最后只剩下1，至少需要多少步操作； 思路：We can prove that, no matter how you choose i,ji,j in the operations, the total number of operations does not change. 题目已经给出了提示，无论我们怎么选都是最优操作，所以只需要使用任一 一种取法算出结果即可，这里直接跑模拟，我们直接选取整个队列中的最大最小值操作 所以我们直接对序列进行排列，又因为每次操作A%B = C，C会比A更小，所以只需将每次算出的结果插入队首（不为0）并且删除队尾即可，始终保证序列的单调 性。最后当队首为1时直接停止模拟加上现有的队列长度-1即可。 不要用数组模拟太容易错了（就是这样wa了一个点），这种首尾操作直接上双端队列即可
#include<bits/stdc++.h>
using namespace std;
deque<int> q;
const int N = 2e5 + 10;
int n, a[N], t;
int main() {
std::ios::sync_with_stdio(false);//加快cin读取速度的
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
q.push_back(a[i]);
int k = a[1], ans = 0;
while (k > 1 && q.size() > 1) {
t = q.back();
t = t % k;
if (t == 0)
q.pop_back();//直接消失
else {
q.pop_back();
q.push_front(t);
k = q.front();
}
ans++;
}
ans += q.size() - 1;
cout << ans;
return 0;
}
Problem B
题目大意：现在对一串整数序列（序列中元素为1,2,3,4,5·····n，就是因为看漏了这一点才做不出来呜呜呜）进行排序，我们只有两种操作
操作A：将Pi和Pi+1位置上的数交换
操作B：将Pi和Pi+2位置上的数进行交换
不限操作次数，同时保证操作A次数最小，询问如何操作
思路：找到A和B操作的不同，我们可以发现A操作改变了（i&1）==（Pi&1）和（i+1&1）==（Pi+1&1）的值，而B操作并没有改变（i&1）==（Pi&1）和（i+2&1）==（Pi+2&1）的值，
也就是没有改变两个位置上 奇偶性Pi & 奇偶性i 的值，这就是破题点，因为两个操作都可以改变大小顺序，所以从大小顺序这个角度上来说不好破题，所以我们利用这个差异性破题
奇偶性Pi & 奇偶性i =1， 我们记为0， 奇偶性Pi & 奇偶性i =0， 我们记为x
所以假设最开始的序列为：0x00xx0x
首先用B操作将序列变换为: xxxx0000
然后对"xx"进行操作A使得其变为“00”即可（必要的操作，因为我们目标序列1,2,3,4.....的奇偶性序列是00000....）
最后用B操作使得序列 00000000 恢复到1 2 3 4 5.......的有序序列即可
#include<bits/stdc++.h>
using namespace std;
int n;
int a[500];
vector<pair<char, int>> ans;
void solve(char c, int i) {
ans.emplace_back(c, i);//没有构造临时对象效率更高
swap(a[i], a[i + 1 + c - 'A']);
}
int main() {
std::ios::sync_with_stdio(false);//加快cin读取速度的
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n - 2; j++)
if (((a[j] & 1) == (j & 1)) && ((a[j + 2] & 1) != ((j + 2) & 1)))
solve('B', j);
for (int i = 1; i <= n - 1; i++)
if (((a[i] & 1) != (i & 1)) && ((a[i + 1] & 1) != ((i + 1) & 1)))
solve('A', i);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n - 2; j++)
if (a[j] > a[j + 2]) solve('B', j);
cout << ans.size() << endl;
for (auto x : ans)
cout << x.first << ' ' << x.second << endl;
return 0;
}
奇偶性Pi & 奇偶性i
标签：AtCoder,147,int,奇偶性,cin,Regular,序列,操作,Pi
From： https://www.cnblogs.com/Aacaod/p/16663837.html