AtCoder Grand Contest 041 Table Tennis Training 如果 $a,b$ 奇偶性相同,那么一起往中间走即可。 否则,走到某一端,浪费一次步数之后再一起往中间走。 int main() { ll n, a, b; rd(n, a, b)...
题解
AtCoder Grand Contest 046 题解
AtCoder Grand Contest 046 Takahashikun, The Strider 相当于要找到最小的正整数 $t$ 满足 $tx \equiv 0 \pmod {360}$,暴力即可。 int main() { int x; rd(x); int t = 1; while (1) { ...
LOJ3298 「BJOI2020」封印 题解
LOJ3298 「BJOI2020」封印 新鲜出炉的 2020 省选题嗷。 首先对于每个 $s$ 的后缀 $i$ 找到其与 $t$ 的最长公共子串长度 $f_i$,这个把 $s$ 和 $t$ 隔一个字符并起来做 SA,然后从前往后从后往前扫一遍即可...
AtCoder Grand Contest 045 题解
AtCoder Grand Contest 045 Xor Battle 倒序考虑,如果在一个 $1$ 处能够成功加入线性基,则说明无论 $1$ 之前的数是什么情况,都可以使 $1$ 之后的数不在线性基内,因此 $1$ 赢,否则 $0$ 赢。 const int...
Codeforces Round #647 (Div. 1) – Thanks, Algo Muse! 题解
Codeforces Round #647 (Div. 1) - Thanks, Algo Muse! Johnny and Contribution 傻逼模拟题,用 stable_sort 排序一下,然后判一下无解。 const int N = 5e5 + 7; int n, m, a[N], p[N], q[N]; vi e[N]; ...
AtCoder Grand Contest 037 题解
AtCoder Grand Contest 037 Dividing a String 可以证明划分出来的段长度不超过 $2$,于是 $\mathcal O(n)$ DP 即可。 const int N = 2e5 + 7, inf = 1e9; int n, f[N][2]; char s[N]; int main() { ...
JOISC 2018 题解
JOISC 2018 Day 1 道路建设 发现操作本质上是一个 $\text{access}$,LCT 维护即可,逆序对就把路径上的颜色块爬下来树状数组求就行了,时间复杂度 $\mathcal O(n \log^2 n)$。 const int N = 1e5 + 7; s...
AtCoder Grand Contest 044 题解
AtCoder Grand Contest 044 Pay to Win 倒着考虑,记忆化搜索一下即可。 #define ll __int128 const int o[3] = {2,3,5}; const ll inf = 1e18; ll n, a[3], d; map<ll, ll> p; inline ll f(ll x) ...
USACO 2018-2019 Platinum 题解
USACO 2018 December Contest Balance Beam 单调栈求一个上凸壳即可。 卡精度,要用 __int128。 const int N = 1e5 + 7; int n; __int128 a[N]; vi s(1, 0); inline bool pd(int i, int j, int k) { ...
JOISC 2019 题解
JOISC 2019 Day1 試験 (Examination) 裸的三维偏序模板题,$\mathcal O(n \log^2 n)$ 的 CDQ 分治即可。 const int N = 6e5 + 7; int n, m, a[N], c[N], t, ans[N]; struct P { int x, y, z, o; ...