F. Forest Program（图论、环的求取） 思路：如果没有环的话，每个元素都没有限制，总贡献2^n。但条件是必须使剩下的图全是树，也就是说环必须去掉。那么直接dfs深度优先搜索，看有多少个环，用deep记录长度。每遍历到一个环就把乘上这个环的贡献 pow(2,环的长度)-1（这个环只有所有边全取的情况不行）。 Code: #include<iostream> #include<string> #include<stdio.h> #include<map> #include<memory.h> #include<vect...

题目 思路：首先想能不能在原有的b中出现* * * * 1 2 3 … k，如果可以的话则利用b中原有的再添上前面的即可构成1 2 3 …n，但这个构成有一个限制，对于每一个从k往后添加k+1 k+2 … n一定要连贯着一次性达成，如果中间出现k+x没取的到，要再从前面取几个用0做缓冲，则该顺序一定会混入0，方案作废。 剩下的情况，则看一个b数组中最多需要额外多取几个才能在用到该数时能放到底部，例如 n=6 b:0 0 2 5 6 3 对于第3个元素5，想要取到其需额外先取次数 = 3 - 4（5前面会先输出4个数，所以能少额外取4个），对于第二个元素2 想要取到其需额外先取次数= 2 - 1...

ax+by=c，求出其中一组解x y int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 {  if(b==0) {  x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=y; //把x y变成上一层的 y=x-(a/b)*y; x=temp; return r; //得到a b的最大公因数 } bool linear_equation(int a,int b,int c,int &x,int &y) {  int d=exgcd(...

题目 思路：要找到满足 x+y<=n x⋅w+y⋅d=p, ->xw+yd+wd-wd=w*(x+d)+d*(y-w) 因为w>d，令x1=x+d,y1=y-w，x1+y1<x+y 只要x⋅w+y⋅d=p成立，w*(x+d)+d*(y-w)也成立，一旦y>w就可以化为y1=y%w使得x1+y1更小的情况，所以只要枚举y=[0,w-1]的所有情况即可 Code: #include<iostream> typedef long long ll; using namespace std; const int Max = 1e6 + 5; int a[Max]...

题目 思路：假设有只有一种数字，答案为该数字数量，两种数字，答案为大的数量减去小的数量，三种数字，假设数量从小到大排序 s1 s2 s3 ,可以知道当s1+s2<=s3, 答案为s3-(s1+s2) 当s1+s2>s3 ,如果(s1+s2+s3)%2 == 0,答案为0，(s1+s2+s3)%2 == 1，答案为1（这里好好想想应该不难，cf有一道800分的题就是只有三个数的）。然后对于数字种数为3个以上的情况，其实都可以转化为3个的情况。 Code: #include<iostream> #include<map> #include<algorith...

题目 思路：首先可以肯定的是，在某个数第一次出现时，在那个位置一定要填该数，因为它更新了那个最大的数，这些数的位置是固定的。 对于求最小的情况，只需从1–n开始填那些不是固定的数空出来的地方,如果该数是上文提到的固定的数则跳过。 对于求最大的情况，创建一个multiset（当作一个优先队列来使用,按降序排列），从开始的位置1遍历到n,如果遇到一个固定的数则输出该数，然后将该数之前到上一个固定数之间的数insert进multiset。如果该位置不是固定的数，则将multiset中最大的数输出，然后erase掉该数。这样做的原因是，要想数列最大，又不能超过前面那个数，如果超过了就会造成更新，而更新...

题目 思路：对于c⋅lcm(a,b)−d⋅gcd(a,b)=x，由裴蜀定理可得想要使该式c,d为整数成立则x=k * gcd(gcd(a,b),lcm(a,b))=ngcd，所以第一个条件得出gcd的是x的因数。且c,d,x都已经明确给出，我们枚举每个x的因数作为gcd时会得出对应的lcm=(dgcd+x)/c，如果lcm不为整数排除。 那么现在我们已经花费O(n^(1/2))求出了每个gcd作为x的因子，现在要求的就是每一步中知道了gcd(a,b),lcm(a,b)求出相应的a,b有多少种可能。 a,b,gcd,lcm关系差不多如上图，将lcm/gcd=(a/gcd) * (b/gcd)，l...

题目 思路：开一个优先队列存放每一行（高度1）还剩余的长度，将所有的木块从大到小排序，1开始遍历，如果优先队列中还能容纳最大的长度比当前木块大则加入到当前高度所在行，否则另开一行存放。 Code: #include<iostream> #include<algorithm> #include<set> #define ll long long using namespace std; const int Max = 1e6 + 5; int lst[Max]; int main() {  int t;cin >> t; while (t--) {...

题目 思路：模拟一下过程，有n个平面，那么在一次飞跃中位于第1个平面的粒子向右飞会在后面每个平面都产生一个粒子，那第一个平面有m个粒子后面每个平面2–n都产生m个粒子，同理第二个平面的每个粒子也会对其后面的所有平面产生一个粒子。然后最共会裂变n-1次进行这么多次飞跃,每一次飞跃记录结果作为下一次飞跃的各平面所拥有的粒子数,再每次飞跃变换一下方向即可。再来看一下数据大小n<=1000,k<=1000。 如果直接暴力模拟 O(n^3)，但对于给第i个平面后面所有平面粒子+1的操作可以用前缀和处理，复杂度变为 O(n^2)，细节见代码。 Code: #include<iostrea...

对于正整数来说：原码、反码、补码都一样。 但对于负整数：原码、反码、补码符号位都为1，反码等于原码各位取反，补码等于源码各位取反＋1. 再来说移码，就是将补码符号位取反可得。 例： +9 源码： 01001 反码： 01001 补码： 01001 移码： 11001 -9 源码： 11001 反码： 10110 补码： 10111 移码： 00111

转载于某大佬的github用来收藏https://github.com/fool2fish/dragon-book-exercise-answers/find/master

思路：从一开始，直接暴力DFS，每次有三个选择*3 *5 *7，遇到小于结果的sum++,大于则返回。 #include<iostream> #include<map> typedef long long ll; using namespace std; map<ll, int> ma; ll sum = 0, s = 0; void dfs(ll a) {  if (a >= s)return; if (ma[a] >= 1)return; ma[a]++; sum++; dfs(a * 3); dfs(a * 5); dfs(a * 7); ...

直接模拟一波，看到数据比较小就不用记忆化搜索了，每次搜索直接暴力，然后判断是否兜圈子，用一个sum记录步数,sum>200还没走完则为兜圈子。 Code: #include<iostream> #include<map> #define pii pair<int,int> typedef long long ll; using namespace std; map<char, pii> ma; ll sum = 0, s = 0; char lst[105][105]= {  { 'U','D','D','L','U','U','L','R...

思路：有两个问题需要解决，一个是每次遇到一个括号把括号里的运算当成一个整体处理，第二个是遇到 | 时将(前面的值与)和|中间的取最大。 那么我们将每一个()封装用dfs处理，| 左右再进行比较即可。细节见代码。 Code: #include<iostream> #include<map> #define pii pair<int,int> typedef long long ll; using namespace std; string str; int p = 0; int dfs() {  int sum = 0, left = 0; while (p ...