C++ Primer Chapter 15 OOP 作者: rin 时间: October 14, 2021 分类: C++ 评论 # Ch15 OOP ## 15.1 An Overview OOP is based on 3 fundamental concepts: 1. **Data abstraction**: Separate interface from implementation 2. **Inheritance**: Define classes that model the relationships among similar types. 3. **Dynamic binding**(run-time binding): Use objects(*virtual function*) while ignoring the details of thow they differ (through *pointers* or *references* to the base class). Inheritance: - A derived class must declare each inherited menber function it intends to override. - The access specifier in derivation list is *optional*, default value = `private` for `class`, `public` for `struct` - A derived class ctor initializes its *direct* base class only. - Base part and derived part in an object are not guranteed to be stored contiguosly. ## 15.3 Virtual Function Virtual function: - Root of an inheritance hierarchy almost define a virtual dtor `virtual ~dtor(){}`. - Any *nonstatic* member func (other than ctor) can be virtual - If a virtul func with default args is called, which version of args to use is denpent on the static type. Thus, such functions should use same default args. P607 - Virtual func declared in base class is implicitly virtual in derived classed: ```c++ // inside base class: virtual void func() {} // inside derived class: void func() = 0 // omitting keyword virtual is OK ``` --- ## 15.4 Abstract Base Classes - We can provide a definition for a *pure virtual* function (outside the class). It is used to provide some common operations. [c++ - Defining pure virtual functions outside the class definition - Stack Overflow](https://stackoverflow.com/questions/29449492/defining-pure-virtual-functions-outside-the-class-definition) ```c++ // outside the class void B::func() { /*common operations */} void B::~B() { /* some cleaning up *} ``` - Abstruct base class defines an *interface* - A derived class ctor initializes its *direct* base class only. --- ## 15.5 Access Control & Inheritance - Members and **friends** of a derived class can access this (derived) class's protected members. But the friends can't access the members of base class. - In fact, a derived type object has no special access to the protected *ordinary* base type object. ``` c++ class B { protected: int v; }; class D : public B { friend void func(D&); // can access D's protected member D::v friend void func(B&); // can't access B's protected member B::v void func(B& b){b.v=1;} // no direct access to ordinary object's v void func() {v=1;} // OK }; ``` ### Dervied-to-Base Conversion Accessibility depends on *who* is using the conversion and the *access specifier* in derivation. 1. The User Code: public 2. The Member func and Friend func of the derived class: `public`, `protected`, `private`==<-why private works== #what 3. The Member func and Friend func of the derived class of derived class: `public`, `protected` ```c++ class B { protected: int v = 1; }; class D :/*__what to fill_____*/ B { void member_func() { D d; // CASE#2: derived-to-base conversion in MEMBER FUNC & FRIENDS B b = (B)d; // OK: public, protected, private } friend void friend_func(); // CASE#2: same for the FRIENDS }; class AnotherClass : protected D { void func() { D d; // CASE#3: derived-to-base conversion in the Class derived from D B b = (B)d; // OK: public, protected (both for the D->B and AC->D inheritance) } }; int main() { D d; // CASE#1: derived-to-base conversion in USER CODE B b = (B)d; // OK: only public } ``` --- ## 15.6 Class Scope under Inheritance - Name Lookup happens before Type check. The base functions are hidden even if the functions in derived class have different paramete list. - Once override one of the (Base class's) overloaded functions, other overloaded functions will be hiden. Use `using` to bring all versions: https://stackoverflow.com/questions/888235/overriding-a-bases-overloaded-function-in-c ```c++ #include <iostream> using namespace std; struct B { virtual void a(int) { cout << "B::a(int)" << endl;}; virtual void a(int, int) { cout << "B::a(int,int)" << endl;}; }; struct D: public B { void a(int) { cout << "D::a(int)" << endl;}; void a(int,int,int){ cout << "D::a(int,int,int)" << endl;};; using B::a; // bring all overloded function from B }; int main() { D d; int i = 0; d.a(i); // OK, D::a(int) // d.a(i, i); // NO matching function without `using` d.B::a(i,i); // OK, B::a(int,int) d.a(i, i, i); // OK, D::a(int,int,int) } ``` --- ## 15.7 Ctor and Copy Control - Use `using` to "inherit" ctors from a class's *direct* base class. Compiler generates ctors with a same parameter list as the ctor in the base class. - Unlike `using` ordinary members, this doesn't change the ctors access level and propertirs(explict, constexpr) - Base ctors with default parameters are split into serveral ctors withou default parameters #what - default copy, move ctors are not ingerited - a class that only contains inherited ctors will have a synthesized default ctor. -
Manacher实例 作者: rin 时间: July 18, 2020 分类: 未分类 评论 [前坑](https://lo-li.net/1311-manacher-%E7%AE%97%E6%B3%95%E6%B1%82%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html)  符号说明： * `i`为字符串中的下标，`S`是预处理后的字符串 * `P[i]`代表以`i`为中心（含）的地方，回文的半径长度。例如`P[1]=1`意为以`'#'`为中心的最长回文子串为`"#"`，半径长度为1；同样，`P[16]=4`意为以`'x'`为中心的最长回文子串`"#p#x#p#"`的半径`"#p#x"/"x#p#"`的长度4 * `id`代表当前已知的最长回文子串的中点；`mx`代表该子串的半径长度+1 * 带圈数字代表步骤 ①、起始状态，`i=0,mx=0,id=0` 此时`i=1 >= mx=0`，即此位置已经超过了已知的最长回文范围（因为才开始嘛），同时也能确定`P[1]=至少=1`。 因此现在需要以`i=1`为中心，从其半径范围外两边开始逐一比对。（两边就是`i±P[i]`） 发现`'$'≠'a'`，扩展不下去了便停止，更新`id=1,mx=id+P[id]=1+1=2` ②、`i=2,mx=2,id=1` 此时`i=2 >= mx=2`，同样超过了已知的最长回文范围（注意`mx`是边界+1），同理能确定`P[2]=至少=1`。 继续扩展发现`'#'='#'`，则`P[2]++`，再继续无法扩展`$≠b`。 更新`id=2,mx=id+P[id]=2+2=4` ③、`i=3,mx=4,id=2` 此时`i < mx`了，说明`i`在**已知最长的回文子串（id=2的那个）**的势力范围内了。那么根据对称性，`i=3`在前面就有一个“分身”`j=2*id-i=1` 现在想求的`P[i]`就和`P[j]`有一种关系：`P[i]`=**可能**=`P[j]`，那么此时以`i`为中心的回文子串最右的下标就**有可能**扩展到`i+P[i]-1`，例如此时：  `i+P[i]-1=3+1-1=3 < mx=4`，`3`仍处在**能保证对称的<span style="background-color:#ffe699">势力范围内</span>**，那么上面的“可能”变成“一定”。 （当然现在串还太短效果不是很明显，可以参考后面的⑥；同时“不可能”的情况请参考文末） ④、⑤同理 ⑥、`i=6,mx=10,id=5` `P[6]=P[4]=2`，现在能从下标`6-2=4`和`6+2=8`的位置开始对比，而对称区域内的都不用再比了。所以就利用了已知的信息跳过了很多次对比。 然后`'b'≠'a'`停止，`6+2=8 < mx=10`，说明仍然处于最长的那个子串内部，所以不更新`mx,id` …… 如此便能算出所有的`P[i]`并且能得到最长的长度。 ------------ “不可能”的情况 换一个例子  此时`i=11,id=8,mx=14` 根据预判，`P[11]=P[5]=5`。但是下标`11+5=16 >= mx=14`，预判超过了**能保证对称**的部分，于是剩余的部分`14,15`就要和`8,7`暴力对比。
[POJ1017]Packets 作者: rin 时间: February 1, 2017 分类: Algo 11 条评论 # 题目描述 一家工厂生产的产品以相同的高$$h$$，六种不同的长宽$$1\*1,2\*2,3\*3,4\*4,5\*5,6\*6$$包装。 送货时集装的箱子的高也为$$h$$，长宽为$$6*6$$。 根据每种尺寸的产品的个数求出最少需要多少箱子来装。 # 输入 输入包含多组数据 每组数据为一行六个数，分别代表边长$$1$$到$$6$$产品的个数。 输入以六个$$0$$结束。 # 输出 每组数据输出一行一个数，代表最少需用的箱子个数。 # 样例输入 ``` 0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 ``` # 样例输出 ``` 2 1 ``` --- - 阅读剩余部分 -
Codeforces Round #384 (Div. 2) 作者: rin 时间: December 15, 2016 分类: 未分类 评论 ~~这个灰名选手一直坚持他蓝名梦想~~ ------------ [A. Vladik and flights](http://codeforces.com/problemset/problem/743/A) 有$$n$$个机场，要从$$a$$飞到$$b$$ 每个机场有航空公司$$0$$或$$1$$，同航空公司机场间移动无费用，不同的之间为$$|ni-nj|$$，问从$$a$$到$$b$$最少花费是多少。 因为同公司无费用，所以如果$$a$$和$$b$$地相同的话就输出$$0$$； 如果不相同，那么从$$a$$一定能移动到一个地方，是$$0$$和$$1$$的交界，然后在交界换一家公司飞到b，花费是$$1$$ ```c++ int main(){ int n, a, b; char aType, bType; scanf("%d %d %d", &n, &a, &b); getchar(); for (int i = 1; i <= n; i++) { if (i == a) scanf("%c", &aType); else if (i == b) scanf("%c", &bType); else scanf("%*c"); } puts((aType == bType || a == b) ? "0" : "1"); return 0; } ``` ------------ [B. Chloe and the sequence](http://codeforces.com/problemset/problem/743/B) 初始有一个序列$$[1]$$ 然后将它本身加到后面变成$$[1,1]$$ 再将还未使用的最小的正整数加到正中的位置$$[1,2,1]$$ 重复$$n-1$$次 问这之后第$$k$$个数字是啥 由~~观察瞎猜脑洞~~，~~可以看出~~，这个序列代表从$$1$$到某个数，(二进制)从右数起第一个$$1$$的位置，比如 | 数（二进制） | 1的位置 | | ------------ | ------------ | | 1(1) | 1 | | 2(10) | 2 | |3(11)|1| |4(100)|3| |5(101)|1| |6(110)|2| |...|...| 那么第$$k$$位是啥，就是$$k$$的右起第一个$$1$$位置。 可以直接用glibc里的`__builtin_ffs()`函数 考虑到$$k$$超`int`用其`long long`版本 ` __builtin_ffsll()` ```c++ int main(){ long long k; scanf("%*lld %lld", &k); printf("%d\n", __builtin_ffsll(k)); return 0; } ```
[ICPC2016Dalian Onsite]官方题解 作者: rin 时间: November 6, 2016 分类: Algo 7 条评论 [PDF版](http://pan.baidu.com/s/1bpkkoTD) > 添加 `-D__STDC_FORMAT_MACROS`以支持`PRId64` #Problem A Wrestling Match ##提交情况：170/434 ##解题思路 本题做法比较随意，此处说两种： 1. 读入数据，建好图以后，以每一个点为开始遍历的起始节点，搜索整个图，在搜索的过程中判断是否出现冲突 2. 用并查集维护题目中所谓『好选手』以及『坏选手』的关系，在建立并查集的过程中，就可判断冲突 总的来说，第2种做法需要处理的特殊情况较少，并且计算量照第1种做法少，所以标程采用第2种做法。 - 阅读剩余部分 -