递归实现指数型枚举 题目 从1 ~ n这n（n<20）个整数中随机选取任意多个，输出所有可能的选择方案。 思路 对于第i个数，你可以选择选或者不选，两种情况分开递归；边界条件为判断完第n个数是否选。 代码 #include<bits/stdc++.h> using namespace std; vector<int> v; int n; void dfs(int x) { if(x==n+1) { for(int i=0;i<v.size();i++) cout<<v[i]<<(i==v.size()-1?'\n':' '); ret...

题目链接 http://poj.org/problem?id=3263 解题思路 选定的一对牛之间的牛的高度都要减一，差分一下，因为最高的为h，所以最后输出差分数组的前缀和，每次输出+h，同时注意判断当前遍历到的这对牛是否已经访问过，若已经访问过，会进行多余的差分操作，使得每个牛并不是尽可能的高。 AC代码 #include<bits/stdc++.h> using namespace std; const int N=1e4+10; typedef pair<int,int> pii; map<pii,bool> vis; int n,p,h,r,a,b,...

题目链接 https://codeforces.com/problemset/problem/1400/B 解题思路 肯定先拿重量小的，重量小的拿完了才能拿重量大的，除非小的都拿不完。首先枚举第一个人拿到重量小的个数，再确定第二个人拿到重量小的个数，再确定第一个人拿到重量大的个数，再最后确定第二个人拿到重量大的个数，四个个数相加的最小值为答案。我只想说大佬的思路太清晰了，这三个min和一个max直接Orz！！！ AC代码 #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; ...

题目链接 https://codeforces.com/problemset/problem/998/D 解题思路 哇，我还搞数学公式啥的，发现自己错误的证明出没有重复的了……打表找规律大佬思路：  AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; ll a[]={1,4,10,20,35,56,83,116,155,198,244,292}; ll n; int main() { cin>>n; if(n<=11) cout<<a[n]<<endl...

题目链接 https://codeforces.com/problemset/problem/998/C 解题思路 别人的正确思路： 任何一段0 1序列都可以看做是一串 0 然后用 1 切割开。首先，因为我们是要把目标串变成全1串，所以开头的1（和结尾的1）我们可以不去管它，所以我们可以把所有的串看做是这种（开头的1和结尾的1无所谓就全都省略）然后我们可以怎么做呢？例如：000 1 000 1 0000 1 00 1 00这个串，因为上面操作的花费与段的长度无关，所以我们可以把相邻的1合成一个1，相邻的0合成一个0。所以原串就可以转化成 0 1 0 1 0 1 0 1 0。假设0分成的段的数量...

题目链接 https://ac.nowcoder.com/acm/problem/20032 解题思路 有坑点啊：1.xiyi能取到0；2.遍历前缀和的范围最小为正方形边长，要不当最大的xi，yi都小于r的时候输出为0。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=5005; int x,y,n,r,b,xx,yy; short ans,mp[N][N],v; short Max(short a,short b) { return a>b?a:b; } i...

题目链接 http://poj.org/problem?id=1958 解题思路 三个的汉诺塔就不细说了，太基础了（还是细说了……）：将n个盘子从A通过B移到C的方案数表示为tir[n]，完成这件事就得先把前n-1个盘子从A通过C移到B，方案数为tir[n-1]；再把第n个盘子从A直接移动到C，方案数为1；最后把B上的n-1个盘子通过A移到C，方案数为tir[n-1]。所以转移方程为tir[i]=tir[i-1]*2+1;至于四塔，我们还是分析这个过程：A，B，C，D四个塔，开始的i个盘子都在A塔上，我们先把前k个盘子在四塔模下移动到B，方案数为dp[k]；然后把i-k个盘子在三塔模式下移动到...

