思路 介绍一个函数next_permutation，他可以用来求一个序列的下一个排列情况，因此对于初始序列{1,2,3,4,5,6,7,8},一直输出他的下一个序列就好了。 代码 #include<bits/stdc++.h> using namespace std; int main(){ int a[]={1,2,3,4,5,6,7,8}; do{ for(int i=0;i<8;i++){ cout<<a[i]; if(i!=7) cout<<" &quo...

思路 看到楼上有dp做法的，原谅我难以看懂，我是直接暴力过的。前缀和可以O(1)得到答案，只需要进行预处理求1~1e6讨厌的数个数就好了。O(1e6)判断一个数是否讨厌，可以对其每一位模4，每两位模38. 代码 #include<bits/stdc++.h> using namespace std; int n,m,sum[1000005]; bool check(int x){ while(x){ if(x%10==4||x%100==38) return true; x/=10; } return false; } ...

思路 被这道题坑了，看完题意秒写Kmp，交了之后只过了90%，各种改最后才发现没有考虑ABCDEF的情况。（啊太粗心了）做法：第一层循环是进制数k，递归或者循环+reverse得出字符串s，然后如果kmp得t是s的子串，则直接输出yes结束程序，如果k到16还是没有退出，那么输出no。怕麻烦不想写kmp也可以用s.find(t)!=0。 代码 #include<bits/stdc++.h> using namespace std; int n,kmp[1000005]; string t,s; string work(int x,int y){ string str=&...

思路 二分答案，如果满足条件的就向右逼近。判断一个答案是否满足条件，只需要对所有木棍求能分的段数之和是否大于等于k就好了。 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+7; ll n,k,a[maxn],cnt; bool check(ll x){ cnt=0; for(int i=1;i<=n;i++){ cnt+=a[i]/x; } if(cnt>=k) return true; ...

思路 题目要求的是后序遍历，我们可以从根结点出发，查找左右子树，达到叶子结点时返回类型flag，然后决定父节点的类型。 代码 #include<bits/stdc++.h> using namespace std; int len,n; string s; void f(string str,int len){ int flag1=0,flag0=0; // cout<<str<<" "<<len<<endl; if(len==1){ if(str=="1&quo...

思路 题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的节点数，就能求出答案了。 代码 #include<bits/stdc++.h> #define int ll #define inf 0x3f3f3f3f3f3f typedef long long ll; using namespace std; const int maxn=1e5+...

思路 对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。 代码 #include<bits/stdc++.h> #define int ll #define inf 0x3f3f3f3f3f3f typedef long long ll; using namespace std; const int maxn=1e5+5; int n,a[maxn],u,v,tmp,ans,d[maxn]; vector&l...

思路 写一个Dijkstra堆优化的模板供大家参考一下。（码风比较丑，不要介意） 代码 #include<bits/stdc++.h> using namespace std; const int maxn=200005,maxm=500005; struct E{ int next,to,dis; }edge[maxm]; struct X{ int node,dis; }; int n,m,u,v,w; int cnt=0,head[maxn],dis[maxn]; bool operator <(const X a,const X b){ ...

思路 可以顺便把这道一模一样的题给A掉Luogu P5463 小鱼比可爱（加强版）各位可以做完《逆序数》再过来，我是用归并排序写的。考虑到对于一个逆序对<i,j>，i∈[l,m],j∈[m+1,r]，那么它是所有区间[x,y]，x∈[l,i]，y∈[j,r]中的逆序对，每一次merge计算逆序对的时候都乘以外面的区间数（L*(n-R+1)），就是那些逆序对的总贡献。###代码 #include<bits/stdc++.h> #define int __int128 using namespace std; typedef long long ll; const int ...

思路 把n*n的矩阵摊平成一条直线，就可以用线段树的方法解决啦！n<1000，所以展成直线就是1e6的单点修改+区间求和。个人码风问题我全开ll了，第一发因为update写错了爆零（我太菜了） 代码 #include<stdio.h> #include<iostream> #include<cstring> #define int ll using namespace std; typedef long long ll; const int maxn=1e6+5; int tree[maxn*4],n,m,f,x1,x2,y1,y2; bool num...

思路 这道题很开放，spfa能过、Dijkstra能过，普通求法（见代码）也能过。这边供上一个Dijkstra堆优化板子求最短路。坑点：注意优先队列默认是从大到小的，重载运算符要写a.dis>b.dis，别把堆优化做成堆劣化。 Dijkstral代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; const int maxn=2505,maxm=6000000; struct E{ int to,dis; }; bool operator <(...

思路 线段树裸题，区间修改+区间查询，板子如下。需要注意的一个坑点就是读命令的时候不要漏掉换行符。（个人码风习惯把int改成ll，各位还是要注意别爆了） 代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; const int maxn=100005; int n,m,x,y,z,a[maxn],tree[maxn*4]; char ch; void build(int node,int start,int end){ if(start==end){ ...

思路 看数据范围1e5，暴力求和会被查询卡掉，用前缀和会被单点修改卡掉，所以我们要用到线段树。线段树（查询+单点修改），背板代码如下。我的码风把int定义成ll了，希望你们看的习惯。 代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; const int maxn=100005; int n,m,f,x,y,a[maxn],tree[maxn*4]; void build(int node,int start,int end){ if(start==end...

思路 先看一眼数据范围，1e5逐个数逆序数是肯定会超时的；对于排序后的数组，每一个数前面序号比它大的数的个数就是它的逆序数，因此我们可以想到一种O(nlogn)排序并求逆序数的方法，只需要套一个归并排序的板子，然后统计归并排序时每个区域交换元素时相隔的元素个数就好了。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005; int n,a[maxn],tmp[maxn]; long long cnt=0; void Merge(int l,int m,int r){ int i=l,j=...