AC代码&思路：递归的话原则上太慢了
#include<iostream>
using namespace std;
long long solve(long long x)//就是在算二进制1的个数，我感觉还是自己举一些简单的例子比较好理解
{
if(x<=1) {return x;}//递归的结束条件 x==0 f=0, x==1 f=1
if(x & 1){return solve(x>>1)+1;}//由二进制与十进制互化的知识可知，只有最后一位对应的数是奇数，所以x&1判断是不是奇数;x/2向下取整相当于x>>1，因为末尾的数无论是不是1都丢掉了，其他的数都是2**n(n>=1)，都可以被2整除
return solve(x>>1);
}//也可以改成（while(x>1)）
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
long long a,res;，//注意最大范围超过了int
for(int i=1; i<=t; ++i)
{
cin>>a;
res=solve(a);
cout<<res<<' '<<( (1LL<<res) -1)<<'\n';//不是1LL会溢出，一个式子中，左边是LL类型，右边就也会被强制转换为LL
}
return 0;
}
AC代码&思路：其实这道题本来都不打算放进来，但想想以后也许会复习到吧
#include<iostream>
using namespace std;
int solve(int x, int y)
{
if(y!=0){return solve(y, x%y);}//gcd(a,b)=gcd(b,a%b)
else return x;//说明上一个x%y==0了，即y是x的因数了，返回上一个的y(即输入的x)
}
int main()
{
int x,y;cin>>x>>y;
cout<<solve(x,y);
return 0;
}
思路：得先学会归并排序（去B站上找找动画演示），做到3-5分钟写出一个归并算法的程序。 每次归并比较右指针对应的数据严格大于左边相当于消灭（包含）一对逆序对 AC代码：
#include<iostream>
using namespace std;
int a[500005];
int b[500005];
long long count=0;
void mymerge(int l, int mid, int r)
{
int p=l,q=mid+1;
for(int i=l; i<=r; ++i)
{
if( (q>r) || ( (p<=mid)&&(a[p]<=a[q])/*把访问数组写在最后面，由于逻辑运算的熔断机制，保证数组访问不越界*/ ) ) {b[i]=a[p];p++;}
else {b[i]=a[q];q++;count+=mid-p+1;}//植树原理
}
for(int j=l; j<=r; ++j)
{
a[j]=b[j];//别忘了再赋回去，不然下次往上层回归排序是乱的
}
}
void mergesort(int l, int r)
{
if(l == r){return ;}
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
mymerge(l,mid,r);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
for(int i=1; i<=t; ++i)
{
cin>>a[i];
}
mergesort(1,t);
cout<<count;
}
前言：跟题解26一样，需要先学会快速排序（感觉没归并好理解，看来还是递归代码简单些）
AC代码：
#include<iostream>
using namespace std;
int a[5000005];
int myqsort(int l, int r, int k)
{
if(l == r){return a[l];}//因为后面的递归语句设计好了，每次区间【l,r】必包含第K小的数，现在这个区间只有一个数了
int mid=(l+r)/2;
int p=l, q=r;
int x=a[mid];//存下基准值，防止后面交换时被破坏了
while(p<=q)
{
while(a[p]<x) {++p;}
while(a[q]>x) {--q;}//为什么不是++p？因为这里不像归并排序有层for循环保证数组访问不越界，++q无限进行下去就越界了，所以对撞两个指针，也许还有其它好处
if(p<=q)
{
swap(a[p], a[q]);
++p;--q;
}
}
if(k<=q) {myqsort(l, q, k);}//上面while()循环推出的条件是p>q，所以现在q在左边，p在右边。
else if(k>=p) {myqsort(p, r, k);}//这里的p和q都是数组真实的索引，每一次被放弃的在数组的某一边，所以不用更新传入的k
return a[k];//即p和q中间还间隔了一个数（只有在最后一次进if语句p==q才会出现），聪明的你可能会想前面不是判断过l==r return了吗？然而别忘了两个里面的while()语句也会让p==q
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t,n,k;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1; i<=n; ++i)
{
cin>>a[i];
}
cout<<myqsort(1, n, k)<<'\n';
}
}
PS：感觉归并排序就是把问题先划分到达最小的子问题，再一层一层的往上积累起来；而快速排序就是一层又一层的把问题（切半）分散，逐个击破。写到这里，好像又感觉两者思想差不远
题解28：上难度了吖 题目：https://ac.nowcoder.com/acm/problem/201839
前言：其实做到这题是误闯天家，我本来是想做一道递归的汉诺塔问题的，一看数据范围就不对劲，看了讨论区发现是动态规划（记忆化递归），然后就去问deepseek，最后竟然听懂了。不过在这里先给上递归做法（答案绝对正确，但是50%超时），最后给上记忆化递归做法（详细思路？）
递归前言：递归不要死纠在如何从最底层一层一层递归回来的（那样想脑袋会超时和超内存），而是考虑
-
每一层跟上一层的关系式是什么（类比高中数学数列的递归关系式）
-
结束条件是什么，即到什么时候可以不继续递归下去，所有子问题已经无法分割，或已解决
AC代码（普通递归）：
#include<iostream>
using namespace std;
int a[10]={0};
void solve(int n, char begin, char last, char zhongjian)
{
if(n==0){return ;}//没有盘子，自然就结束了，作为递归的出口
//以下是汉诺塔问题的经典解法
solve(n-1,begin,zhongjian,last);//把前n-1个盘子挪到原中转点，用last做这一次中转
//把最底下一个盘子放到这一次的目标点
if( (begin=='a') && (last=='b') ) {a[1]+=1;}
else if( (begin=='a') && (last=='c') ) {a[2]+=1;}
else if( (begin=='b') && (last=='a') ) {a[3]+=1;}
else if( (begin=='b') && (last=='c') ) {a[4]+=1;}
else if( (begin=='c') && (last=='a') ) {a[5]+=1;}
else {a[6]+=1;}
solve(n-1,zhongjian,last,begin);//把前n-1个盘子挪到这一次的目标点，用begin(反正所有盘子都移出去了)做中转
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
solve(n,'a','c','b');
cout<<"A->B:"<<a[1]<<'\n';
cout<<"A->C:"<<a[2]<<'\n';
cout<<"B->A:"<<a[3]<<'\n';
cout<<"B->C:"<<a[4]<<'\n';
cout<<"C->A:"<<a[5]<<'\n';
cout<<"C->B:"<<a[6]<<'\n';
cout<<"SUM:"<<( ( 2 << (n-1) )-1 );//这是公式结论，也可输出a[i]从a[1]加到a[6];
return 0;
}
思路&记忆化递归AC代码：
#include<iostream>
using namespace std;
long long a[66][3][3][6]={0,0,0,0};
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
//下面开始初始化第一层，相对于数列初项a1
for(int from =0; from<=2; ++from)//0->A,1->B,2->C//A->B:0;A->C:1;B->A:2;B->C:3;C->A:4;C->B:5
{
for(int to=0; to<=2; ++to)//这里不能写to=from+1，因为这里不是枚举多少次，而是写入初始的数据，比如从B->A就是to=0，from=1
{
if(from == to) {continue;}//自己移到自己不用移
if( from==0 && to==1 ) {a[1][from][to][0]=1;}
else if( from==0 && to==2 ) {a[1][from][to][1]=1;}
else if( from==1 && to==0 ) {a[1][from][to][2]=1;}
else if( from==1 && to==2 ) {a[1][from][to][3]=1;}
else if( from==2 && to==0 ) {a[1][from][to][4]=1;}
else {a[1][from][to][5]=1;}
}
}
//下面开始记忆化递归,一共有n-1层
for(int k=2; k<=n; ++k)
{
for(int from =0; from<=2; ++from)
{
for(int to=0; to<=2; ++to)
{
if(from == to) {continue;}//自己移到自己不用移,别多忙活了
int aux=3-from-to;//非常巧，from+to+aux(中间柱子)==3，用3减去就行，不用非得多存下来
//注意数组中每个元素都是要进行的累计操作，类似前缀和，不是指当前某步要操作的次数
//首先进行跟上面普通递归解法一样的操作，把前n-1个盘子挪到中转点
for(int m=0; m<=5; ++m)
{
a[k][from][to][m]+=a[k-1][from][aux][m];//其实想想三个的情况理解一下就好了
}
//然后把最底下那个挪到目标点（注意顺序不能乱，递归要符合实际顺序）
if( from==0 && to==1 ) {a[k][from][to][0]+=1;}
else if( from==0 && to==2 ) {a[k][from][to][1]+=1;}
else if( from==1 && to==0 ) {a[k][from][to][2]+=1;}
else if( from==1 && to==2 ) {a[k][from][to][3]+=1;}//PS：写完后自己检查下，像我+=1眼花写成了=1找了......
else if( from==2 && to==0 ) {a[k][from][to][4]+=1;}
else {a[k][from][to][5]+=1;}
//最后把前n-1层移动从中转点移动到目标点
for(int m=0; m<=5; ++m)
{
a[k][from][to][m]+=a[k-1][aux][to][m];
}
}
}
}
//好了，接下来轮到我写了[doge]
cout<<"A->B:"<<a[n][0][2][0]<<'\n';//从0到2
cout<<"A->C:"<<a[n][0][2][1]<<'\n';
cout<<"B->A:"<<a[n][0][2][2]<<'\n';
cout<<"B->C:"<<a[n][0][2][3]<<'\n';
cout<<"C->A:"<<a[n][0][2][4]<<'\n';
cout<<"C->B:"<<a[n][0][2][5]<<'\n';
cout<<"SUM:"<<( ( 2LL << (n-1) )-1 );//这是公式结论，也可上面输出的结果加起来;
}
京公网安备 11010502036488号