House_of_Fan

CF2174A Needle in a Haystack 思路 首先我们发现：只要从 $t$ 中去掉子串 $s$ 中的字母，其余字母一定不受约束，按照字典序排列。 所以我们枚举去掉 $s$ 中的字母的其他字母，若其字典序大于此时的 $s$ 的还没用的首位，就加入 $s$ 的首位，否则就加入其余字母的首位。 若在去掉 $s$ 中的字母后有某种字母不足 $0$ 个，则显然无法使得 $t$ 有 $s$ 子串，输出Impossible。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep...

CF2175B XOR Array 思路 设前缀异或数组为 $pre$，其中 $pre_0=0$，$pre_i= a_1\oplus a_2\oplus\dots\oplus a_i$（$\oplus$ 表示异或）。 根据异或的性质，子数组 $a_x\dots a_y$ 的异或和可以表示为：$f(x,y)=pre_y\oplus pre_{x-1}$。 要求 $f(l,r)=0$，等价于 $pre_r=pre_{l-1}$。 要求其余子数组异或和非 $0$，等价于除 $(x,y)=(l,r)$ 外，任意 $i\neq j$ 都有 $pre_i\neq pre_j$。 初始化 $pre_0=0$，$pre_i=i$（$1\le i\le n$）。此时 $pre$ 数组元素互不相同，保证所有子数组异或和非 $0$。 调整 $pre_r=pre_{l-1}$，满足 $f(l,r)=0$。由于 $l \le r$，$pre_{l-1}$ 的值不会与 $pre_{1}\dots pre_{r-1}$ 重复，因此调整后仅存在一对相等的前缀值 $pre_{r}$ 和 $pre_{l-1}$。 ...

CF2173B Niko’s Tactical Cards 思路 简单 DP，只需要记录到每一步操作的最小值和最大值，再进行更新就行了。 最大值只会由最大值减 $a_i$ 或 $b_i$ 减最小值得到，最小值只会由最小值减 $a_i$ 或 $b_i$ 减最大值得到。 再分别对这两对值取对应的最值即可。 最后输出最后一位的最大值。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define...

CF2170B Addition on a Segment 思路 正难则反，考虑从给出序列每次把一段区间减 $1$ 直到回到全 $0$。 首先从大到小排序。因为若乱序操作很可能会造成中间无法操作而两头还有剩余值的情况，非常浪费。 我们只在第一次操作时考虑最长，后面每次都使 $l=r$，若操作次数多出，则将某几次合并成一次即可。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#defin...

CF2170C Quotient and Remainder 思路 乍一看这个东西非常不好求。 考虑对它进行转化。 观察式子： $$q_i=\lfloor\frac{x}{y}\rfloor,r_j=x\bmod y$$ 但是向下取整这个东西难以逆向，所以先转化为： $$q_i=\frac{x-x\bmod y}{y},r_j= x\bmod y$$ 注意到 $q_i$ 的分子可以由 $r_j$ 转化而来，则有： $$q_i=\frac{x-r_j}{y}$$ $$q_i\cdot y=x-r_j$$ $$x=q_i\cdot y+r_j$$ 因为 $1\le q_i,r_j$，所以 $x>y$。 那么只要 $x\le k$，相应的 $y$ 也就小于 $k$。 而对于 $x=q_i\cdot y+r_j$，$q_i,r_j$ 越小，$x$ 也越小。 所以我们先把 $q,r$ 两个数组从小到大排序，在二分找每个 $q_i$ 对应的最大 $r_j$，只要能删就删即可。 代码 1234567891011121314151617181920212223242526272829303...

