题解codeforces round 879

题目链接 Rroken robot 分析 记 \(f[i][j]\) 为从 \(i\) 行 \(j\) 列到最后一行的期望，则 \( f[i][j]= \begin{cases} \frac{1}{3}(f[i][j]+f[i][j+1]+f[i+1][j])+1 &i=1\\ \frac{1}{4 ......

以后应该都是从 E 开始。 E: problem LCA题。 我们枚举向上跳 \(t\) 步，跳到了 \(y\)。 假如说 \(t = 0\) 那么我们计算 \(\text{clac}(x,k)\) 即可。（\(\text{clac}\) 怎么算放在最后讲） 否则 计算 \(\text{clac}( ......

Preface 这天晚上这场因为不明原因（玩CCLCC中）就没有打，只能赛后补一下 这场的EF都不算难初看都有做法，但好家伙E写挂两发，F写个根号做法直接T到天上去了 A. Rigged! 签到题，对于所有的\(e_i\ge e_1\)的\(i\)，求出\(S=\max s_i\)，根据\(S+1\ ......

洛谷链接 题目简述 给定 \(N \times M\) 的字符矩阵，有 \(Q\) 次询问，对于每次询问给出 \(x,y\)，求以 \((x,y)\) 为中心的最大正方形边长且正方形中字符均相同。 思路 看到数据范围较小，可以考虑深搜解决，约掉常数的时间复杂度最坏为 \(O(q \times \mi ......

洛谷链接&Atcoder 链接。 题目简述 给定一个字符串 \(A\)，可以选择区间 \([i,j]\) 翻转一次，求能得到多少本质不同的字符串。（\(A\) 的长度不超过 \(2 \times 10^5\)）。 思路 首先解释本质不同的含义，即不完全相等的两个字符串（可能 \(A\) 是 \(B\ ......

洛谷连接&Atcoder 链接 题目简述 给定两个数 \(n\) 和 \(m\)，输出 \(\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m\) 的值。 数据范围：\(n \le 10^{18},m \le 10^4\) 思路 首先看到数据范围还是很大的 ......

P1989 无向图三元环计数 题解 考虑对无向图的边定向：对于每一条无向边，度数小的点向度数大的点连边，如果读书相等则按编号大小确定。 这样枚举一个 \(u\)，再枚举它的出点 \(v\)，接着枚举 \(v\) 的出点 \(w\)，如果存在一个 \(w\)，\(u\) 向它连边，那么 \((u, v ......

练习笔记： A：https://codeforces.com/contest/1467/problem/A 一开始以为是 987654321..... 交了两发WA。慢慢想想就是如果说我是第二个号码放8就是98901234.... 交了就是AC B: https://codeforces.com/c ......

Day5，9.25，codeforces round 899 div2 ·事实证明自己的思维和手速都还不够快，晚上还晚来了一点 ·B题属实是，上来就想着并查集（菜鸡是这样的）然后发现不会写捏 ·思考了很久（看数据量）感觉是枚举暴力，但是又想不到怎么去枚举 ·一题遗憾离场 ·顺理成章的-26 ......

题意 给出一个 \(1,\dots,n+1\) 的排列 \(v_{1},\dots,v_{n+1}\) 与两组权值 \(a_{1,\dots,n},b_{1,\dots,n}\)。满足 \(v_{n+1}=n+1\)。 构造一张 \(n+1\) 个点的有向图： 对于 \(i=1,\dots,n\)， ......

更好的阅读体验 题意 原题链接 给出 \(n\) 个城市和 \(m\) 条双向管道，以及两个实数 \(v\) 和 \(a\)。有两种液体，分别是水和 Flubber（下面简写为 W 和 F）。\(1\) 号和 \(2\) 号城市分别生产 Flubber 和水，并通过管道流入 \(3\) 号城市。对于 ......

Problem - 616C - Codeforces C. The Labyrinth 如果是直接对\(*\)去跑dfs或者bfs的话无疑是会超时的 既然如此,那我们可以去对 \(.\) 跑搜索,将各个连通的 \(.\) 块标号并计算出连通块内的点的数量,然后去遍历\(*\)的时候只需要上下左右跑 ......

题目链接 看到这道题按照套路首先想到二分答案（即二分 \(q\) 位置上的数，记作 \(mid\)）。 再按照套路将大于 \(mid\) 的数字设为 \(1\)，将等于 \(mid\) 的数设为 \(2\)，小于 \(mid\) 的数字设为 \(0\)。 那么对于区间 \([l,r,0]\) 操作， ......

其他题解怎么又 Tarjan 又 Dijkstra 的，这是 div4H 的样子吗，来个简单好写的做法。 题面里的人名太复杂了，本题解中称为警察和小偷。 注意到，如果小偷成功到达了环上，那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里，他可以执行相同的操作（顺时针/逆时针/静止），使得他和警 ......

题外话 纪念一下第一道 Ynoi Easy Round.（上次那个是 Ynoi 模拟赛，什么时候才能做正统 Ynoi 啊/ll 在图老师的逼迫下换了洛谷博客的主题和背景，还挺好看的感觉。 原题传送门 题意 给定一个长度为 \(m\) 的序列，初始全为 \(0\)。再给 \(n\) 个区间赋值操作。 ......

include <bits/stdc++.h> typedef long long valueType; typedef std::vector ValueVector; constexpr valueType MAXB = 31; int main() { std::ios::sync_with_ ......

Codeforces Round 900 (Div. 3) A. How Much Does Daytona Cost? 解题思路: 可取一个元素作为子数组，数组中存在\(k\)即可。 代码: #include<bits/stdc++.h> using namespace std; using ll ......

CF1195A Drinks Choosing 先将相同权值的配对直到只剩下一个，然后再配剩下的单个。 #include<iostream> #include<cstdio> using namespace std; const int N=1005; int n,k; int a[N]; int ......

CF1440A Buy the String 每个点有两种决策，要么选当前的字符，要么选跟当前字符不同的字符，取个较小值相加。 #include<iostream> #include<cstdio> using namespace std; const int N=1005; int T; int ......

CF1197A DIY Wooden Ladder 答案为 \(\min(a_{n-1},n-2)\)。 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=100005; ......

CF1447A Add Candies 可以将操作看做将 \(a_i\) 减 \(i\)，然后第 \(i\) 次操作 \(i\) 就是合法的。 #include<iostream> #include<cstdio> using namespace std; int T; int n; void so ......

CF1008A Romaji 直接模拟。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=105; int n; char s[N]; int main() { scanf( ......

CF1011A Stages 每次记下上一个选的位置，贪心能填就填。 #include<iostream> #include<cstdio> using namespace std; const int N=55; int n,k; char s[N]; int cnt[27]; int main( ......

CF1072A Golden Plate 第 \(i\) 个矩形的周长为 \(2(w - 4(i - 1))+2(h - 4(i - 1))-4\)，枚举 \(i\) 求和。 #include<iostream> #include<cstdio> using namespace std; int n ......

CF1079A Kitchen Utensils 令 \(c_i\) 表示餐具 \(i\) 出现的数量，最小的餐具套数为 \(t=\lceil \frac{\max\{c_i\}}{k}\rceil\)，按照这个计算就好了。 #include<iostream> #include<cstdio> # ......

CF1020A New Building for SIS 分类讨论 \(a,b\) 两个端点的几种情况就好了，特判 \(t_a=t_b\) 的情况。 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> usi ......

CF1162A Zoning Restrictions Again 每个位置越高越好，暴力模拟即可。 #include<iostream> #include<cstdio> using namespace std; const int N=55; int n,h,m; int a[N]; int m ......

CF1036A Function Height 答案为 \(\lceil \frac{k}{n}\rceil\)。 #include<iostream> #include<cstdio> using namespace std; long long n,k; int main() { scanf(" ......

CF957A Tritonic Iridescence 如果原序列中有两个相同的字符，显然不合法。 如果开头或者结尾为 ?，或者有两个连续的 ?，或者一个 ? 两边的字符不同显然合法。 否则一定不合法。 #include<iostream> #include<cstdio> using namesp ......

CF992A Nastya and an Array 答案为非零数的个数。 #include<iostream> #include<cstdio> #include<map> using namespace std; const int N=100005; int n; int a[N]; map< ......