HLAIA-光子

树形DP 首先是树的储存，树的储存是图的储存的特殊情况，可以用邻接表储存，或链式向前星 洛谷P2015二叉苹果树 定义状态dp[u][j]表示以节点u为根的子树上留 j 条边时的最多苹果数量。dp[1][q]就是答案。 状态转移方程：dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w) 其中，v 是 u 的一个子节点。dp[u][j]的计算分以下两部分： dp[v][k]：在v上留k条边 dp[u][j-k-1]：除了v上的k条边，以及u-v边，那么以u为根的这棵树上还有j-k-1条边，它们在u的其他子节点上 总复杂度小于O(n3) PS： 这道题是无向图储存，因为题目没有说明输入的两个节点哪个是爹哪个是儿，所以要push_back两次，然后在搜的时候跳过father j 循环必须递减，例如dp[u][5]会用到dp[u][4]和dp[u][3]等等，若是递减循环，先算5，再算4，再算3…dp[u][5]用到的是dp[u][4]和dp[u][3]的原值；若是递增循环，dp[u][5]就会用到dp[u][4]和dp[u...

本部蓝桥试炼 续上回 B 线段树板子，但奈何我现在没法手撕线段树哇(码太长了) 遂选择树状数组，但是–按理说树状数组（nlog2n）的复杂度是能过此题的，而且赛后题解里也说了树状数组能过，为什么才拿25分？？ (后来发现问题了–忘记取模，唉) 题补就写线段树的吧 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e5+10;const int mod = 1e9+7; int a[N]; int tree[N<<2]; int tag[N<<2]; int ls(int p){return p<<1;...

牛客月赛113 A 签到 12345678910111213141516#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int sum = 1; string s; cin >> s; for(char i : s){ if(i == '-') sum -= 1; else sum *= 2; } cout << (sum >= 2025 ? "YES\n" : "NO\n"); return 0;} B 统计相邻相同字符即可 12345678910111213141516#include <bits/stdc++.h>using namespace std;int ...

牛客周赛86 A 签到 1234567891011#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int x,y; cin >> x >> y; cout << (y%x ? y/x+1 : y/x) << '\n'; return 0; } B 贪心，很明显删除全部负数就可以使总和最大，也就是把正数相加 1234567891011121314151617181920212223#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 2e5+1;signed main(void){ ios::sync_with_stdio(fals...

牛客周赛 85 A 签到 1234567891011#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin >> n; cout << (n%2 ? "kou\n" : "yukari\n"); return 0;} B 贪心 由题目可知，小红和小紫的拿取元素的倾向都是拿尽可能小的元素 因此直接对数组升序排序，然后遍历数组对x进行操作即可 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+1;int arr[maxn];int main(void){ ios::sync_with_...

牛客周赛84 续上周 D 赛时用的数学方法，花的时间和代码量比较多。差分我写得少，这里用题解的差分方法补个题 用差分数组对每个k区间做修改，然后求和以及相邻数字绝对值差对陡峭值的贡献即可 123456789101112131415161718192021222324#include <bits/stdc++.h> using namespace std;const int maxn = 1e6+1;int t[maxn],d[maxn];int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,k,ans=0; cin >> n >> k; string s; cin >> s; for(int i=1,j=k;j<=n;i++,j++){ d[i]++; d[j]--; } t[0]=0; for(int i=1;i...

牛客月赛 111 A 贪心，田鸡的最大的a比齐威王次大的v大，田鸡的次大的a比齐威王最小的v大就能赢 123456789101112131415161718#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int v[3],a[3]; for(int i=0;i<3;i++) cin >> v[i]; for(int i=0;i<3;i++) cin >> a[i]; sort(v,v+3); sort(a,a+3); if(a[2] > v[1] && a[1] > v[0]) cout << "Yes\n"; else cout << "No\n"; ...

牛客周赛81 A 题目 签到 代码 12345678910111213#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int a,b,c; cin >> a >> b >> c; if(a==b && b==c) cout <<"Yes\n"; else if(a+1==b && b+1==c) cout << "Yes\n"; else cout << "NO\n"; return 0;} B 题目 一颗完全二叉树，如果每个节点的两个子节点都不小于它，那么这称颗二叉树是“平衡的”。数据量不大，把树储存在二维数组里，逐节点判断即可 如果某个节点满足G[i][j...

牛客周赛80 A 题目 签到 代码 123456789101112#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int x,y; cin >> x >> y; if(x >= y) cout << x-y << '\n'; else cout << "quit the competition!\n"; return 0;} B 题目 降序排序，相邻两项之间相减，取绝对值，求和即可 代码 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;const int maxn = 2e5+1;bool cp...

牛客寒假训练营1 大家都报了训练营呐，那我也报一个 ^v^(虽晚不亏) 补一下之前的 A 题目 这题考察素数。由题目得，ai不超过1e9，因此如果给的数有1就输入-1(1和任何数都构成倍数关系)，否则输出任意一个比1e9大的素数、 那比1e9大的素数怎么找呢？ 新开一个cpp，用埃氏筛把这个数找到，是999999937，CV 代码 埃氏筛 1234567891011121314151617181920212223#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn=1e9+5;bool visi[maxn];vector <int> prime;void sushu(){ for(int i=2;i*i<maxn;i++) if(!visi[i]) for(int j=i*i;j<maxn;j+=i) visi[j] = true; for(int ...