初赛2007 csp

9.12 CSP 模拟 36 T1 博弈 如果路径上最小值数量为奇数，那么先手第一个取最小值必胜。如果是偶数，那么双方都尽量避免第一个取最小值，变成了删去最小值不能操作的必败，就是子问题，归纳发现先手必败当且仅当所有值的出现次数都是偶数。 关于偶数的统计想到异或哈希，由于重复路径异或后贡献消失，直接 ......

复杂度计算 ①.主定理 （$T(n) = a T(\frac{n}{b}) + f(n) $ 型） ②. 分层 (\(T(n)=k\sqrt{n}T(\sqrt{n})+n\) 型) 相当于将 \(n\) 分成若干层,层数 \(c\)。 最底层的大小大约为2（因为大小为1时不好计算，且2很接近1了） ......

题目链接：题目 20. ......

T2暴力也能过？ A. 斐波那契树 一眼看上去有点神奇，但是仔细想一想，其实也没有什么。 对于一棵生成树，树上有白边和黑边，我们会发现，对于白边的数量，会有一个最大值和最小值（这不废话吗），而且可以证明，在这个区间内的所有数，总有一种方案可以符合。 证明，可以先从下界，考虑用一个白边去换一个黑边，发 ......

一.2. 错误原因：不会 解析：real代表实际运行时间，user代表用户态运行时间，sys表示内核态运行时间，故选A 5. 错误原因：不会 解析： 基数排序的思路类似于桶排序，故选A 9. 错误原因：不会 解析： 这个问题可以转化成圆排列问题，公式为A(n-1,n-1)，即(n-1)!,要考虑从两 ......

