The 2019 ICPC Asia Shanghai Regional Contest(重现赛) The 2019 ICPC Asia-East Continent Final 2018 ACM-ICPC EC-Final  2016年 Asia Regionals Contests The 2016 ACM-ICPC Asia Shenyang Regional Contest The 2016 ACM-ICPC Asia CH...

好久没写代码了，我太菜了。做一下签到题，结果写的又慢，脑子还转不过来。出题人的题解是排序做的，我没有排序。(其实也差不多判断一个题是签到题一共两个条件， 通过人数大于等于全场人数的80% 通过人数是所有题目前三多的题对于第一点，只需要判断 就好对于第二点，遍历一遍，记录一下有多少题目的通过人数比I题多这个数字小于等于2的话，这道题目就是签到题啦#include using namespace std; int main() { int n,m; cin>>n>>m; int a[20000]; for(int i = 0 ; i< n ; i++) { ...

2020牛客寒假算法基础集训营已经开始啦~ 欢迎参赛的小伙伴来写出你的感受/建议！ 你们的建议是我们改进的方向和动力~ 建议回复格式：场次+内容 例：【第1场】感受:XXXXXXXX 我们将抽取6位回复的小伙伴赠送100牛币 开奖日期:2020年2月20日

A、 序列 每组i，j对答案的贡献可以分开考虑。对于给定的i，j，对于所有在s[i], s[j]之间的数字k，答案的贡献是2^(n-j+i-1)。那么我们可以从小到大枚举数字k，每次k上升1的时候都有一些位置对被激活，一些位置对被关闭，这些位置对共享一个公共点，用线段树维护delta即可。 B、 四边形不等式 注意到一个集合其实就是若干个区间。 把这些区间的函数值加起来当做集合的函数值就行了。 C、 10^5万 这个题有很多种构造方法。可以按照k模3的余数分情况构造，也有比较漂亮的统一构造方法（考虑数字连续的一些牌，每种有3张，除了第二小的有4张。如1112222333444555。） D、 ...

难度分布 Easy: C,K,L,M,N Easy-Medium：J,F,I,G Medium：D,E,H Medium-Hard：A,B A. Convolution 2^(ab)=sqrt(2)^((a+b)^2-a^2-b^2) 对每个 a+b，求出 sqrt(2)^(-a^2-b^2) 的和 NTT 时间复杂度：O(nlogn) B. 双圈覆盖 先将每个点度数变成3：拆点 之后⼀定有偶数个点，且去掉环后点两两配对了 第⼀类圈：最外层的环...

Note: Some problems have been weakened. A、 Alternative Accounts There are at most contest. We consider the hardest case that . For each account, wecompute the set of contests it participated in.Let be the number of accounts whose participated contest is set .It is easy to see for an account tha...

A、黑色气球 签到题 ？ B、小吨的点分治 假设我们已经对一棵树进行了点分治得到对应的点分树。如果我 们删去原树中的一条边，把得到的两个连通块中的点分别称为黑点和白点。对于点分树中的每个白点（黑点），我们找到它的祖先中最近的一个白点（黑点）作为它新的父亲，这样就能得到两棵全由白点组成的树和全由黑点组成的树（因为有且仅有一个白点和黑点找不到同色的祖先），它们分别为原树切分得到的两棵树的点分树。 反过来再考虑，如果我们把两棵树通过一条边 连接起来，我们怎样把原有的两棵点分树合并起来，并且保持原本点分树中的祖先后代关系呢？可以发现，我们只要把 到所在点分树根节点的路径以及 到所在点分树根...

难度预期 预期A,C < E < D,K,I,H < J < F,B < G 实际：A,C < E < H,K < F < B,J < D,I < G A 托米的字符串 题意：统计所有子串元音字母占比的平均值 题解：令表示前个字母中元音字母个数令长度为的子串中元音字母出现的个数之和为， 最后答案是. C 纳新一百的石子游戏 题意：对于每个前缀的所有石子堆，询问先手必胜方案数。 题解：设当前异或和为，则要找到的就是有多少堆石头满足，这样就能将变为来使得异或和为。考虑异或和的最高的为的二进制位，所有这一位是的显然都满足条件，这一位是...

A、期望逆序对 medium假设最终序列是 ，它作为最优解的一个必要条件是交换两个相邻的位置 不能让答案变得更优。交换两个相邻的数的时候，只有它们之间的相对顺序发生了改变，所有这个条件也可以被写成所有 是逆序对的概率不超过 。对于两个随机变量，考虑（x，y）是逆序对的概率不超过。的条件：1.，这时 的区间整体在 的左侧，因此形成逆序对的概率不超过号。2.，即 的区间包含 的区间时，如果 的区间在 的区间的正中央时，根据对称性，形成逆序对的概率是恰好。因此当 在 中间偏右的时候，逆序对的概率就小于了；中间偏左的时候，逆序对的概率大于。综上，条件可以被总结为。因此最开始把所有区间按...

你是不是也有这个常态？ 当信心十足想刷个题的时候。。。 怎么这么多题？？算了，还是下次再做吧。 作为竞赛选手，我们需要做题，更需要科学做题——有规划！有路线！ 牛油A：“有没有最短路的练习题集呀？” 牛油B：“想做蓝书的题，一道一道地找好麻烦。” 牛油C：“想把之前做过的题目整理在一起。” 牛油D：“我刚入门，该做哪些题目？” 牛油E：“我汇总了这几场比赛中数论的题目：链接 链接 链接 链接 链接...” 现在，牛客题单功能上线啦！~ ...

https://vjudge.net/problem/UVA-514 解题思路：.A的铁轨从1到n依次判断 如果和当前轮到的铁轨相同 则从A驶入B，如果不相同，则入栈等候。每次判断之前先判断栈顶的元素是否和当前轮到的铁轨相同 直到不相同为止。 #include<iostream> #include<stack> using namespace std; int main() { int N; while(cin >> N&&N) { int target[1010]; while...

https://vjudge.net/problem/HDU-6152 我也是绝望啊 怎么写怎么超时 居然是人数大于6就直接是bad team了。 证明：先从6个人中选出一个人，他与另外5人要么认识，要么不认识。 所以至少有3个人对于他是一样的（至少有三个人他都认识或都不认识）。 假设这3个人他都认识。 再看这三个人，若是他们三个中有两个人认识，则这两个人已经与第一个人组成3个人，互相都认识；若是他们三个中两两都不认识，则他们三个人两两都不认识。 用图形来表达也许会更好： 假设6个人是6个点，其中两个人认识就用红色线段连线；若不认识就用黄色线段连线。只需证“其中必有一个同色三角形”那么...

https://vjudge.net/problem/UVA-122 学习的第一个关于树的题目，按着紫书上的思路来的。再整理一下 #include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; struct Node{//结点的结构体 bool have_value; int v; Node *left,*right; Node():have_value(false),left(NULL),...

https://vjudge.net/problem/HDU-1003 刚开始接触DP算法，细节上错了好多次。整理一下 dp数组存储以a[i]为结尾的和最大的子序列的值。 如果dp[i-1]是负的则dp[i]肯定等于a[i]，并更新起始位置。 最后判断一下dp[i]是不是目前最大的。 #include<iostream> #include<cstring> using namespace std; int a[100005]; int dp[100005]; int main() { int T; cin >> T; for...