主要思路
首先这题有个提示：
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。
那么我们可以考虑直接算这个钱反复转手的最大值即可。设计状态 \(dp[i]\)，然后有转移：
\[ dp[i] = \max_{j \in [0, i)} \frac{(A_i Rate_j + B_i)f[j]}{A_j \times Rate_j + B_j} \]
首先这题有个提示：
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。
那么我们可以考虑直接算这个钱反复转手的最大值即可。设计状态 \(dp[i]\)，然后有转移：
\[ dp[i] = \max_{j \in [0, i)} \frac{(A_i Rate_j + B_i)f[j]}{A_j \times Rate_j + B_j} \]
这道题是要求你实现一个 Checker，来判断是否有长度相同的环。实现的主要方式是找出所有的环并放到桶里面进行统计。我们可以观察出一些简单的性质，来做一次判断：
之后，我们可以考虑把度数为 2 的点去掉，缩成一张新的图。然后，再做暴力的 DFS 来判断是否存在同长环：具体而言，选择一个起点，然后在 DFS 之后删去。
时间复杂度是 \(\Theta(n^2)\) 的。
这道题乍一看不是很能做，因为摆放状态很多。然而，计算机科学这种东西解决不了问题的时候不讲究正解，只讲究近似。所以，我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。
竖的横的上下分开填。
// CF1103A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, ux, uy, dx, dy;
char str[MAX_N];
int main()
{
scanf("%s", str + 1), n = strlen(str + 1);
ux = 1, uy = 1, dx = 0, dy = 1;
for (int i = 1; i <= n; i++)
if (str[i] == '0')
printf("%d %d\n", ux, uy), uy = uy % 4 + 1;
else
printf("%d %d\n", (dx >> 1) + 3, dy), dx = (dx + 1) % 4, dy = (dy + 1) % 4 + 1;
return 0;
}
一共有 60 次询问机会，我们可以分两个 30 次：第一个 30 次用来询问最高位前的一位，第二个 30 位用来补全我们对 \(a – 1\) 的猜测。