传送门 一棵树每个节点用一个字母表示 已知序,求树的可能结构 害,本来想到了区间,冲动了啊 定义表示根为的合法树的数目 此时要求,意思是在原来树的根上再加一个节点 然后枚举一个使得 有转移 意思是仍然以为根,子树之一是 那么现在,区间也是一个相同的子问题了 状态的理解需要非常准确. #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 309; const int mod = 1e9; int dp[maxn][maxn]; signed main() { ...

G. Xor-MST 最小生成树,但是边太多了,不好写 但是如果按照最高位1来分类成个集合 集合内部连边肯定比较优秀 集合与集合之间连一条边构成树就好了 连哪条边呢?可以采用字典树来完成 #include <bits/stdc++.h> using namespace std; const int maxn=2e7+10; int n,zi[maxn][2],id,a[maxn]; long long ans; void insert(int x) { int now=0; for(int i=30;i>=0;i--) { int t ...

就把p加入字典树 然后删除..... 写法和上一题差不多,所以不说了.... #include <bits/stdc++.h> using namespace std; const int maxn=6e6+10; int n,m,zi[maxn][3],id,isok[maxn],cnt[maxn][3],a[maxn]; bool ok[maxn]; void insert(int x) { int now=0; for(int i=30;i>=0;i--) { int w = ((x>>i)&1); ...

要求个数和异或后,没有出现的最小数字 那么这个数异或后的值是没有用的,因为都出现过 所以我们把所有不是这个数的数插入字典树 这样这些数异或后一定是没有出现的数字 这样贪心找最小值即可 还有一个小技巧,因为 所以不需要真的改变数组的值,只需要把操作数异或起来就可以 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=6e6+10; int n,m,zi[maxn][3],id,isok[maxn]; bool ok[maxn]; void insert(int x) { ...

一点细节没写好结果疯了..... 按照求树直径那样出子树内的最远距离 然后换根求子树外的最远距离 所以数组设置为无穷小,因为我们要求的是最大 #include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,m,x; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v){ d[++cnt]=(edge){v,head[u]},head[u]=cnt; } int ok[maxn],...

每一位二进制互相不影响 所以预处理第位为或者的最后值 这样就是一个简单的数位了 非常简单啊.... #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+10; int n,m; int a[maxn][4],dp[maxn][3]; //dp[i][j]表示在第i位二进制初始是j的情况下现在是多少 signed main() { cin >> n >> m; for(int j=0;j<=30;j++) dp...

定义为跳跃到的最小代价 那么枚举每个座标和每个座标 每个状态都是前一个位置跳跃若干次上来的,所以可以写出很暴力的代码 #include <bits/stdc++.h> using namespace std; const int maxn=10009; int n,m,k,id=1; int x[maxn],y[maxn]; struct p{ int x,l,r; bool operator < (const p&tmp ) const{ return x<tmp.x; } }a[maxn]; int dp[100...

月份的题目,现在又不会写了 暴力枚举每一个点作为堆成二叉树的根节点 这样看上去是的,但是却跑得飞快,跑不满 #include <bits/stdc++.h> using namespace std; const int maxn=2e6+19; int n,m,l[maxn],r[maxn],val[maxn],root,ans=1,siz[maxn]; bool dfs(int u) { siz[u]=1; if( l[u]!=-1 ) { dfs( l[u] ); siz[u]+=siz[l[u]]; } ...

我的解法非常暴力 开10个的数组 因为最多只有9个数去构造 因为对于某一位来说,等于几就需要几个1来构造 #include <bits/stdc++.h> using namespace std; bool a[10][1000009]; int n,top; int main() { char x; while( cin >> x ) { x-='0'; ++n; for(int j=1;j<=top;j++) a[j][n]=(j<=x?1:0); if( x...

m这么小,不用状压也太扯淡了 我们发现有价值的是每条路线上的经过的点集合 定义为第天点,目前走集合为的路线的最小花费 那么使用爆搜出所有路线(当然要剪枝),记录对应状态和花费 发现数组的第一维可以滚动数组变成 又因为每条路线都有点,所以可以去掉变成 就是枚举当前第天的路线,再枚举上一天的路线,这样是的 其实上一天我们只需要最小值就好了,所以过程中就可以取最小值 跑起来也很快 #include <bits/stdc++.h> using namespace std; const int maxn=209; int f[1<<19],vis[209],isok[209],j...

操作二可真是太毒瘤了...可以一直嵌套嵌套嵌套 能不能对操作二进行差分呢??当然可以 而且有一个很重要的性质,前面的操作二不会影响后面的操作二 所以从后往前看所有操作二,对操作在树状数组上差分 为什么在树状数组上?因为可以直接查询此时操作需要执行几次 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+10; const int mod=1e9+7; int l[maxn],r[maxn],top,type[maxn]; int zhi[maxn],a[max...

动笔之前多想想可以节约很多时间 想象一下删掉某条边会会发生什么 就是把以为根的子树砍掉,此时满足子树内的权值是树的三分之一 但是砍掉时候,的祖先们就不能利用这些权值了,所以设置为0 就这样一遍回溯就可以解决 亏我还想了那么久......彩笔 #include <bits/stdc++.h> using namespace std; const int maxn=2e6+10; int f[maxn],root,a[maxn],su,c[maxn]; int ans,q,w; struct edge{ int to,nxt; }d[maxn]; int head[maxn],...

牛客练习赛71 数学考试(两种dp方式+容斥思想) 这道题可以说是对的考察非常特别 好题,但是我是废物,一种做法都没想到 转移是 这部分表示若前个数字不大于,现在就可以放数字来转移 这部分表示若前个数的最大值是,说明还有个小于的没用过 这样最后就是答案 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2009; const int mod=20000311; int p[maxn],dp[maxn][maxn],pre[maxn]; signed mai...

答案是求最小,所以我们可以二分 如何 容易想到,最左边的那个牛肯定要被覆盖,假设他的位置是 那第一个爆炸点选在位置肯定是最优的 所以可以再次进行二分,双二分,没什么好说的 #include <bits/stdc++.h> using namespace std; const int maxn=5e5+10; int a[maxn],k,n; bool isok(int mid) { int now=1,s=k; while( now<=n ) { int nxt = upper_bound(a+now,a+1+n,a[now]+mid*...