|
#2
叶纤2020-04-11 16:37
 有关算法的地方其实我是看不懂的，现在只学习了少部分的语法，所以以下说法只是个人意见首先，如果是学习算法和说据结构的话还是用自己的理解去敲代码，不要看百度（根据个人经验，我面对算法方面的一旦复制粘贴我不理解的句子，整串代码一旦出现不是自己想要的结果，我将不知道该如何去改正，就算别人帮忙改正了，也是半迷糊） 其实，你这串代码，我是看不懂的，看不懂的地方有很多 1#define rg register int 像这种宏定义除了c出现的次数多，其实c++很多书是不允许这样的，会导致代码的可读性很差，而且效率不好，最好还是使用define进行标题保护比较好 再看看register 这个关键字，太老了吧，c++11已经不让使用了，c++17已经抛弃但是保留关键字 最后你提问的是关于x-=x&-x 这和bieset有关，bitset又和2进制有关，and这个符号的意思是两者都是1结果才是1，否则为0， 就比如y=1&3，结果是1 1如果是四位数的话那就是 std::bitset<4> bits { 0b0001 }; 3 如果是四位数的话 std::bitset<4> bits { 0b0011 }; 0001+0011=0001，换成10进制的话就是1， 最后关于位运算是比较绕脑的，我也不怎么熟悉，只能说个大概 |
程序代码：#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define rg register int
using namespace std;
int n;
int s[200005];
struct su{
int v,id; //按照权值为第一关键字保证算法正确性
inline bool operator <(su x){
if(v==x.v)return id>x.id; //按照序号从大到小可以保证所求为上升子序列
return v<x.v; //（针对标号）因为相同权值的数，前面的状态不能转移给后面
} //（针对标号）从大到小枚举就不会出现这种情况
}a[200005];
inline void add(int x,int y){
for(;x<=n;x+=x&-x) s[x]=max(s[x],y);
}
inline int ask(int x){
rg res=0;
for(;x>=1;x-=x&-x) res=max(s[x],res);
return res;
}
int main(){
cin>>n;
for(rg i=1;i<=n;++i)
cin>>a[i].v,a[i].id=i;
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i)
add(a[i].id,ask(a[i].id)+1);
cout<<ask(n)<<endl;
return 0;
}
#include<cstdio>
#include<algorithm>
#define ll long long
#define rg register int
using namespace std;
int n;
int s[200005];
struct su{
int v,id; //按照权值为第一关键字保证算法正确性
inline bool operator <(su x){
if(v==x.v)return id>x.id; //按照序号从大到小可以保证所求为上升子序列
return v<x.v; //（针对标号）因为相同权值的数，前面的状态不能转移给后面
} //（针对标号）从大到小枚举就不会出现这种情况
}a[200005];
inline void add(int x,int y){
for(;x<=n;x+=x&-x) s[x]=max(s[x],y);
}
inline int ask(int x){
rg res=0;
for(;x>=1;x-=x&-x) res=max(s[x],res);
return res;
}
int main(){
cin>>n;
for(rg i=1;i<=n;++i)
cin>>a[i].v,a[i].id=i;
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i)
add(a[i].id,ask(a[i].id)+1);
cout<<ask(n)<<endl;
return 0;
}
请问里边的add函数和ask函数中for循环的那个x+=x&-x和x-=x&-x是什么意思？
能用非位运算表达式写吗？