关键词：
一时暴搜一时爽 一直暴搜一直爽 cxl居然和我写的同款dfs，天呢
菜鸡开始对这题并没有什么想法 状态方程死活想不出来 还是暴搜好
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define rg register 5 const int N=200,K=100,P=9901; 6 int n,k,f[K+5][N+5],ans=0; 7 template <class t>void rd(t &x) 8 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 14 15 void dfs(int deep,int l,int r) 16 17 if(deep==k&&(l+r+1)==n) ++ans;ans%=P;return; 18 if((l+r+1>=(1<<deep))||deep>k) return; 19 dfs(deep+1,l,r+2);dfs(deep+1,l+2,r); 20 dfs(deep,l+2,r);dfs(deep,l,r+2); 21 22 23 int main() 24 25 freopen("nocows.in","r",stdin); 26 freopen("nocows.out","w",stdout); 27 rd(n),rd(k); 28 if(n==(1<<k)-1) printf("1");exit(0); 29 dfs(2,1,1); 30 printf("%d",ans); 31 return 0; 32
然后考完一讲 dp[i][j]表示j个点不超过i层的方案数 不超过？！ 怎么可以这么机智啊啊啊啊 我怎么就想不到
然后最后答案用dp[k][n]-dp[k-1][n] 因为中途%了有可能减出来为负 最后要+P然后% 别问我为什么知道
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define rg register 5 const int N=200,K=100,P=9901; 6 int n,k,f[K+5][N+5],ans=0; 7 template <class t>void rd(t &x) 8 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 14 15 int main() 16 17 //freopen("nocows.in","r",stdin); 18 //freopen("nocows.out","w",stdout); 19 rd(n),rd(k); 20 for(rg int i=1;i<=k;++i) f[i][1]=1; 21 for(rg int dep=1;dep<=k;++dep) 22 for(rg int i=3;i<=n;i+=2) 23 for(rg int j=1;j<i;j+=2) 24 f[dep][i]=(f[dep][i]+f[dep-1][j]*f[dep-1][i-j-1])%P; 25 printf("%d",(f[k][n]-f[k-1][n]+P)%P); 26 return 0; 27
[luogup1472]奶牛家谱cowpedigrees（dp）
传送门 一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。然而我真的没有想到。 f[i][j]表示深度为i节点数为j的个数sum[i][j]表示深度小于等于i节点树为j的个数 #include<cstdio>#de... 查看详情
奶牛家谱cowpedigrees(代码片段)
令人窒息的奶牛题题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)。这些二叉树有如下性质:每一个... 查看详情
美国血统
【题目描述】农夫约翰把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和... 查看详情
luogu1345奶牛的电信（网络流）
【Luogu1345】奶牛的电信（网络流）题面题目描述农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,...,a(c)，且... 查看详情
[luogu2847]奶牛广播-金(代码片段)
...0)为了在他们之间传播信息,想要组织一个"哞哞广播"系统.奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫,所以每一头奶牛都必须有一个步话机.这些步话机都有一个限制传播半径,但是奶牛们可以间接地通过中... 查看详情
luogu1345奶牛的电信
拆点、最小割的模板题。 我只想说一点。拆点时不可以下意识地初始化！起点和终点不能直接写编号！写拆点后的Id！#include<cstdio>#include<cstring>#include<algorithm>#include<queue>usingnamespacestd;#defineIn(x)(x)*2-1#defi... 查看详情
luogu2869挑剔的美食家(代码片段)
GourmetGrazers传送门题目大意约翰的奶牛对食物越来越挑剔了。现在，商店有(M)份牧草可供出售，奶牛食量很大，每份牧草仅能供一头奶牛食用。第(i)份牧草的价格为(P_i)，口感为(Q_i)。约翰一共有N头奶牛，他要为每头奶牛订购一... 查看详情
luogu1843奶牛晒衣服
点此进入原题算法：二分答案题解：本题算法就是二分所需的时间啦二分答案的难点大部分都在check函数上吧然而我居然把二分模版打错了好囧啊总的来说这题还是不难的啊~代码：#include<cstdio>constintN=500005;intn,a,b,t[N],l=0,r=N;bo... 查看详情
luogu2996拜访奶牛
点此进入原题算法：树形DP题解：一道树形dp。由题意可知，这题是树形结构题。我们设f[i][0]，表示不访问i号节点，f[i][1]表示访问i号节点。因为访问了i号节点，则不能访问i的孩子节点，所以可以得出下面的式子：f[i][0]+=max{f[k]... 查看详情
luogu1113杂物(拓扑排序)
题目描述John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才... 查看详情
luogu2858奶牛零食题解--区间dp(代码片段)
题目链接https://www.luogu.org/problemnew/show/P2858一句话题意:https://cn.vjudge.net/problem/POJ-3186#author=Re0分析很显然这道题是不行滴,但是把这个数列看作从一个个区间倒着向外扩展取数而成的话,这样就保证了最优子结构和无后效性两个特点,... 查看详情
题解luogu2915[usaco08nov]奶牛混合起来mixedupcows(代码片段)
题目描述EachofFarmerJohn’sN(4<=N<=16)cowshasauniqueserialnumberS_i(1<=S_i<=25,000).Thecowsaresoproudofitthateachonenowwearshernumberinagangstamannerengravedinlargelettersonagoldplatehung 查看详情
luogu3067平衡的奶牛群meetinthemiddle(代码片段)
题意：给出$N$个范围在$[1,10^8]$内的整数，问有多少种取数方案使得取出来的数能够分成两个和相等的集合。$Nleq20$ 发现爆搜是$O(3^N)$的，所以考虑双向搜索。先把前$3^fracN2$搜完，然后每一次搜出后$3^fracN2$的时候，枚举前面... 查看详情
[題解]（最小生成樹）luogu_p2916安慰奶牛(代码片段)
可以發現每個點經過次數恰好等於這個點的度數，所以把點權下放邊權，跑最小生成樹，原來邊權乘二在加上兩端點權，答案再加一遍起點最小點權#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintmaxn=10010;constintmaxm=100010;in... 查看详情
[luogu3067usaco12open]平衡的奶牛群(代码片段)
传送门Solution折半搜索模板题考虑枚举每个点在左集合和右集合或者不在集合中，然后排序合并即可Code//ByMenteur_Hxy#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorit 查看详情
洛谷p1827美国血统americanheritagelabel：字符串water
题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是... 查看详情
luogu2917_[usaco08nov]奶牛混合起来mixedupcows_key
题目传送门看到数据范围就果断装压。设f[i][j]表示i状态下最后一个数字为a[j]。code： #include<cstdio>usingnamespacestd;intN,K,a[17];longlongf[1<<16][17];inlineintabs(intx){returnx>0?x:-x;}intmain(){scanf("%d%d",& 查看详情
[luogu2870][usaco07dec]最佳牛线bestcowline(贪心+后缀数组)(代码片段)
...stCowLine(贪心+后缀数组)题面FJ打算带他的(N(1leqNleq30,000))头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。今年，竞赛委员会在接受队伍报... 查看详情