寒假营4 D 数论，特判！！ 每次可以把一个数减一，零一个数加一，问最终整个序列有多少种可能的gcd。一个数是整个数组的gcd，他首先一定是每个元素的约数，也就是说所有元素的和是这个数的倍数。 我们现在得到了一个判断的必要条件，但它实际上也是一个充分条件，可以通过构造证明：我们可以把一个数减一，零一个数加一，那么我们实际上就可以把sigma(a(i))的值随意分配到n个位置上。那么如果sigma(a(i))是一个数x的倍数，我们可以把一个元素变成x，剩下的元素都变成kx，k>=1。此时整个序列的gcd就是x了。 前面的比赛时都想到了，但是没考虑到元素个数为1的特判，我以为都说gcd了，肯...

寒假营第五场 B 思维 可以删任意个数的字符串，但是不能删连续两个，每种删除方案的得分是"mygo"出现的次数，问全部方案的总分。 首先一个重要的观察是，由于不能删连续字符，删除后能出现"mygo"的字符串实际上只有八种，具体来说就是"mygo"中间的三个空都可以插入一个其他字符。对于这八种字符串，都有唯一的删除方式使删完出现一个"mygo"。 另一个重要的观察是，既然遍历所有删除方式，分别计算贡献很麻烦，那么我们可以分开计算每一个"mygo"对答案的贡献。对于每一个"mygo"，得到他的删除方式再mygo内部是唯一的，而外部可以随意删。我们需要外部随意删有多少种方案，这些方案的贡献都是1，也...

周赛round32 D 树形dp 每个节点有0或1的权值，设f(i)为从i节点出发，向叶子节点走，可以中途停下，所形成的数字中奇数的个数，求所有f(i)。奇数显然就是最后一位为1，所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定：单独的叶节点不能形成一个数，因此叶节点虽然对祖先的f(i)有贡献，但对自己的f(i)无贡献。 所以这个dfs不能写成无返回值，f(i)初始化为当前节点权值，每次都把儿子节点的f(i)加进当前节点f(i)中的形式从，这样会把叶节点的f(i)也算成1。而应该写成有返回值，f(i)初始化为0，f(i)加上子节点递归返回值，返回f(i)加当前节点权值的形式...

寒假训练营2 C 字典树 求升序子序列个数，其中最大值和最小值的异或小于等于d。如果确定了最小值最大值分别为a[i]，a[j]，，那么中间的数都可选可不选，这组maxmin对总方案数的贡献就是2^(j-i-1)。 直接二重循环枚举minmax显然是不行的，只能枚举一个，然后logn查询另一个。但这个查询是要查询抑或上一个数不超过d的元素个数，此时用字典树才能达到logn。 字典树用叶子节点表示一个元素，从根节点到叶结点的路径则是这个元素的二进制表示，0为左，1为右。查询时，由于异或的结果不大于d，如果d某一位是1，那么minmax在这一位可以一样，也可以不一样，如果不一样，接着往下走，直到达到...

寒假训练营1 E dfs 被骗了，名字叫贪心，实际上是dfs。 注意到比赛场数只有10场，每场只有3种结果，爆搜复杂度也只有3^10，果断dfs。教训是数据小到能爆搜，就直接爆搜。  if(x==m+1){//比完了 int p0=p[0]; sort(p.begin(),p.end(),cmp); // rep(i,0,p.size()-1)cout<<p[i]<<' '; // cout<<'\n'; rep(i,0,p.size()-1){//计算排名 if(p[i]==p0){ ans=min(ans,i+1); return; } } } vect...

小白月赛86 D.dfs 问图中有多少个长方形，正方形也算长方形，并且每个长方形都是当前区域最大的。 判断长方形可以计算连通块面积s，以及横坐标之差最大值mx，纵坐标之差最大值my，如果mx*my=s则是长方形。 int xm[4]={1,0,-1,0}; int ym[4]={0,-1,0,1}; int mxx,mxy,mnx,mny,sum; void dfs(int x,int y,int n,int m){ vis[x][y]=1; sum+=1; mxx=max(mxx,x); mxy=max(mxy,y); mnx=min(mnx,x); mny=min(mny,y); rep(...

周赛Round31 D.map模拟静态数组 给一个数列，要完成两种操作：在一个指定元素的右侧插入，删除指定元素。 维护序列首先考虑一下最经典的两种结构：数组和链表，数组插入和删除都需要O(n)，而本题操作次数有1e5，舍去。链表插入是只需要O(1)，但是寻找插入位置需要O(n)，也不行。 看起来都不行了，那怎么办呢？实际上这是我们的思路被这两种经典模型限制住了，除了数组和指针链表外，还有一种维护序列插入删除的结构：静态链表，对于每一个元素，直接记录他左右的元素，那么插入时，就可以O(1)找到插入位置，O(1)完成修改。不过本题元素大小有1e9，单纯用数组的话会MLE，可以用map进行离散化，代...

周赛Round29 D.小红的中位数 开始想用堆顶堆，但很快就发现每次都只是自在初始序列上删一个之后的查询，中位数只会跟中间几个数有关，只要根据初始序列长度的奇偶和删去元素的位置讨论一下就能以O(1)算出每次查询 如果是偶数，删去元素位于左半边，会让右半边第一个成为中位数，位于右半边，会让左半边最后一个元素成为中位数。 如果是奇数，删去元素位于右边，会让中间数和左边最后一个数得平均数成为中位数，如果位于左边，会让中间数和右边第一个数的平均数成为中位数，如果是中间，那么会让左边最后一个和右边第一个的平均数成为中位数。  rep(i,1,n){ cin>>a[i].val; a[i]....

周赛Round30 D.小红整数操作 首先一个很显然的思路是算出满足大于等于l的最小的x需要乘几，再算出满足小于等于r的最大的y需要乘几，然后这两个数之差就能得到有几组可行的x,y。开始就是这样写的，但是挂了 因为问题是这个思路默认了x,y开始都小于l,r，但这是不一定的。在赛场上意识到这个问题后我一度想分类讨论x,y和l,r的大小关系，但情况太多，显然也是不可行的。 其实仔细看一下，我们除了乘a之外，还可以除a，那我们完全可以先把x,y除到最小，再开始乘，就可以按上面的思路来了，而除到最小需要除gcd(x,y)。 void solve(void){ int x,y,l,r,low,up; c...