测试题面链接：problems.pdf
这次测试可以说是一场娱乐赛。采用的是ACM赛制。
这一次测试成绩如下，是我与冯译宽一起合作出来的成绩。
其中，有两道题 (G, H) 其实都不是很正确的解法，只是因为数据比较水……
其中，G题是fyk想出的，A,C,H题都是我写的（其实只花了5+20+10分钟，其他时间都耗在了D题上，关键是还没有有想出来……）
所以说，HFu说的我们的策略很好其实是不正确的……QwQ （被Sqrtyz学长全图炮骂了）
其实我和fyk还是比较互补的，他的思路非常的独特，而我的又相对死板……
废话也不多说了，我们看题
签到题之二……是一个最优构造题。
我们只要使得 \(A\) 是严格递增的，此时，求出对应的 \(B'\) 序列的 \(LIS\)。
那么，答案就是 \(n + LIS(B')\)
由于我们保证了 \(LIS(A)\) 已经是最大了，考虑对其进行一次操作，绑定交换其中两个数。
那么此时 \(LIS(A)\) 会减少一个，而 \(LIS(B)\) 要么不变，要么增加一个。也就是说 \(LIS(A) + LIS(B)\) 实际上是不会再变多了。换句话来说，这就是最优解了。
其实这道题在考场上我是没有过多思考的……
说来也惊险，在 12:09 我才开始思考这道题 （12:20结束比赛），随便口胡了这个思路，验证了一下样例，发现没有问题，于是在 12:15 就写出来了，于是就 AC 了……一发入魂
第一次提交的代码太难看了……仓促之下写的，下面的是把格式优化了一下的……
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
#define lowbit(i) (i & -i)
class BIT {
private:
int b[N];
public:
int update(int i, int x) {
for (; i < N; i += lowbit(i)) b[i] = max(b[i], x);
}
int query(int i, int r = 0) {
for (; i; i -= lowbit(i)) r = max(r, b[i]);
return r;
}
};
struct Item {
int a, b;
bool operator<(const Item & i) {
return a < i.a;
}
};
int main() {
static BIT bit;
static Item items[N];
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> items[i].a;
}
for (int i = 1; i <= n; ++i) {
cin >> items[i].b;
}
sort(items + 1, items + 1 + n);
int res = 0;
for (int i = 1; i <= n; ++i) {
int k = items[i].b;
int ans = bit.query(k);
bit.update(k, ans + 1);
res = max(res, ans + 1);
}
cout << res + n << endl;
return 0;
}
我现在还没有写出来，候补
其实说来也多亏了 Sqrtyz 学长的解释，我才终于看懂了样例……然后花了7分钟写了一个暴力（结果就过了……）
所谓暴力，也就是说深搜寻找到所有的输赢情况，并且统计……
其实正解就是暴力搜索。其复杂度的保证在进攻的方式上。
每一次进攻就必定有一个随从死亡。经过一点点分析，其复杂度不会超过 \(O(n!)\) 。考虑 \(n\) 最大也才7……
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
#include <iomanip>
using namespace std;
#define double long double
const int N = 10;
double W[2], E; // A win, B win, No win
int n[2];
int atk[2][N]; // 攻击力
int hp[2][N]; // 血量
int ats[2][N]; // 攻击次数
// a 打 b,当前状态的可能性为 P
double calc(int a, int b, double P) {
// 找到攻击次数最少的存活者
int minAts = INT_MAX, at, alive(0);
for (int i = n[a]; i; --i) {
if (hp[a][i] > 0) { ++alive; // 统计a存活人数
if (ats[a][i] <= minAts) minAts = ats[a][i], at = i;
}
}
int blive(0);
for (int i = 1; i <= n[b]; ++i) {
if (hp[b][i] > 0) ++blive; // 统计b存活人数
}
if (alive == 0 && blive == 0) { // 平局
return E += P;
} else if (alive == 0) { // b win
return W[b] += P;
} else if (blive == 0) { // a win
return W[a] += P;
}
// at 攻击随机一个
++ats[a][at];
for (int i = 1; i <= n[b]; ++i) {
if (hp[b][i] > 0) { // at 可以攻击这个狗
hp[a][at] -= atk[b][i];
hp[b][i] -= atk[a][at];
calc(b, a, P / blive);
hp[a][at] += atk[b][i];
hp[b][i] += atk[a][at]; // trace back
}
}
--ats[a][at]; // trace back
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n[0] >> n[1];
for (int i = 1; i <= n[0]; ++i) {
cin >> atk[0][i];
hp[0][i] = atk[0][i];
}
for (int i = 1; i <= n[1]; ++i) {
cin >> atk[1][i];
hp[1][i] = atk[1][i];
}
double init = 1.0;
if (n[0] == n[1]) init = 0.5;
if (n[0] >= n[1]) { // 0 first
calc(0, 1, init);
}
if (n[1] >= n[0]) { // 1 first
calc(1, 0, init);
}
cout << fixed << setprecision(11);
cout << W[0] << '\n' << W[1] << '\n' << E << endl;
return 0;
}
真的毒瘤……我深搜了4个小时，结果只得了60分……太可恶了
Sqrtyz 学长给出的正解是DP，奇奇怪怪的那种……其实思路理清楚非常简单。
我们令 dp[i][0/1] 表示前 i-1 行清理完之后到达 0/1 至少需要清理的次数
我们让机器人一步一步走。假设我们当前位置为 dp[i][j]
那么我们分两种情况：
dp[i][j ^ 1] == 0，也就是说当前列没有需要清理的了。那么我们让机器人向右走一步，到达 dp[i+1][j] 即可（花费代价为0）
dp[i][j ^ 1] == 1，也就是说当前列还有一个需要清理的。我们又要分两种情况讨论
dp[i + 1][j] == 1，两个需要清理的地方发生了冲突，我们必须要清理一个。那么我们有两种选择：
人为清理同列的。那么我们让机器人走到 dp[i + 1][j] 即可，花费代价为1
人为清理同行的。意味着我们让机器人向上走让后再向右即可。这个时候如图
（红色为机器人的位置，蓝色为我们人为清理的位置，绿色为机器人需要清理的位置）经过观察我们可以知道，机器人不走已经被清理过的格子是最优的。那么显而易见，我们让机器人走到 dp[i+2][j^1] 的位置，就非常的优秀了（花费代价为1）
dp[i + 1][j] == 0，也就是说没有冲突了。此时我们仍然有两种选择
人为清理这个格子。那么机器人就直接向右走转移到 dp[i+1][j]，花费代价为1 （就是因为我没有考虑到这个点，所以错了……QwQ）
机器人清理这个格子，那么机器人就向上然后向右，转移到 dp[i + 1][j ^ 1] 即可，花费代价为0
为了方便DP，我们使用刷表法。定义刷新函数：
int flush(int i, int k) {
if (mp[i][k ^ 1]) { // 上面有脏东西
if (mp[i + 1][k]) { // 右边也有
// 略过右边的
update(dp[i + 2][k ^ 1], dp[i][k] + 1);
} else {
// 没有冲突
update(dp[i + 1][k ^ 1], dp[i][k]);
}
// 略过上面的
update(dp[i + 1][k], dp[i][k] + 1);
} else { // 没有脏东西
update(dp[i + 1][k], dp[i][k]);
}
return 0;
}
初始化并用每一个值刷表：
memset(dp, 0x7F, sizeof(dp));
dp[1][0] = 0; // 初始位置
for (int i = 1; i <= n; ++i) {
flush(i, 0);
flush(i, 1);
}
那么这道题就做出来了……（考场上这道题我得分最高……60分……可是还是没有AC）
考场上我就是用这个方法写的，就是因为忽略了一种情况，痛失40分……
而且我当时的写法很奇怪……思路还是有一点区别。见代码，有注释。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 1e6 + 7, INF = 0x7F7F7F7F;
int n, f[N][2];
char mp[N][2];
// 状态定义为清理完了前i列，并且在k行的答案
// impa指前面的操作有没有对这里的答案产生影响
// 记忆化一下就ok了
inline int dfs(int i, int k, int impa = false) {
if (i == n) return 0;
if (!impa && ~f[i][k]) return f[i][k];
int ans = 0, backup = mp[i][k], j;
mp[i][k] = 0;
// 寻找第一个需要清理的地方
for (j = i; j <= n; ++j) {
if (mp[j][0] || mp[j][1]) break;
}
// 如果是i,j同一列的话……就会对其产生影响
if (j >= n) ans = 0;
else if (mp[j][k]) {
// 唯一解
ans = dfs(j, k, i == j ? true : false);
} else if (mp[j + 1][k]) { // 有冲突
// 选择清理不同行的
ans = dfs(j + 1, k) + 1; // 对其答案没有影响
// 清理同行的
mp[j + 1][k] = 0;
ans = min(ans, dfs(j + 1, k ^ 1, true) + 1); // 对其答案有影响
mp[j + 1][k] = 1;
} else { // 没有冲突
ans = dfs(j, k ^ 1, i == j ? true : false);
// 或者我们清理这个点，进入后面一个点
ans = min(ans, dfs(j + 1, k) + 1);
}
// trace back
mp[i][k] = backup;
if (!impa) f[i][k] = ans;
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
memset(f, 0xFF, sizeof(f));
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> mp[i][0], mp[i][0] -= '0';
}
for (int i = 1; i <= n; ++i) {
cin >> mp[i][1], mp[i][1] -= '0';
}
cout << dfs(0, 0, false) << endl;
return 0;
}
哎……这种写法表现极其不优秀……DP写法是214ms，这种写法512ms
都是套路……
我们一点点剖析需求。
首先，我们肯定需要找到所有回路的异或和，同时，还需要求出这些异或和的最大值……考虑到 a ^ a = 0 的性质，我们用可以通过拼接两个环形成一个全新的环。
为了让每一条边都在一个环内，我们可以先找一棵生成树。然后遍历每一条非树边，形成一个只有一条非树边的环。这样，我们就可以通过拼接这些环，构造出所有的回路了。
由于有了每一种环的异或值，我们考虑如何凑出最大值。那么就需要用到线性基……
那么恭喜你，这道题就做出来了……都是套路啊
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 7, M = 1e5 + 7;
int n, m;
class MergeFindSet {
private:
int grp[N];
public:
MergeFindSet(int n) { init(n); }
void init(int n) {
for (int i = 1; i <= n; ++i) grp[i] = i;
}
int find(int x) {
if (grp[x] == x) return x;
return grp[x] = find(grp[x]);
}
void merge(int x, int y) {
grp[find(x)] = find(y);
}
};
struct Edge {
int from, to, w;
} edge[M], ver[M];
int head[N], tot = 0, vtot = 0;
int W[N]; // 生成树上点到根的路径权值异或和
int xorRing[M];
void add(int u, int v, int w) {
edge[++tot] = {head[u], v, w}, head[u] = tot;
}
// 点x, 到根的路径异或和s，父节点fa
void dfs(int x, int s, int fa) {
W[x] = s;
for (int y, i = head[x]; i; i = edge[i].from) {
if ((y = edge[i].to) != fa) {
dfs(y, s ^ edge[i].w, x);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
static MergeFindSet mfs(n);
int u, v, w;
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w;
if (mfs.find(u) == mfs.find(v)) {
ver[++vtot] = {u, v, w}; // 记录非树边
} else {
mfs.merge(u, v);
add(u, v, w), add(v, u, w); // 建生成树
}
}
// 预处理树上路径异或和
dfs(1, 0, 0);
static int xxj[40];
#define marked(x, i) ((x>>i)&1)
for (int i = 1; i <= vtot; ++i) {
u = ver[i].from, v = ver[i].to, w = ver[i].w;
int val = W[u] ^ W[v] ^ w;
for (int k = 30; k >= 0; --k) {
if (marked(val, k)) {
if (!xxj[k]) {
xxj[k] = val; break;
}
val ^= xxj[k];
}
}
}
int ans = 0;
for (int k = 30; k >= 0; --k) {
ans = max(ans, ans ^ xxj[k]);
}
printf("%d\n", ans);
return 0;
}
虽然代码写出来了，但是……有一个点一直过不了。可恶
其实这道题就是优化建图的问题。建完图之后，跑一次DJK就行了。
那么如何建图？
我们记 W(x) 为点 x 的权值。
对于一条边 (u, v)，其编号为 i。我们在另外一张图里面加入边 (i, u, W(u) / 2) 以及 (i, v, W(v) / 2) （无向边！）
那么对于新的图……跑一次DJK就OK了
不要用
double，会出现这种错误情况所以，我们建图的时候先不除以2，在答案的地方除以二就行了。
还有，最大值能有多大设多大
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int N = 5e6;
struct Edge {
int to, next;
long long w;
} edge[N];
int head[N], tot = 0;
inline void add(int u, int v, long long w) {
edge[++tot] = {v, head[u], w}, head[u] = tot;
}
long long Vw[N];
int n, m, S, T;
typedef pair<long long, int> Pr;
void djk(int s, long long * dis) {
static int vis[N]; memset(vis, 0, sizeof(vis));
priority_queue<Pr, vector<Pr>, greater<Pr> > pq;
dis[s] = 0;
pq.push(make_pair(0, s));
while (pq.size()) {
int x = pq.top().second; pq.pop();
if (vis[x]) continue;
vis[x] = true;
long long w;
for (int y, i = head[x]; i; i = edge[i].next) {
y = edge[i].to, w = edge[i].w;
if (!vis[y] && dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
pq.push(make_pair(dis[y], y));
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m >> S >> T;
for (int i = 1; i <= n; ++i) cin >> Vw[i];
int u, v;
for (int i = 1; i <= m; ++i) {
cin >> u >> v;
add(i, u + m, Vw[u]);
add(u + m, i, Vw[u]);
add(i, v + m, Vw[v]);
add(v + m, i, Vw[v]);
}
static long long dis[N];
for (int i = 1; i <= m + n; ++i) dis[i] = LLONG_MAX;
djk(S, dis);
cout << dis[T] / 2 << endl;
return 0;
}
感性理解一下，对于这个序列，相邻两个元素只差最大为
n - 1，而我们单次操作至多却是n，也就是说，最终状态一定是单点不下降的序列……
这是一道构造题。总的来说，有两种构造方法
(d, i)，d指差分的值，i指位置。以d为第一关键字，i为第二关键字排序，然后，我们将 i 依次输出即可#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int main() {
cin.tie(0)->sync_with_stdio(false);
static pair<int, int> dif[N];
int px(0), n, x;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
dif[i] = make_pair(px - x, i);
px = x;
}
sort(dif + 1, dif + 1 + n);
for (int i = 1; i <= n; ++i) {
cout << dif[i].second << ' ';
} cout << endl;
return 0;
}
O(n) 的构造法。考虑到元素是唯一的，我们尝试把每一个元素凑到 n + 1。也就是说，值为 x 的数，在第 n + 1 - x 次被操作。#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(false);
int n, x, ans[100007];
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
ans[n + 1 - x] = i;
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
} cout << endl;
return 0;
}
真·田才
一道不是那么数学的数学题，从来没有做过的交互体……结果写了一个假的解……数据太假了。
考场思路：
我们令未确定的位置全集为 \(S\), 随机选取其中一个元素 \(i\) 作为基准，枚举其他元素 \(j\)，令 \(gcd(i, j)\) 最大值为 \(d\)，记录下所有 \(gcd(i, j) = d\) 的 \(j\)，作为新的全集 \(S\)。重复上述步骤，直到全集中只剩下 1 或 2 个数为止。
次数上限 \(3n - 1\) 是不符合要求的……但是，Sqrtyz 学长出了一堆 \(n = 10\) 的情况，而在 \(n = 10\) 的时候，其实刚好需要 \(2n\) 次……所以没有被Hack掉……QwQ
那么 Sqrtyz 学长对此给出了优化的方法，我们只需要寻找到一个不为 1 的基准开始即可。
枚举 \(i \in [1, n)\) ，直到 \(gcd(i, i+1) \ne 1\)，那么，\(i\) 与 \(i + 1\) 就一定都不为 \(1\)。钦定任一为基准即可。但是，为了不浪费寻找的那些次数，我们可以发现，如果 \(gcd(i, i+1) = 1\) 并且 \(gcd(i + 1, i + 2) == 1\) ，那么可以保证 \(i + 1\) 一定不为 \(0\)。（假定我们如此寻找了 \(k\) 次）也就是说，我们未确定的全集减少了 \(k - 1\) 个数。那么总的询问次数上限为 \(2(n - k + 1) + k = 2n - k + 1\) 次，又由于 \(k \ge 1\)，那么可以保证次数在 \(2n\) 次以内
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int ask(int i, int j) {
if (i > j) swap(i, j);
static map<pair<int, int>, int> cache;
pair<int, int> P = make_pair(i, j);
if (cache[P] != 0) return cache[P];
cout << "? " << i << ' ' << j << endl;
int g;
cin >> g;
return cache[P] = g;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
vector<int> S;
// 找到全集
for (int gcd(0), i = 1; i < n; ++i) {
gcd = ask(i, i + 1);
if (gcd != 1) {
for (int j = i; j <= n; ++j) S.push_back(j);
break;
}
}
if (S[0] != 1) S.push_back(1);
if (S.size() == 1) {
cout << "! 1 " << n << endl;
return 0;
}
for (int id(1); id <= n; ++id) {
if (S.size() == 2) {
cout << "! " << S[0] << ' ' << S[1] << endl;
return 0;
}
vector<int> V;
int i = S[0], gmax = -1;
for (size_t si = 1; si < S.size(); ++si) {
int j = S[si];
int gcd = ask(i, j);
if (gcd > gmax) gmax = gcd, V.clear();
if (gcd == gmax) V.push_back(j);
}
if (V.size() == 1) {
cout << "! " << i << ' ' << V[0] << endl;
return 0;
}
S.swap(V);
}
return 0;
}
正解：
对于题目，我们有下述发现
也就是说，每两次询问，就一定能排除一个数。那么最多 \(2n\) 次，就确定为 \(0\) 的数。
这种思路的代码我就不放了，我没有写……QwQ
Update at 2023.3.10 更改图片链接