Contest

洛谷传送门 AtCoder 传送门 第一步就没想到 可以考虑化简限制。设所有点按 $E_i$ 从小到大排序后顺序是 $p_1,p_2,...,p_n$。发现只需满足 $E_{p_{i+1}} - E_{p_i} \ge \operatorname{dis}(p_i, p_{i+1})$。证明是对于任 ......

A - Water Pressure #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; printf("%.6lf\n" , n / 100.0 ); return 0; } B - Election ......

Educational DP Contest ATcoder_link 夯实基础的好东西 I 记录一下此时第 i 个有多少概率小于等于 j 的就可以了。 #include<bits/stdc++.h> using namespace std; const int N=3005; #define db ......

A - N-choice question (abc300 a) 题目大意 给定一个元素互不相同的数组$c$和 $a,b$，找到 $i$使得 $c_i = a + b$ 解题思路 直接for循环寻找即可。 神奇的代码 ```cpp #include using namespace std; usin ......

洛谷传送门 AtCoder 传送门 很强的博弈 + 性质题。下文令 A 为 Takahashi，B 为 Aoki。 发现单独考虑一个序列 $a_1,a_2,...,a_n$： 若 $n \bmod 2 = 0$： 若 A 为先手，答案为 $\max(a_{\frac{n}{2}}, a_{\frac ......

洛谷传送门 AtCoder 传送门 不妨假设 $B_X \le B_Y$。设 $f(x) = A_X + \frac{x}{B_X}, g(x) = A_Y + \frac{x}{B_Y}, F(x) = \left\lfloor{f(x)}\right\rfloor, G(x) = \left\l ......

洛谷传送门 AtCoder 传送门 算是对这篇博客的补充吧。 设 $a_1 \le a_2 \le \cdots \le a_n$。 发现最优操作中一定是对相邻的数进行操作，因为如果 $a_j$ 想把 $x$ 给 $a_i$（$i < j$），最优是依次操作 $(j-1,j,x),(j-2,j-1, ......

洛谷传送门 AtCoder 传送门 感觉太人类智慧了。 设 $A = (c_1,c_2,...,c_n)$ 表示当前每种牌的数量，$f(A)$ 为状态 $A$ 只进行换牌操作最终最少剩下几张牌。 $f(A)$ 是可以贪心求出的，因为策略必然是能换则换。 并且我们发现依次换 $2,3,...,n,1$ ......

洛谷传送门 AtCoder 传送门 从低位往高位考虑。设当前个位为 $k$，暴力搜索这一位向上进 $i$ 位，设 $\left\lfloor\frac{n}{10}\right\rfloor - i$ 的答案为 $t$。 若 $t > 10i + k$ 显然就不可行，因为就算个位全部填 $1$ 也不 ......

洛谷传送门 AtCoder 传送门 Hint 如果是一个环怎么做？ Answer 由于是一个环，因此环上每个点对最终答案造成的贡献都相同。设 $f_{i,j}$ 为长度为 $i$ 的序列选 $j$ 个不相邻的点的方案数，则 $f_{i,j} = \binom{i-j+1}{j}$。应该很好理解，考虑 ......

洛谷传送门 AtCoder 传送门 很棒的 flow 题，考虑建二分图。 源点向每种零食连边权为 $a_i$ 的边，每种零食向每个孩子连边权为 $b_j$ 的边，每个孩子向汇点连边权为 $c_j$ 的边，这个图的最大流就是答案。 直接跑最大流肯定 T，考虑最大流等价于求这个图的最小割，因此转而求最小 ......

洛谷传送门 AtCoder 传送门 很不错的状压。 考虑先把最后作为答案的数聚到一起，再算它们的逆序对个数。 设 $f_S$ 为当前选的数集合为 $S$ 的答案。有转移： 选 $a_i$，答案加上之前选的比它大的数； 不选 $a_i$，此时需要把左边的数或者右边的数往中间挪一个，答案加上左右两端的最 ......

A. Wrong Subtraction 在k次操作里, 将n的最后一位数减1,如果是0就去掉,模拟一下就好了. #include <bits/stdc++.h> //#define inf 0x3f3f3f3f #define endl '\n' #define int long long usi ......

SMU Spring 2023 Trial Contest Round 10 A - Remove Duplicates #include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<strin ......

AtCoder Beginner Contest 159 https://atcoder.jp/contests/abc159 EF 是打基础的好题 D - Banned K #include <bits/stdc++.h> #define ll long long using namespace ......

A. Remove Duplicates #include <bits/stdc++.h> using namespace std; #define int long long int read() { int x = 0, f = 1, ch = getchar(); while ((ch < ' ......

AtCoder Beginner Contest 158 https://atcoder.jp/contests/abc158 基础不牢，地动山摇 D - String Formation 一个小小的STL应用 #include <bits/stdc++.h> #define ll long lon ......

洛谷传送门 AtCoder 传送门 挺有意思的计数。 计数感觉很难做，不妨转成期望，期望又可以转成概率之和。 考虑枚举 $w \in [0,m-1]$，把 $> w$ 的数设为 $1$，$\le w$ 的数设为 $0$。那么期望就是所有 $w$，$a_i$ 为 $1$ 的概率之和。对于一个 $i$， ......

SMU Spring 2023 Trial Contest Round 9 A - Wrong Subtraction #include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string ......

A. Wrong Subtraction #include <bits/stdc++.h> using namespace std; int32_t main() { int n, k; cin >> n >> k; while (k--) { if (n % 10 == 0) n /= 10; e ......

对于要打印的 $B$，我们首先尝试确定 $B_1$。 让 $f(x) (1≤x≤M)$ 是最大的 $i$，使 $A_i = x$。 对于 $r:=\underset{{{1≤x≤M}}}{\min}f(x)$，我们可以证明 $B_1$ 是 $A_1 ,A_2 ,...,A_r$ 中的一个（否则，$B ......

A - Treasure Chest (abc299 a) 题目大意 给定一个包含 |*.的字符串，其中|两个，*一个，问*是否在两个|之间。 解题思路 找到两个|的下标$l, r$以及 *的下标$mid$，看看是否满足 $l < mid < r$即可。 神奇的代码 ```cpp #include ......

