WORIA

排列组合 排列组合就是计算题啊。。 数学期望线性 概率dp 计算题，找规律 递推 A. Game on Tree   期望可加性 需要知道一个定理：Esum=∑EiE_{sum}=\sum E_iEsum​=∑Ei​，可以把整个树上的期望变为单点的期望值之和。 要求删除整个树的操作数的期望值，我们就转化为求每个点的操作数期望值。 单点期望值=∑\sum∑ 各种情况出现的概率*各种情况下的对该点的操作数。 首先我们考虑在哪些情况下该点会被删除 该点某一个祖宗节点被删除 该点被删除 对于第一种情况，我们对该点并无操作，操作数=0；对于第二种情况，操作数=1。 **再来看两种情况概率，由于只有上述两种情况会删除该点，所以对其子节点的操作不应该考虑。**因此总的情况数应等于该点的所有祖宗节点+自身。设祖宗节点+1=k，则第一种情况概率为(k-1)/k；第二种情况概率为1/k. 前面说了子节点不应该考虑，通过观察根节点可以更能理解，若考虑所有子节点，则根节点自身被删除的概率为1/n，n为总节点数，所以根节点操作数的期望值应该是1/n，这就说明我们可能不通过直接删除根节点自身而去除根节 ...

差分 bfs 01背包dp Dijkstra 递归，大数 A. 阿卡的萝卜 单点时限: 1.0 sec 内存限制: 512 MB 输入： 输出：   差分+前缀和+dp求最大子段和 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<algorithm>using namespace std;#define ll long longconst int maxn = 5e5 + 5;ll n, m;ll a[maxn];ll cha[maxn];ll dp[maxn];int main() { cin.sync_with_stdio(false); cin >> n ; for (ll i = 1; i <= n; i++) { cin >> a[i]; } cin >> m; for (ll i = 0; i < ...

这次其实难度还行，也都是一些可以下手的题，但由于做的太少了，敲的代码太少，出了很多bug，一些细节也有些遗忘，例如bfs的vis标记在push时记录，等，同时由于参加的比赛少，有些紧张，第一道题卡了挺久，后面做得入迷了心态也好了些。 图，流，最短路 完全图 点与边的数量关系 联通块，染色 A. Vasya and Isolated Vertices   要得到最少的孤立点，就需要每条边都连两个独立点，任意两条边无公共端点； 得到最多的孤立点，就需要尽量密集，尽量构造完全图，完全图上边数m,点数n，m=n(n−1)2m=\frac{n(n-1)}{2}m=2n(n−1)​，那么我们先用尽量多的边去构造完全图，找到n(n-1)/2<m的最大n，接下来可能还剩余一些边，那么我们再拿出一个孤立点，与完全图中所有点相连，可以证明只要拿出一个点就能用完所有剩余的边。 设已构造的完全图中有k个点，则有k(k-1)/2条边，我们再拿出一个点，最多与图中k个点都相连，则共有k(k−1)2+k\frac{k(k-1)}{2}+k2k(k−1)​+k条边，由于k(k−1)2+k−(k+1)k2 ...

greedy 贪心的题目比较杂，主要是要明确贪心什么，要什么越大越好，要什么越小越好。 做得算是比之前的轻松一些，但是容易陷阱去，对一个问题写着写着发现有细节没考虑到，就急了，直接加进去，最后发现代码一团糟，思路也不清楚，还是应该想好框架，考虑完细节处理再动手。 素数数列构造 大数模板 二分 二次分配 因数分解 树形dp A. Prefix Sum Primes   Day2的原题，有其它做法。 一个数列[2,1,2,2,2,······,2,1,1,1,······,1]可以包含该范围所有素数。 123456789101112131415161718192021222324252627282930313233343536373839404142#include<iostream>#include<map>using namespace std;map<int,int>mp;int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int a ...

A. Three Piles of Candies   想法很简单，三个数相加除2，主要是大数模板。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518 ...

DP DP真是做到自闭，除了第一题，其它都是连蒙带猜，状压dp有些熟悉，H题的简单DP也想不到，果然DP和数论是魔鬼。 状态压缩DP 树形DP 简单DP 拓扑排序 A. QAQ   对于Q，若有QA个数大于0，则ans加QA的个数，Q的个数加一，对于A，若Q的个数大于0，则QA的个数加上Q的个数。 1234567891011121314151617181920212223242526#include<iostream>#include<string>#include<cstring>using namespace std;string s;int main() { cin >> s; int len = s.length(); int ans = 0; int qa = 0; int q = 0; for (int i = 0; i < len; i ++ ) { if (s[i] == 'Q') { if (qa == 0)q ++ ; else { ...

random mushup 现场时比较乱，尤其是第一题，理不清思路，补题时好很多，学到三分查找，数论，延迟标记等。 三分查找 数论，模运算 DP求连续子数组元素和最大值 埃氏筛 线段树，延迟标记，区间更新 二维直线 双指针 A. New Year and Rating   根据每一次比赛前的等第列出不等式，若最终不等式右端无穷大，则Infinity，若右小于左，则Impossible，否则确定原值为右端最大值，知道原值后加上所有得分即为最终值。 123456789101112131415161718192021222324252627#include<iostream>#include<algorithm>using namespace std;const int INF = 0x3f3f3f3f;int main() { int n; cin >> n; int high_div2 = -INF; int low_div1 = INF; int so_far = 0; for (int i = 0; i < n; ++i) ...

dp 1234567891011121314double a[maxn];int n;double calc(double k) { double res1 = 0; //正最大 double res2 = 0; //负最大 double sum1 = 0, sum2 = 0;//当前正负最大 for (int i = 1; i <= n; i++) { sum1 = max(sum1 + a[i]+k, a[i]+k); res1 = max(sum1, res1); sum2 = min(sum2 + a[i]+k, a[i]+k); res2 = min(sum2, res2); } return max(fabs(res1), fabs(res2));}

data structure 这次总的来说有些懵逼，不知道系统，做出来的也有很大一部分乱搞的成分，赛后补题学到很多。 erase为O(n)的复杂度。 根据一个条件排序后，二分查找满足另一个条件。 区间过渡 莫队算法 差分 线段树，树状数组   A. Cells Not Under Attack    每次放棋子时，检查棋子所在的行和列是否已经有棋子，若没有，则将未受威胁的格子总数减去（行数+列数-1），若行或列上已经有棋子，则只减去行数或列数，分类讨论即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<iostream>#include<queue>#include<algorithm>using namespace std;#define ll long longconst int maxn = 1e5 + 5;vector<int>x;vecto ...

最大流   汇点 s，源点 t ，每条边有容量限制，求从 s 到 t 的最大流量，即最大流。   对于图G(V,E)G(V,E)G(V,E)，设每条边的实际流量f(e)f(e)f(e)，最大流量（容量）c(e)c(e)c(e) .  Ford-Fulkerson算法    分两步求得最大流： 找到一条从 s 到 t 的且只经过f(e)<c(e)f(e)<c(e)f(e)<c(e)的边路径。沿着该路径尽可能增大f(e)f(e)f(e)，不断重复以上操作，直到不存在满足条件的路径。 只利用满足f(e) < c(e)的边e或者f(e) > 0的边e的反向边rev(e)，寻找一条 s 到 t 的路径，沿着该路径尽可能增加流，不断重复，直到找不到满足条件的路径。    称由满足f(e) < c(e)​的边以及满足f(e) > 0 的边的反向边rev(e)组成的图为残余网络，称残余网络上的s-t路径为增广路。     代码 12345678910111213141516171819202122232425262728293031323334 ...