题目链接 大意：给你一个组士兵，告诉你身高     i    i   i的人数      a   i     a_i   ai​，让你放在     k    k   k行，使得每行人数相同且每行中士兵身高差不超过     1    1   1，问你最多能放多少士兵满足条件。 思路:二分每行人数。证明：如果     x    x   x满足的话，显然可以把每行都去掉相同的人数使得     [   1   ,   x   ]    [1,x]   [1,x]都满足。 遍历     n    n   n个人，先把上一个身高的士兵没用完的看能不能和当前身高的放满一行，再放当前身高的。 如果最后放的行数...

题目链接 大意：给你一个n变形，一个长度n的排列，依次写在n个点上，每次割掉连续三个点组成的三角形。 给你n-2次切割的三角形的三个顶点标号，求出这个排列，和切割顺序。 思路：显然n-2个三角形的所有边必然包含 长度n的排列的相邻点（首尾相连）连边所构成的边集， 且每条边必然只能出现一次。 那么输入的时候把三角形所有的边的出现次数都统计一下，出现一次的即为我们需要找的边（长度n的排列的相邻点（首尾相连）连边所构成的边集）,然后直接dfs一下就可以把排列弄出来了。 切割顺序的话：显然每次去掉的点必然是度数为1的点，那么直接拓扑排序就好了。 细节见代码： #include<bits/stdc...

题目链接 题目大意： 思路：构造一个这样的序列。 特判一下答案长度在1，2的情况。 我们假设有解，且长度为     k    k   k,那么显然我们可以得到一个等式： 1.设     b    b   b数组为每次加的值，      b   1    =   0    b_1=0   b1​=0 2.      ∑    i   =   1     k   −   1      2    k   −   i   −   1     ∗    b   i    +    b   n    +   A   ∗    2    k   −   2     =   B    \sum_{i=1}^{...

题目链接 问题转化：给你一个数组     a    a   a，构建一个矩阵     b    b   b，使得      b    i   j     =    a   i    +    a   j     b_{ij}=a_i+a_j   bij​=ai​+aj​，你要从矩阵中选m个数使得和最大。 显然二分一下第      n   2    −   m   +   1    n^2-m+1   n2−m+1小的数是啥，然后用总和减掉前      n   2    −   m    n^2-m   n2−m小的数就好了。 注意一下细节： #include<bits/stdc++.h&...

题目链接 大意：给你一个序列，让你构造一颗合法的有根树，满足： 序列的第      i    t   h      i_{th}   ith​数代表的是第      i    t   h      i_{th}   ith​大的边的父亲节点，边的价值定义为：子树内所有节点编号的2的幂次方和。 思路：直接逆向拓扑排序，开一个优先队列，把入度为0的先进队，倒着扫，把最小的和当前点连边即可。 细节见代码： #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; ...

题目链接 大意：给你一颗树和一些操作(初始所有节点都是白***r> 1:把     v    v   v点染成黑***r> 2:找到一个最小节点编号     y    y   y,使得     x    x   x到某个黑色节点到最短路径上存在节点     y    y   y. 思路：我们把第一个变成黑色节点到点 设为根节点，然后求出根节点到所有点的路径上到最小节点编号，设为数组     f    f   f，那么如果没有其他黑点的话，那么     f   [   x   ]    f[x]   f[x]就是询问点     x    x   x的答案了。如果存在别的黑点     ...

题目链接 大意：给你     n    n   n个事件，每个时间在     a   ,   b    a,b   a,b地点的开始结束时间。问你有没有一个事件子集，使得，在一个地点不冲突，但是另一个地点冲突。（冲突的意思是：时间相交/重合） 思路：显然，问题简化为，存不存在任意两个事件，使得，两个地点有且只有一个地点使得两个事件时间相交。 那么问题就好解决了：     a   l   ,   a   r   ,   b   l   ,   b   r    al,ar,bl,br   al,ar,bl,br，代表每个事件的     a   ,   b    a,b   a,b地点的开始结束事...

比赛链接 A - Garland 大意：给你一个可能没补完的排列，让你把剩下的数填上，使得奇偶不同的相邻数目最少。 思路：直接上     d   p    dp   dp,表示第     i    i   i个，有     j    j   j个     1    1   1，     k    k   k个     0    0   0，第     i    i   i个是     0   /   1    0/1   0/1的最小答案。 枚举     1   −   n    1-n   1−n分情况转移即可。 #include <bits/stdc++.h> using na...

比赛链接 A - Expression 给你三个数，让你插入一些     +   ,   −    +,-   +,−和小括号，使得值最大 直接输出所有情况的最大值即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back int main() { ios::sync_with_stdio(false); int a,b,c; cin>...

比赛链接 A - Magic Spheres 把多余的都拿出来看能不能生成需要的那么多即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back int main() { ios::sync_with_stdio(false); int a,b,c,x,y,z; cin>>a>>b>>c>>x&...

总结一下公式，定期更新       ∑    K   =   0    N    K    C   N   K    =   N    2    N   −   1      \sum_{K=0}^NKC_N^K=N2^{N-1}   ∑K=0N​KCNK​=N2N−1       ∑    K   =   0    N    (   K   +   1   )    C   N   K    =   (   N   +   2   )    2    N   −   1      \sum_{K=0}^N(K+1)C_N^K=(N+2)2^{N-1}   ∑K=0N​(K+1)CNK​=(N...

紧张刺激(自闭)的camp开始了。 首先感谢各位老师，志愿者的辛苦付出！ 一开始知道是jls出的题，感觉就会很自闭啊？结果确实也是这样子。 开场我先扫了一下题，发现有个题很好做？（最先的时候没看清数据有非正数情况） 写着写着终于发现数据包含负数了，随机自闭了一会，然后想想好像也挺好做吧？ 就开始慢吞吞的开始自闭讨论所有情况，写完跟暴力拍了拍，发现0的情况还得拎出来讨论一下，随即改了改，再拍没拍出错。然后自信的submit，然后返回tle？我看了看代码，嗯，常数好像有点大，然后xjb改改细节，优化了很多地方，然后再交，还是tle啊？就这样自闭了1h+之后，我看了看我函数传vector参数的地方 ...

045 早上dls讲课是真的nb，讲的太好了！！！dlsnb！！！！ 下午比赛的时候，看一下A题，想了一会(很久？)，最后发现大概是个推推贡献的题目吧？ 然后推出了用差分数组维护差分数组的这么个东西，然后做一做，但是最后的统计贡献，分子分母写颠倒了，，对着式子自闭半天嘤嘤嘤？ 之后看到了启发式合并的题目，我想这tm不是才讲过吗，但是好像是我第一次写呢？中间的一个细节调了很久才发现那地方的错误，修正后一发ac了。 后来就开始挂机看神仙队友表演了，队友太nb了啊！！！我就是躺狗(实锤) 中间我也有 推推 H的式子，想出了奇数情况的答案，但是偶数的地方没想明白怎么弄啊，我太难了啊，晚上回到宾馆，把H...

题目链接 题意：给你一颗树和一些限制，让你构造每个边的边权满足 限制。 限制：     a   −   >   b    a->b   a−>b的最短路径上的最小边权等于     c    c   c. 思路：把所有限制按照c从大到小排序，然后依次遍历所有限制，对每条路径上没有赋值的赋值成当前的c。如果都有值且值都大于c，那显然无解。 细节见代码： #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first ...