与其熬夜通宵抄40页的实验报告，还不如打开b站看看番(明天不能水了～)

之前用树形dp写的,这次用点分治写一下,不解释~ #include <bits/stdc++.h> using namespace std; const int N=2e4+500; const int mod=2019; struct Tree{ int to,val; }; vector<Tree>v[N]; bool vis[N]; int sz[N],f[N],sum,root; long long ans=0; map<int,int>s; void f_root(int u,int fa) { sz[u]=1;f[u]=0; for(int i=...

1.前言 去年湖南省赛有个弱化版的题.点分治和树形dp都可以写.以后一个月不会刻意写题了,准备考试,上海站加油吧,相信自己也相信队友~https://ac.nowcoder.com/acm/contest/1099/I   2.思路 对于题目给定的,假如我们考虑分治一个点,假如分治1,那么我肯定是统计1的所经过链的答案,但是呢,我们肯定会出现不合法的状态,比如我从1到4到6,然后从1到4到5,显然不是一条链,但是这样被计算了,我们只要保留1 4这条边,容斥一下就可以了.当然这只是讲点分治,并没有讲这个题,关于这个题呢,我们可以考虑从1个节点往下数出一个数为a,从下往上数为b.很显然题目就是要你...

不想复习扩展欧几里得了,万年不考的东西...也没太多用.. inline int exgcd(int a,int b,int& x,int& y) { if(!b) { x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int z=x; x=y; y=z-a/b*y; return d; } inline int inv(int a,int m)//a在mod m意义下的逆元 { int x,y,d=exgcd(a,m,x,y); return d==1?(x%m+m)%m:-1; }

自己纸上画画应该就会了,这种题多做点就好了吧,推式子就会快很多,当时省赛没写出来.读了假题+时间太短+太饿了吧?另外感谢清楚姐姐帮忙重现~ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; ll qp(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; }return res; } ll iv; ll Cnt(ll a,ll b) { re...

板子题...并没有太多的变化.和之前做的,唯一的变化就是对于字符串可以哈希成数字的变成点权.代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+50; //可以用map把每个字符串做一次离散化,这样就相当于查询权值了. map<string,int>mp; vector<int>v[N<<1]; int w[N];//存这个点的权值. int dfn[N],Son,sz[N]; int dep[N]; set<int>s[N<<1]; st...

1.题意 给你n个数,n个数的权值,然后它们连边的规则是每个数连向它们异或最小的边.然后问你最少删掉多少个数,才能使得它们构成一棵树?  2.思路 对于位运算,我们应该从高位向低位进行.既然是从高位向低位进行,那么思考一下,假如那个高位有两个1,两个0,它们会如何连边.必定是1与1相连,0与0相连,所以考虑每一位,假如我选取1的话,这位为0的点就只能保留一个,假如我这位选0的话,这位的1的点就只能保留一个.所以直接dfs在字典树上跑就好了...maybe?  3.代码 #include <bits/stdc++.h> using namespace std; const int N...

可不可以现在开始鸭~

快挂科的菜鸡可能真的不能太刷题了...列下以前欠的题目.然后贴一下吧....然后题解都在这个博客更吧><https://atcoder.jp/contests/arc109/tasks/arc109_c (完成,https://atcoder.jp/contests/arc109/submissions/18501522) https://vjudge.net/contest/409728#problem/C (完成)  https://codeforces.ml/gym/102832/problem/F (完成,我就是个***...) https://vjudge.net/con...

这题思路就还行!  1.思路 可以思考下如何判断回文串,回文串的组成必定奇数字母小于等于一个.如此,我们把每个数都表示成二进制的形式.只和奇偶有关.这里开(1<<23)即可.D[u]表示从根节点1到u节点,a-v的奇偶性情况.然后我们只需要开个C数组,C[D[u]]表示当前子树下,值为D[u]的节点最深的深度是多少,考虑合法的方案数,必然答案是2^i/0才能组成回文串对吧?然后又贪心+dp一下.首先子树的最长回文串可能就是子树中的答案,然后还可能是根节点到某个子树的分支,最后可能是根节点到两个子树的分支,取个max大功就告成了!  2.代码 #include <bits/st...

树状数组维护下dsu on tree即可.复杂度为O(nloglogn). #include <bits/stdc++.h> using namespace std; const int N=1e5+50; int c[N],cnt[N],ans[N]; vector<int>v[N]; map<int,bool>mp; struct DSU{ int id,k; }; vector<DSU>ask[N]; int Son,dfn[N],sz[N]; int d[N];//记录大于等于i的颜色数量有多少. int sum[N]; int lowb...

https://vjudge.net/contest/406992#problem/B

1.思路 对于这题来说,总的来说还是dsu的一个板子,我们计算完了之后暴力更新就好了.复杂度是O(26*nlogn)的.  2.代码 #include <bits/stdc++.h> using namespace std; const int N=5e5+50,M=26; struct DSU{ int id,k; }; vector<DSU>ask[N]; vector<int>v[N]; bool ans[N];//存询问的答案. char s[N]; int dep[N],sz[N],dfn[N],Son; int tot[M][N];//统计当前在...

1.算法 尺取+树状数组(nlogn)  2.实现 对于每个i来说,维护一个[l,r].然后对于每个i维护一个区间L[i],R[i]表示这个区间最大数量为k的可行区间.这里可以用个尺取就行.求出区间了之后呢,因为离线,我们可以考虑将所有区间进行排序.然后对于每个区间来说,我们可以枚举移动的点,也就是i,然后更新这个区间的答案,因为是排序完了所以必然是互不影响的,我只要控制指针移动即可得到答案.  3.代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+50; s...