Atcoder Beginner Contest 251-260 EFG

B-chess960题目大意给定一串字符串,里面一定包含2个'B',2个'R',1个'K',问该字符串是否满足以下两个条件,一是两个'B'所在位置奇偶性不同;二是'K'的位置在两个'R'之间解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusi......

洛谷传送门AtCoder传送门不错的dp。考虑按行从上往下dp，并且把列的连通状态塞进dp状态里面。实际上就是塞一个并查集。判状态合法性就是当一个竖的全黑长条结束后，有没有跟别的列连起来。code//Problem:Ex-Unite//Contest:AtCoder-AtCoderBeginnerContest29......

洛谷传送门AtCoder传送门好奇特的题。考虑显式建图，那么这是一个\(9\)个结点，\(12\)条边的图，需要找到一条回路使得第\(i\)个点被经过\(a_i\)次。首先会有一个基本思路：先求出每条边经过的次数，然后每条边复制这么多次即可直接构造欧拉回路。其中每条边经过次数的限制就是，......

E题目大意给定数字$k$，规定数组$A$的函数$f(A)$：$A$数组前$k$大数字的和如$A=[1,3,7,~4]$，$k=2$，则$f(A)=7+4=11$现在给定最大数组长度$n$，有$q$组操作，每次将第$x$个数字修改为$y$，输出每次操作后的$f(A)$其中$0<k\leqn\leq5\times10^5,~q\leq5\times......

洛谷传送门AtCoder传送门？这啥啊，不会。考虑行和列分别作为左部点和右部点建二分图（实际上这个建图只是辅助理解，不需要显式建图），每个左部点和每个右部点，边权为格子中的数。容易想到一个dp，设\(f_{i,j}\)为走了\(i\)步，当前在点\(j\)，走过的所有边权组成的不同整数的数量。但......

A-Sandglass2#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongint32_tmain(){inta,b;cin>>a>>b;cout<<max(a-b,0ll);return0;}B-OddString#include<bits/stdc++.h>......

洛谷传送门AtCoder传送门考虑期望转计数，方案数显然是\(n!\)（第\(i\)次操作有\(n-i+1\)个人可供选择），所以问题转化为求所有方案的代价之和。考虑倒着做，变成先放一个人，然后依次放\(n-1\)个人，每次放的这个人可以让左边的人的\(S\)变成R，代价是他与他左边的人的距离，......

洛谷传送门AtCoder传送门一开始看错题了，看了好久才发现就是个板子。。。这个东西本质上是循环移位，我们考虑在\(S\)前后各添加\(W-1\)个.，例如\(W=5,S=\texttt{ABC}\)时，添加后\(S=\texttt{....ABC....}\)。此时我们发现\(S\)的每个长度为\(W\)的子串一一对......

A-WeeklyRecords题目大意小莫每天跑步,输入n周每天的步数,输出每周跑的总步数;解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m,k,idx;signedmain(){ cin>>n; intsum=0; for(inti......

洛谷传送门AtCoder传送门考虑我们如果确定了最终态\(B=(B_1,B_2,...,B_n)\)，如何计算最少操作次数。显然从左往右依次使\(A_i=B_i\)。当操作到第\(i\)个位置时，此时\(A'_i=\sum\limits_{j=1}^iA_j-B_j\)，所需操作次数为\(|A'_i|\)。令\(C_i=\sum\limits_{......