题解 联盟noip
CSP-S 2023 T1 题解
CSP-S 2023 T1 题解 很简单,我们只需要暴力枚举五位密码,每次判断拨一个齿轮和两个齿轮能达到的状态数,如果等于 \(n\),答案 \(+1\)。时间复杂度 \(O(10^5 \times 5n)\)。 code #include <iostream> #include <algorith ......
qbxt23国庆刷题Day2 题解
Day2 \(100+96+60+70=326,rk1\) T1 签到题 暴力 T2 莫比乌斯反演题 首先容易想到枚举最大公约数是多少,不妨设枚举的 \(\gcd=g\) ,则我们可以开一个桶 \(b_i\) 表示 \(i\) 倍数的数有多少个 对于每个固定的 \(g\) 答案为 \(\large ......
[CSP-S 2023] 消消乐 & CF1223F 题解
LG9753 CF1223F 我们称一个字符串是可消除的,当且仅当可以对这个字符串进行若干次操作,使之成为一个空字符串。其中每次操作可以从字符串中删除两个相邻的相同字符,操作后剩余字符串会拼接在一起。 You are trying to push array elements to the stac ......
【2023.11.08】NOIP2023模拟试题-30
前言 数论迎我归,数学送我葬 组合数学不容易,又有 DP 当 T3 刚爆零,T4 又遭殃 OI 路上怅前望,且行且彷徨 T1 最大公约数 T1 应该想一想就会,接下来我们讨论是怎么减去他的复杂度的。 题目的关键在于,如果根据给出的 \(a\) 推出 \(\gcd\) 的话,就会有 \(9\times ......
2023NOIP A层联测27 A.kotori
2023NOIP A层联测27 A.kotori 目录2023NOIP A层联测27 A.kotori题目大意思路code 题目大意 琴里的飞船中有 \(n\) 个人,其中有 \(n - 1\) 个通道,所以飞船的内部是一个树形结构。每个人从 \(1-n\) 编号,编号越小代表这个人的投票经验最丰富 ......
CF351B Jeff and Furik 题解
summarization 有一个长为 \(n\) 的排列 \(p\), 现有甲乙两人轮流执行操作,甲是先手: 甲每次可以交换 \(p\) 中相邻的两个数 \(p_i,p_{i+1}\) 乙每次等概率执行下面两种操作的一种: 选择一对 \(p_i,p_{i+1}\),且 \(p_i\le p_{i+ ......
2019 CCPC Harbin 哈尔滨 E 题 Exchanging Gifts 题解
2019 CCPC Harbin E. Exchanging Gifts 题意 已知序列 \(g\),将序列 \(g\) 以某种方式乱序后的结果为序列 \(h\),定义序列 \(g\) 的开心值为:在相同下标情况下,序列 \(g\) 对应下标的值和序列 \(h\) 对应下标的值不相同的下标的个数的最 ......
从[SDOI2011]消防 到[NOIP2007]树网的核
应该都和我一样一下水了两题吧 P2491 [SDOI2011] 消防 P1099 [NOIP2007 提高组] 树网的核 题目描述 在一颗 \(n\) 个节点的无根树中,找到一条不超过 \(s\) 的路径,使得图中所有点到此路径距离的最大值最小,图中边权非负 分析 若想将此题转化到树网的核,首先要证 ......
23级ACM第二次招新测试题解
A. lyynuu 思路: 先了解子序列的概念: 在数学中,某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列 接下来我们就思考什么样的字符串可以让子序列 lynu 形成的数量最多,显然当相同字符连在一起时可以形成尽可能多的 lynu ,例如: lly ......
题解 P4755 Beautiful Pair
洛谷。 题意 显然。 分析 首先考虑到分治,那么问题就在于如何维护经过某个结点的方案数。 利用从中间结点向两端的前缀后缀最大值,接下来我们对左端点的每一个结点考虑连向右侧的方案数。 考虑分类讨论,令左端点为 \(i\),右端点为 \(j\)。 假如 \(mx_i> mx_j\),那么我们整个区间的最 ......
NOIP2023模拟13联测34 总结
NOIP2023模拟13联测34 总结 目录NOIP2023模拟13联测34 总结比赛过程题目A. origen题目大意思路B.competition题目大意思路C. tour题目大意D.abstract题目大意 比赛过程 看了一下题,感觉就 \(T2\) 有一点思路。 \(T1\) 先打一个 \( ......
NOIP2023模拟13联测34 B.competition
NOIP2023模拟13联测34 B.competition 目录NOIP2023模拟13联测34 B.competition题目大意思路code 题目大意 现在有 \(n\) 个区间 \([l_i , r_i]\) ,现在问你选取若干的连续的区间的区间并的大小的和。 思路 设 \(pre_{i , ......
NOIP2023模拟13联测34 A. origen
NOIP2023模拟13联测34 A. origen 目录NOIP2023模拟13联测34 A. origen题目大意思路code 题目大意 给定 \(n\) 个整数 \(a_1,a_2,a_3\cdots a_n\) ,求 \[\sum_{i = 1}^n\sum_{j = i}^n(\oplus ......
NOIP2023模拟9联测31 总结
NOIP2023模拟9联测31 总结 题目 T1 游戏 大意 博弈论,在 \(1—n\) 中 \(\phi(i)\) 小于 \(m\) 都选入集合 \(S\)。在集合 \(S\) 中选数 \(x\),选择完后把数 \(x\) 及其的因数从 \(S\) 中删去。当不能取数时的人败。给 \(n,m\) ......
2023NOIP A层联测25 总结
2023NOIP A层联测25 总结 题目 T1 构造 大意 构造一个 \(a\times b\) 的矩阵,要求 \(a,b\leq 40\),且有 \(n\) 个 ryx。(横向,纵向,和 \(45^\circ\) 的方向上的 ryx) 赛时思路 一开始发现求出最大的构造方法后一定可以缩减到另外一 ......
NOIP2023模拟13联测34
T1 把 \(a_i\) 前缀和,式子就变成了 \(\sum_{i=0}^n\sum_{j=i+1}^na_i\oplus a_j\),我们把这些贡献看成 \(a_j\) 的贡献。 然后按位考虑,那么一个数的平方就拆成了一些数加和的平方,拆开就会变成一些数的平方,和一些数的乘积的二倍。考虑分开计算这 ......
NOIP2023模拟8联测29 总结
NOIP2023模拟8联测29 总结 题目 T1 集合 大意 给出一个序列 \(S\),找出有多少个区间 \([L,R]\),使得 \([L,R]\) 值域的连续长度不超过 \(k\)。 \(n \leq 2*10^5,k\leq n\) 赛时思路 对于区间 \([L,R]\),如果有 \([L', ......
NOIP2023模拟9联测30 总结
NOIP2023模拟9联测30 总结 题目 T1 上海 大意 判断是否存在 \(n\) 正整数 ,使得 \(n^2\) 是 \(k\) 的倍数,且 \(n\) 不是 \(k\) 的倍数。如果存在,输出最小的 \(n\) ;不存在输出 \(-1\) 。 \(k\leq 10^{12}\) 赛时思路 对 ......
NOIP2023模拟9联测32 总结
NOIP2023模拟9联测32 总结 题目 T1 花菖蒲 大意 构造一个一度点数等于 \(a\),二度点数等于 \(b\),总点数小于 \(2000\) 的树。 \(a,b \leq 200\) 赛时思路 构造一条链,去除首位后有 \(b\) 个节点,这 \(b\) 个节点接一个一度点,加上首位两个 ......
[ARC105F] Lights Out on Connected Graph 题解
题意 给定一个 \(N\) 个点 \(M\) 条边的简单无向联通图 \(G\)。每个边有红和蓝两种颜色,初始时每条边均是红色。 现在通过移除 \(G\) 中的一些边来获得一个新的无向图 \(G^{\prime}\),求在所有的 \(2^M\) 种方案中有多少种方案可以使得 \(G^{\prime}\ ......
[NOIP2022] 喵了个喵
补一下往年的构造题。。。 \(k\) 大概是 \(n\) 的两倍往下,这启示我们每个栈最多只放两个元素。 首先考虑 \(k=2n-2\) 的分,容易得到一个策略:留一个空栈不放,每个栈最多放两个。如果当前卡牌存在一个栈顶/栈底和它一样,那当前牌总是可以消掉的。否则当前栈中的卡牌一定两两不同,那一定还 ......
NOIP 模拟13(NOIP A层联测26)
100+100+20+17,T3 按理说应该想到考虑两部分分别的贡献的,明明这个套路很常见。 5k:就喜欢这种数据结构专场,多来点。 A.origen 先前缀和,以下 \(p_i\) 表示前缀异或和。 考虑将一个数 \(k\) 二进制差分,假设拆成 \(2^a+2^b+2^c\),则 \(k^2=( ......
AT_abc327 会题解
2023.11.7 18:53 上一次打 ATCoder 还是在上次呢?上一次打外网网络比赛还是在暑假集训吧。 A 乱搞。 B 最多 \(15^{15}\),乱搞即可,记得开 long long 和中途退出。 C ...记得好像做过类似的题来着,同样乱搞。 D 类似于条件之间的叠加,直接建图跑个拓扑 ......
[NOIP2012 提高组] 开车旅行
题目描述 小 AA 和小 BB 决定利用假期外出旅行,他们将想去的城市从 11 到 nn 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 ii 的海拔高度为hihi,城市 ii 和城市 jj 之间的距离 di,jdi,j 恰好是这两个城市海拔高度之差的绝对值 ......
CF301E Yaroslav and Arrangements 题解
### $\text{Description}:$ 给定一个长为 $s$ 序列 $a$,如果 $a_1 = \min_{i=1}^{r} a_i$。令 $a_{s + 1} = a_1$,有 $\forall i ,\left | a_i-a_{i+1} \right | =1$,我们称这个序列是良 ......
2023NOIP A层联测25 T4 滈葕
2023NOIP A层联测25 T4 滈葕 配血实验与2-SAT。 思路 \(z=1\) 表示配血实验发生凝集反应,设 \(a_i,b_i\) 分别表示第 \(i\) 个人有无凝集原 A,B。(无凝集原 A,肯定有抗 A 凝集素,B同理)那么发生反应的必要条件是 \(a_x \and \neg a_ ......
23级ACM实验室第一次招新测试题解
A. 还是Hello World? 思路:无 代码: c++: #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->ios::sync_with_stdio(0); cout << "Hello,World!" ......
2023NOIP A层联测25 T2 游戏
2023NOIP A层联测25 T2 游戏 优秀且新颖的期望题。 思路 分析问题,由于双方都是最优策略,所以可以说学生知道老师会选择那些教室设置概率(概率设置好就不能改变),老师也知道学生会怎样选择教室(不是知道一定会去那个)。 设老师选择的集合是 \(S\)。 那么老师在学生不清空的情况下,老师的 ......
NOIP2023模拟12联测33 总结
NOIP2023模拟12联测33 总结 目录NOIP2023模拟12联测33 总结比赛过程正解A. 构造题目大意思路思路B.游戏题目大意思路C. 数数题目大意D. 滈葕题目大意思路总结 比赛过程 先看了一眼 \(T1\) ,发现又是恶心构造题,果断跳过。 \(T2\) 期望题,这么恶心吗,果断跳过。 ......
[ARC105E] Keep Graph Disconnected 题解
题意 给定一张由 \(N\) 个点和 \(M\) 条边组成的简单无向图 \(G\),定义一个无向图是好的当且仅当这张图满足以下条件: \(1\) 号节点和 \(N\) 号节点不联通 图中不存在重边和自环 现有两人轮流采取操作,每轮操作如下: 选择两个点 \(u, v\),将边 \((u, v)\) ......