map 学习笔记（不定时更新）

· · 个人记录

本篇笔记纯属个人的一些理解，可能理解有误或者术语不当，还请理解

开头：

传送门

首先声明，此题我并没有过，正解是欧拉函数。

这虽然是一道数学题，但我用它来练习一下 map

思路很简单，求各点斜率，如果不同说明合法。

但由于斜率 k 是浮点数，所以不能用 vis 数组打标记

那正好就练习一下 map 吧

map <double,bool>k;

int main(void)
{
    cin >> n;
    for(int i=1;i<n;i++)
    for(int j=1;j<i;j++)
    {
        map <double,bool> :: iterator it;
        it = k.find((double)i/j);
        if(it == k.end())
        {
            k[(double)i/j] = 1;
            ans++;
        }
    }
    /*
    map <double,bool> :: iterator it;
    for(it=k.begin();it!=k.end();it++)
    {
        cout << it->first << endl;
    }*/
    cout << 2*ans+3;
}

代码大概就是这样，不过这样做并不会 AC , 等 A 了再来填坑吧

好，我来填坑了，这道题正解是欧拉函数，详情请见

正文：

现在，来学习一下 map

支持快速查找以及修改，并且可以~~胡乱的~~在两个参数之间建立对应关系 总之，在某些情况下非常好用。 **首先是头文件**，作为 $STL$ 库里的一种容器，它被包含于 $<map>$ 头文件中 **还有定义**， $map$ 的定义如下： ```cpp map < 依个变量类型， 另依个变量类型 > a_map; //或者 map < map < 依个变量类型 ，另依个变量类型 > ，第三个变量类型 > a_map; //这样就相当于定义了依个类似于二维数组的东西 ``` 那么， 让我们来看看 $< stl\_map.h >$ 里都有些什么： 。 。 。 嗯，好，看不懂。 虽然头文件里的东西一点也没有看明白，但还是找到了些有用的东西： ```cpp class map { public: typedef _Key key_type; typedef _Tp mapped_type; ： ： ``` 这里 $typedef$ 了两个奇怪的东西: $\_key$ : $Key$ 值类型，在 $map$ 中的每个元素都是由其 $Key$ 值唯一指定的。 $\_Tp$ : 映射值的类型，在 $map$ 中的每个元素，都存储了一些数据作为其映射值。 还是让我们来看看 $map$ 都有些什么**操作**吧： # 常用函数： ------------ $erase$： 删除 map 中指定位置的元素； $insert$： 在 $map$ 指定位置添加 $pair$ 类型的元素； $find$： 获取 $map$ 中元素的迭代器； $begin$ , $end$： $map$ 的迭代器（正向）的起始位置与终点位置； 在这里，提到了一个东西， 那就是：**迭代器** 这是一个类似于指针的东西， 它的作用就是~~在容器内指来指去~~，为各种函数指明方向 它的定义如下： ```cpp map < 依个变量类型，另依个变量类型 > ::iterator an_iterator; ``` 接下来就是如何**使用**它了 既然是笔记， 那么这里我打算持续补充它的用法等知识~~（大概）~~ **一：**普通的查询。 ```cpp map <int,int> :: iterator it; it = k.find(i); if(it == k.end()) cout << "where is it ? "; else cout << " I get it ! "; //find() 函数会返回 i 值对应的地址，如果没有，则返回尾指针。 ``` **二：**遍历。 ```cpp map <int,int> :: iterator it; for(it=k.begin();it!=k.end();it++) cout << it->first << endl; //从头到尾跑一遍，fist 指的是 key ，second 指的是 T ``` 好吧，我懂你的意思，我解释一下这个 "->" 是个啥。 **敲黑板，划重点，做笔记 ！** "->" 是**成员提取**符，与 "." 的用法差不多，但 "->" 是指针类型，即指针引用，所以 "->" 前必须是一个指针。 ```cpp //举个栗子： struct node{ int x; }*example; //现在，要访问 example 中的成员 x 的话： *example.x = 19260817 //与 example->x = 19260817 //是等价的 //因为 *example 是一个实体，所以用点，而example是一个指针，所以用箭头 //简而言之，直接访问结构体的成员时使用点运算符，而通过指针访问结构体的成员时，则使用箭头运算符。 ``` *2018.9.9 17:33* ------------ # 实例练习： [传送门](https://agc028.contest.atcoder.jp/tasks/agc028_a) 前不久才去 $CC$ 做了些题，这回又去了日本 $AtCoder$ 正巧就碰到了个需要 $map$ 做的题，就搬运过来了。。。 其实题不难，就是 $map$ 不熟有很多细节没注意 **题目大意：** ``` 你得到一个长度为 N 的字符串 S 和另一个长度为 M 的字符串 T，这些字符串由小写的英文字母组成。 当下列条件全部满足时，字符串 X 被称为好字符串： 1.设 L 等于 X 的长度， L 能被 N 和 M 整除。 2.连接 X 的第 1 个，第（L / N+1）个，第（2 * L / N+1）个，……，第（（N - 1）L / N+1）个字符，不改变顺序，结果为 S 3.连接 X 的第 1 个，第（L / M+1）个，第（2 * L / M+1）个，……，第（（M - 1）L / M+1）个字符，不改变顺序，结果为 T 确定是否存在一个好的字符串。如果它存在，找到最短的长度。 数据规模与约定： 1.1 ≤ N,M ≤ 100000 2.S 和 T 保证是小写英文字母 ``` ```cpp long long M,N; long long L; char c1[MAXN]; char c2[MAXN]; map <long long,char>m; long long gcd(long long a, long long b) { if(b == 0) return a; return gcd(b,a%b); } int main(void) { cin >> N >> M; for(long long i=1;i<=N;i++) cin >> c1[i]; for(long long i=1;i<=M;i++) cin >> c2[i]; L = (long long)N*M/gcd(M,N); if(c1[1] != c2[1]) { cout << "-1"; return 0; } m[1] = c1[1]; for(long long i=1;i<N && i*L/N+1<=L;i++) m[i*L/N+1] = c1[i+1]; for(long long i=1;i<M && i*L/M+1<=L;i++) if(m[i*L/M+1]!='\0' && m[i*L/M+1]!=c2[i+1]) { cout << "-1"; return 0; } cout << L; return 0; } ``` 代码中有这么一句：$m[i*L/M+1]\ \ != \ '$\$0'