CF2170D Almost Roman 思路 首先我们对每个数字进行分析： $I$ 权值最大为 $1$，最小为 $-1$， $V$ 权值为 $5$， $X$ 权值为 $10$。 注意到无论在何种情况下，$X$ 的权值和造成的影响一定比 $V$ 多 $5$。 可以把原字符串中的所有 $X$ 替换成 $V$，每替换一次就给总权值加 $5$。 又发现对于任意位置，填 $I$ 一定比填另外两个更优。 所以我们先将所有问号的位置都填上 $I$，如果不够就再替换成另外两个。 对于每一次替换，有以下三种情况： 增加了权值为 $-1$ 的 $I$ 的个数， 权值为 $-1$ 的 $I$ 的个数不变， 减少了权值为 $-1$ 的 $I$ 的个数。 显然我们应先替换第一种，再替换第二种，最后选第三种。 那代码就很好实现了。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707...

NOIP 破鼎记 省流： 预估 $100+24+0+0$，$124$ 惨惨惨。 实则 $95+24+36+5$，$160$ 爽爽爽。 已严肃成为机房公敌。 骗分赢麻了。 今天英语课讲的啥我咋第一题都不会做。

NOIPlus 破鼎失败记 还没出成绩…… Day -2 打了@Getaway_Car 的信心赛，100+55+50+0，希望CCF的部分分也这样给。 Day -1 在家水谷，打了几个板子，复习了下缺省源。 Day 1 早起坐车到考场。 门口看见了教练，确认证件无误后进了嘉祥。 跟着严格不小于一百万个指示牌找到了考场。 纷争开始了 携带巧克力$\times 8$，饮料$\times 2$ 进入考场。 T1感觉一眼，显然只会有一种糖果被购买两次及以上。 啊我贪心怎么伪了。 哦原来被购买两次以上的也可以是奇数啊。 15min调出，看T2。 开始尝试第一档部分分。 状压写出12pts。 推了一下 $m=2n-1,m=2n-2$。前者显然直接输出 $2^n$，后者枚举只有一个糖果被定价为 $1$ 的情况。 开始推 $m=2$。尝试构造小样例。 想了一个性质，似乎非常正确。 写+调试到3h无法战胜，遂弃之。 监考员开始询问&分发小面包和牛奶，不饿就没要。 T3不会，打了个神秘树形DP拿8pts跑路了。 T4打了最朴素的5pts。 还剩1h，吃零食，喝饮料。 东方树叶咋这么苦。 吃了...

CF1919D 01 Tree 模拟赛赛时做了一道非常类似的题，但题面是一条为 $0$ 的边和一条可能为 $0$ 或 $1$ 的边，修改合并条件后就能通过此题。 与现有题解做法均不同（雾），求通过。 思路 因为这道题目中的两条边都是固定的，所以为 $0$ 的节点一定有且仅有一个。 我们不考虑拆分点，而是合并点，将新点权设为。 发现两点之差为 $1$ 的时候就可以合并这两个点。 那我们考虑维护四个值：$l_{mi},l_{mx},r_{mi},r_{mx}$ 分别代表某个区间从左/右开始往中间合并能合并出的最大/小值。 显然最大值和最小值之间的所有值都是可以取到的。因为合并的值最大差值为 $1$，并且必须连续。 不妨维护多个区间的这四个值，判断可否合并，再判断最后剩下的那个区间最小值是否为 $0$ 即可。 具体的： 两个最小值显然都更新为合并完所有点后的值； 左/右最大值为左/右边区间的左/右最大值，因为它们显然无法变的更大，也不需要变小； 若一个区间的合并方向最大值加 $1$ 后还是小于另一个区间的合并方向最小值，显然无法合并。 若两个区间的合并方向的四个值均相等，则这两个值只能...

CF2157C Meximum Array 2 题意 构造长度为 $n$ 的序列 $a$，满足 $q$ 个限制条件。 思路 对于 $a_i$： 若 $a_i$ 被 min 限制且被 MEX 限制，则易得填 $k+1$ 即可； 若 $a_i$ 仅被 min 限制，则填 $k$ 即可。 若 $a_i$ 不属于以上两种，则循环填 $1$ 到 $k-1$。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#d...