题解3175 2015 haoi
题解:【COCI2019-2020#6】 Trener
题目链接 本人于三月二十四日模拟赛本题中使用 $\mathcal O(n^2 k + n k^2)$ 哈希+DP,因神秘常数原因竟打不过 $\mathcal O(n^2 k^2)$,甚至被卡的TLE飞起,怒挂五十分。赛后交了一页的TLE,最后换成自然溢出才能过,~~铭记贰点贰叁~~。 不会吧不会吧不 ......
【思维题、KMP】P3526 [POI2011]OKR-Periodicity 题解
P3526 [POI2011]OKR-Periodicity 题解 前言 一道非常厉害的思维题。看题解得到了一些提示搞出来了。 作为 2011 年的题还是很厉害的。 约定 定义 $s[l,r]$ 为 $s$ 当中下标为 $[l,r]$ 的字符组成的子串。 $st,ed$ 表示字符串的某段前缀和后缀。 ......
训练round1题解
SMU Spring 2023 Trial Contest Round 1 A. 大意: 给出一个仅由0,1组成的字符串,该字符串是多次在首位各加0或1得到,问最短的原始字符串的长度。 思路: 一次操作增加两个字符, 特判字符串长度为1直接输出1. 首尾双指针进行判断,满足条件同时移动,不满足则退出 ......
3 月 22 日测试题解
3 月 22 日测试题解 T1 题意 定义两个长度为 $n$ 的 01 串 $i$ 与 $j$ 的差异值 $d(i, j)$ 为: $$ \sum_{k = 0}^{n - 1}{i_k \oplus j_k} $$ 现在给你 $n$ 个 01 串的集合 $s$,你需要找到一个 01 串 $ans$ ......
Educational Codeforces Round 145 (Rated for Div. 2) - 题解
https://codeforces.com/contest/1809/problems A. Garland 只需要枚举颜色种类数即可。如果颜色为 $2$ 还要枚举一下颜色分布,形如 aabb 的答案为 $4$,形如 abbb 的答案为 $6$,如果形如 aaaa 无解,否则答案均为 $4$。 # ......
[ABC276G] Count Sequences 题解
考虑差分,设 $d_i=a_i-a_{i-1}$,特别的,$d_1=a_1$,那么约束就变成了 $\displaystyle\sum d_i\le m$。 对所有 $i>1$ 有 $d_i\not\equiv 0\pmod 3$。 发现 $d_1$ 非常特殊,于是可以单独考虑 $d_1\equiv ......
ARC070F 题解
前言 题目传送门! 更好的阅读体验? 牛逼构造题。 思路 代码 #include <iostream> #include <cstdio> #include <stack> using namespace std; bool query(int x, int y) { cout << "? " << ......
CSP20230319-4 星际网络II 题解
〇、题目 题目描述 随着星际网络的进一步建设和规模的增大,一个新的问题出现在网络工程师面前——地址空间不够用了!原来,星际网络采用了传统的IPv6协议,虽然有 $2^{128}$ 级别的可用地址数量,但面对广袤无垠的宇宙和爆炸式增长的网络用户数,如此庞大的地址空间也面临了用尽的那一天。 新的通信协议 ......
T324159 卡空间的题目/电脑白吃 题解
https://www.luogu.com.cn/problem/T324159 题目大意: 给定一个大小为 $n$ 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 $\lfloor \frac{n}{2} \rfloor$ 的元素。 并且给定的数组总是存在多数元素。 我们现在希望使用 ......
CF1168C And Reachability 题解 线性dp
题目链接 https://codeforces.com/problemset/problem/1168/C 题目大意 给定一个数组 $a$,从下标 $x$ 能够转移到下标 $y$ 要满足 $x \lt y$ 且 $a_{p_i}, &, a_{p_{i+1}} > 0$,其中 $&$ 表示逻辑与。多 ......
2015-CS
2015-CS 数据库部分 create table [EMPLOYEE]( [EmpNo] varchar(10) not null primary key, [EmpName] varchar(10) not null, [EmpSex] varchar(5) check([EmpSex]='男 ......
【ACM算法竞赛日常训练】DAY2题解与分析【比赛】【数学考试】【简单瞎搞题】
DAY2共三题: 比赛(概率) 数学考试(前缀和与思维) 简单瞎搞题(dp) 视频讲解:https://www.bilibili.com/video/BV1hP411o7RD/ 🎈 作者:Eriktse 🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️ ......
P3489 [POI2009]WIE-Hexer 题解
一、题目描述: 大陆上有 n 个村庄,m 条双向道路,p 种怪物,k 个铁匠,铁匠都在一个村庄里,他可会给你打造他所能打造的所有剑,特定的剑可以对付特定的怪物,每条道路上都可能出现一些特定的怪物,每条道路有一个通过时间。现在要从 1 走到 n,初始的时候你没有剑,要求在经过一条道路的时候,对于任意一 ......
洛谷 P8026 [ONTAK2015] Bajtocja
简要题意 有 $d$ 张初始为空的无向图,每张中都有 $n$ 个点,标号从 $1$ 到 $n$,$m$ 次操作,每次往一张图加一条边,并询问有多少有序数对 $(a, b)$ 使得在全部的 $d$ 张图中 $a, b$ 联通。 数据范围:$1\le d \le 200, 1\le n \le 5000 ......
P4221 [WC2018]州区划分 题解
题目链接 题目描述 给出 $n$ 个城市,$m$ 条边,一个划分合法当且仅当所有划分中的点集和集合中点之间存在的边集所构成的图不构成欧拉回路且联通。 定义一个点集的值为 划分的总值为其中所有点集的值之积,求所有合法划分的值之和。 题目分析 看到数据范围以及题目描述,不难想到使用状压 dp 解决此问题 ......
【ACM算法竞赛日常训练】DAY1题解与分析
DAY1 共四题: 月月查华华的手机:https://ac.nowcoder.com/acm/problem/23053 Rinne Loves Edges:https://ac.nowcoder.com/acm/problem/22598 逆序对:https://ac.nowcoder.com/a ......
CF1630E 题解
题意 传送门 一个长度为 $ n $ 的环状序列 $ {a_i} $ ,其中的数值满足 $ 1\leq a_i\leq n $ ,序列中可能有相等的数。 序列 $ {a_i} $ 的一个排列和另外一个排列本质相同,当且仅当可以通过旋转使它们变得每一项都对应相等。 对于 $ {a_i} $ 的任何一种 ......
LDAP - 题解【模拟】
题面 该题为CCF-CSP认证考试真题,试题编号为202303-3。我参加了这次CSP认证(虽然说认证成绩没有达到预期emmm),原题链接见:202303-3。下面搬运题面如下: 题目背景 西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业,拥有数千名员工。公司内有很多 IT 系统。为了能 ......
题解 CF1149D【Abandoning Roads】
~~看到 $n\le 70$,想到状压 DP。~~ 首先,显然对于一棵最小生成树,每个轻边连通块内部都是一棵树,轻边连通块缩点后点之间的重边也是一棵树。也就是说,缩点后不存在重边组成的环(包括自环),路径一旦离开了一个轻边连通块就再也不会回来了。 于是先洪水填充求出连通块,设共有 $k$ 个连通块。 ......
P4769[NOI2018 冒泡排序] 题解
题面链接 简要题意 求 $\displaystyle{\sum_{i=1}^n\lvert p_i-i\rvert}=$ 冒泡排序最少交换次数的排列 ${p_n}$ 的数量。 Lemmas Lemma 1:冒泡排序最少交换次数等于逆序对数量 证明 考虑冒泡排序的过程交换一次逆序对减少一易证。 Lem ......
SCOI2015 情报传递 主席树+LCA
哈哈哈哈老婆我有出息了,犬犬第一次从思路到代码都是自己一发切了紫题呢~ 好了一眼数据结构。 考虑如何转化第i个时刻有威胁的情报员,若能产生威胁 则说明他们至少在i-c-1这个时刻"出生" 也就是转化为在权值线段树上查询[1,i-c-1]有多少个人。 启发了我们可以先把未来的情报员都弄下来,再记一个他 ......
CF1268D Invertation in Tournament 题解
CF1268D Invertation in Tournament 题解 传送门 CF1442F Differentiating Games 题目大意 给定一个竞赛图,一次操作可以将一个节点相连的所有边方向翻转。求让图强连通的最小操作次数。 竞赛图是一个无向完全图的每条边分配方向后的图。 思路 因为 ......
Edu Round 板刷计划 2. Educational Codeforces Round 2 题解
Change Log: 2023.03.22 开坑. A - Extract Numbers ......
题解 ABC025D【25個の整数】
*3006。 数据范围明示状压 DP,但是涉及到填数不好直接状压,因为我们对每个格子只能记录一个二进制位,不可能知道每个数都在什么位置。 不妨换个思路,不难想到一个二进制位可以用来记录这个位置是否已经填数,只需要利用上这个信息。注意到我们不关心具体填的数是多少,只关心偏序关系,因此可以从小到大填数。 ......
【题解】CF487E Tourists / 圆方树
概念 圆方树是一种基于无向图构造的树。 我们知道,圆方树最早是 WC 上提出的处理仙人掌的东西,用于将树上做法拓展到复杂度正确的仙人掌做法。 但是一些关于点双有性质的题也可以用圆方树转化成树上问题,例如这个。 构造 对于原图中的点,称之为圆点。 对于原图的每个点双,考虑为其虚拟一个对应的结点,称之为 ......
qt+msvc2015 配置文件中文乱码
有个配置文件 config.ini,里面有中文项。 我知道windows上消除中文乱码的方法:https://www.cnblogs.com/warmlight/p/12341673.html 但是现在考虑到跨平台,我不能在跨平台的时候再去改文件编码格式为utf8bom啊。 胡乱试了下,发现这样可以 ......
【题解】Codeforces Round 858(CF1806) A-C,E
比赛体验表示极差,分类讨论相当崩溃,甚至前两个题 $30min$ 才过。 A. Walking Master 题目分析: 慢慢分析一下,看看到底能不能走过去以及走到什么地方就好了。 一个前置知识,$x \to y$,如果只能 $+1$ 或 $-1$ 的最小操作步骤是 $|x - y|$ 代码: 点击 ......
GB/T 7714-2015参考文献规范性写法
根据参考资料类型可分为: 纸质文献类型:专著[M],会议论文集[C],报纸文章[N],期刊文章[J],学位论文[D],报告[R],标准[S],专利[P],论文集中的析出文献[A],杂志[G] 电子文献类型:数据库[DB],计算机[CP],电子公告[EB] 电子文献的载体类型:互联网[OL],光盘[C ......
「题解」ABC294Ex K-Coloring
感谢 ZCPB 的指导! 可以不断删一度点和二度点,来对图进行简化。删完之后一条边有两个权值,分别代表两端颜色相同/不同时这条边对答案乘上的系数。(其实这个并不必要) 对于每个连通块单独考虑。如果点数很小,可以直接枚举颜色的最小表示,也就是爆搜一下集合划分。点数很多的话,非树边会比较少,所以就对于每 ......
牛客小白月赛 68 题解
网址:https://ac.nowcoder.com/acm/contest/51958 A - Tokitsukaze and New Operation 先将 $a,b$ 的每一位分解,如果位数不一样直接 $-1$。 设 $a,b$ 有 $n$ 位,$a$ 的第 $i$ 为 $x_i$ & $b ......