模拟赛

题意 给定一张有向图，问你反转一条边后是否对 \(scc\) 有变化。 \(n \le 1500, m \le 10^6\) Sol 先对图跑一边 \(tarjan\)，考虑对每条边进行分讨。 在同一强连通分量里。如果反转后依然有一条 \(u \to v\) 的路径，那么 \(scc\) 不变，否则 ......

简要题意 \(n\le 10^3 , \sum K_i\le3\times10^5\) 思路 首先容易想到一个暴力DP，\(f_{l,r,x}\) 表示区间中最大值为 \(x\) 的最大值 稍微想亿下可以发现如果这个位置选的不是区间最大值的话，答案一定不优 所以我们可以直接 \(f_{l,r}\) ......

题意 给定 \(n\) 个不可重集，初始每个集合 \(i\) 有元素 \(c_i\)。 请你以下 \(3\) 种操作： 1 x y 在集合 \(x\) 插入 \(y\)。 2 x y 将 \(y\) 集合所有数插入 \(x\)，并删除 \(y\) 集合（不影响别的集合的下标） 3 x y 求 \(x ......

简要题意 每个点有一定概率向前面的点连边，求两点之间距离的期望 思路 推柿子 code #include<bits/stdc++.h> using namespace std; #define int long long #define N 1000005 int n,m,u,v; const in ......

【10.11 D组 T4】cat 给定长为 \(n\) 的序列 \(a_i,c_i\) 和长为 \(m\) 的序列 \(b_j,d_j\)。 对于每个 \(i\in[1,n]\)，求 \[\mathop{\operatorname{max}}\limits_{j=1}^{m} [b_j\ge c_i ......

简要题意 求一个抽象函数，满足 \(∀𝑥 ∈ ℤ, 𝑓(𝑥) + 𝐶 = 𝑓(2𝑓(𝑥) − 𝑥 + 1)\)，给定 \(n\) 个点，使得 \(\sum |f(x_i)-y_i|\) 最小，输出最小值 思路 对这个函数进行一次迭代，可以得到 \(f(x+2C)=f(x)+2C\) ......

题意 给定 \(n\) 个数，你需要把每个数分成两组，使得： 没有组为空。 两个组内所有数的按位或相等。 Sol 不难发现，当某一位上全是 \(1\) 的数被分在了一个集合内时，方案一定不合法。 考虑容斥计算这个东西。 对于每一位，建一个点。考虑把所有数抽象成边，对于当前 \(a_i\) 如果第 \ ......

简要题意 略 思路 先考虑啥样的 \(T\) 可能合法，就大概类似于一个一边删除，一边加入的操作，如果能删空，那就合法 但这样的 \(T\) ，不一定能作为答案，只有能将多余的数删除时才合法 那就用同样的策略，判断是否合法即可 接着考虑 \(T\) 的方案数咋求，设 \(dp_{i,j,k}\) ， ......

简要题意 给定一棵有根树，操作分别为：将某个点到根路径上全部点颜色改为 \(c\)；询问某个点到根路径上不同颜色数。 \(n\le10^5\) 思路 考虑对修改根号重构，那对于某次询问的路径，实际上就是前面有至多 \(\sqrt m\) 个相同颜色段，再拼上后面一段树上的颜色，也就是和修改中点的最深 ......

2023.11.13 CWOI T1 神奇模拟题，最直接的做法就是每个石头暴力向下滚，有 \(60\) 分。但是大样例跑了 \(15s\)。稍微观察一下，会发现很多次循环都是在重复向下走到一格空位上，于是考虑优化：用 set 维护每一列的那些位置有障碍（包括石头），每次直接 lower_bound ......

2024年了，新开一个模拟赛。 2024.1.2 CWOI 被龙哥吊打了。就只会做一道题，暴力还挂分。但是B题乱写的 \(k=1\) 有 \(30\) 分，乐。 T1 先欧拉筛，然后把每个数分解质因数，顺便统计答案。再做一个前缀和，就能 \(O(1)\) 回答询问了。时间 \(O(n \log n ......

10.8 没啥好说的，感觉像CSP-J+模拟赛 T1博弈论简单题，但我做了40min T2双指针简单题，但我判右界判挂了，-10 T3tg-的树形dp题，吸取上次调一整场没调出树形dp的经验，先不打 T4分块难写题，但我写的主席树，调了2.5h。 最后回去0.5h打T3暴力50分和特殊性质30分，然 ......

题意 你有一个长为 \(n\) 的序列 \(a_n, a_i = i^k\) 从这个序列里抽出 \(m\) 个互不相同的数，求出这些数中最大值的期望。 请输出答案对 \(998244353\) 取模的结果。 \(8MB\)。 Sol 首先将 \(n,m\) 自减一。 很显然，我们需要求出 \(\db ......

题目大意 有一个矩形，上面有若干个关键点，每次随机一个相邻的位置，问全部关键点被选取的期望时间 思路 设每个关键点被选取的时间为 \(t_i\) ，则答案就为 \(E(max(t_i))\) 然后我们发现 \(E(min(t_i))\) 是好求的，只需要保证在此之前全部都不被选即可，所以可以 \(m ......

题意 给一棵树，带点权（可为负），单点修改，求直径，求过某一点的直径 \((n<=100000)\) 思路 发现强制过某一点，可以转化为单点改成正无穷，求直径 于是就只用考虑单点修改求直径 考虑点分树，在每个重心维护到他的最长链，和不同子树中的次长链，全部答案取个max即可（但是被卡常） code ......

题意 给定一棵大小为 \(n\) 的树。 有两个人，每个点属于其中某一个人。 每轮选择一个度数为 \(1\) 的点删掉，设最后取得点的主人获胜。 问谁会获胜。 Sol 博弈分讨萌萌题。 首先这道题直接做肯定不好做。 考虑从特殊性质出发。 首先，对于链来说。不难想到要对于 \(n\) 的奇偶性分讨。 ......

题意 给定一个序列，你需要维护下面两种操作： 将所有 \(i mod k \in [l, r]\) 的 \(a_i\) 加上 \(x\) 求 \(\sum_{i = l} ^ r a_i\) Sol 考场代码挂成 \(35\) 了，数组全开两倍就直接过了/cf 初始化加强版，把单修改成了区修。 类似 ......

T1 sequence Question 请构造一组长度为 \(n\) 的数列 \(S\)，满足题目给出的 \(m\) 个数对 \((a, b)\) 所对应的 $S_a ≠ S_b \(，若存在多组解，请输出十进制下最小的那组。\)n,m$ 均不超过 \(200\)，并且保证答案中的任何一位不超过 ......

前言：这次还行，今年的最后一场比赛，300pts，rank4 T1 赛时摆烂了，没有牢记“正难则反”，打了暴力，还挂了 正解从后往前考虑，考虑在这个点对后面的点的影响，发现就是p乘上了一个系数，直接从后往前算的时候乘上即可，最后再考虑初始的w T2 发现取权值连续的一段数一定是最优的，随便维护一下即 ......

前言：这次比赛打的不是很好，100pts，rank8 T1 赛时想到了正解，但是因为一些题面的原因和代码细节没调出来 首先可以写出暴力dp：\(f[i][j]\)表示到第i位，选了i且选了j个哨岗的最大范围 枚举k为上一个，直接暴力转移是\(O(n^3)\)的，过不去 然后，我们发现可以分类讨论,如 ......

依然倒一，虽然比上次完全不会强一些了，但是挂了一堆分…… T1 奇怪地挂掉了，但是也反映了代码能力还是不行，求个子树内最大最小都要错，而且还把问题复杂化了。就是先并查集找根，记录子树内最值然后看子树大小等不等于极差就完事儿了，没那么多别的。 点击查看代码 #include<bits/stdc++.h ......

11.16（C0389） 100+10+50=160，rk3。 本来 BC 都应该写出来的。 A：dp 或 贪心 都可以，贪心直接从下往上覆盖即可。 B： 注意：这里的 \(\oplus\) 指的是按位或。 合法条件可以化简为：\(\oplus_{i=1}^{p}a_i = \oplus_{i = ......

题意 给定一个序列。 每次询问求两个区间排序后是否只有一个或者没有位置不同。 Sol 不难想到主席树维护值域。 考虑如何判断。 注意到当前答案正确，当且仅当值域上两点不同且相邻。 维护每个点的哈希值判断即可。 Code #include <iostream> #include <algorithm> ......

题意 给定一个矩阵，你需要支持： 循环左移 循环右移 循环下移 循环上移 按行置换求逆 按列置换求逆 Sol 前 \(4\) 个操作是 \(trivial\) 的。 如何处理后两个操作？ 考虑设一个三元组：\((x, y, A_{xy})\)。 每次操作，对于每一个元素都能确定操作后另外某个元素。 ......

T1 正解：莫反推导出来的整除分块，证明不会： 然后直接快速幂来算是 \(O(\sqrt{m}·log\:n)\) 的，过不了剩下三个点。考虑到模数很小且为质数，用费马小定理预处理幂次然后去算，复杂度 \(O(\mathbf{10007}·log\:n+\sqrt{m})\)，注意字符串处理 \(n ......

前言：这次比赛又是tm的AB组一起打，tm的题目怎么一点质量都没有啊，三道简单题+一道模板题，而且模板我还没做过，而且我的一个部分换成那个模板就A了 这次300pts，rank3，感觉不太好 T1 dp，\(f[i][0/1]\)表示i位置填0/1的方案数，直接转移，写高精度 T2 感觉应该放T4， ......

开坑的原因是模拟赛最近打的太抽象了，记录一下自己赛时的抽象行为。 三行分别是得分，挂分，能力范围内得分。 12.19 $$85+50+60=195$$ $$15+0+0=15$$ $$100+100+60=260$$ T1 没有观察到链上问题满足区间可合并，看到区间内选一对点直接上了一个线段树历史 ......

title: 9.18 模拟赛#20 date: 2023-09-18 15:11:52 categories: - 题解 top: #114 T1 手玩后发现第一个人的最后个数最多，易证。 然后考虑别人给了他多少贡献，应为 \(\frac{m}{3}+\frac{\frac{m}{3} }{3}+ ......

这次比赛打的好，但又不好，200pts，rank4，但原本可以360pts的 T1 每一条边减去端点贡献，最小生成树即可 T2 从小到大枚举花瓣数，然后对于每一列记录前四大的，防止不能转移，然后直接跑即可 赛时打了一个线段树，被卡常+卡空间，hahaha T3 暴力，先分解质因数，由于\(\varp ......

更好地观看 总结 今天是模拟赛，哈哈，计算几何。哈哈。哈哈。哈哈。link。 不想说太多了，上上上！ 算了，还是多说一点。今天的题目……质量还是很高啊。哈，自己还是很🥬啊。 题解 这里是简要的思路。 T1 一眼闵可夫斯基和，参看 [JSOI2018] 战争，然后对于速度求到一条边最短距离即可。 T ......