初赛2007 csp

集合专练？？？？？逆天！！！！！！！ # T1 卷 逆天！！！！！！！！！！！！！！！！！！！！又没看懂题。独立集指集合里的每个点不相连呜呜呜呜呜，我还以为是剩下的点互不相连，直接寄掉。 式子好推，就不推了，咕。 ```cpp #include #include #include #include ......

今天T1终于看懂辣。。。。但今天名次最低QAQ。T1没算空间复杂度，直接炸QAQ # T1 Coprime 2 今天T1确实简单，将输入的数的质数公因数用埃氏筛筛出来，用一个数组存下来。每次将质因数的倍数用 $flag$ 存下 $true$ ,表示这个数存在因数与输入的数重复的情况，让后就没有辣。 ......

#### 闲话 今天老吕从国赛，带来一个消息：“省选可能取消，完全看 NOIP 成绩”。 不过对我没什么影响，反而还开心一些。 ## A. Coprime #### 题目大意 给定一个长度为 $n$ 的数列 $a$，要求出 $1 \sim m$ 中与 $a$ 中的所有元素互质的数。 数据范围：$1\ ......

#「赛后总结」20230727 CSP 模拟赛 点击查看目录 > [TOC] 2023 年 7 月 28 日 20:04：早上就写完了但忘了发了。以下内容均写于「2023 年 7 月 27 日」。 前两天题还没改完呢，有空补上。 情商有待提高。 破防了，今天看啥感觉都在 D 我。 ![image]( ......

### T1 卷 简单题，比较转化为 $\log$ 比较，然后就是没有上司的舞会 点击查看代码 ```cpp #include #define int long long #define double long double #define N 200005 using namespace std; ......

# Solution ## T1 出现次数 ### 原题链接 [**4102: 出现次数**](https://noip.ac/rs/show_problem/4102 "4102: 出现次数") ### 简要思路 利用类似前缀和的 “后缀和” 来记录下每个数后面有几个未重复出现的数，定义一个 $f ......

### T1 排序 [基本是原题 CF1375E](https://www.luogu.com.cn/problem/CF1375E) 好像是简单题，考虑这个排列 $\pi$ 的逆排列 $\pi^{-1}$（如果排列是 $a_i$，则逆排列为 $b_{a_i}=i$），因为逆序对的定义是序列编号和数 ......

## A. 卷 一道可爱的树形 DP 喵！ 题目保证了 $w_i$ 是在给定范围内随机生成的，所以不会炸精度。 首先明确题意，**是求出最大乘积独立集之后取模，而不是边乘边取模**。边乘边取模会炸，例如 $10^9 +8$ 对 $10^9+ 7$ 取模后小于 $2$，但显然 $10^9 + 8 > ......

### T1 第一题 贪心，观察肯定是从较浅的点上来一个士兵或者从根节点来一个士兵，用 set 或者 vector 启发式合并维护这个过程即可 点击查看代码 ```cpp #include #define N 100005 #define inf 0x3f3f3f3f #define pii pai ......

[toc] # NOIP初赛备考 ## Week 1 8.14~8.20 ### 1.CSP-J 2022 【总结】 【传送门】https://zhuanlan.zhihu.com/p/565894794 ### 2.CSP-J 2021 【总结】 【传送门】https://ti.luogu.com ......

## CSP-J $T1$ 一眼看出直接快速幂，其实直接乘就可以，特判一下$1，2$以上次数不会超过$logn$，看看是否大于零就行了，$20min$解决。代码： ```cpp #include #define int long long using namespace std; int a,b; ......

CSP-S (70+25+40+0=135,挂了 考试策略 T1->T2->T4->T3 考场实况（20min(看题)70min+60min+30min+60min） T1 DFS打出暴力K=0的特例和小点，花了一点时间检查时间复杂度。 T2 打了一个前缀和优化暴力常数，错了，应该直接打暴力一遍扫过 ......

# T1 题目描述 给出一个长为的排列，请你把它排序。排序方法是：定义一种操作表示交换，先找到所有逆序对满足，任意排成一个排列，使得按照这个顺序操作以后是单调递增的。如果有多种排列，输出任意一种。 输入格式 第一行输入，第二行输入数组。保证是排列。 输出格式 如果不存在答案，输出。 否则，第一行输出 ......

~~新系列，系列名叫垫底模拟，厉害吧~~ ## T1 排序 最开始想的都是很简单的东西，就是把最大的数放到最后嘛，然后发现显然不行，比如说： ``` hack: input: 5 1 5 3 2 4 output: 3 4 2 5 2 4 2 3 ``` 题目很明显地告诉我们先输出逆序对数 $m$ ......

# [[CSP-S2020] 儒略日](https://www.luogu.com.cn/problem/P7075) 本题需要掌握正确的方法，不然写起来很麻烦。 在格里高利历中，日期计算以400年为周期，每400年都有恰好146097天。 预处理出400年内的情况，将年份模400即可快速得到答案。 ......

悲，昨天存本地忘发了，今天又不想写模拟 5 的。 考了四道 ARC 就离谱。 ## A. LIS to Original Sequence 首先考虑 $k = 1$，唯一的方案就是倒序输出 $1$ 到 $n$。 我们可以想到，这道题的方法是向已经确定的序列 $A$ 中插入其他数。 对于一个数 $x( ......

posted on 2022-09-13 15:19:49 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/479462) ## problem 一个字符串 $a$，一开始全空，支持区间修改为同一字符，后修改的覆盖先修改的，求将字符 ......

