rin's

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)

![manacher2.png](https://static.lo-li.net/typecho/2020/07/2154660342.png)
符号说明：
* `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`，例如此时：
![manacher1.png](https://static.lo-li.net/typecho/2020/07/3248822752.png)
`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]`并且能得到最长的长度。

------------
“不可能”的情况
换一个例子
![manacher3.png](https://static.lo-li.net/typecho/2020/07/31183235.png)
此时`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 条评论

- 阅读剩余部分 -

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 条评论