思维的体操——构造专项训练
目录
受CF一场比赛的教训，认识到自己在构造上的思维不足，故写下此博客记录刷题时碰到的一系列构造题
题单(不保证难度递增）
- CF1325A
- CF1325D
- CF1428D
受CF一场比赛的教训，认识到自己在构造上的思维不足，故写下此博客记录刷题时碰到的一系列构造题
题单(不保证难度递增）
CF1325A
- 简要题意
给你一个数 x ，找出任意两个数 a , b 使得 \(GCD(a,b)+LCM(a,b)=x\) - 题解
将 \(a=1\) ,则 \(\gcd(a,b)=1,LCM(a,b)=b,b=x-1\)
CF1325D
- 题意
给你 u 和 v ,找出最少的数使得异或和为u,和为v - 题解
当 \(v
CF1428D
- 题意
咕咕咕 - 题解
对于第 \(i\) 列， 分为3列讨论
\(a_i = 1\) , 假设放在第 \(j\) 行易知 \(j\) 是这列目标中最大的, 故能放多下面就放多下面， 为了方便， 我们放在 \((i, i)\)
\(a_i = 2\) , 假设有两个目标， 最下面是第 \(j\) 行 , 且这一行中最左边的是这个目标， 最右边的那一列 \(k\) 一定满足 \(a_k = 1\)
\(a_i = 3\) , 若所有第 \(j(j > i 且 a_j = 3)\) 列的都已经有两个目标， 跟后面随便一个列为 1 的匹配， 即跟它同一行放两个目标， 为了方便， 我们放在第 i 行。若没有， 那么同理我们也跟它放在第 i 行。
然后无解的情况自然是匹配不到
code
#include
using namespace std;
const int N = 1e5 + 7;
int n;
int a[N];
vector> ans;
stack st[4];
void gg() {
puts("-1");
exit(0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = n; i; --i) {
if (a[i] == 1)
ans.emplace_back(i, i);
if (a[i] == 2) {
if (st[1].empty())
gg();
int tmp = st[1].top();
st[1].pop();
ans.emplace_back(tmp, i);
}
if (a[i] == 3) {
bool flag = false;
for (int j = 3; j; --j) {
if (st[j].empty())
continue;
int tmp = st[j].top();
st[j].pop();
ans.emplace_back(i, i);
ans.emplace_back(i, tmp);
flag = true;
break;
}
if (!flag)
gg();
}
st[a[i]].push(i);
}
cout << ans.size() << endl;
for (auto [x, y] : ans)
cout << x << ' ' << y << endl;
return 0;
}