看题
有外校的一起考, 那我爆个 \(0\)
\(\rm{A}\)
至少不能是简单题
考虑找规律一类的东西, 看能不能推出来?
\(\rm{B}\)
啊?
也是需要脑子, 多半不会做, 应该也是规律题
\(\rm{C}\)
至少暴力可以打, 争取达到高档暴力
\(\rm{D}\)
能打到这在想吧
完了嘛
时间分配: \(1 \rm{h} + 30 \rm{min} + 45 \rm{min} + 1 \rm{h} 15 \rm{min}\)
\(\rm{A}\)
手玩样例看能不能找到明显的性质
没有什么头绪, 显然的, 对于 \(30\%\) 的数据, 我们可以更改之后再跑一遍
考虑优化, 感性理解上, 每次只改变一个地方的交换, 肯定有大量重复的计算, 考虑优化掉这些重复的计算
-
前面没改的
这显然是不需要重复计算的, 我们通过简单的二分操作, 就知道 \(id\) 位置的人在 \(t\) 操作前在哪里 -
后面没改的
这一部分比较复杂, 但是显然的, 我们知道如果这个操作没有涉及到 \(id\) 位置的人在 \(t\) 操作前所在位置, 那么对答案没有影响
考虑涉及到了的情况, 我们假设 \(id\) 当前位置为 \(u\), 位移之后位置为 \(v\)
那么有, \(v\) 本来在后面的操作全部都位移到了 \(u\) 身上, 我们直接利用 \(v\) 的操作即可
那么思路大概就有了, 时间复杂度约为 \(\mathcal{O}(Q \log n)\) , 大概可以通过
那么考虑代码的具体实现
维护 \(n\) 个位置变换链表, 记录第 \(i\) 次变换时, 变换操作的编号以及当前所在的位置
显然的, 空间复杂度为 \(\mathcal{O}(n)\)
记录每个位置变换了多少次, 建立链表时, 考虑利用辅助数组
对于具体的操作, 我们先找到 \(id\) 编号在 \(t\) 次操作之前, 最后一次所在位置, 如果更改之后两编号 \(u, v\) 与最后一次所在位置无关, 那么直接输出最后一次答案, 如果有关, 那么我们找到(假设 \(u\) 为当前节点最后一次所在位置) \(v\) 后续的最终节点即可
其中 \(v\) 后续的最终节点怎么求?
问题转化为找 \(t\) 次操作之前最后一个出现 \(v\) 的操作, 即 \(v\) 在 \(t\) 操作前到底是那个最初位置的人在, 然后直接输出这个人的最终节点即可, 在当前的写法中不好实现
考虑再建立一个链表, 我们考虑记录每一个位置变换 \(id\) 的链表, 即记录第 \(i\) 次更改时, 最后一个 \(id\) 的编号
那么对于第一个操作, 我们在第一个链表里面求, 对于第二个操作, 我们在第二个链表里面求
现在主要问题在于链表的建立, 对于第一个链表, 我们记录每一个位置对应最初的 \(id\) , 一直更改即可
对于第二个链表, 我们建立第一个链表的过程中即可处理
注意到, 当当前被替换的操作与 \(id\) 有关时, 我们还是需要从后面的推, 不能直接输出
预期得分: \(100 \rm{pts}\)
\(\rm{B}\)
对于 \(30 \%\) 的数据, 考虑直接处理 \(x, y\) 坐标的链, 每次删一个就把其之后的全部推上来
预期得分: \(30 \rm{pts}\)
\(\rm{C}\)
注意到 \(m\) 很小啊, 考虑从这里下手
显然的, 本质不同的字符串只有 \(2 ^ {m + 1} - 1\) 种, 对于 \(m \leq 10\) 已经可以处理了
考虑 \(m\) 更大的情况
考虑不出来
预期得分: \(30 \rm{pts}\)
\(\rm{D}\)
看不懂题, \(S\) 是啥?
预期得分: \(0 \rm{pts}\)
代码
预期得分: \(100 + 30 + 30 = 160 \rm{pts}\)
剩下 \(1 \rm{h }30 \rm{min}\) 打代码
\(\rm{A}\)
决定我今天到底有多少的题, 大吉保佑我
先理清楚思路
读入直接用题面里面的
首先是建立链表
第一个链表
维护原本在 \(id\) 位置的人变换顺序
初始化时, 记录 \(pos_{id} = id\) 表示 \(id\) 位置上的人是 \(id\)
每次对于一个变换 \(u, v\) , 考虑找到 \(pos_u, pos_v\), 然后对于链表 \(pos_u\) , 插入当前位置 \(v\) , 对于 \(pos_v\) , 插入当前位置 \(u\) , 令 \(pos_u, pos_v\) 交换
第二个链表
维护位置 \(id\) 上人的变换顺序
在第一个链表的维护过程中, 每次 \(pos_{id}\) 变化, 将 \(pos_{id}\) 插入进 \(id\) 这一链表
注意两个链表都要记录在第几次操作到达方便二分
其次是查询
每次知道 \(t, id\) , 二分查询 \(id\) 在 \(t\) 之前的最后位置, 检查 \(u, v\) 中是否有 \(id\)
-
没有
直接输出最终答案 -
有
二分查询 \(v\) 位置在 \(t\) 前最后一个所在人的编号, 输出这个人的最终答案
\(\rm{C}\)
今天能拿到的所有分了
#include <bits/stdc++.h>
#define FILE_IO
const int MAXN = 1e5 + 20;
const int MAXSIZ = 3000;
int n, m;
/*n <= 1000*/
class Subtask1
{
private:
std::string Now[MAXN];
int NowNum[MAXN];
int Calc(int u, int v)
{
int x = u ^ v;
int ans = 0;
while (x)
{
if (x & 1) ans++;
x >>= 1;
}
return ans;
}
public:
void solve()
{
for (int i = 1; i <= n; i++) {
std::cin >> Now[i];
}
for (int i = 1; i <= n; i++) {
NowNum[i] = 0;
for (int j = 0; j < Now[i].length(); j++)
{
if (Now[i][j] == 'G') {
NowNum[i] += (1 << j);
}
}
}
for (int i = 1; i <= n; i++) {
int Ans = 0;
for (int j = 1; j <= n; j++) {
Ans = std::max(Ans, Calc(NowNum[i], NowNum[j]));
}
printf("%d\n", Ans);
}
}
} S_1;
/*m <= 10*/
class Subtask2
{
private:
int Have[MAXSIZ];
int Ans[MAXSIZ];
std::string Now[MAXN];
int Calc(int u, int v)
{
int x = u ^ v;
int ans = 0;
while (x)
{
if (x & 1) ans++;
x >>= 1;
}
return ans;
}
public:
void solve()
{
for (int i = 1; i <= n; i++) {
std::cin >> Now[i];
int NowNum = 0;
for (int j = 0; j < Now[i].length(); j++)
{
if (Now[i][j] == 'G') {
NowNum += (1 << j);
}
}
Have[NowNum]++;
}
for (int i = 0; i < (1 << (m + 1)); i++) {
if (!Have[i]) continue;
Ans[i] = 0;
for (int j = 0; j < (1 << (m + 1)); j++) {
if (!Have[j] || i == j) continue;
Ans[i] = std::max(Ans[i], Calc(i, j));
}
}
for (int i = 1; i <= n; i++) {
int NowNum = 0;
for (int j = 0; j < Now[i].length(); j++)
{
if (Now[i][j] == 'G') {
NowNum += (1 << j);
}
}
printf("%d\n", Ans[NowNum]);
}
}
} S_2;
int main()
{
#ifdef FILE_IO
freopen("different.in", "r", stdin);
freopen("different.out", "w", stdout);
#endif
scanf("%d %d", &n, &m);
if (m <= 10) {
S_2.solve();
} else {
S_1.solve();
}
return 0;
}