题目链接 https://ac.nowcoder.com/acm/problem/50920 解题思路 很重要的思想就是，1.枚举对第0行的全部操作方案，从第1行开始的每一行，用当前行的开关去维护上一行灯的亮灭。2.判断是否能使全部灯变亮，只需要去遍历最后一行，若不存在灭的灯，成立；因为前面的4行我们已经用其下一行都维护好了，都变成了亮的了。3.当对第0行的操作固定时，是否能使全部灯变亮也已经确定了，且若可行，最少总转换开关的次数也就确定了。 AC代码 #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f...

例题链接  以本题为例讲解  概述 求最小生成树的两种算法：1.Kruskal算法2.Prim算法 熟悉实现思路 下面的讲解比较好，代码可以看我写的。这写的也太好了吧（我真的不是懒）  Kruskal算法（比较简单） 本质是 贪心+并查集这个方法我记得离散数学学过，老师称其“避圈法”。田呈亮yyds！！！ //最小生成树板子 Kruskal算法 并查集实现 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=5100; int a,b,fa[N],rx,ry,n,m; ll c,...

题目链接 https://ac.nowcoder.com/acm/contest/8564/I 解题思路 也不知道大佬是怎么想出来的，要用最小生成树。 一大佬题解：给你的序列a是任意的, 我们就人为添加一个 点(n+1) 且 a[n+1] = 0每次操作 l, r, 可以使得 a[l] 和 a[r + 1] 变得相同最终目标是所有点都可以和 a[n+1] 相同变成 0这不就是最小生成树吗? 另一大佬题解  如果有人不知道最小生成树（比如我）就看看这个吧：最小生成树讲解  AC代码 #include<bits/stdc++.h> #define ll long long using ...

题目链接 https://ac.nowcoder.com/acm/contest/8564/C 解题思路 来自官方题解：首先可以发现当 n 为奇数时必然无解对于 n 是偶数，我们给出两种构造方案 1：以一个 2×2×1 的方块为基本单位，黑白相间摆满整个立方体即可 2：从外向内一圈一圈黑白染色，上下两层颜色相反即可 AC代码1 //对应方案一 #include<bits/stdc++.h> using namespace std; int n; int F;//控制每一层开始的颜色 int f;//控制每一层中每两行颜色的交换 int out;//控制每一层每一个小正方区域（即4个...

题目链接 https://codeforces.com/problemset/problem/445/C 解题思路 题意：求一个图的最大密度，密度定义：为顶点的价值和/边的价值和题解：一个图最大的密度只由两个顶点构成。 证明：V1和V2边价值为a，构成图的最大密度。 若加上与V2相连的一个顶点V3最大，边的价值为b，则要求：V3/b>(V1+V2)/a;那么（V2+V3）/b，就是较大的。所以最大密度就是由两个顶点比他们的边得到的。 详细证明：已知：V3/b>(V1+V2)/a => a*V3>b*(V1+V2) => a*V3+a*V2>b*V1+b*V2...

题目链接 https://codeforces.com/problemset/problem/445/B 解题思路 我直接想错了，我居然在找最大的连通区域，原来即使小的连通区域也会有贡献，我直接忽略了，不知道自己为何如此傻X。思路：n-连通分支数，是化学药品反应的次数，2^(n-连通分支数)为答案。连通分支数用并查集来求。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+100; int a,b,n,m,fa[N]; ll ans; int find(int...

题目链接 https://ac.nowcoder.com/acm/contest/8564/F 解题思路 很多同学是不是没理解题目，画个图（其中f表示翻转次数，f=1表示翻转奇数次，f=0表示翻转偶数次）：   大致思路：数据结构啊，用结构体数组模拟链表。因为涉及类似节点移动的操作，用线性表时间复杂度太高，这时候链表的优势就发挥出来了。模拟过程就好。详细思路：建立结构体数组information[i]，内含两个变量before和after，分别指向i节点的前面节点和后面节点；注：我们模拟的时候是不进行彻头彻尾的翻转操作的，因为太浪费时间了，我们不妨记录下来是否发生了翻转，翻转后的插入操作是将“...