CF1931G One-Dimensional Puzzle 题解

题目传送门前置知识二分答案解法最小值最大，考虑二分答案。关于check函数的书写，比luoguP1182数列分段SectionII多了个对位置的判定，注意对当前是第一次展出时进行特判。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsigne......

牛客练习赛122A.黑白配代码：#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+7;constintINF=0x3f3f3f3f;typedeflonglongll;#defineendl"\n"voidsolve(){ intt,n;cin>>t>>n;inta[n+1];while(t--)......

题解首先拜谢波叔呀，一眼看上去没思路，直到看见了四重循环，大彻大悟。Solution没什么好说的，暴力四重题意大意就是给你一个数，在1，3，6，10，15中取数，使取出的数等于输入的数，求出至少需要用多少个数。求数代码： for(longlongi=0;i<=2;i++){ for(longlongj=0;j<=1;j++){ for(lo......

如果我们定义\(dp[i][j]\)表示对于前i个字符而言，其子集满足条件的个数。那4么对于一个位置i而言，要么选择它贡献要么不选择，所以\(dp[i][j]=dp[i-1][j-a[i]](j>=a[i])+dp[i-1][j]\)，这是每一个\(f(i)\)的函数。然后我们加上所有的\(dp[i][k](i:1到n)ans+=dp[i][k......

若某一位\(i\)上\(A_i>B_i\)，则显然无解。否则，建立并查集，然后遍历字符串，若\(A_i,B_i\)不在一个集合就合并\(A_i\)与\(B_i\)，直到只剩下一个集合，此时的合并总次数即为答案。为什么呢？因为将\(A_i,B_i\)合并的操作可以视为等价于将以\(A_i\)开头的连续若干个相同字符均改......

这里是出题人题解。\(\text{SolutionOfProblemC:UnknownGraph.}\)题意还是很清晰的，这里就不再赘述题意了。首先如果没有\(q\)的限制，显然有一种贪心思想就是每个点每次选剩余入度最多的与之连边。但是因为限制，就无法保证贪心的正确性。那该怎么办呢？一个大提示：这题是......

P3200[HNOI2009]有趣的数列感性地，我们认为在按照数值从小到大填数时每个时刻所填的奇数位的个数\(x\)不小于所填偶数位的个数\(y\)。我们考虑如何证明这一点。性质1：每一个偶数位上的数都要大于它前面所有的数。这一点应当是显然的。性质2：每一个偶数位上的数都不小于它的下......

我们发现，brute-force的复杂度的优化瓶颈主要在建图上。于是我们有一个巧妙的转化：因为所有满足\(L\leS,T\leR\)的所有边\((S,T)\)的长度均为\(C\)。然后题目要求的是\(1\simN\)的最短路。那么在边权相等的情况下，走到的点的编号一定越大越好。于是在所有点对\((......

首先，我们可以得出一个结论：令点\(i,j\)之间的最短路径边权和\(dis_{i,j}\)，若存在一个点\(k\)，使得\(k\neqi\)且\(k\neqj\)且\(dis_{i,k}+dis_{k,j}=dis_{i,j}\)，则连接\(i,j\)的边可以被删去。该结论的正确性是显然的，因为将连接\(i,j\)的边删去后，\(i,j\)之间的......

难度虚高，建议评橙/黄qwq。首先我们发现这是一道最短路问题，且\(N\le300\)，于是采取floyd算法解决。具体地，我们分情况分类讨论。令我们当前枚举到的最短路径起点为\(i\)，终点为\(j\)，中转点为\(k\)，输入的矩阵为\(dis\)。若\(dis_{i,j}>dis_{i,k}+dis_{k,j}\)，则一定无......