KDOI

CSP前的晚自习本来想打板子的，但是没有做题的欲望，就来写题解了。 小清新 dp。 思路 先观察每一个操作，发现操作一最特殊，思考下它有什么性质。如果我们进行了一次以上的操作一，一定不是最优的。因为每次都会把前 \(i\) 个数都变成零，重复之后就会覆盖原来的操作，回到第一次操作的初始状态，这样前 ......

一个区间合法的充要条件是存在 \(x\) 满足其为区间按位或，并且《\(x\) 左侧所有数或起来》《\(x\) 右侧所有数或起来》二者有其一为 \(x\)。 扫描线扫右端点，不同的按位或将左端点分为 \(\log A\) 个区间，对于每个区间 \([l,r]\) 先在区间按位或 \(v\) 在序列中 ......

我会组合数！ 首先发现同一列只有被不同的横块填或被一个相同的竖块填，且用竖块填完1列之后，会分成两个封闭的长方形，而长方形内部则用横块来填充。 先考虑一个子问题，某个 \(2 \times n\) 长方形内只用 \(k\) 个 \(1 \times x\) 的横块填的方案数，显然有 \(\sum\l ......

题目传送门 思路： 按题意算出总分。 如果已经过了分数线，输出，结束程序。 否则开始循环，如果这道题已经全部对了，输出。 否则，判断可不可以过分数线，输出。 Code： #include<bits/stdc++.h> using namespace std; int n,score,a[105],w ......

P9744 「KDOI-06-S」消除序列 我们可以很容易发现操作 1 只可能使用一次。 先考虑序列固定的情况下的做法。 我们设 \(f_i\) 表示 \(1\sim i\) 用操作 1，\(i+1\sim n\) 不用的最小值。（\(i\) 可以取 \(0\)，表示不用操作 1） 对于前半部分，先 ......

P9745 「KDOI-06-S」树上异或 参考：https://www.luogu.com.cn/blog/710100/p9745-kdoi-06-s-shu-shang-yi-huo-jian-yao-ti-xie 其中，转移中一部分考虑的是断边，那么两部分分离，乘法原理；如果连边，需要异或为 ......

题目 思路： 先计算总分数 \(sum\)，\(c_i=\frac{100}{a_i}\) 为每道题的每个测试点分数。 如果总分数达到 \(Au\) 线，直接输出 Already Au. 。 否则计算到达 \(Au\) 线还需多少分 \(p\)，遍历所有题，求出每道题的失分，如果失分大于等于 \(p ......

@目录DesciptionSolutionCode Desciption 给定一个长度为 \(i\) 的序列 \(v_1,v_2,\dots,v_n\)，初始时所有元素的值都为 \(1\)。 对于下标 \(i\) 有 \(3\) 种操作： 将 \(v_1,v_2,\dots,v_i\) 的值变为 \ ......

目录P9744 「KDOI-06-S」消除序列P9745 「KDOI-06-S」树上异或 P9744 「KDOI-06-S」消除序列 发现这是一道贪心题，第一种操作只会使用一次，也就是在最开始的时候进行清零操作，从而使得整个前缀都变成0。考虑两种情况，一种是前缀全部为1，另一种为0，分别考虑转移即可 ......

原题 挺好的树形 dp ，正好 dp 不太熟练，练习一下 赛时只想到了暴力和\(X \leq 7\) 的链的部分分，过于 naive 不说了 先考虑链的情况，既然是二进制考虑按位拆分。设 \(g_{i,j,0/1}\) 表示以 \(i\) 为根，从 \(i\) 点连通块的疑惑和第 \(j\) 位为 ......

题目传送门 这道题在比赛时先花了一个小时理解好题意才打了一个 \(70\) 分的 \(O(n^2)\) 暴力。下午刚起床，有点困，还没进入状态，打得挺慢。 具体地，会发现操作实际上是在这个长度为 \(n\) 的序列找一个点 \(i\)，将 \([0,i]\) 通过操作 \(1\) 全变 \(0\)， ......

「KDOI-06-S」 A.「KDOI-06-S」消除序列 赛时写了一个 \(O(nq)\) 的线性 DP，喜提 60 分。 注意到如果操作 1 被使用，则一定只会使用一次，而且在最优策略中一定是第一次使用操作 1。则我们可以通过以下方式进行操作，使序列满足条件： 首先执行 \(a_i\) 和 \( ......

P9745 「KDOI-06-S」树上异或 题解 \(x_i = 0\) 这题一看就不是很可做，先考虑部分分。 对于一条链的情况，我们可以枚举上一个断边的位置，然后转移。 一看数据范围，估计和值域有关，所以考虑 \(x_i = 1\) 的部分分，如果全部点权都是 1，那么一种方案只有 0 和 1 两 ......

Saintex 1分钟就切啦,有什么好说哒! 首先可能想到设 \(c_{i,j}\) 表示(i,j)被操作的次数,那么答案很好求。 但是这个数量并不好记录。 如果仅仅钦定(i,j)从小到大之类的东西也不好搞。 所以考虑钦定其他的东西。 设 \(dp_{i,j,k}\) 表示前 i 位,有 j 个操作 ......