A. 比大小思路：直接比较大小关系，模拟题意输出 #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; if (a > b) cout << '>' << endl; if (a < b) cout << '<' << endl; if (a == b) cout << '=' &...

当d<=sqrt(n)时 直接暴力修改树状数组的值会使复杂度退化到O(n²)所以这里要用到分块的思想，修改lazy标记lazy[i]表示i的倍数的位置中所有的数组成的一个块，查询时l到r对应的lazy，这中间有r/i-(l-1)/i个数，乘以lazy[i]就是分块记录的答案跟树状数组直接记录的答案相加就是最终的答案 #include <bits/stdc++.h> using namespace std; #define int long long int n,m; const int N=100010; int c[N]; int lazy[1000]; int lowbi...

二进制状压dp，只要相邻行列没有同时有两个战士，并且满足只有1的位置有战士，即可。注意多组数据要重置f数组 #include <bits/stdc++.h> using namespace std; #define int long long const int mod=100000000; int st[1<<12]; int mp[14][14]; int mpst[14]; int f[14][1<<12]; bool judge(int x) { while(x) { if((x&1)&&(x&...

本题考察基环外向树上的树形dp首先需要找到环上的任意一条边，然后删去这条边，再对这条边的两个点进行树形dp，最后选择根节点都不选的最大值，就是最后的答案。根节点都不选的理由是：如果选上根结点，由于环上找出来的这条边切断了，所以在进行树形dp的时候，没有考虑切断的这条边上的另一个点，有可能把那个点选上了，答案会比实际答案大，造成错误。 #include <bits/stdc++.h> using namespace std; #define ll long long const int N=1000100; struct node { int v,next; }e[N<...

记录一下当前数和前导0即可，相邻两数位之差绝对值小于2的方案直接忽略不计。五分钟AC解决战斗。 #include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][12][2]; int dp(int pos,int num,bool leg,bool flag) { if(pos==0) return 1; if(flag&&f[pos][num][leg]!=-1) return f[pos][num][leg]; int x=f...

记录位置、这一位的数、上一位的数，然后比较三个数是否相同，相同则符合，还要两个参数记录是否出现4和8，要注意处理前导0 //记录最后出现的数字是几 上一位是几 是否已经有三连号 有没有出现8 有没有出现4 #include <bits/stdc++.h> using namespace std; #define int long long int f[13][11][13][2][2][2]; int a[13]; int dp(int pos,int num,int last,bool ok,bool have8,bool have4,bool flag,bool first)...

统计0的个数，再判断有没有前导0，如果出现了007就记录，然后用相应的四位数组进行记忆化，比较常规的数位dp #include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][20][2][2]; int dp(int pos,int num0,bool h007,bool have,bool flag) { if(pos==0) return h007; if(flag&&f[pos][num0][h007][have]!=-1) ret...

根据题目，要求什么设什么。因为题目要求的是m以后第n个符合的数，在数位dp中，求出数的答案个数，总是单调递增的，由此可以分析出需要二分答案。 对于dp如何设定状态，由于题目要求一个“明七”，一个“暗七”，那么明七很明显就是有没有某个数位出现7，用一个变量have来表示，“暗七”就在最后算完的时候，看看能不能被7取模，然后每步加的时候都取模7，方便使用f数组来进行记忆化。 #include <bits/stdc++.h> using namespace std; #define int long long int f[20][10][2]; int a[20]; int dp(int...

题意：求出l到r中，能整除自己各非0位的和的数有多少个。 转换一下，就相当于求整除自己各非0位的最小公倍数，然后1到9公倍数范围是1到2520，会爆内存，考虑离散化。 转移过程有两种，一种是非0的，一种是数位是0的，是0的话最小公倍数不变，否则最小公倍数跟新的数求一下最小公倍数。然后mod要一直取余2520，防止数组越界。 //多少个数能够整除自身各位数 //相当于 多少个数能够整除自身各位数的最小公倍数 #include <iostream> #include <algorithm> #include <string.h> #include <set...

吐槽一下，这题内存卡的比较紧我#define int long long + 数组开了15150150*150 就爆内存了，一直以为我递归错误，查了好久。。。 用sum表示各个位之和，d表示枚举1到129的一个变量（因为sum要递归完了才能算出来，我们不知道sum究竟是多少，所以要枚举一下），mod表示后几位取模d以后得到的一个数。那么只要递归到最深处（整个数字都算出来），d==sum（枚举的这个d刚好是这个数各个位之和），并且mod%d==0（整个数对各个位之和取模为0，就是题目中要求的），就符合条件进行返回。然后用一个f数组（这个因为开了long long，要计算一下记忆化的有效数组大小）...

算一算每一位对应会有多少个0，然后两个数相减即可 #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define int long long int cul(int x) { if (x < 0) return 0; int res = 1, last = 0, base = 1; while (x) { int tmp = x % 10; x /= 10; if (...

dp过程主要是三个参数，第一个是位置pos，第二个是pre（数字取余7），第三个是sum（数位之和取余7）递推的过程pre这一维要乘以10再加上i，sum这一维度加上i即可，注意都要取余7然后注意要开long long，f数组存下能任意填以后的数值，以便加速后面的操作，不然会超时。 #include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][20][20]; int dp(int pos,int pre,int sum,int flag) { if(pos=...

数位dp，注意当出现次数大于限制次数的时候直接返回0，pos==0还不大于就返回1 f[pos][num][cnt] 表示第pos位，末尾数字为num，连续次数为cnt如果下一位还是num，那么转移到dp(pos-1,num,cnt+1)否则转移到dp(pos-1,i,1)也就是说转移到新的数字 这个数字连续出现了一次。 最后注意答案算出来要加上mod再取余一次 #include <bits/stdc++.h> using namespace std; const int mod=20020219; #define int long long int book[20]; int f...

数位dp，如果有4直接标记状态2，如果有3标记状态1，如果有8并且状态为1，标记状态2。依次枚举数位，如果发现数字一定合法（该位小于x，后面的位上的数可以任意填），并且f数组已经算过，可以直接返回。 //注意记忆化 如果后面可以任意填了并且已经算过就直接返回 if(flag&&f[pos][st]!=-1) return f[pos][st]; //后面可以任意填了，就在对应位置记录一下，提高时间效率 if(flag) f[pos][st]=ans;以下是加了这两句话和没加这两句话的对比： #include <bits/stdc++.h> using namesp...