# Day 1：基础算法 ## 枚举 从可能得集合中一一尝试统计贡献。 ## 模拟 模拟题目中要求的操作 ### NOIP2014 生活大爆炸版石头剪刀布 洛谷链接：[**P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布**](https://www.luogu.com.cn/pro ......

#「赛后总结」20230724 CSP 模拟赛 点击查看目录 > [TOC] 想听歌，想看巨人，但是没有条件。 ## 总结。 rk1 三个首杀，前二没有 HZOI 土著，前三没有 HZOI 2022 人，咋整的呀？ T1 5min 过掉样例交了一发，然后手玩一个样例不小心 Hack 掉了，改完了手玩 ......

今日推歌： 9. Serenade in G ‘Eine kleine Nachtmusik’ K525 - Wolfgang Amadeus Mozart 今天比赛直接搬的 ARC 125，126 的 CD 题，那这样我也能出模拟赛（ 但是为什么 HZOI2022 都不写比赛题解，差评 今天被 H ......

## Day1比赛 ### T1 #### [方差](https://noip.ac/rs/show_problem/4063 "方差") 求和可以用前缀和。 求平均值时，特判是否整除而输出结果。 求方差，我们直接用他给的公式以分数形式算出结果，维护两个分子和分母，通分相减后特判输出。 注意要输出最 ......

t3：**不要随便用 map** t4: **~~代码转移要删全~~** 首先考虑暴力，类似线段树，首先你要先dfs出每个节点子树的左右节点，然后修改查询时要考虑左儿子右边界是否大于查询左边界，右儿子左边界是否小于查询有边界，进行 $dfs$ $（46pts）$ 点击查看代码 ``` #includ ......

今天感觉很热，但是天气转凉的时候我也该退役了吧。 今日推歌： 透明哀歌 - n-buna / Gumi echo - Crusher-P / Gumi English >>> 歌词 The clock stopped ticking,时钟停止发出嘀嗒声 Forever ago.在很久以前 How l ......

感觉像是 noi 模拟赛多了个 p ### T1 F 咋做都行，但是考场上的正确做法被后来优化 RE 了，痛失 60pts 其中一种做法是考虑只有 $a_1\oplus b_i$ 有可能成为答案，然后验证即可 ### T2 S 定义 dp 状态 $f_{i,j,k,0/1/2}$ 为用了 $i$ 个 ......

# 「赛后总结」20230722 CSP 模拟赛 点击查看目录 > [TOC] 吓死我了我还以为 K8He 不更博了。 为啥前天模拟赛不写啊？ 打过，没参加。 为啥昨天模拟赛不写啊？ 一些原因没空打。 ![image](https://img2023.cnblogs.com/blog/2480572 ......

题目： 题目描述 设有 n*m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。 输入格式 第一行有两个整数 n, m。 接下来 ......

## A. 回文 $20$ 多分的纯暴力搜索，$A_{i,j} = A_{i-1,j+1}$ 可以判完回文直接递推出路径数，共 $42 \text{pts}$。 正解 $DP$。 回文可以转化一下思路，两个人分别从 $(1,1),(n,m)$ 出发，走的路径相同的方案数。 设计 $dp[i][j][ ......

T1 洞穴 本质上是给出树上两点之间的距离，还原树的结构。 可以直接$floyd$来判定。 进一步的可以对边进行排序每次取最小的加入集合即最小生成树的过程保证正确性。 T2 小度养小猫 本质上是求出一个贪心的顺序使得代价最小。 每个代价为$(t_i^2-i^2)c_i$ 展开$t_i^2c_i-i^ ......

第一道 AC 自动机 + DP 题。 题目链接：[P4052 [JSOI2007] 文本生成器 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P4052) 利用容斥原理的思想，答案就是所有串的数量减去不可读的串的 ......

## A. F 考场没想出来，寄。 既然 $x$ 需要满足所有的 $a$ 和 $b$ 成立，所以我们把 $a_1$ 与 $b$ 数组异或一遍就可以直接得到所有 $x$ 的预备役。 可能符合条件的 $x$ 最多也只有 $n$ 个，那就可以直接把剩下的 $a$ 与 $x$ 进行异或，看 $b$ 中是否存 ......