这里，就要说一下 map 的初始化：

通常，map 的默认值是 0 ，但在 char 类型中默认值是 \0

如果是结构体类型，则可以自定义默认值

//举个栗子：
struct node{
    int a{5};
};

map<string,node> m1;

cout << m1["s"].a << endl;
//这时的输出为 5

2018.10.14 10:04

实例练习：

传送门

虽然这道题我用了 set ，不过 set 和 map 很像，就放在一起吧~

练 STL 的好题，有很多操作可以参考一下。

int vis[MAXN];
queue <int> que;

struct node{
    set <int> s;
}group[MAXN];

int main(void)
{
    scanf("%d%d",&n,&g);
    for(int i=1;i<=g;i++)
    {
        scanf("%d",&num);
        for(int j=1;j<=num;j++)
        {
            scanf("%d",&cow);
            group[i].s.insert(cow);
        }
    }
    que.push(1);
    ans = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for(int i=1;i<=g;i++)
        {
            group[i].s.erase(u);
            int x = *group[i].s.begin();
            if(group[i].s.size()==1 && !vis[x])
            {
                que.push(x);
                vis[x] = 1;
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

注：

这里穿插一些 set 的内容，set 表示集合，可以把元素丢进去，放在一起，由于 set 和 map 非常的像，所以打算放在一起讲，短时间内没有开新坑的打算，可能要 AFO 之后了。

实例练习：

传送门

值得注意的是，set 在你丢入元素后会自动排序，而且支持lower\_bound 和 upper\_bound ，这就省去了很多麻烦。

再来说说这道题，主体是贪心，存下没变规则前能赢几把的前缀和与改变后能赢几把的后缀和，枚举 i 使前后缀相加最大值即是答案。

与田忌赛马类似，要用一张与 a[i] 相近的牌取胜是最划算的，所以自然要用到 lower\_bound 了，可能是由于边界问题。本题用 upper\_bound 是过不了的，

至于正确性的证明，可以这么想 :

在贪心时唯一可能出错的问题在于前后缀中可能重复使用了某一张牌，但如果出现重复使用的情况，必有某一张没有被用到，这里设重复使用的那张为 a ， 没被使用的那张为 b ，如果 a > b 那么在后缀中 b 必可以代替 a ，反之 亦然。

int n,ans;
int a[MAXN];
int vis[MAXN];
int f[MAXN],g[MAXN];
set <int>s1,s2;

int main(void)
{
    cin >> n;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
        vis[a[i]] = 1;
    }
    for(int i=1;i<=2*n;++i)
        if(!vis[i])
        {
            s1.insert(i);
            s2.insert(-i);
        }
    for(int i=1;i<=n;++i)
    {
        set <int>:: iterator it = s1.lower_bound(a[i]);
        if(it != s1.end())
        {
            f[i] = 1;
            s1.erase(it);
        }
        f[i] += f[i-1];
    }
    for(int i=n;i>=1;--i)
    {
        set <int>:: iterator it = s2.lower_bound(-a[i]);
        if(it != s2.end())
        {
            g[i] = 1;
            s2.erase(it);
        }
        g[i] += g[i+1];
    }
    for(int i=0;i<=n;i++)
        ans = max(ans,f[i]+g[i+1]);
    cout << ans;
    return 0;
}

2018.10.17 20:44

实例练习：

传送门

短小而精悍，用 vector 强行水过。

vector <int> a;
int main(void)
{
    int n,F,K=0; cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> F;
        a.insert(lower_bound(a.begin(),a.end(),F),F);
        if(!(i&1)) continue;
        cout << a[K++] << endl;
    }
    return 0;
}

实在是没有时间开新坑了，关于 STL 的东西先堆在这里以后再整理吧。。。

2018.10.31 14:43