我们可以轻松地发现这道题是一道dp的题目 对于整张图来说，总共有2*n-2地度数，由于每一个点都至少有一个度数，我们就只剩下n-2的度数可以进行自由分配 我们将每个点看做一个点加上一条没有连上其他点的边，然后在更新的时候将所有点联向当前树的叶子节点上，然后根据其度数做一下背包就好了 f[i] 表示树上已经有i 个点的最佳权值 假设度数为i的贡献为a[i]，当一个节点插入的时候，会损失a[1]的价值，增加a[i-j+1]的价值，所以转移方程为 f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i; 然后直接转移即可 ...

首先要明确题干中有两个限制条件 墙不能穿过。 除墙和终点外其余地方均有一个豆子 结合上述两个限制条件和样例一，不难得出，若一个人能从起点到达终点，则它可以获得$n$个豆子。 所以原问题就可以等价于：判断这两个人”能否达到终点，且路径不重合“。 由于人只能向下走或向右走，假设在第一行没有墙。所以在起点开始时，一个人向下走，一个人向右走。 先看这个向下走的人，当他在向下走的过程中碰到第一堵墙时，他就必须向右走。我们称这堵墙为第一列的特殊墙，其位置记为$(1,y_1)$。再看向右走的人，不然发现只有当他进入第三列后不会遇...

非常经典的回溯算法，可以算作板子题练手 举个例子将 $a=coca$变为 $b=caoc$ 从第一个字符比较。容易发现$dfs$里有两个变量，一个是当前位置$pos$，另一个是在当前位置时已经交换了的次数。 $pos=0$，$a[0]=b[0]$，直接$dfs$下一位置 $pos=1$，$a[1] \neq b[1]$，我们要找到使得$a[i]=b[1]$的$i$，然后交换二者。尤其注意要**恢复**你刚才修改的状态。 注意：边界是$pos=8$ 按照上述思想，很容易写出此题的代码。 ```c++ #include <bitsdc++.h> using namespa...

A 不知大家有没有发现一个小细节，这道题所有的数字都和 2 有关。 直线上第 $i$ 个格子所代表的米粒数在二进制下表示为一个（自右往左）第 $i$ 位为1，其余位为0的一个二进制数。 考虑数 $s$ 在二进制下的表达方式，其某一位为1则判断一个该位是否存在米粒。 #include<cstdio> #define LL long long const int MAXN=68; bool vis[MAXN]; int main() { int n,k; LL s; scanf("%d%d%lld",&n,&k,&...

思路：设置两个源点，。s 连红色格子且上限为正无穷， 连白色格子且上限为 ，相邻格子双向两边上限为1。求此网络中的最小割。 #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<map> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=910; const int maxm=1e4+10; int level[...

给出两个结论 对 进行质因数分解，若只含有质因子和，则是不循环小数，即 否则，是循环的，且循环开始于小数点后第位，其中，表示表示质因数分解形式下的指数项，表示质因数分解下的指数项。即 首先，类似前缀和的思路，只要能求解~ 的答案，相减就可以得到的答案。下面，我们考虑一种类似容斥的做法，记表示~ 中的倍数有多少个。初始时，然后我们按照的值从大到小遍历，每遍历到一组，就对所有的进行一次。这样，当继续往下遍历的时候，就能保证总是能“恰好”被整除的数的个数（而不会被更大的数整除）。在遍历的时候顺便统计答案即可。 总复杂度，足够通过本题（尽管代入左式算出来会有的运算量，但由于上式复杂度估的很粗，偏...

我们可以轻松地发现这道题是一道dp的题目 对于整张图来说，总共有2*n-2地度数，由于每一个点都至少有一个度数，我们就只剩下n-2的度数可以进行自由分配 我们将每个点看做一个点加上一条没有连上其他点的边，然后在更新的时候将所有点联向当前树的叶子节点上，然后根据其度数做一下背包就好了 f[i] 表示树上已经有i 个点的最佳权值 假设度数为i的贡献为a[i]，当一个节点插入的时候，会损失a[1]的价值，增加a[i-j+1]的价值，所以转移方程为 f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i; 然后直接转移即可 #include<cstdio&...

b题非常经典的回溯算法，可以算作板子题练手 举个例子将 变为 从第一个字符比较。容易发现里有两个变量，一个是当前位置，另一个是在当前位置时已经交换了的次数。 ，，直接下一位置 ，，我们要找到使得的，然后交换二者。尤其注意要恢复你刚才修改的状态。 注意：边界是 按照上述思想，很容易写出此题的代码。 #include <bitsdc++.h> using namespace std; int ans = 10; char a[10]; char b[] = "cocacola"; inline void dfs(int pos, int move) { i...

C题首先要明确题干中有两个限制条件 墙不能穿过。 除墙和终点外其余地方均有一个豆子 结合上述两个限制条件和样例一，不难得出，若一个人能从起点到达终点，则它可以获得个豆子。 所以原问题就可以等价于：判断这两个人”能否达到终点，且路径不重合“。 由于人只能向下走或向右走，假设在第一行没有墙。所以在起点开始时，一个人向下走，一个人向右走。 先看这个向下走的人，当他在向下走的过程中碰到第一堵墙时，他就必须向右走。我们称这堵墙为第一列的特殊墙，其位置记为。再看向右走的人，不然发现只有当他进入第三列后不会遇见任何一堵墙它才可以到达终点，我们称这堵墙为第三列的特殊墙,其位置记为。 画图容易发现，当第二列...

不知大家有没有发现一个小细节，这道题所有的数字都和 2 有关。 直线上第 个格子所代表的米粒数在二进制下表示为一个（自右往左）第 位为1，其余位为0的一个二进制数。 考虑数 在二进制下的表达方式，其某一位为1则判断一个该位是否存在米粒。 #include<cstdio> #define LL long long const int MAXN=68; bool vis[MAXN]; int main() { int n,k; LL s; scanf("%d%d%lld",&n,&k,&s); for(i...

dfs wa了大佬们帮帮我 #include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack&...