洛谷传送门 AtCoder 传送门 记录一下这个神奇的套路。 首先有 $\operatorname{popcount}(n) = n - \sum\limits_{i=1}^{\infty} \left\lfloor\frac{n}{2^i}\right\rfloor$。证一下： $$\operat ......

洛谷传送门 AtCoder 传送门 若连通块是一棵树，考虑钦定 $k$ 个点为奇度点，方案数为 $\binom{n}{k}$。对于叶子，如果它是奇度点，那么连向它父亲的边要保留，否则不保留。这样自底向上考虑，任意一条边的保留情况都可以唯一确定，所以最后方案数就是 $\binom{n}{k}$。 若连 ......

洛谷传送门 AtCoder 传送门 这题居然是之前某场模拟赛（contest 701）的 T1……（@Vidoliga 场切但是被卡常/bx） 下面记 $m$ 为原题面中的 $K$，$a_i$ 为原题面中的 $P_i$。 不难发现后手的策略是把所有段按照段的第一个数从大到小排序接在一起。 考虑若 $ ......

洛谷传送门 AtCoder 传送门 挺有意思的题。 首先显然地，一个棋子不会走回头路。于是一个棋子沿着边走的效果就是区间异或。 更进一步，设 $s_i$ 为 $i-1 \to i$ 的边颜色与 $i \to i+1$ 的边颜色是否相同（差分），相当于对于每个 $i$ 都选择 $s_{a_i}$ 和 ......

A: 思路： 首字母如果是0，直接输出0。 如果首字母是?,提供九种方案，之后每一个？提供10种方案。 void solve(){ string s; cin>>s; if(s[0]=='0'){ cout<<"0"<<endl; return ; } int ans=1; for(int i=0; ......

CatOJ C140（初中） $100+93+100+10=303$，Rank 1。 是个 dp 场，A 题期望 dp，B 题神奇猜结论，C 题换根 dp，D 题树上博弈 dp。 A 题设 $f_u$ 为填满子树 $u$ 的期望次数，$s_u$ 为 $u$ 子树大小，容易得到 $f_u=f_v+\f ......

题目：E - Unfair Sugoroku (atcoder.jp) 分析：这题状态转移方程挺好推的，但是用dp解是我没想到的 dp[i][j][0]表示T在i点，A在j点且轮到T走时赢的概率 dp[i][j][1]表示T在i点，A在j点且轮到A走时赢的概率 代码： #include <bits/ ......

洛谷传送门 AtCoder 传送门 考虑判断一个终止态是否可达。如果只有一个棋子连续段那一定可达；否则就存在 $\ge 2$ 个连续段。此时把放棋子看成删除，那么限制就是如果删除一个孤立的棋子（两边没有棋子）且还有别的格子有棋子，这个棋子的颜色 异于其他连续段的两边棋子的颜色 。 设第一个被删的段（ ......