1902
[CF1902E] Collapsing Strings
题目链接 考虑拆贡献。 显然答案可以拆成对于所有 \(s_i\) 的每一个后缀的反串,作为前缀在所有串中的出现次数的加和。 这个东西字典树维护一下就行了。 不知道是谁考场上写哈希赛后被人对着模数卡掉了 点击查看代码 #include <bits/stdc++.h> #define FL(i, a, ......
codeforces刷题(1100):1902B_div2
B、Getting Points 跳转原题点击此:该题地址 1、题目大意 Monocarp为了完成总共n天的某学期的p学分任务。Monocarp每天可以选择两种度过方式:上一次课和完成最多两个任务 或者 休息一天。其中上课获得l学分,每个任务获得t学分,其中任务不可以重复接取,并且每周获得一个新的任 ......
CF1902D Robot Queries 题解
题意:有一个二维平面直角坐标系,给定一串向某个方向移动 \(1\) 个单位的操作。 有 \(q\) 个询问,对于每个询问给定 \(x,y,l,r\),问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作,是否会经过 \((x,y)\)。 ds 题。先预处理出 \(sx_i,sy_i\) 表示执 ......
CodeForces 1902F Trees and XOR Queries Again
洛谷传送门 CF 传送门 如果我们能把 \(x \to y\) 路径上的所有点权插入到线性基,那么可以 \(O(\log V)\) 查询。 但是因为线性基合并只能 \(O(\log^2 V)\)(把一个线性基的所有元素插入到另一个),所以只能倍增做 \(O((n + q) \log n \log^2 ......
【题解】CodeForces 1902F Trees and XOR Queries Again
传送门:https://codeforces.com/contest/1902/problem/F 数据结构题,这里讲两种思路。 $ST$ 表思路: 判定“从若干个数中能否取出其中一些,使得异或和为 $x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性 ......
【题解】Trees and XOR Queries Again - Codeforces 1902F
https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分(也可以用其他种类的LCA算法),然后从数的异或表示很容易想到线性基。 然后因为是无修改的,所以可以轻重链剖分+ST表+线性基。具体来说就是: 先进行轻重链剖分。然后把每次 ......
[CF1902] Educational Codeforces Round 159 A~E 题解
[CF1902] Educational Codeforces Round 159 A~E 题解 A. Binary Imbalance 很快观察到如果有不同的相邻元素,那么一定有解,意味着如果全是 1 无解,其他有解 B. Getting Points 题面很长,可以发现,最好的偷懒方式一定是把所 ......
[Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/contest/1902)
Educational Codeforces Round 159 (Rated for Div. 2) 好困,差点没打 A - Binary Imbalance #include <bits/stdc++.h> #define int long long #define endl '\n' usin ......
CF1902 D Robot Queries 题解
Link CF1902 D Robot Queries Question Robot 初始在 \((0,0)\) ,有一个字符串 \(s\) ,表示运行列表 \(U\):y+1 \(D\):y -1 \(L\) :x -1 \(R\) :x+1 之后有 \(Q\) 次询问,有\(L,R,x,y\), ......
CF1902 C Insert and Equalize 题解
Link CF1902 C Insert and Equalize Question 有一个 \(n\) 个元素的数组 \(a\),每个元素都不一样 现在我们需要在 \(a\) 中添加一个数字 \(a_{n+1}\),和之前的元素都不一样 然后选择一个数 \(x\),可以在一个元素上加 \(x\), ......
CF1902 B Getting Points 题解
Link CF1902 B Getting Points Question Monocarp 的一个学期有 \(n\) 天,需要修 \(P\) 个学分,完成一节课程加 \(l\) 个学费,完成一个任务加 \(t\) 个学分 Monocarp 一天可以完成一节课+两个任务 任务每周分配一个,也就是 d ......