会 T1 T2 的正解，并且都没写挂。（除了 T2 因为 map 被卡了 20 分）
A 计算异或和
给出
先把所有的
这样看貌似也只能整除分块之类的搞一搞，可是发现并没有用，转而考虑换一种枚举的顺序
这时，模数是固定的，只有被模数变化。发现这个东西有极强的周期性。
- 整块共出现了偶数次。此时所有整块的贡献都没了，只用算最后一个小块，即
\displaystyle \bigoplus_{v = 0}^{n \bmod j} v 。 - 整块共出现了偶数次。此时整块的贡献会和小块的贡献抵消，答案为
\displaystyle \bigoplus_{v = n \bmod j + 1}^{j - 1} v 。
这两个东西预处理一下前缀异或和就都能
const int MAXN = 1e5 + 10;
int n, ans, sum[MAXN];
int calc(int k) {
int cnt = (n / k), ret = 0;
if (cnt & 1) ret = sum[k - 1] ^ sum[n % k];
else ret = sum[n % k];
return ret;
}
int main() {
#ifdef LOCAL
freopen("calcxordata.txt", "r", stdin);
#endif
IO::read(n);
rep(i, 1, n) {
int x; IO::read(x);
ans ^= x;
sum[i] = sum[i - 1] ^ i;
}
rep(k, 1, n) ans ^= calc(k);
IO::write(ans, '\n');
return 0;
}B 配置香水
给出长度为
发现这个
时间复杂度
可是 map 会在 auoj 上被卡成 80，但是用 multiset 就过了。
typedef long long ll;
const ll MAXVAL = 1e14;
const int MAXN = 1e5 + 10;
int n, k, arr[MAXN];
ll sum[MAXN], ans;
vector<ll> pows[20 + 10];
multiset<ll> cnt;
void solve() {
IO::read(n), IO::read(k);
cnt.clear(); ans = 0;
rep(i, 1, n) IO::read(arr[i]), sum[i] = sum[i - 1] + arr[i];
cnt.insert(0);
rep(i, 1, n) {
for (int idx = 0; idx < pows[k + 10].size(); ++idx) ans += cnt.count(sum[i] - pows[k + 10][idx]);
cnt.insert(sum[i]);
}
IO::write(ans, '\n');
}
int main() {
#ifdef LOCAL
freopen("perfume.txt", "r", stdin);
#endif
rep(i, -10, 10) {
pows[i + 10].push_back(1);
if (0 <= abs(i) && abs(i) <= 1) continue;
ll cur = i;
while (abs(cur) <= MAXVAL) {
pows[i + 10].push_back(cur);
cur = 1ll * cur * i;
}
}
pows[-1 + 10].push_back(-1);
int t; IO::read(t);
while (t--) solve();
return 0;
}C 分配
有
每一轮，由局面上编号最大的人进行提出一个分配方案。即，把这若干个物品分配给还在局面上的人。
接下来，局面上所有人会进行投票。一个人会支持，当且仅当满足下列三者条件至少其一：
- 他是提出方案的人。
- 该方案中他获得的物品个数，严格 大于以后的所有方案中获得的物品个数。
- 在以后的所有方案中，他会出局。
如果一个方案有大于等于
否则，提出该方案的人会出局。
现在，有两问需要你回答。
- 如果第
n 号人必须获得至少1 个物品，至少需要多少物品使得存在至少一种分配方案使得他能不出局？ - 如果第
n 号人可以获得任意多的物品，至少需要多少物品使得存在至少一种分配方案使得他能不出局？
先考虑第一个问。
- 一个人，只需要
1 个。 - 两人，也只需要
1 个。因为这样 支持-反对 比是1:1 的。 - 三人，因为如果
3 号出局，2 不会给1 号任何物品；所以3 号只需要给1 号1 个物品再加上自己的1 个物品，共2 个物品即可。 - 四人，因为如果
4 号出局，3 不会给2 号任何物品；所以4 号只需要给2 号1 个物品再加上自己的1 个物品，共2 个物品即可。 n 人，只要n 给所有n - 1 不会给的人1 个物品，他们就会支持。容易发现编号与n 同奇偶的人都不会收到n - 1 的物品，所以只需要给和自己同奇偶的人即可。答案就是\big\lceil \dfrac{n}{2}\big\rceil 。
再考虑第二个问。
第二个问，考虑对于有
k = 0 ，n = 1, 2, 4, 8, 16\cdots 2^x 。k = 1 ，n = 1, 2, 3, 4, 6, 10, 18 \cdots 2^x + 2 。k = 2 ，n = 1, 2, 3, 4, 5, 6, 8, 12, 20 \cdots 2^x + 4
有理由猜测，
下面我们来证明一下。
首先，对于
对于后面的那些
事实上，令
因为每个
那么有两个解
由于
综上所述，
由此，我们可以得到一个一阶的递推式：
所以对于所有
至此，问题转化为，对于一个
- 如果
n 是一个奇数，显然不存在n = 2k + 2^{x - 1} 。答案为k = \big\lfloor \dfrac{n}{2} \big\rfloor 。 - 否则，将
n 最高位去掉之后（即把2^{x - 1} 去掉）除以2 就是答案。
时间复杂度
void solve() {
int n, S; IO::read(n), IO::read(S);
if (S == 1 || (n & 1)) return IO::write((n + S) >> 1, '\n'), void();
per(_, 31, 0) if ((n >> _) & 1) return IO::write((n - (1 << _)) >> 1, '\n'), void();
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
int t; IO::read(t);
while (t--) solve();
return 0;
}D 数列编辑器
维护一个序列与一个光标，操作涉及：
- 在光标后加入一个数，并将光标移到加入的数后。
- 将光标左右移动。
- 把光标前的数删除。
- 修改某个数。
- 求当前序列的某个区间和。
块 状 链 表。
时间复杂度
typedef long long ll;
const int MAXN = 3e5 + 10;
struct BlockList {
static const int BLOCKSIZE = 830;
static const int BLOCKNUM = MAXN / BLOCKSIZE + 10;
static const int HEAD = 1, EMPTY = 0;
struct Node { int data[BLOCKSIZE * 2 + 10], nxt, sz; ll sum; } t[BLOCKNUM];
int avaliNode[BLOCKNUM], tp;
BlockList() { per(i, BLOCKNUM - 1, 2) avaliNode[++tp] = i; t[HEAD].nxt = EMPTY, t[HEAD].sz = 0, t[HEAD].sum = 0; }
inline void del_node(int blockNum) { avaliNode[++tp] = blockNum, t[blockNum].sz = 0, t[blockNum].sum = 0, t[blockNum].nxt = EMPTY; }
inline int new_node() { int ret = avaliNode[tp--]; t[ret].nxt = EMPTY; return ret; }
inline void get_pos(int& dataIdx, int& blockNum) {
for (blockNum = HEAD; blockNum != EMPTY && dataIdx > t[blockNum].sz; blockNum = t[blockNum].nxt) dataIdx -= t[blockNum].sz;
}
inline void cpy(const int& blockNum, const int & s, const int data[], const int& len) { // 将 t[blockNum].data[s] 开始的 len（包含 s）个 int 赋值为从 data[0] 开始的 len 个 int
register int ed = s + len - 1;
for (register int i = s; i <= ed; ++i) t[blockNum].data[i] = data[i - s];
}
inline void link(int blockNum1, int blockNum2) { // insert blockNum2 after blockNum1
t[blockNum2].nxt = t[blockNum1].nxt, t[blockNum1].nxt = blockNum2;
}
inline void calc_sum(int blockNum) { t[blockNum].sum = 0; rep(i, 1, t[blockNum].sz) t[blockNum].sum += t[blockNum].data[i]; }
inline int split(int blockNum1, int p) { // 将 t[blockNum1].data 从 p 开始（不包括 p）到结尾分裂成 t[blockNum2]，并返回 blockNum2
if (blockNum1 == EMPTY) return EMPTY;
if (p >= t[blockNum1].sz) return EMPTY;
int blockNum2 = new_node();
cpy(blockNum2, 1, t[blockNum1].data + p + 1, t[blockNum1].sz - p);
t[blockNum2].sz = t[blockNum1].sz - p, t[blockNum1].sz = p;
link(blockNum1, blockNum2), calc_sum(blockNum1), calc_sum(blockNum2);
return blockNum2;
}
inline void merge(int blockNum1, int blockNum2) {
cpy(blockNum1, t[blockNum1].sz + 1, t[blockNum2].data + 1, t[blockNum2].sz);
t[blockNum1].nxt = t[blockNum2].nxt;
t[blockNum1].sum += t[blockNum2].sum, t[blockNum1].sz += t[blockNum2].sz;
del_node(blockNum2);
}
inline void maintain() {
for (int blockNum = HEAD; blockNum != EMPTY; blockNum = t[blockNum].nxt) {
while (t[blockNum].nxt != EMPTY && t[blockNum].sz + t[t[blockNum].nxt].sz <= BLOCKSIZE) {
merge(blockNum, t[blockNum].nxt);
}
}
}
inline void ins(int p, int val) { // add val after position p
int blockNum1, blockNum3;
get_pos(p, blockNum1), split(blockNum1, p);
t[ blockNum3 = new_node() ].sum = val, t[blockNum3].data[1] = val, t[blockNum3].sz = 1;
link(blockNum1, blockNum3);
maintain();
}
inline void del(int p) { // delete the p-th number
int blockNum1, blockNum2, blockNum3;
get_pos(p, blockNum1);
if (p == t[blockNum1].sz) return t[blockNum1].sz--, calc_sum(blockNum1), void();
blockNum2 = split(blockNum1, p - 1), blockNum3 = split(blockNum2, 1);
t[blockNum1].nxt = blockNum3;
del_node(blockNum2);
maintain();
}
inline void modify(int p, int val) { // modify the p-th number's val
int blockNum1, blockNum2;
get_pos(p, blockNum1);
if (p == t[blockNum1].sz) return t[blockNum1].data[p] = val, calc_sum(blockNum1), void();
blockNum2 = split(blockNum1, p - 1), split(blockNum2, 1);
t[blockNum2].data[1] = val, calc_sum(blockNum2);
maintain();
}
ll query(int l, int r) { // query the sum from l to r
int blockNum1, blockNum2, curBlock; ll ret = 0;
get_pos(l, blockNum1), get_pos(r, blockNum2);
if (blockNum1 == blockNum2) { rep(i, l, r) ret += t[blockNum1].data[i]; return ret; }
for (curBlock = t[blockNum1].nxt; curBlock != EMPTY && curBlock != blockNum2; curBlock = t[curBlock].nxt) ret += t[curBlock].sum;
rep(i, l, t[blockNum1].sz) ret += t[blockNum1].data[i]; rep(i, 1, r) ret += t[blockNum2].data[i];
return ret;
}
} blockList;
int n, p, tot;
char opt[10];
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
IO::read(n);
rep(i, 1, n) {
scanf("%s", opt + 1);
p = min(p, tot), p = max(p, 0);
if (opt[1] == 'I') {
int x; IO::read(x);
blockList.ins(p, x);
++p, ++tot;
} else if (opt[1] == 'D') {
blockList.del(p), --tot, --p;
} else if (opt[1] == 'L') {
--p;
} else if (opt[1] == 'R') {
++p;
} else if (opt[1] == 'Q') {
int l, r; IO::read(l), IO::read(r);
IO::write(blockList.query(l, r), '\n');
} else if (opt[1] == 'C') {
int pos, val; IO::read(pos), IO::read(val);
blockList.modify(pos, val);
}
}
return 0;
}复盘与总结
45min 拍完了 T1，没啥问题。
50min 在厕所会了 T2。
66min 写完了 T2。
84min 拍完了 T2，拍出个小问题。改了后就拍过了。
90min ~ 110min 一直在看 T3，但是 读错题了，甚至怀疑样例的正确性，遂去写了 T4 60 分暴力。
150min 左右写完了暴力，但是发现 T4 20 分的部分分会 RE，看来自己还是不太熟悉迭代器啥的。
然后后面尝试修锅，修到了比赛结束 180min。
事实证明，对拍并花不了太多的时间。T1 T2 能快速的写出来并且拍出来是很好的，可惜 T3 读错题了，不然至少能再多个 30 分。
下次，如果觉得样例错了，一定是自己把题意理解错了或者手玩错了，不可能题错了，要再仔细读一读题。