A. 斐波那契树 发现在最终的生成树中可以出现的白边数量为一个区间，所以求其边界即可。 最大 / 小化生成树中白边的数量可以将其边权置为 \(0 / 1\) 后求最小生成树即可。 不过其实不用显式排序，将边按颜色种类存储，然后先考虑一个颜色的边集即可。 复杂度 \(\mathcal{O}(\left ......

9.10 CSP 模拟 34 T1 斐波那契数 由于边权只有 \(\{0,1\}\)，因此生成树的边权和取值连续，求出最小和最大判断即可。 点击查看代码 int t; int n,m; struct edge{ int u,v,w; edge()=default; edge(int u_,int v ......

T1：算术计算 \(T\) 组数据，每组数据给出 \(n, m, p\)，求 \(\sum\limits_{i=1}^n ia^i\) 对 \(p\) 取模的值。 部分分 直接暴力求和可以拿到 \(15\) 分 另外 \(10\%\) 的数据 \(a = 1\)，不难通过数据计算得到答案为 \(\f ......

Genral 惊险刺激。但还是菜。 统计： 得分 得分率 挂分率 AC 数 200 50% 0% 2 各题目详情： 题目 A B C D Total 期望得分 100 0 100 0 200 实际得分 100 0 100 0 200 挂分 0 0 0 0 0 A \(n≤4\)？直接搜！ 于是就没了 ......

一.1. 错误原因：没读题 解析： ls是list的缩写，用于列出当前目录下所含的文件和子目录 cd是change directory的缩写，用于改变文件目录 cp是copy的缩写，用于复制 8. 错误原因：计算错误 解析： 一棵含有n个节点的二叉树的高度至少为floor(log2n)+1,还有一种 ......

LAST UPD:2023/09/09 内容非常杂乱，算是初赛前的总结吧qwq 排序算法比较 插入排序，冒泡排序，选择排序 ： \(O(n^2)\) 其他非线性排序的时间复杂度为 \(O(n)\) 线性排序的时间复杂度为 \(O(n)\) 。 稳定性比较： 插入，冒泡，二叉树，归并以及其他的线性排序 ......

其实是我 Li-Chao-Tree 哒！！ 考虑转移 \(f_x = \min f_{anc} + (d_{x} - d_{anc})p_x + q_x\) 其中 \(anc\) 为 \(x\) 的祖先，然后满足 \(d_{anc} \geq d_{x} - li_{x})\)。 考虑如果用权值线段 ......

题目链接 以下设 \(B\) 为一个阈值，同时也表示值域分块的块长。 先考虑所有 \(b\) 都不为 \(0\) 的情况。对于一组询问，我们设一个 \(x\) 表示：当前已搬完所有 \(a\leq x\) 的砖。那么每次只可能是以下两种情况之一： 有至少一摞砖在当前这个单位时间内被搬完 拿 \(x\ ......

一、十进制数 \(114\) 的相反数的 \(8\) 位二进制补码是： A. \(1000 1110\) $\ \ \ \ \ $ B. \(1000 1101\) $\ \ \ \ \ $C. \(01110010\) $\ \ \ \ \ $ D. \(01110011\) 点击查看答案 根据原 ......

1. P3959 [NOIP2017 提高组] 宝藏 发现 $n$ 是很小的，考虑状压。 我们先记录下当前的树包含了哪些节点，然后因为转移时肯定会需要经过了多少边，也就是树的深度。 我们记录 $\text{expand(i)}$ 表示当前选的集合为 $i$ 时，扩展一次后的集合。$\text{roa ......

`2023-09-07 16:21:33` `2023.9.7 15:46` ## 前言 算是旧事重提了吧，过去了快一年才想着来订正，不过不得不说我去年 -S 拿了挺多分的，虽然就想出了一道正解。 # T1 这题我考场上暴力乱搞拿了 60。然后听说有什么 meet in the middle 的算法 ......

## Day -3 ###### 下午在学校打了场模拟赛，结果炸了，两个部分分的算法都打挂了，发现好多东西忘了，有点慌。 ## Day -2 ###### 教练强调了一些注意事项,紧张感++。 ### Day-2 ###### 又是一天无聊的文化课，已经开始期待在杭州的充实（摸鱼）生活了 ### D ......

2022年，总算是拿到了的``CSP-J 1=``。好吧，压线（算是）。 ``100+60+0+15=175`` HN 分数线``170``。真的很悬。。。 ## 情况 ### T1 so water。10分钟就切了，本来看见题目还以为要快速幂（忘了），吓死了。 ### T2 看见 $m$ 的范围， ......

# [[CSP-S 2022] 策略游戏]( https://www.luogu.com.cn/problem/P8818) ## 题意： 给定两个序列A,B。每次先从A序列规定区间内取出一个数，再从B序列规定区间内取一个数，答案为两数乘积。A希望答案尽可能大，B希望答案尽可能小。 ## 思路： # ......

1 #include <iostream> 2 using namespace std; 3 4 int main() { 5 int a,b; 6 cin>>a>>b; 7 long long ans=1;//注意long long ,不能用int 8 for(int i=1; i<=b; i++ ......

考虑一个长度为 $L$ 的最长上升子序列 $P$，以它的第 $i$ 个元素 $a_{x_i}$ 开头的最长上升子序列长度至少为 $L-i+1$。反之，若一个数满足以其开头的最长上升子序列长度至少为 $L-i+1$ 则这个数必定可以作为 $P$ 的第 $i$ 个元素。 所以我们可以先倒着跑一遍最长下降 ......

一.1. 错误原因：不知道 解析： 正确答案B 星型结构，类似于一颗星星，优点是节省材料，弊端是，如果源点计算机故障，那么网络就会瘫痪。 环形结构，类似于一个环，环上有一些端点，每个端点对应着一台计算机，弊端是，如果在环上断了2条边，网络就会瘫痪 网状结构，就是现在的因特网(Internet)，类似 ......

## T1 以下哪一种设备属于输出设备 - A. 扫描仪 - B. 键盘 - C. 鼠标 - D. 打印机 答案 **D** ## T2 下列四个不同进制的数中，与其它三项数值上不相等的是 - A. $(269)_{16}$ - B. $(617)_{10}$ - C. $(1151)_8$ - D ......

## T1 中国的国家顶级域名是 - A. cn - B. ch - C. chn - D. china 答案 **A** 域名级数是指一个域名由多少级组成，域名的各个级别被“.”分开，最右边的为顶级域名。顶级域名，又称一级域名，常见的有“.com”、“.org”、“.net”、“.cn”等，二级域 ......

``` = 80) { die("太长了不会算"); } $blacklist = [' ', '\t', '\r', '\n','\'', '"', '`', '\[', '\]']; foreach ($blacklist as $blackitem) { if (preg_match('/' ......

[题目传送门](https://www.luogu.com.cn/problem/P5665) ## 题目描述 2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $n$ 组数据，数据从 $1 \sim n$ 编号，$i$ 号数据的规模为 $a_i$。 小明对该 ......

# P1463 [POI2001] [HAOI2007] 反素数 题解 可以发现，最大的不超过 $n$ 的反素数就是 $1\sim n$ 中因数最多的数字。 > 证明： > > 设 $x, x\in[1, n]$ 为 $1\sim n$ 中因数最多的数字，则 $x #define x first # ......

不可以，总司令。 [题目传送门](https://www.luogu.com.cn/problem/P8819) # 思路 首先，当图中每个点出度为 $1$ 时，从任一点出发必定会进入环。 证明：假设有一点不符合，则沿着它的出边一直走会到一个出度为 $0$ 的「终点」，与每个点出度为 $1$ 矛盾。 ......

# 9.1 赛前集训的前一天。 学校报道的日子，大半天都在 yzsy 上课。晚上回来没有颓废~~（很难得啊）~~，把线性基学了一下，然后就开始补数学，从 $9$ 点补到 $10$ 点。然后只写了几章，看来效率不是只有一点点底啊。 然后写了一篇脸滚键盘，总结了一下前半段 OI 生涯所犯的一些错误，汲取 ......

一.7. 错误原因：不知道 解析： 快速排序在理论上最低的时间复杂度为O(n),但实际最低的时间复杂度为O(n log n) 二.1. 错误原因：漏项了 解析： 这棵树最少有12层，但题目是问可能是几层，所以还可能是2011层 5. 错误原因：漏了一种情况 解析： 这道题的树有两种，所以答案也有两种 ......