__zyn__-CSDN博客

原创 Bzoj 3453 tyvj 1858 XLkxc

StatementproSolution拆式子，发现答案为:∑i=0n∑j=1a+id∑xjxk\sum_{i=0}^n\sum_{j=1}^{a+id}\sum_{x}^jx^ki=0∑nj=1∑a+idx∑jxk直接暴力插值即可，时间复杂度为O(Tk3)\mathcal O(Tk^3)O(Tk3)#include <bits/stdc++.h>using namespace std;const int MAXK = 2021;const unsigned int

2021-02-17 16:02:14 74 1

原创 [TJOI2018]教科书般的亵渎

StatementstatementSolution经过推导发现答案为:∑i=1m+1[∑j=1n−ai−1jm+1−∑j=im(aj−ai−1)m+1]\sum_{i=1}^{m+1}\left[\sum_{j=1}^{n-a_{i-1}}j^{m+1}-\sum_{j=i}^m(a_j-a_{i-1})^{m+1}\right]i=1∑m+1[j=1∑n−ai−1jm+1−j=i∑m(aj−ai−1)m+1]复杂度瓶颈在∑i=1nik\sum_{i=1}^ni^k∑i=1ni

2021-02-17 14:51:52 124

原创【CF908D New Year and Arbitrary Arrangement】

x←ba+b⋅∑i=0∞(d+i)×(aa+b)ix\gets \dfrac {b}{a+b} \cdot \sum\limits_{i=0}^\infty (d+i)\times (\dfrac{a}{a+b})^ix←a+bb⋅i=0∑∞(d+i)×(a+ba)i

2020-03-25 10:09:20 109

原创【 Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)】

【A - XORinacci】【Analysis】Fn=Fn−3F_n =F_{n-3}Fn=Fn−3【Code】long long t, a, b, n; long long F[3]; int main(void){ t = read(); while (t--) { a = read(), b = read(), n = read(); n = n % 3...

2019-09-01 18:40:37 248

原创【20190813模拟赛Div2T2 逆序对 (inversion)】

Problem【Analysis】考虑每个区间[l,r][l,r][l,r],Len=r−l+1Len = r-l + 1Len=r−l+1,期望逆序对个数为Len×(Len−1)2×12\frac{Len\times(Len-1)}{2}\times\frac{1}{2}2Len×(Len−1)×21即Len×(Len−1)4Len\times(Len-1)\over44Len×(Le...

2019-08-30 21:18:01 159

原创【题解 CF1205A Almost Equal】

【Analsis】因为任意两个和相差最多为111,可以构造答案，比如n=3n = 3n=3 -> $1, 4, 5, 2, 3, 6 $nnn为奇数时 [小]，[大]，[小]，[大],..................[小]，[大] 这样是可以的nnn为偶数时 [小]，[大]，[小]，[大]，[小]..................[大]，[小]可以发现这样不行，然后就做完了...

2019-08-19 12:17:56 507

原创【CF1206B Make Product Equal One】

【Analysis】这题应该贪心和DP都能过；可以发现，一个数只能变成−1-1−1或111,令Dpi,jDp_{i,j}Dpi,j表示前i个数有j个变成了−1-1−1,发现转移和j的数量无关，只和奇偶性有关，令Dpi,0Dp_{i,0}Dpi,0表示前i个数用了偶数个−1-1−1,那么方程就是Dp[0][1] = 1e18;Dp[i][0] = std::min(Dp[i - 1][...

2019-08-19 12:17:01 596

原创【UVA12299 RMQ with Shifts】

【Analysis】这题其实在考输入吧，其他好像不难，shiftshiftshift就用线段树的单点修改即可【Code】#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>typedef long l...

2019-08-18 21:32:27 70

原创【CF570C Replacement】

线段树模板题【Analysis】先建线段树，考虑如何合并不难发现两段区间和并时，只有左区间的最右边是 ‘.’ && 右区间的左边是’.'时大区间 + 111【Code】#include <cstdio>#include <iostream>#include <cstdlib>#include <algorithm>#...

2019-08-18 21:31:07 120

原创【[USACO09FEB]环绕岛屿Surround the Islands】

【Analysis】TarjanTarjanTarjan缩点，再在所有强连通分量中找一条最小的边作为强连通分量的边，因为还要回来，所以AnsAnsAns最后要乘二【Code】#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>#include ...

2019-08-18 21:29:45 139

原创【UVA1121 Subsequence】

【Analysis】这是TwoPointerTwoPointerTwoPointer模板题吧可以先让右端点不断向右，直到sum≥ssum \ge ssum≥s时停下，记录长短，为了使长短最小，不断使左端点不断向右，每次向右一格且sum≥ssum \ge ssum≥s 时记录如果sum<ssum < ssum<s就退出【Code】#include <...

2019-08-18 21:28:17 75

原创【CF901C Bipartite Segments】

【Analysis】有一个重要的结论：如果一个无向图是二分图，则图中不存在奇环因为题目保证不会有偶环，那么只要存在环就不行，那么题目就转化成了询问区间[L,R][L,R][L,R],有多少区间满足[L‘,R‘][L`,R`][L‘,R‘]不存在环；不妨设flf_lfl表示rmaxr_{max}rmax满足[l,r][l,r][l,r]不存在环，那么Ans=∑i=lrmin(fi,r)−...

2019-08-18 20:53:43 162

原创【[USACO12FEB]附近的牛Nearby Cows】

【Analysis】不难发现fi,j=∑fk,j−1f_{i,j} = \sum f_{k,j - 1}fi,j=∑fk,j−1 kkk是iii的儿子；首先它是棵无根树，我们可以先算出以1为根的fff值，然后考虑换根DPDPDP, fk,j+=fi,j−1−fk,j−2f_{k,j} += f_{i,j - 1} - f_{k,j - 2}fk,j+=fi,j−1−fk,j−2;...

2019-08-18 19:30:35 82

原创【UVA12235 Help Bubu】

【Analysis】可以发现书的高度的值域很小，肯定和状压有关；很容易想到Dp[i][j]....表示前i本书中拿了j本的最小混乱值现在再加一维Dp[i][j][s]..表示前i本书中拿了j本，剩下的书的种类的集合的最小混乱值注意这里的sss是种类的集合，而不是每本书的状态我们考虑第iii本书是否要拿走，如果这本的前面没拿走的最后那本的高度和这本的相同，那么这本不需要那走，然而已有...

2019-08-16 18:31:48 86

原创【Luogu】P3939 数颜色

Problem【Analysis】对每个颜色开一棵主席树，维护一下和就好了,O(MlogN)O(M log N)O(MlogN)【Code】#include <cstdio>#include <iostream>#include <cstdlib>#include <algorithm>#include <cmath>#...

2019-08-16 18:26:17 102

zyn_615的博客