2021-07
下标池 IdPool template<typename T> struct IdPool { map<T, int> idmap; vector<T> items; void clear() { idmap.clear(); items.clear(); } int getid(const T &t) { auto it = idmap.find(t); if (it != idmap.end()) return it->second; int ans = items.size(); items.push_back(t); idmap[t] = ans; return ans; } T& operator[](int i) { return items[i]; } int size() { return items.size(); } }; IdPool<int> idp;
…
第 13 章 拷贝控制 拷贝控制 copy control 操作包括： 拷贝构造函数 copy constructor 拷贝赋值运算符 copy-assignment operator 移动构造函数 move constructor 移动赋值运算符 move-assignment operator 析构函数 destructor 13.1 拷贝、赋值与销毁 合成拷贝构造函数 synthesized copy constructor #include <iostream>#include <string>using namespace std; class A { public: string name; A() : name("") { cout << "default ctor" << endl; } A(string
…
第 12 章 动态内存 静态内存用来存储 局部 static 对象，类 static 成员，定义在任何函数之外的变量。 栈内存用来存储 定义在函数内的非 static 对象。 除了这两部分，程序还拥有一个内存池。这部分内存被称为自由空间 free store 或 堆 heap。程序用
…
第 11 章 关联容器 关联容器 associative-container map set multimap multiset unordered_map unordered_set unordered_multimap unordered_multiset 11.1 使用关联容器 map 通常称为关联数组 associative array。 11.2 关联容器概述 有序容器的关键字类型 需要定义 <，且该运算需要满足严格弱序 strict weak ordering。 11.2.3 pair 类型 pair 定义在
…
Title typedef long long LL; typedef vector<int> VI; typedef vector<VI> VVI; const LL INF=0x3f3f3f3f3f3f3f3f; inline LL sqr(LL x){ return x*x; } inline LL dis(const VI &a,const VI &b) { return sqr(a[0]-b[0])+sqr(a[1]-b[1]); } bool cmp(const VI &a, const VI &b) { return a[1]<b[1]; } VVI tmp; LL help(VVI &ps,int l,int r) { int n=r-l+1; if(n<=3) { LL ans=INF; for(int i=l;i<=r;i++) { for(int j=i+1;j<=r;j++) ans=min(ans,dis(ps[i],ps[j])); } sort(ps.begin()+l, ps.begin()+r+1, cmp); return ans; } int m=(l+r)>>1; int mp=ps[m][0]; LL ans=min(help(ps,l,m),help(ps,m+1,r)); int i=l,j=m+1,p=l; while(i<=m || j<=r) { if(i>m || j<=r&&cmp(ps[j],ps[i])) { tmp[p++]=ps[j++]; } else { tmp[p++]=ps[i++]; } } copy(tmp.begin()+l, tmp.begin()+r+1,ps.begin()+l); p=0; for(int i=l;i<=r;i++) { if(sqr(ps[i][0]-mp)
…