题解1545 cf
CF1213 合集
CF1213A Chips Moving 考虑是一道非常简单的入门题 就是奇数的个数和偶数的个数取 \(\min\) 即可 code #include<bits/stdc++.h> using namespace std; const int NN = 108; int n; int a,cnt[2 ......
CF1680F Lenient Vertex Cover 题解
CF1680F Lenient Vertex Cover 题解 这道题和「JOISC 2014 Day3」电压非常类似,或者说就是一道题。 题意就是给你一个图,问能否对所有点黑白染色,允许最多一条边的两个顶点都染成黑色。 黑白染色后其实就是一个二分图,那如果有一条边的两个顶点染成黑色,就是说去掉该边 ......
题解:CF237D
题目传送门 思路 构造 \(k\) 个集合,使这些集合满足以下性质: 集合的并集为 \(V\)。 对于树 \(s\) 中的任意一条边 \((a,b)\),都能在 \(k\) 个集合中找到一个集合 \(x\) 使得 \(a,b\in x\)。 对于树 \(s\) 中的任意一个点 \(a\),所有在 \ ......
题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】
题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】 problem 首先是有一个字符串 \(S=\texttt{"0"}\),做无限次“将 \(S\) 的每一位取反接在 \(S\) 后面”的操作,形如 \(S=0110100110010110\cdots\)。 另外给一个 ......
题解 ABC267F【Exactly K Steps】
Robin 有一棵树,他有 $m$ 次询问,每次询问他给你 $u,k$,你需要输出树上的一个节点 $v$ 满足 $dist(u,v)=k$,或者报告无解。
$dist(u,v)$ 表示树上 $u$ 到 $v$ 的最短路径的边数。$n\leq 10^5$ ......
Math teacher's homework 题解
preface 网上的题解看不懂,看代码看懂了 :) solution 考虑 \(\mathrm{x_i}\) 的倒数第 \(\mathrm{low_i - 1}\) 位到倒数第 \(\mathrm{1}\) 位可以乱选(选 \(\mathrm{0/1}\) 都满足 \(\mathrm{x_i \l ......
CF1168C And Reachability
CF1168C And Reachability And Reachability - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 目录CF1168C And Reachability题目大意思路code 题目大意 给定一个长度为 \(n\) 的数组 \(a\) 。 你可以选择一个 ......
题解整理
CF1740A CF1740B CF1740D CF1711B CF1253B CF1080B CF1237A CF1743A CF1743C CF1743B CF1370B ......
YACS 2023年9月月赛 甲组 题解
题目链接1 题目链接2 题目链接3 榜单终于公布了,这应该是第二长的榜单公布吧。(最长的一次是去年八月,拖到九月开始后才公布) T1 是傻逼数据结构不说了吧,对于每个点枚举以他为角的 $k\times k$ 的四个正方形算一下点的数量,用 $cdq$ 或者扫描线都行。 看这个题目编号是 $81$,看 ......
CF1168C
CF1168C 题面及数据范围 Ps:链接为洛谷OJ。 发现对于每一个 \(i\) 需要求经过若干次转移使第 \(j\) 个二进制位为 \(1\) 的最近位置 \(k\),查询时,当 \(k \leq y\) 便可以到达。 下文的位无特殊说明位均指二进制位。 设 \(f[i][j]\) 为 \(i\ ......
CF1548E Gregor and the Two Painters
Day \(\text{叁拾肆}\)。 DS 写不动了,标题也取不动了www。 类似 Day 1 CF1270H Number of Components,每个连通块中选出一个代表的点。令一个连通块内所有点按照 \(v_{i,j}=\{a_i+b_j,i,j\}\) 排序,对最小的 \(v_{i,j ......
【codeforces】cf880div2 vp小结
碎碎念 多测要清空!清空从0开始循环!!!!!!!爆哭 不知道因为初始化和清空罚了多少次了呜呜呜呜呜 这次真的真的记得清空了,但是因为一直习惯下标从1开始所以导致for循环清空的时候a[0]没有清空 A和B简简单单的两个签,但是C的难度就突然升高,补题的时候发现1700的时候真的...犹豫了一下要不 ......
P9744 消除序列 题解
本题有多种解法,我这里先讲一个我的考场做法吧。 切入点 我们发现我们至多使用一次操作一,而剩下部分的 \(0\) 肯定是依靠操作二补全,操作三的作用只是用来填补操作一的空白的,所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三,后一段用操作二。 思路1 一开始考虑暴力 \(O(n)\) 枚 ......
CEIT 23练习编程题 题解
本文部分题目提供c/c++两种解法,顺便可以让你们知道c++在面对某些题时的优势 部分题目提供多种解法 日期格式化 C #include <stdio.h> int main(){ int m,d,y; scanf("%d-%d-%d",&m,&d,&y); printf("%04d-%02d-%0 ......
【题解】「KDOI-06-S」补题
「KDOI-06-S」 A.「KDOI-06-S」消除序列 赛时写了一个 \(O(nq)\) 的线性 DP,喜提 60 分。 注意到如果操作 1 被使用,则一定只会使用一次,而且在最优策略中一定是第一次使用操作 1。则我们可以通过以下方式进行操作,使序列满足条件: 首先执行 \(a_i\) 和 \( ......
[COCI2015-2016#4] ENDOR 题解
[COCI2015-2016#4] ENDOR 题解 首先要发现一个很重要的性质,那就是两只变色龙碰撞后回头,等效于两只变色龙继续往前走,其中向右走的颜色不变,而向左走的要改变颜色。 那这样就有一种 \(O(n^2)\) 的做法:对于向右的变色龙,直接贡献答案;对于向左的变色龙,我们按照碰到的先后顺 ......
CF1886
A 给你一个正整数 \(n\),问是否存在 \(3\) 个正整数 \(a,b,c\) 满足 \(a+b+c=n\) 且 \(a,b,c\not\equiv 0 \pmod{3}\)。 分类讨论: 如果 \(n \not\equiv 0 \pmod{3}\) :若 \(n\le 5\) 则无解,否则可 ......
【题解】AtCoder-ARC167
AtCoder-ARC167A Toasts for Breakfast Party 一定不会有空盘,问题转化成 \(2m\) 个数,其中 \(2m-n\) 个是 \(0\),这样一定是最大值和最小值一起,次大值和次小值一起,以此类推。 提交记录:Submission - AtCoder AtCod ......
CF1119F Niyaz and Small Degrees 题解
原题 翻译 首先 \(O(n^2 \log n)\) 的 dp 是 simple 的,我们设 \(dp_{i,0/1}\) 表示以 \(i\) 为根, \(i\) 到 \(fa_i\) 这条边删/不删的最小权值和。转移是一个非常 trick 的问题,只需要假设所有都选 \(dp_{i,0}\) ,然 ......
CF27D Ring Road 2
好一眼的题,据说出题人给的做法不是2-SAT,因此才会有这样的数据范围,但这个模型yysy实在是太典了啊喂 不难发现每条边的取法就是两种,并且内部和外部的边之间绝对不会相交,因此考虑使用2-SAT模型 枚举两条边\(i,j\),如果\(i,j\)同时放在一边会产生冲突,就钦定两者的状态必须相异,然后 ......
CF553C Love Triangles
很有意思的一个题,想了一会才发现解题的关键 首先我们注意到对于某个大小\(\ge 3\)的连通块,其实连通块内的所有边的颜色都会被已知的边唯一确定 而不同的连通块间的连边方式有两种,因此设连通块个数为\(tot\),最后的答案就是\(2^{tot-1}\) 但还要考虑判掉不合法的情况,注意到不管是\ ......
CF1108F MST Unification
很丁真的一个题,权当复习下树上倍增的写法了 考虑先给图求出一个MST,那么很容易发现对于每条非树边\((u,v)\),它的权值必须严格大于MST上\(u,v\)之间所有边的权值,否则就可以用这条非树边来替换某一条树边 因此直接倍增维护树上两点间最大边权即可,复杂度\(O(n\log n)\) #in ......
CF549B Looksery Party
这些题都是上周五写的了,周末两天因为比赛都没来得及写博客,只能到周一来补一补 这题做法很简单,考虑如果当前状态中\(\{a_i\}\)不含有\(0\)的话就已经得到一组合法解了 否则我们找到某个\(a_i=0\)的点,钦定让\(i\)这个人去派对即可,这样一定可以满足\(i\)这个人的条件,同时更新 ......
P9745 「KDOI-06-S」树上异或 题解
P9745 「KDOI-06-S」树上异或 题解 \(x_i = 0\) 这题一看就不是很可做,先考虑部分分。 对于一条链的情况,我们可以枚举上一个断边的位置,然后转移。 一看数据范围,估计和值域有关,所以考虑 \(x_i = 1\) 的部分分,如果全部点权都是 1,那么一种方案只有 0 和 1 两 ......
[ARC167D] Good Permutation 题解
题意 对于一个长度为 \(N\) 的排列 \(Q\),定义其为好的,当且仅当 对于任意整数 \(i \in \left[1, N\right]\),在进行若干次操作 \(i \leftarrow Q_i\) 后可以得到 \(i = 1\)。 给定一个排列 \(P\),定义一次操作为交换两个数。定义 ......
UVA12046 题解
前言: 有些虚高,建议降蓝。感觉比 CF55D 要简单。 题目大意: 定义一个数为好数,满足以下要求: 每个数位都能整除原数。 每个数位都小于等于 \(6\)。 求长度为 \(n\) 的好数有多少个。 思路: 首先,\(0\) 整除任何数都没有意义,可以不枚举。其次,要满足条件二,所以每个数位可以只 ......
UVA1366 Martian Mining 题解
这个题可以用动态规划解决。 令\(sbe_{i,j}\) 为第 \(j\) 列 \(1\) 至 \(i\) 个格子 \(BE\) 矿总和,令\(snw_{i,j}\) 为第 \(i\) 行 \(1\) 至 \(j\) 个格子 \(NEW\) 矿总和。 \(dp_{i,j,0}\) 表示为以第(\(i ......
CF1873E Building an Aquarium 题解
这题看到第一眼就是二分。 单调性 二分最关键的东西是单调性在哪。单调性是如果高度越高,需要的水就越多,高度越矮,要用的水越少。 不难得出代码: check 函数: int check(int mid){ int sum=0; for(int i=1;i<=n;i++){ sum+=max(0ll,m ......
P8854 [POI2002] 超级马 题解
这题其实就是搜索,不知道怎么评绿的。 题意 有一个大小无限的棋盘,有一只马,给定 \(n\) 种跳法,判断马是否能跳到棋盘所有点。 题解 搜索马是否可以跳到他上下左右的四个点,因为只要能跳到这四个点,就可以以这四个点为基础跳到其他所有的点。 这里有一些细节需要处理: 因为每次操作能是横纵坐标加减 1 ......